Software caching and computation migration in Olden

ABSTRACT

The goal of the Olden project is to build a system that provides parallelism for general purpose C programs with minimal programmer annotations. We focus on programs using dynamic structures such as trees, lists, and DAGs. We demonstrate that providing both software caching and computation migration can improve the performance of these programs, and provide a compile-time heuristic that selects between them for each pointer dereference. We have implemented a prototype system on the Thinking Machines CM-5. We describe our implementation and report on experiments with ten benchmarks.

REFERENCES

• 1: A. Agarwal , D. Chaiken , K. Johnson , D. Kranz , J. Kubiatowicz , K. Kurihara , B. H. Lim , G. Maa , D. Nussbaum , M. Parkin , D. Yeung, THE MIT ALEWIFE MACHINE: A LARGE-SCALE DISTRIBUTED-MEMORY MULTIPROCESSOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 2: Henri E. Bal , M. Frans Kaashoek , Andrew S. Tanenbaum, Orca: A Language for Parallel Programming of Distributed Systems, IEEE Transactions on Software Engineering, v.18 n.3, p.190-205, March 1992 [doi>10.1109/32.126768]
• 3: J. Barnes and P. Hut. A hierarchical (o)(NlogN) forcecalculation algorithm. Nature, 324:446-449, December 1986.
• 4: J Bentley A parallel algorithm for constructing minimum spanning trees. J. of Algorithms, 1:51-59, 1980.
• 5: Gianfranco Bilardi , Alexandru Nicolau, Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines, SIAM Journal on Computing, v.18 n.2, p.216-228, April 1989 [doi>10.1137/0218014]
• 6: M. Carlisle and A. Rogers. Software caching and computation migration in Olden. Technical Report PU-CS-TR 483- 95, Princeton University, 1995.
• 7: Nicholas Carriero , David Gelernter , Jerrold Leichter, Distributed data structures in Linda, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-242, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512666]
• 8: J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.147-158, November 1989
• 9: H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.299-307, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 10: 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]
• 11: E. Darnell , K. Kennedy, Cache coherence using local knowledge, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.720-729, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169821]
• 12: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 13: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 15: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 16: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 17: 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
• 18: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.218-229, June 20-24, 1994, Orlando, Florida, United States
• 19: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 20: R. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problemin the plane. Mathematics of Operations Research, 2(3):209-224, August 1977.
• 21: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• 22: L. Lamport. How to make a multiprocessor that correctly executes multiprocess programs. IEEE Trans. on Computers, C-28(9), September 1979.
• 23: G. Lomow, J. Cleary, B. Unger, and D. West. A performance study of Time Warp. In SCS Multiconference on Distributed S, muIation, pages 50-55, February 1988.
• 24: 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]
• 25: E. Mohr , D. A. Kranz , R. H. Halstead, Jr., Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.264-280, July 1991 [doi>10.1109/71.86103]
• 26: Rishiyur S. Nikhil, Cid: A Parallel, "Shared-Memory" C for Distributed-Memory Machines, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.376-390, August 08-10, 1994
• 27: S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
• 28: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 29: H. Samet. Computing perimeters of regions in images represented by quadtrees. IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-3(6):683-687, November 1981.
• 30: 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
• 31: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Measurement, Performance, Theory