| Compebitive Algorithms for Replication and Migration Problems (1989) | |||||||||||||||
Abstract | |||||||||||||||
| In this paper we consider problems that arise in a shared memory multiprocessor in which memory is physically distributed among a number of memories local to each pIocessor or cluster of processors. The issue we a d b s is that of deciding which local memories should contain copies of pages of data. In the migration problem we operate under the constraint that a page must be kept in exactly one local memory. In the replication problem we allow a page to be kept in any subset of the local memories, but do not allow a local memory to drop a page once it has it. For interconnection topologies that arc complete graphs, or trees we have obtained efficient on-line algorithms for these pmblems. Our migration algorithms also extend to interconnections that arc products of these topologies (e.g. a hypercube is a product of simple trees). An on-line algorithm decides how to process each request (which is a read or write request from a processor to a page) without knowing future requests. Our algorithms are also said to be competitive because their performance is within a small constant factor of that of any other algorithm, including algorithms that make use of knowledge of future requcStS. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||