On data structures and memory models

Sammanfattning: In this thesis we study the limitations of data structures and how they can be overcome through careful consideration of the used memory models. The word RAM model represents the memory as a finite set of registers consisting of a constant number of unique bits. From a hardware point of view it is not necessary to arrange the memory as in the word RAM memory model. However, it is the arrangement used in computer hardware today. Registers may in fact share bits, or overlap their bytes, as in the RAM with Byte Overlap (RAMBO) model. This actually means that a physical bit can appear in several registers or even in several positions within one register. The RAMBO model of computation gives us a huge variety of memory topologies/models depending on the appearance sets of the bits. We show that it is feasible to implement, in hardware, other memory models than the word RAM memory model. We do this by implementing a RAMBO variant on a memory board for the PC100 memory bus. When alternative memory models are allowed, it is possible to solve a number of problems more efficiently than under the word RAM memory model. We look at three priority queue related problems: the Discrete Extended Priority Queue, the Time Queue, and the Prefix Sum problems. We side-step several lower bounds for the discrete extended priority queue problem and the prefix sum problem by allowing alternative memory models. We suggest two data structures and algorithms, which provide all the operations for the two problems in worst case constant time. It is not possible to achieve this time bound using the word RAM memory model. We also suggest a data structure for the time queue problem. The algorithms run in expected constant time for the operations that delete the minimum element and worst case constant time for the other operations. The data structure can be maintained by several processes that share a part of the memory. Finally, we also show that it is possible to replace the ALU in a processor with memory while still keeping the ALUs functionality. Hence it is well worth and practical to consider alternative memory models, at least for special purpose processors.