|
 ABSTRACT
Many parallel algorithms are naturally expressed at a fine level of granularity, often finer than a MIMD parallel system can exploit efficiently. Most builders of parallel systems have looked to either the programmer or a parallelizing compiler to increase the granularity of such algorithms. In this paper we explore a third approach to the granularity problem by analyzing two strategies for combining parallel tasks dynamically at run-time. We reject the simpler load-based inlining method, where tasks are combined based on dynamic load level, in favor of the safer and more robust lazy task creation method, where tasks are created only retroactively as processing resources become available.
These strategies grew out of work on Mul-T [14], an efficient parallel implementation of Scheme, but could be used with other applicative languages as well. We describe our Mul-T implementations of lazy task creation for two contrasting machines, and present performance statistics which show the method's effectiveness. Lazy task creation allows efficient execution of naturally expressed algorithms of a substantially finer grain than possible with previous parallel Lisp systems.
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
|
Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
|
| |
2
|
|
| |
3
|
Culler, D.E., "Managing Parallelism and Resources in Scientific Dataflow Programs," Ph.D. thesis, M.I.T. Dept. of Electrical Engineering and Computer Science, Cambridge, Mass., June 1989.
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
Goldman, R., R. Gabriel, and C. Sexton, "Qlisp: Parallel Processing in Lisp," p~per presented &t the U.S./Japan Workshop on Parallel Lisp, June 5-7, 1989, Tohoku University, Sendal, Japan.
|
| |
8
|
|
| |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
|
| |
15
|
David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
|
| |
16
|
|
| |
17
|
|
| |
18
|
Pehoushek, D., "Low Cost Forks and Dynamic Control," paper presented at the U.g./Japan Workshop on Parallel Lisp, June 5-7, 1989, Tohoku University, Sendai, Japan.
|
| |
19
|
|
| |
20
|
Sabot, G., The Paralation Model, M.I.T. Press, 1988.
|
| |
21
|
|
| |
22
|
|
| |
23
|
Weening, J., "An Analysis of Dynamic Partitioning," paper presented at the U.S./japan Workshop on Parallel Lisp, June 5-7, 1989, Tohoku University, Sendal, Japan.
|
| |
24
|
Weening, J., "Parallel Lisp Programs," Stanford Computer Science Report STAN-CS-89-1265, June 1989.
|
CITED BY 36
|
|
|
|
|
|
|
|
|
|
|
M. C. Rinard , D. J. Scales , M. S. Lam, Heterogeneous parallel programming in Jade, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.245-256, November 16-20, 1992, Minneapolis, Minnesota, United States
|
|
|
Ganesh Bikshandi , Jose G. Castanos , Sreedhar B. Kodali , V. Krishna Nandivada , Igor Peshansky , Vijay A. Saraswat , Sayantan Sur , Pradeep Varma , Tong Wen, Efficient, portable implementation of asynchronous multi-place programs, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Hicks , Suresh Jagannathan , Richard Kelsey , Jonathan T. Moore , Cristian Ungureanu, Transparent communication for distributed objects in Java, Proceedings of the ACM 1999 conference on Java Grande, p.160-170, June 12-14, 1999, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
Joseph Polastre , Jonathan Hui , Philip Levis , Jerry Zhao , David Culler , Scott Shenker , Ion Stoica, A unifying link abstraction for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA
|
|
|
Matthew Fluet , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Manticore: a heterogeneous parallel language, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.37-44, January 16-16, 2007, Nice, France
|
|
|
|
|
|
|
|
|
Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
|
|
|
|
|
|
|
|
|
Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.1