Microarchitecture support for dynamic scheduling of acyclic task graphs
References
[1]
A. Ah0, R. Sethi, J. Ullman, Compilers Principles, Techniques, and Tools, Addison-Wesley 1986.
[2]
U. Banerjee, Dependence Analysis for Supercomputers, Kluwer Academic Press, 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]
D. Culler, A. Sah, K. Schauser, T. von Eiken, J. Wawrzynek, "Fine-grain Parallelism with Minimal Hardware Support: A Compiler-Controlled Threaded Abstract Machine", ASPLOS 91, pp. 164-175
[6]
J. Dehnert, P. Hsu, J. Bratt, "Overlapped Loop Support in the Cydm 5", ASPLOS 89, pp. 26-38
[7]
J. Ferrante, K.J. Ottenstein and J.D. Warren, "The Program Dependence Graph and its Use in Optimization,'' ACM Transactions of Programming Languages and Systems, 9(3):319-349, July 1987,
[8]
E. Freudenthal, O. Peze, "Efficient Synchronization Algorithms Using Fetch&Add on Multiple Bitfield Integers", Ultracomputer Note # 148, February 1988.
[9]
M. Girkar, C. Polychronopoulos, "Automatic Detection and Generation of Unstructured Parallelism in Ordinary Programs", IEEE Transactions on Parallel and Distributed Systems, April 1992.
[10]
M. B. Girkar, "Functional Parallelism: Theoretical Foundations and Implementation," Ph.D. thesis, CSRD report # 1182, Center for Supercomputing Research and Development, University of Illinois at Urbana- Champaign, December 1991.
[11]
M. Haghighat, C. Polychronopoulos, "Symbolic Program Analysis and Optimization for Parallelizing Compilers," 5th Workshop on Languages and Compilers for Parallel Computing, YALEU/DCS~R-915, Yale University, August 3-5, 1992, pp. 355-370.
[12]
R. Iannucci, "Toward a Dataflow/Von Neumann Hybrid Architecture", Proc. Intl. Syrup. on Computer Architecture 1988, pp. 131-140
[13]
D. J. Kuck, The Structure of Computers and Computations, John Wiley & Sons, 1978
[14]
M. Lain, "Software Pipelining: An Effective Scheduling Technique for VLIW Machines", SIG- PLAN Con/~ on Programming Language Design and Implementation, ACM (June), Atlanta, Ga. 318-328. (p. 340)
[15]
R. Nikhil, Arvind, "Can Dataflow subsume von Neumann computing?", Proc. Intl. Syrup. on Computer Architecture 1989, pp. 262-272
[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]
G. Papadopoulos, D. Culler, "Monsoon: an Explicit Token-Store Architecture", Proc. Intl. Syrup. on Computer Architecture 1990, pp. 82-91
[20]
G. Papadopoulos, K. Traub, "Multithreading: A Revisionist View of Dataflow Architectures", Proc. Intl. Syrup. on Computer Architecture 1991, pp. 342- 351
[21]
B. Rau, C. G laeser, R, Picard, "Efficient Code Generation for Horizontal Architectures: Compiler Techniques and Architectural Support", Proc. Intl. Syrup. on Computer Architecture 1982, pp. 131-139
[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. Thistle, B. Smith, "A Processor Architecture for Horizon", Proc. Supercomputing '88, pp. 35-41
[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
Index Terms
- Microarchitecture support for dynamic scheduling of acyclic task graphs
Recommendations
Global EDF scheduling of directed acyclic graphs on multiprocessor systems
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and SystemsIn this paper, we study the problem of real-time scheduling of parallel tasks represented by a Directed Acyclic Graph (DAG) on multiprocessor architectures. We focus on Global Earliest Deadline First scheduling of sporadic DAG tasksets with constrained-...
Directed acyclic graphs with the unique dipath property
Let P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let @p(G,P) be the maximum of the load of all the arcs and let w(G,P) be the minimum number of wavelengths (colors) needed ...
On the Granularity and Clustering of Directed Acyclic Task Graphs
The authors consider the impact of the granularity on scheduling task graphs. Schedulingconsists of two parts, the processors assignment of tasks, also called clustering, and theordering of tasks for execution in each processor. The authors introduce ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1992 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 December 1992
Published in SIGMICRO Volume 23, Issue 1-2
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations6Total Citations
- 343Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)15
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in