research-article

The Inhibition of Potential Parallelism by Conditional Jumps

Authors:

E. M. Riseman,

C. C. FosterAuthors Info & Claims

IEEE Transactions on Computers, Volume 21, Issue 12

Pages 1405 - 1411

https://doi.org/10.1109/T-C.1972.223514

Published: 01 December 1972 Publication History

Publisher Site

Abstract

This note reports the results of an examination of seven programs originally written for execution on a conventional computer (CDC-3600). We postulate an infinite machine, one with an infinite memory and instruction stack, infinite registers and memory, and an infinite number of functional units. This machine wiU exectite a program in parallel at maximum speed by executing each instruction at the earliest possible moment.

References

[1]

H. Hellerman, "Parallel processing of algebraic instructions," IEEE Trans. Comput., vol. C-15, pp. 82-91, Feb. 1966.

Google Scholar

[2]

H. S. Stone, "One-pass compilation of arithmetic expressions for a parallel processor," Commun. Ass. Comput. Mach., pp. 220- 223, Apr. 1967.

Digital Library

Google Scholar

[3]

C. V. Ramamoorthy and M. J. Gonzalez, "A survey of techniques for recognizing parallel processable streams in computer programs," in Proc. 1969 Fall Joint Comput. Conf., AFIPS Conf. Proc., vol. 35. Montvale, N. J.: AFIPS Press, 1969, pp. 1-15.

Digital Library

Google Scholar

[4]

M. J. Flynn, "Very high-speed computing systems," Proc. IEEE, vol. 54, pp. 1901-1909, Dec. 1966.

Crossref

Google Scholar

[5]

G. S. Tjaden and M. J. Flynn, "Detection and parallel execution of independent instructions," IEEE Trans. Comput., vol. C-19, pp. 889-895, Oct. 1970.

Digital Library

Google Scholar

[6]

E. Bloch, "The engineering design of the Stretch computer," in Proc. 1959 Eastern Joint Comput. Conf., p. 48.

Digital Library

Google Scholar

[7]

R. T. Blosk, "The instructions unit of the Stretch computer," in Proc. 1960 Eastern Joint Comput. Conf., pp. 299-325.

Digital Library

Google Scholar

[8]

J. Cocke and H. J. Kolsky, "The virtual memory of the Stretch computer," in Proc. 1959 Eastern Joint Comput. Conf., pp. 82-94.

Digital Library

Google Scholar

[9]

D. W. Anderson, F. J. Sparacio, and R. M. Tomasulo, "The model 91: Machine philosophy and instruction handling," IBM J. Res. Develop., vol. 11, Jan. 1967.

Digital Library

Google Scholar

[10]

H. S. Stone, "A pipeline pushdown-stack computer," in Parallel Processor Systems, Technologies, and Applications, L. C. Hobbs, Ed. Washington, D. C.: Spartan, 1970, pp. 235-249.

Google Scholar

[11]

H. H. Goode, notes from a course on system design, Univ. Michigan, Ann Arbor, spring 1957.

Google Scholar

[12]

M. J. Flynn, personal communications.

Google Scholar

[13]

D. J. Kuck, Y. Muraoka, and S. C. Chen, "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Comput. Soc. Repository, Publ. R72-109, May/June 1972.

Google Scholar

Cited By

View all

Krause P(2021)lospre in linear timeProceedings of the 24th International Workshop on Software and Compilers for Embedded Systems10.1145/3493229.3493304(35-41)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3493229.3493304
Adileh ALilja DEeckhout LOskin MInoue K(2018)Architectural support for probabilistic branchesProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00018(108-120)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00018
Michaud PMondelli ASeznec A(2015)Revisiting Clustered Microarchitecture for Future Superscalar CoresACM Transactions on Architecture and Code Optimization10.1145/280078712:3(1-22)Online publication date: 31-Aug-2015
https://dl.acm.org/doi/10.1145/2800787
Show More Cited By

Recommendations

Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading

To achieve high performance, contemporary computer systems rely on two forms of parallelism: instruction-level parallelism (ILP) and thread-level parallelism (TLP). Wide-issue super-scalar processors exploit ILP by executing multiple instructions from a ...
Exploiting instruction level parallelism in the presence of conditional branches
Bungee jumps: accelerating indirect branches through HW/SW co-design
MICRO-48: Proceedings of the 48th International Symposium on Microarchitecture

Indirect branches have historically been a challenge for microarchitectures and code generators alike. The recent steady increase in indirect branch predictability has translated into continual performance improvements especially for Out-of-Order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 21, Issue 12

December 1972

227 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1972

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Krause P(2021)lospre in linear timeProceedings of the 24th International Workshop on Software and Compilers for Embedded Systems10.1145/3493229.3493304(35-41)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3493229.3493304
Adileh ALilja DEeckhout LOskin MInoue K(2018)Architectural support for probabilistic branchesProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00018(108-120)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00018
Michaud PMondelli ASeznec A(2015)Revisiting Clustered Microarchitecture for Future Superscalar CoresACM Transactions on Architecture and Code Optimization10.1145/280078712:3(1-22)Online publication date: 31-Aug-2015
https://dl.acm.org/doi/10.1145/2800787
Nair AEyerman SChen JJohn LEeckhout L(2015)Mechanistic Modeling of Architectural Vulnerability FactorACM Transactions on Computer Systems10.1145/266936432:4(1-32)Online publication date: 20-Jan-2015
https://dl.acm.org/doi/10.1145/2669364
Sharafeddine MJothi KAkkary H(2012)Disjoint out-of-order execution processorACM Transactions on Architecture and Code Optimization10.1145/2355585.23555929:3(1-32)Online publication date: 5-Oct-2012
https://dl.acm.org/doi/10.1145/2355585.2355592
Caparrós Cabezas VStanley-Marbell PMeyer auf der Heide FRajaraman R(2011)Parallelism and data movement characterization of contemporary application classesProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989506(95-104)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989506
Eyerman SEeckhout LKarkhanis TSmith J(2009)A mechanistic performance model for superscalar out-of-order processorsACM Transactions on Computer Systems10.1145/1534909.153491027:2(1-37)Online publication date: 29-May-2009
https://dl.acm.org/doi/10.1145/1534909.1534910
Eyerman SEeckhout LSmith J(2008)Studying compiler optimizations on superscalar processors through interval analysisProceedings of the 3rd international conference on High performance embedded architectures and compilers10.5555/1786054.1786067(114-129)Online publication date: 27-Jan-2008
https://dl.acm.org/doi/10.5555/1786054.1786067
Akkary HJothi KRetnamma RNekkalapu SHall DShahidzadeh SWatson IEl-Shishiny H(2008)On the potential of latency tolerant execution in speculative multithreadingProceedings of the 1st international forum on Next-generation multicore/manycore technologies10.1145/1463768.1463772(1-10)Online publication date: 24-Nov-2008
https://dl.acm.org/doi/10.1145/1463768.1463772
Joao JMutlu OKim HAgarwal RPatt Y(2008)Improving the performance of object-oriented languages with dynamic predication of indirect jumpsACM SIGPLAN Notices10.1145/1353536.134629343:3(80-90)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1145/1353536.1346293
Show More Cited By

Abstract

References

Cited By

Recommendations

Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading

Exploiting instruction level parallelism in the presence of conditional branches

Bungee jumps: accelerating indirect branches through HW/SW co-design

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations