|
 ABSTRACT
Compiling for distributed-memory machines has been a very active research area in recent years. Much of this work has concentrated on programs that use arrays as their primary data structures. To date, little work has been done to address the problem of supporting programs that use pointer-based dynamic data structures. The techniques developed for supporting SPMD execution of array-based programs rely on the fact that arrays are statically defined and directly addressable. Recursive data structures do not have these properties, so new techniques must be developed. In this article, we describe an execution model for supporting programs that use pointer-based dynamic data structures. This model uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a technique based on futures and lazy task creation. We intend to exploit this execution model using compiler analyses and automatic parallelization techniques. We have implemented a prototype system, which we call Olden, that runs on the Intel iPSC/860 and the Thinking Machines CM-5. We discuss our implementation and report on experiments with five benchmarks.
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
|
|
| |
2
|
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
|
| |
9
|
CALLAHAN, D. AND KENNEDY, K. 1988. Compiling programs for distributed-memory multiprocessors. J. Supercomput. 2, 2 (Oct.), 151-169.
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States
[doi> 10.1145/169627.169724]
|
| |
16
|
|
| |
17
|
GERNDT, M. 1990. Automatic parallelization for distributed-memory multiprocessing systems. Ph. D. thesis, University of Bonn.
|
| |
18
|
GumAs, L. AND STOLFI, J. 1985. General subdivisions and voronoi diagrams. A CM Trans. Graph. g, 2, 74-123.
|
| |
19
|
GUPTA, R. 1992. SPMD execution of programs with dynamic data structures on distributed memory machines. In Proceedings of the 1992 International Conference on Computer Languages. IEEE Computer Society Press, Los Alamitos, Ca., 232-241.
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
|
| |
24
|
Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States
[doi> 10.1145/125826.125886]
|
| |
25
|
I-IOGEN, G. AND LOOGEN, R. 1993. A new stack technique for the management of runtime structures in distributed implementations. Tech. Rep. 3, RWTH Aachen.
|
| |
26
|
W. Horwat , A. A. Chien , W. J. Dally, Experience with CST: programming and implementation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.101-109, June 19-23, 1989, Portland, Oregon, United States
|
| |
27
|
Wilson C. Hsieh , Paul Wang , William E. Weihl, Computation migration: enhancing locality for distributed-memory parallel systems, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.239-248, May 19-22, 1993, San Diego, California, United States
|
| |
28
|
|
| |
29
|
|
| |
30
|
|
| |
31
|
I~ARP, 1:(. 1977. Probabilistic analysis of partitioning algorithms for the traveling-saleman problem in the plane. Math. Oper. Res. 2, 3 (Aug.), 209-224.
|
| |
32
|
|
| |
33
|
|
| |
34
|
|
| |
35
|
|
| |
36
|
James R. Larus , Paul N. Hilfinger, Restructuring Lisp programs for concurrent execution, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.100-110, July 19-21, 1988, New Haven, Connecticut, United States
|
| |
37
|
LEE, D. W. AND SCHACHTER, }3. J. 1980. Two algorighms for constructing a delaunay triangulation. Int. J. Comput. Inf. Sci. 9, 3, 219-242.
|
| |
38
|
S. Lumetta , L. Murphy , X. Li , D. Culler , I. Khalil, Decentralized optimal power pricing: the development of a parallel program, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.240-249, December 1993, Portland, Oregon, United States
[doi> 10.1145/169627.169718]
|
| |
39
|
|
| |
40
|
M/JLLER, J. 1993. Parallelverarbeitung auf workstation-clustern mlttels express und networklinda. Diplomarbeit in Elektrotedanik, RWTH-Aachen.
|
| |
41
|
|
| |
42
|
ROBERTS, E. S. AND VANDEVOORDE, ~I. T. 1989. WorkCrews: An abstraction for controlling parallelism. Tech. Rap. 42, DEC Systems Research Center, Palo Alto, Ca. April.
|
| |
43
|
|
| |
44
|
|
| |
45
|
Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
|
| |
46
|
Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
|
| |
47
|
WEII-m, W., BREWER, E., COLBROOK, A., DELLAROCAS, C., HSIEH, W., JOSEPH, A., WALD- SPURGER, C., AND \~ANG, t}. 1991. Prelude: A system for portable parallel software. MIT/LCS 519, Massachusetts Institute of Technology, Cambridge, Mass.
|
| |
48
|
|
| |
49
|
ZIMA, H., BAST, H., AND GERNDT, M. 1988. SUPERB: A tool for semi-automatic MIMD/SIMD parallelizatlon. Parallel Comput. 6, 1, 1-18.
|
CITED BY 78
|
|
Gary M. Zoppetti , Gagan Agrawal , Lori Pollock , Jose Nelson Amaral , Xinan Tang , Guang Gao, Automatic compiler techniques for thread coarsening for multithreaded architectures, Proceedings of the 14th international conference on Supercomputing, p.306-315, May 08-11, 2000, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States
|
|
|
Yuan Chou , Pazhani Pillai , Herman Schmit , John Paul Shen, PipeRench implementation of the instruction path coprocessor, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.147-158, December 2000, Monterey, California, United States
|
|
|
|
|
|
Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Plevyak , Vijay Karamcheti , Xingbin Zhang , Andrew A. Chien, A hybrid execution model for fine-grained languages on distributed memory multicomputers, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.41-es, December 04-08, 1995, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wilson C. Hsieh , M. Frans Kaashoek , William E. Weihl, Dynamic computation migration in DSM systems, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.44-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
|
|
|
W. Zhang , M. Karakoy , M. Kandemir , G. Chen, A compiler approach for reducing data cache energy, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
|
|
|
|
|
|
Matthew Spencer , Renato Ferreira , Michael Beynon , Tahsin Kurc , Umit Catalyurek , Alan Sussman , Joel Saltz, Executing multiple pipelined data analysis operations in the grid, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Oscar Plata , Rafael Asenjo , Eladio Gutiérrez , Francisco Corbera , Angeles Navarro , Emilio L. Zapata, On the parallelization of irregular and dynamic programs, Parallel Computing, v.31 n.6, p.544-562, June 2005
|
|
|
Stephen Curial , Peng Zhao , Jose Nelson Amaral , Yaoqing Gao , Shimin Cui , Raul Silvera , Roch Archambault, MPADS: memory-pooling-assisted data splitting, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
|
|
|
|
|
|
Takashi Nakamura , Toshiyuki Iwamiya , Masahiro Yoshida , Yuichi Matsuo , Masahiro Fukuda, Simulation of the 3 dimensional cascade flow with numerical wind tunnel (NWT), Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
|
|
|
Luis M. Ramos , José Luis Briz , Pablo E. Ibáñez , Victor Viñals, Data prefetching in a cache hierarchy with high bandwidth and capacity, Proceedings of the 2006 workshop on MEmory performance: DEaling with Applications, systems and architectures, p.37-44, September 16-20, 2006, Seattle, Washington
|
|
|
Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, ACM SIGPLAN Notices, v.41 n.10, October 2006
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Brian Larkins , James Dinan , Sriram Krishnamoorthy , Srinivasan Parthasarathy , Atanas Rountev , P. Sadayappan, Global trees: a framework for linked data structures on distributed memory parallel systems, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
|
|
|
|
|
|
|
|
|
|
|
|
|
REVIEW
"R. Nigel Horspool : Reviewer"
A good general principle for programming a distributed-memory
machine is that the processor that owns an item of data is responsible
for updating that item. This principle reduces the volume of
interprocessor messages and makes synchronization
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3