Knowledge States for the Caching Problem in Shared Memory Multiprocessor Systems

Document Type

Conference Proceeding

Publication Date

5-12-2004

Publication Title

7th International Symposium on Parallel Architectures, Algorithms, and Networks, Proceedings.

Volume

2004

First page number:

307

Last page number:

312

Abstract

Multiprocessor systems with a global shared memory provide logically uniform data access. To hide latencies when accessing global memory each processor makes use of a private cache. Several copies of a data item may exist concurrently in the system. To guarantee consistency when updating an item a processor must invalidate copies of the item in other private caches. To exclude the effect of classical paging faults, one assumes that each processor knows its own data access sequence, but does not know the sequence of future invalidations requested by other processors. Performance of a processor with this restriction can be measured against the optimal behavior of a theoretical omniscient processor, using competitive analysis. A 4/3 competitive randomized online algorithm for this problem for cache size 2 is presented. This algorithm is derived with the help of a new concept we call knowledge states. We also prove a matching lower bound, thus this online algorithm is best possible. Finally, a lower bound of 3/2 on the competitiveness for larger cache sizes is shown.

Language

english

Find It

UNLV article access

Share

COinS