Change search
ReferencesLink to record
Permanent link

Direct link
On data structures and memory models
Luleå tekniska universitet.
2006 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2006. , 13 p.
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2006:24
Identifiers
URN: urn:nbn:se:ltu:diva-18070Local ID: 6ade40a0-86b3-11db-8975-000ea68e967bOAI: oai:DiVA.org:ltu-18070DiVA: diva2:991076
Note
Godkänd; 2006; 20061205 (haneit)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(1068 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 1068 kBChecksum SHA-512
0ff48379a42a7670d2a4be70afb5a3140ea7553d3fca03b897e5a39376d8d0c7f701f6d036eb78a8b7eb1941fa14ace74f742dfdb03349f79ef53fe6a687f275
Type fulltextMimetype application/pdf

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 12 hits
ReferencesLink to record
Permanent link

Direct link