Partitioning parallel programs for macro-dataflow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Partitioning parallel programs for macro-dataflow

Full text

Pdf (725 KB)

Source

Conference on LISP and Functional Programming archive
Proceedings of the 1986 ACM conference on LISP and functional programming table of contents

Cambridge, Massachusetts, United States

Pages: 202 - 211

Year of Publication: 1986

ISBN:0-89791-200-4

Authors

Vivek Sarkar	Computer Systems Laboratory, Stanford University
John Hennessy	Computer Systems Laboratory, Stanford University

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 43, Citation Count: 21

Additional Information:

references cited by collaborative colleagues

Tools and Actions:	Request Permissions 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/319838.319863 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	W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
	2	Cek~ J. R. & Henneny, J. 1.,. SAL: A Single- Asset Language for Parallel Algorithms. ClaSSiC-83-01, Center for Large Scale Scientific Computation, Stanford University, Sept., 1983.
	3	Davis, A. L & Kelly, R. M. "Data Flow Program Graphs". IEEE Cvmp~er 15, 2 (Feb. 1982).
	4	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	5	Gaudiot, J. }. & Ercegovac, M.D. Performance Analysis of a Data-flow comput~"r with Variable Resolution Aclors. Proc. 4th lnt Conf Dist Comp Sys, 1984, pp. 2-9.
	6	Oilberk a.J. An Investigation of the Partitioning of Alg~th~ Across an MIMD Computing System. Technical Note No. 176, Computer Systems Laboratory, Stanfo~ University, 1980.
	7	Graham, R. L "Bounds on Mu 'ltipmcessing Tuning Anomalies". SIAM J. Appl. math.17, 2 (Match 1969).
	8	J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
	9	David Andrew Hornig, Automatic partitioning and scheduling on a network of personal computers, 1984
	10	Paul Hudak , Benjamin Goldberg, Serial combinators: “optimal” grains of parallelism, Proc. of a conference on Functional programming languages and computer architecture, p.382-399, January 1985, Nancy, France
	11	McGraw, J. ~ dL SISAl.: Streams and Iteration in a Single Assignmmt Language, tanguage Refermee Mmual, Version 1.2. M-146, !,LNL, March, 1985.
	12	John L. Pfaltz, Computer Data Structures, McGraw-Hill, Inc., New York, NY, 1977
	13	Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.17-26, June 25-27, 1986, Palo Alto, California, United States
	14	Sl~apiro, E. Y. A Subset of Conc~t Prolog and Its Inmp~ter. TR-003, The Wcizmmm Institute of Science, Israel, Feb., 1983.
	15	Sites, R. et al. MacMne-independent Pascal Optimiz~ Project: Final Report UCS!~S-79/038, Univextity of California at San Diego, Nov., 1979.
	16	Skedzielewski, S. & Olauctk J. IPl - An inteam~atc Form for Applicative languages, Venion 1.0. M-170, July, 1985.
	17	Turner, D. A. "A new implementation techniques for applicative languages". Soj~wore .. Pro~fice and Experience 9 (t979), 3;-49.

CITED BY 21

	V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989
	Susan L. Graham , Steven Lucco , Oliver Sharp, Orchestrating interactions among parallel computations, ACM SIGPLAN Notices, v.28 n.6, p.100-111, June 1993
	Steven Lucco, A dynamic scheduling method for irregular parallel programs, ACM SIGPLAN Notices, v.27 n.7, p.200-211, July 1992
	T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
	F. Allen , M. Burke , R. Cytron , J. Ferrante , W. Hsieh, A framework for determining useful parallelism, Proceedings of the 2nd international conference on Supercomputing, p.207-215, June 1988, St. Malo, France
	R. A. Iannucci, Toward a dataflow/von Neumann hybrid architecture, ACM SIGARCH Computer Architecture News, v.16 n.2, p.131-140, May 1988
	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
	J. Ramanujam , P. Sadayappan, Tiling multidimensional iteration spaces for nonshared memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.111-120, November 18-22, 1991, Albuquerque, New Mexico, United States
	Vivek Sarkar , David Cann, POSC—a partitioning and optimizing SISAL compiler, ACM SIGARCH Computer Architecture News, v.18 n.3b, p.148-164, Sept. 1990
	V. Sarkar, Instruction reordering for fork-join parallelism, ACM SIGPLAN Notices, v.25 n.6, p.322-336, Jun. 1990
	Hilda M. Standley, A very high level language for large-grained data flow, Proceedings of the 15th annual conference on Computer Science, p.191-195, February 1987, St. Louis, Missouri, United States
	Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Min-cut program decomposition for thread-level speculation, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Brent Hailpern , Tien Huynh , Gyorgy Revesz, Comparing Two Functional Programming Systems, IEEE Transactions on Software Engineering, v.15 n.5, p.532-542, May 1989
	K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990
	Peter G. Sassone , D. Scott Wills, Scaling Up the Atlas Chip-Multiprocessor, IEEE Transactions on Computers, v.54 n.1, p.82-87, January 2005
	Lucian Codrescu , D. Scott Wills , James Meindl, Architecture of the Atlas Chip-Multiprocessor: Dynamically Parallelizing Irregular Applications, IEEE Transactions on Computers, v.50 n.1, p.67-82, January 2001
	Seung Chan Slim Lim , Peter Lucas, JDA: a step towards large-scale reuse on the web, Companion to the 21st ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
	Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Speculative thread decomposition through empirical optimization, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Saisanthosh Balakrishnan , Gurindar S. Sohi, Program Demultiplexing: Data-flow based Speculative Parallelization of Methods in Sequential Programs, ACM SIGARCH Computer Architecture News, v.34 n.2, p.302-313, May 2006
	Moez Ayed , Jean-Luc Gaudiot, Analysis of a Heuristic for Code Partitioning, The Journal of Supercomputing, v.12 n.3, p.191-226, May 1, 1998
	S. K. Skedzielewski , R. K. Yates , R. R. Oldehoeft, DI: an interactive debugging interpreter for applicative languages, ACM SIGPLAN Notices, v.22 n.7, p.102-112, July 1987

Collaborative Colleagues:

Vivek Sarkar: colleagues

John Hennessy: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player