A case for user-level dynamic page migration

ABSTRACT

This paper presents user-level dynamic page migration, a runtime technique which transparently enables parallel programs to tune their memory performance on distributed shared memory multiprocessors, with feedback obtained from dynamic monitoring of memory activity. Our technique exploits the iterative nature of parallel programs and information available to the program both at compile time and at runtime in order to improve the accuracy and the timeliness of page migrations, as well as amortize better the overhead, compared to page migration engines implemented in the operating system. We present an adaptive page migration algorithm based on a competitive and a predictive criterion. The competitive criterion is used to correct poor page placement decisions of the operating system, while the predictive criterion makes the algorithm responsive to scheduling events that necessitate immediate page migrations, such as preemptions and migrations of threads. We also present a new technique for preventing page pingpong and a mechanism for monitoring the performance of page migration algorithms at runtime and tuning their sensitive parameters accordingly. Our experimental evidence on a SGI Origin2000 shows that unmodified OpenMP codes linked with our runtime system for dynamic page migration are effectively immune to the page placement strategy of the operating system and the associated problems with data locality. Furthermore, our runtime system achieves solid performance improvements compared to the IRIX 6.5.5 page migration engine, for single parallel OpenMP codes and multiprogrammed workloads.

REFERENCES

• 1: E. Ayguadd et al. NanosCompiler: A Research Platform for OpenMP Extensions. In Proc. of the First European Workshop on OpenMP, pages 27-31, October 1999.
• 2: D. Black and D. Sleator. Competitive Algorithms for Replication and Migration Problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989.
• 3: William J. Bolosky , Michael L. Scott , Robert P. Fitzgerald , Robert J. Fowler , Alan L. Cox, NUMA policies and their relation to memory architecture, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.212-221, April 08-11, 1991, Santa Clara, California, United States
• 4: T. Brewer , G. Astfalk, The evolution of the HP/Convex Exemplar, Proceedings of the 42nd IEEE International Computer Conference, p.81, February 23-26, 1997
• 5: L. Brieger. HPF to OpenMP on the Origin2000: A Case Study. In Proc. of the First European Workshop on OpenMP, pages 19-20, October 1999.
• 6: Rohit Chandra , Scott Devine , Ben Verghese , Anoop Gupta , Mendel Rosenblum, Scheduling and page migration for multiprocessor compute servers, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.12-24, October 05-07, 1994, San Jose, California, United States
• 7: Rohit Chandra , Anoop Gupta , John L. Hennessy, COOL: An Object-Based Language for Parallel Programming, Computer, v.27 n.8, p.13-26, August 1994 [doi>10.1109/2.303616]
• 8: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 9: Pedro C. Diniz , Martin C. Rinard, Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.89-132, May 1999 [doi>10.1145/312203.312210]
• 10: Erik Hagersten , Michael Koster, WildFire: A Scalable Path for SMPs, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.172, January 09-12, 1999
• 11: Cristina Hristea , Daniel Lenoski , John Keen, Measuring memory hierarchy performance of cache-coherent multiprocessors using micro benchmarks, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509638]
• 12: Dongming Jiang , Jaswinder Pal Singh, Scaling application performance on a cache-coherent multiprocessor, Proceedings of the 26th annual international symposium on Computer architecture, p.305-316, May 01-04, 1999, Atlanta, Georgia, United States
• 13: H. Jin, M. Frumkin, and J. Yam The OpenMP Implementation of NAS Parallel Benchmarks and its Performance. Technical Report NAS-99-011, NASA Ames Research Center, 1999.
• 14: 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
• 15: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 16: J. Levesque. The Future of OpenMP on IBM SMP Systems. In Proc. of the First European Workshop on OpenMP, pages 5-6, October 1999.
• 17: Tom Lovett , Russell Clapp, STiNG: a CC-NUMA computer system for the commercial marketplace, Proceedings of the 23rd annual international symposium on Computer architecture, p.308-317, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 18: Michael Marchetti , Leonidas I. Kontothanassis , Ricardo Bianchini , Michael L. Scott, Using simple page placement policies to reduce the cost of cache fills in coherent shared-memory systems, Proceedings of the 9th International Symposium on Parallel Processing, p.480-485, April 25-28, 1995
• 19: Thu D. Nguyen , Raj Vaswani , John Zahorjan, Maximizing Speedup through Self-Tuning of Processor Allocation, Proceedings of the 10th International Parallel Processing Symposium, p.463-468, April 15-19, 1996
• 20: Lisa Noordergraaf , Ruud van der Pas, Performance experiences on Sun's Wildfire prototype, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.38-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331570]
• 21: M. Resch and B. Sander. A Comparison of OpenMP and MPI for the Parallel CFD Test Case. In Proc. of the First European Workshop on OpenMP, October 1999.
• 22: Silicon Graphics Inc. IRIX 6.5 Operating System Man Pages. http://techpubs.sgi.com, 1999.
• 23: Silicon Graphics Inc. Origin2000 and Onyx2 Performance Tuning and Optimization Guide. http://techpubs.sgi.com, 1999.
• 24: Vijayaraghavan Soundararajan , Mark Heinrich , Ben Verghese , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Flexible use of memory for replication/migration in cache-coherent DSM multiprocessors, Proceedings of the 25th annual international symposium on Computer architecture, p.342-355, June 27-July 02, 1998, Barcelona, Spain
• 25: Ben Verghese , Scott Devine , Anoop Gupta , Mendel Rosenblum, Operating system support for improving data locality on CC-NUMA compute servers, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.279-289, October 01-04, 1996, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory