Microarchitecture support for dynamic scheduling of acyclic task graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Microarchitecture support for dynamic scheduling of acyclic task graphs

Full text

Pdf (1.08 MB)

Source

International Symposium on Microarchitecture archive
Proceedings of the 25th annual international symposium on Microarchitecture table of contents

Portland, Oregon, United States

Pages: 140 - 148

Year of Publication: 1992

ISBN:0-8186-3175-9

Also published in ...

Authors

Carl J. Beckmann
Constantine D. Polychronopoulos

Sponsors

IEEE-CS : Computer Society
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 5, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/144953.145791 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	3	M. Berry, et al., "The Perfect Club Benchmarks: Effective Performance Evaluation of Supercomputers," CSRD report #827, November 1988.
	4	C. Beckmann, C. Polychronopoulos, "Microarchitecture Support for Dynamic Scheduling of Acyclic Task Graphs," CSRD report # 1207, April 1992.
	5	David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
	6	James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
	7	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	8	E. Freudenthal, O. Peze, "Efficient Synchronization Algorithms Using Fetch&Add on Multiple Bitfield Integers", Ultracomputer Note # 148, February 1988.
	9	M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
	10	Milind Baburao Girkar, Functional parallelism: theoretical foundations and implementation, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
	11	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Program Analysis and Optimization for Parallelizing Compilers, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.538-562, August 03-05, 1992
	12	R. A. Iannucci, Toward a dataflow/von Neumann hybrid architecture, Proceedings of the 15th Annual International Symposium on Computer architecture, p.131-140, May 30-June 02, 1988, Honolulu, Hawaii, United States
	13	David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
	14	M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
	15	R. S. Nikhil, Can dataflow subsume von Neumann computing?, Proceedings of the 16th annual international symposium on Computer architecture, p.262-272, April 1989, Jerusalem, Israel
	16	C. Polychronopoulos, M. Girkar, M. Haghighat, C. L. Lee, B. Leung, D. Schouten, "Parafrase-2: An Environment for Parallelizing, Partitioning, Synchronizing, and Scheduling Programs on Multiprocessors," Proc. Intl. Confi Parallel Processing 1989, vol. Ii, pp. 39-48.
	17	C. Polychronopoulos, "Toward Autoscheduling Compilers", CSRD report #789, and Journal of Supercomputing, Nov. 1988, pp. 297-330.
	18	C. Polychronopoulos, "Auto-Scheduling: Control Flow and Data Flow Come Together", CSRD report //1058, 1990.
	19	Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
	20	Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, Proceedings of the 18th annual international symposium on Computer architecture, p.342-351, May 27-30, 1991, Toronto, Ontario, Canada
	21	B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
	22	D. Schouten, "An Overview of interprocedural Analysis Techniques for High Performance Parallelizing Compilers", CSRD report # 1005, University of Illinois at Urbana-Champaign, May 1990.
	23	B. Smith, "A Pipelined, Shared Resource MIMD Computer", Proc. Intl. Conf. Parallel Processing 1978, pp. 6-8
	24	M. R. Thistle , B. J. Smith, A processor architecture for horizon, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.35-41, November 12-17, 1988, Orlando, Florida, United States
	25	J. E. Thornton, "Parallel Operations in the Control Data 6600", AFIPS Proceedings FJCC, pt 2, Vol 26, 1964, pp. 33-40
	26	R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units", IBM Journal, No. 11, 1967, pp. 25-33
	27	A. Veidenbaum, "Compiler Optimization and Architecture Design Issues for Multiprocessors", CSRD report #520, May 1985

CITED BY 3

	Jack L. Lo , Joel S. Emer , Henry M. Levy , Rebecca L. Stamm , Dean M. Tullsen , S. J. Eggers, Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.322-354, Aug. 1997
	Ian Lintault, A transaction execution engine architecture for multiplayer online games, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA
	Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, ACM SIGARCH Computer Architecture News, v.24 n.2, p.191-202, May 1996

INDEX TERMS

Primary Classification:
B. Hardware
B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
B.1.5 Microcode Applications
Subjects: Instruction set interpretation

Additional Classification:
C. Computer Systems Organization
C.0 GENERAL
Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

D. Software
D.1 PROGRAMMING TECHNIQUES
D.1.3 Concurrent Programming
Subjects: Parallel programming

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sequencing and scheduling

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Theory

Collaborative Colleagues:

Carl J. Beckmann: colleagues

Constantine D. Polychronopoulos: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

This Article has also been published in:

ACM SIGMICRO Newsletter
Volume 23 , Issue 1-2 Dec. 1992

Adobe Acrobat

QuickTime

Windows Media Player

Real Player