Name
Title | ||
|---|---|---|
A special function unit for database operations (SFU-DB): design and performance evaluation |
Abstract | ||
|---|---|---|
The design and analysis of a special function unit for database operations (SFU-DB) that uses a novel hardware sorting module, the automatic retrieval memory (ARM), are described. The SFU-DB is a functionally independent unit that efficiently performs certain nonnumeric operations. It can function as a coprocessor for a host CPU or as a special processing unit in a highly parallel processing system. The ARM implements in hardware a true distribution-based sort algorithm that requires no comparison operations. Without performing any comparison, the SFU-DB avoids the lower bound constraint on comparison-based sorting algorithms and achieves, for the worst case, a complexity of O(n) for both execution time and main memory size. Using the fundamental sort algorithm with slight modifications. the SFU-DB also uses the ARM as an engine for other primitive database operations such as relational join, elimination of duplicates, set union, set intersection, and set difference, also with complexity of O(n). The SFU-DB/ARM architecture is rather simple and requires only a modest amount of specialized hardware. The specialized hardware has been designed and simulated for fabrication using CMOS gate arrays, and the remainder of the SFU-DB has been simulated in software using Turbo Pascal running on an IBM-PC. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1109/12.76403 | Computers, IEEE Transactions |
Keywords | Field | DocType |
computational complexity,database management systems,parallel algorithms,performance evaluation,sorting,special purpose computers,CMOS gate arrays,SFU-DB,Turbo Pascal,automatic retrieval memory,coprocessor,database operations,distribution-based sort algorithm,duplicates elimination,execution time,fabrication,fundamental sort algorithm,hardware sorting module,host CPU,main memory size,nonnumeric operations,parallel processing system,performance evaluation,relational join,set difference,set intersection,set union,special function unit,special processing unit,worst case complexity | ARM architecture,Central processing unit,Computer science,Parallel algorithm,Parallel computing,Real-time computing,Sorting,Turbo Pascal,Coprocessor,Worst-case complexity,Database,Sorting algorithm | Journal |
Volume | Issue | ISSN |
40 | 3 | 0018-9340 |
Citations | PageRank | References |
2 | 0.52 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Herman Lam | 1 | 305 | 91.31 |
| Chiang Lee | 2 | 294 | 149.40 |
| Su, S.Y.W. | 3 | 60 | 32.50 |