PAGE MIGRATION ALGORITHMS USING WORK-FUNCTIONS

The page migration problem occurs during management of a globally addr essed 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 dista nce. 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 schedu le movements online so as to minimize the total cost of memory referen ces. Page migration can also be viewed as a restriction of the 1-serve r with excursions problem. This paper presents a collection of algorit hms and lower bounds for the page migration problem in various setting s. Competitive analysis is used. The competitiveness of an online algo rithm is the worst case ratio of its cost to the optimum cost on any s equence of requests. Randomized (2 + 1/2D)-competitive online algorith ms are given for trees and products of trees, including the mesh and t he hypercube, and for uniform spaces when D = 1,2. These algorithms ar e shown to be optimal. A lower bound of 85/27 on the competitiveness o f any deterministic algorithm (in arbitrary spaces) with D = 1 is show n, disproving a conjecture of Black and Sleator. Deterministic (2 + 1/ 2D)-competitive algorithms are given for products of continuous trees under the L-1 metric, such as Rn with the Manhattan metric. A determin istic algorithm for R-n under any norm is presented and is shown to ha ve competitive ratio tending to 1 + phi = 2.618.... The paper makes ex tensive use of the concept of a work function, a tool which provides a systematic approach to many competitive analysis problems. (C) 1997 A cademic Press.