|
Abstract : |
Abstract. The page migration problem is to manage 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 incur a cost proportional to the network distance. At times the page may migrate between processors at cost proportional to the distance times D, a page size factor. The problem is to schedule movements on-line so that the total cost of memory references is within a constant factor c of the best off-line schedule. An algorithm that does so is called c-competitive. Black and Sleator gave 3-competitive deterministic on-line algorithms for uniform networks (complete graphs with unit edge lengths) and for trees with arbitrary edge lengths. No good deterministic algorithm is known for general networks with arbitrary edge lengths. We present randomized algorithms for the migration problem that are both simple and better than 3-competitiveagainst an oblivious adversary. We give one algorithmdesigned for uniformgraphs that is approximately 2.28-competitive as D grows large. We also give a second, more powerful algorithm that works on graphs with arbitrary edge distances. This algorithm is approximately 2.62-competitive (or, 1 plus the Golden Ratio) for large D. Both these algorithms use random bits only during an initialization phase, and from then on run deterministically. We also examine the competitiveness of a very simple coin-flipping algorithm., |
