Computation migration: enhancing locality for distributed-memory parallel systems

ABSTRACT

We describe computation migration, a new technique that is based on compile-time program transformations, for accesing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. The access is performed at the remote processor, and the migrated thread portion continues to run on that same processor; this makes subsequent accesses in the thread portion local.

We describe an implementation of computation migration that consists of two parts: an implementation that migrates single activation frames, and a high-level language annotation that allows a programmer to express when migration is desired. We performed experiments using two applications; these experiments demonstrate that computation migration is a valuable alternative to RPC and data migration.

References

1. ACD+91.A. Agarwal, D. Chaiken, G. D'Souza, K. Johnson, D. Kranz, J. Kubiatowicz, K. Kurihara, B.H. Lim, G. Man, D. Nussbaum, M. P arkin, and D. Yeung. "The MIT Alewife Machine: A Large-Scale Distributed- Memory Multiprocessor". In Proceedings of Workshop on Scalable Shared Memory Multiprocessors. Kluwer Academic Publishers, 1991. Extended version is MIT/LCS/TM- 454.
2. AHS91.J. Aspnes, M. Herlihy, and N. Shavit. "Counting Networks and Multiprocessor Coordination". In Proceedings of the #3rd Annual Symposium on the Theory of Computing, May 1991.
3. BCZ90.J.K. Bennett, 3.B. Carter, and W. Zwaenepoel. "Munin: Distributed Shared Memory Based on Type-Specific Memory Coherence". In Proceedings of the #nd PPoPP, March 1990.
4. BDCW91.E.A. Brewer, C.N. Dellarocas, A. Colbrook, and W.E. Weihl. "Proteus: A High- Performance Parallel Architecture Simulator". Technical Report MIT/LCS/TR-516, MIT LCS, September 1991. Shorter version appears in 1992 SIGMETRICS.
5. BM72.R. Bayer and E.M. McCreight. "Organization and Maintenance of Large Ordered Indexes". Acta Informatica, 1(3):173-189, 1972.
6. BN84.A.D. BirreU and B.J. Nelson. "implementing Remote Procedure Calls". A GM Transactions on Computer Systems, 2(1):39-59, February 1984.
7. BS77.R. Bayer and M. Schkolnick. "Concurrency of Operations on B-trees'. Acta In.formation, 9:1-22, 1977.
8. CAL+89.J.S. Chase, F.G. Amador, E.D. Lazowska, H.M. Levy, and R.J. Littlefield. "The Amber System: Parallel Programming on a Network of Multiprocessors". In Proceedings o} the 12th SOSP, pages 147-158, December 1989.
9. CBDW91.A. Colbrook, E. Brewer, C. Dellorocas, and W. E. Weihl. "Algorithms for Search Trees on Message-Passing Architectures". In Proceedings of 1991 ICPP, pages IIi138-iii141, 1991.
10. CD88.E.C. Cooper and R.P. Draves. "C Threads". Technical Report CMU-CS-88-154, CMU Computer Science Dept. June 1988.
11. CKA91.D. Chaiken, J. Kubiatowicz, and A. Agarwal. "LimitLESS Directories: A Scalable Cache Coherence Scheme". In Proceedings of the 4th ASPLOS, pages 224-234, April 1991.
12. Com79.D. Comer. "The Ubiquitous B-Tree". A CM Computing Surveys, 11(2):121-128, June 1979.
13. Cos93.P.R. Cosway. "Replication Control in Distributed B-Trees". Master's thesis, MIT, 1993. To appear in May.
14. DBRD91.R.P. Draves, B.N. Bershad, R.F. Rashid, and R.W. Dean. "Using Continuations to Implement Thread Management and Communication in Operating Systems". in Proceedings of the 13th SOSP, pages 122-136, October 1991.
15. DCC+87.W.J. Dally, L. Chao, A. Chien, S. ttassoun, W. Horwat, J. Kaplan, P. Song, B. Totty, and S. Wills. "Architecture of a Message-Driven Processor". In Proceedings of the 14th ISGA, pages 189-196, June 1987.
16. FK92.R.J. Fowler and L.I. Kontoth#n#siks. "Improving Processor and Cache Locality in Fine-Grain Parallel Computations using Object-Affinity Scheduling and Continuation Passing (Revised)". Technical Report 411, Univ. of Rochester Computer Science Dept. June 1992.
17. GW92.A. Gupt# aaxd W.D. Weber. "Cache Invalidation Patterns in Shared-Memory Multiprocessors". IEEE Transactions on Computers, 41(7):794-810, July 1992.
18. HJ92.D.S. Henry and C.F. Joerg. "A Tightly- Coupled Processor-Network interface". In Proceedings of the 5th ASPLOS, pages 111- 122, October 1992.
19. HKK+91.S. Hiramandani, K. Kennedy, C. Koelbel, U. Kremer, and C. Tseng. "An Overview of the Fortran D Programming System". In Proceedings o.f the 4th Workshop on Languages and Compilers for Parallel Computing, August 1991.
20. HLN92.M. Heflihy, B.H. Lira, and N.Shavit. "Low Contention Load Balancing on Large-Scale Multiprocessors". In Proceedings of the $th SPAA, June 1992.
21. JC92.T. Johnson and A. Colbrook. "A Distributed Data-Balanced Dictionary Based on the B- Link Tree". In Proceedings of the 6th IPPS, pages 319-324, 1992.
22. JLHB88.E. Jul, H. Levy, N. Hutchison, and A. Black. "Fine-Grained Mobility in the Emerald System". A CM Transactions on Computer Systems, 6(1):109-133, February 1988.
23. JS90.T. Johnson and D. Shasha. "A Framework for the Performance Analysis of Concurrent B-tree Algorithms". In Proceedings of the 9th A CM Symposium on Principles of Database Systems, April 1990.
24. Li88.K. Li. "IVY: A Shared Virtual Memory System for Parallel Computing". In Proceedings of the 1988 ICPP, volume II, pages 94-101, 1988.
25. LLG+90.D. Lenoski, J. Landon, K. Gharachorloo, A. Gupta, and J. Hennessy. "The Dixectory- Based Cache Coherence Protocol for the DASH Multiprocessor'. In Proceedings of the 17th ISCA, pages 148-158, May 1990.
26. LS86.V. Lanin and D. Shasha. "A Symmetric Concurrent B-Tree Algorithm". In 1986 Proceed. ings Fall Joint Computer Conference, pages 380-386, November 1986.
27. LY81.P.L. Lehman and S.B. Yao. "Efficient Locking for Concurrent Operations on B-Trees". A CM Transactions on Database Systems, 6(4):650-670, December 1981.
28. Man87.C.R. Manning. "ACORE: The Design of a Core Actor Language and its Compiler". Master's thesis, MIT, August 1987.
29. ML91.E.P. Markatos and T.J. LeBlanc. "Load Balancing vs. Locality Management in Shared- Memory Multiprocessors". Technical Report 399, Univ. of Rochester Computer Science Dept. October 1991.
30. MR85.Y. Mend and Y. Raz. "Concurrency Control in B+ Trees Using Preparatory Operations". In Proceedings o} the ilth International Conference on Very Large Data Bases, pages 331-334, August 1985.
31. PM83.M.L. Powell and B.P. Miller. "Process Migration in DEMOS/MP". In Proceedings of the 9th SOSP, pages 110-119, 1983.
32. RRH92.A. Rogers, J.H. Reppy, and L.J. Hendren. "Supporting SPMD Execution for Dynamic Data Structures", 1992.
33. Sag86.Y. Sagiv. "Concurrent Operations on B- Trees with Overtaking". Journal of Computer and System Sciences, 33(2):275-296, October 1986.
34. SB90.M.D. Schroeder and M. Burrows. "Performance of Firefly RPC". A CM Transactions on Computer Systems, 8(1):1-17, February 1990.
35. SBS92.P. StenstrSm, M. Brorsson, and L. Sandberg. "An Adaptive Cache Coherence Protocol Optimized for Migratory Sharing", November 1992. Unpublished manuscript.
36. SCvE91.K.E. Schauser, D.E. Culler, and T. yon Eicken. "Compiled-Controlled Multithreading for Lenient Parallel Languages". In Proceedings of 1991 FPCA. Springer Veflag, August 1991.
37. SN90.M.S. Squillante and R.D. Nelson. "Analysis of Task Migration in Shared-Memory Multiprocessor Scheduling". Technical Report 90- 07-05, Univ. of Washington Dept. of Computer Science, September 1990.
38. TLC85.M.M. Theimer, K.A. Lantz, and D.R. Cheriton. "Preemptable Remote Execution Facilities for the V-System'. In Proceedings oj: the lOth SOSP, pages 2-12, December 1985.
39. vECGS92.T. yon Eicken, D.E. Culler, S.C. Goldstein, and K.E. Schanser. "Active Messages: a Mechanism for Integrated Communcation and Computation". In Proceedings of the 19th ISCA, pages 256-266, May 1992.
40. Wan91.P. Wang. "An In-Depth Analysis of Concurrent B-Tree Algorithms". Master's thesis, MIT, January 1991. Available as MIT/LCS/TR-496.
41. WBC+91.W. Weihl, E. Brewer, A. Colbrook, C. Dellateens, W. Hsieh, A. Joseph, C. Waldspurger, and P. Wang. "PRELUDE: A System for Portable Parallel Software". Technical Report MIT/LCS/TR-519, MIT LCS, October 1991. Shorter version appears in Proceedings o/PARLE '9P.
42. WW90.W.E. Weihl and P. Wang. "Multi-Version Memory: Software Cache Management for Concurrent B-Trees (extended abstract)". In Proceedings of the P.nd IEEE Symposium on Parallel and Distributed Processing, pages 650-655, December 1990.
43. ZBC+92.H. Zima, P. Brezany, B. Chapman, P. Mehrotra, and A. Schwald. "Vienna Fortran- a Language Specification". Technical Report ICASE Interim Report 21, ICASE Nasa Langley Research Center, March 1992.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel programming languages

• Information systems

  • Information storage systems

    • Record storage systems

      • Directory structures

        • B-trees

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

        • Parallel programming languages