Scanning Multiple Sequences via Cache Memory |
| |
Authors: | Mehlhorn Sanders |
| |
Affiliation: | (1) Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany. mehlhorn@mpi-sb.mpg.de, sanders@mpi-sb.mpg.de., DE |
| |
Abstract: | Abstract. We consider the simple problem of scanning multiple sequences. There are k sequences of total length N which are to be scanned concurrently. One pointer into each sequence is maintained and an adversary specifies which pointer
is to be advanced. The concept of scanning multiple sequence is ubiquitous in algorithms designed for hierarchical memory.
In the external memory model of computation with block size B , a memory consisting of m blocks, and at most m sequences the problem is trivially solved with N/B memory misses by reserving one block of memory for each sequence.
However, in a cache memory with associativity a , every access may lead to a cache fault if k > a . For a direct mapped cache (a = 1 ) two sequences suffice. We show that by randomizing the starting addresses of the sequences the number of cache misses can
be kept to O(N/B) provided that k = O(m/B
1/a
) , i.e., the number of sequences that can be supported is decreased by a factor B
1/a
. We also show a corresponding lower bound.
Our result leads to a general method for converting sequence based algorithms designed for the external memory model of computation
to cache memory even for caches with small associativity. |
| |
Keywords: | , Cache memory, Set associative cache, External memory algorithm, Memory hierarchy, Multi-Merge, Data distribution, |
本文献已被 SpringerLink 等数据库收录! |
|