The performance of multiprogrammed shared-memory multiprocessors suffers often from scheduler interventions that neglect data locality. On cache-coherent distributed shared-memory (DSM) multiprocessors, such scheduler interventions tend to increase the rate of remote memory accesses. This paper presents a novel dynamic page migration algorithm that remedies this problem in iterative parallel programs. The purpose of the algorithm is the early detection of pages that will most likely be accessed remotely by threads associated with them via a thread-to-memory affinity relation. The key mechanism that enables timely identification of these pages is a communication interface between the page migration engine and the operating system scheduler. The algorithm improves previously proposed competitive page migration algorithms in many aspects, including accuracy, timeliness and cost amortization. Most notably, the algorithm is not biased by obsolete memory access history that may be accumulated in the page access counters at runtime. Experiments on the SGI Origin2000 show that the algorithm outperforms by far the best static page placement algorithm and a customized page migration engine implemented in IRIX, the Origin2000 operating system. The algorithm is implemented at user-level and its functionality is orthogonal to the scheduling policy of the operating system. Key Words: Distributed shared-memory multiprocessors, NUMA, multiprogramming, memory management, page migration, data locality, operating systems, runtime systems. Computer Architecture at UPC since 1990. He has been lecturing on computer architecture, operating systems, computer networks and performance evaluation since 1981. His research interests include parallel computing, multiprocessor architectures, memory hierarchies, parallelizing compilers, operating systems, parallelization of numerical kernels, metacomputing tools and performance analysis and prediction tools. He has lead the technical work of UPC in 15 industrial R&D projects. Dr. Labarta is the director of CEPBA (European Center for Parallelism of Barcelona) since 1995. In CEPBA, he has been highly motivated by the promotion of parallel computing into industrial practice, especially within SMEs, and has been responsible for three clusters of projects on technology transfer, involving 28 subprojects. Eduard Ayguadé received the Engineering degree in Telecommunications in 1986 and the Ph.D. degree in Computer Science in 1989, both from the Universitat Politecnica de Catalunya (UPC) in Barcelona, Spain. He has been lecturing at UPC on computer organization and architecture and optimizing compilers since 1987. He is a Professor of the Department of Computer Architecture at UPC since 1997. His research interests cover the areas of processor microarchitecture and ILP exploitation, parallelizing compilers for high-performance computing systems and tools for performance analysis and visualization. He has published more than 100 papers in these topics and participated in several multiinstitutional research projects, mostly in the framework of the European Union ESPRIT and IST programmes. 4
They have shown their approach can even be more efficient when the page migration engine and the operating system scheduler REF are able to communicate.
Scheduler-Activated Dynamic Page Migration for Multiprogrammed DSM Multiprocessors 1 2
Computer Science