Page Migration Algorithms Using Work Functions

The page migration problem occurs in managing a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to that page by other processors are charged a cost equal to the network distance. At times the page may migrate between processors, at a cost equal to the distance times a page size factor, D. The problem is to schedule movements on-line so as to minimize the total cost of memory references. Page migration can also be viewed as a restriction of the 1-server with excursions problem. This paper presents a collection of algorithms and lower bounds for the page migration problem in various settings. Competitive analysis is used. The competitiveness of an on-line algorithm is the worst-case ratio of its cost to the optimum cost on any sequence of requests. Randomized (2 + 1 2D )-competitive on-line algorithms are given for trees and products of trees, including the mesh and the hypercube, and for un..