ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Bit-Sliced VLSI Algorithm for Search and Sort.

Yuzuru Tanaka: Bit-Sliced VLSI Algorithm for Search and Sort. VLDB 1984: 225-234
@inproceedings{DBLP:conf/vldb/Tanaka84,
  author    = {Yuzuru Tanaka},
  editor    = {Umeshwar Dayal and
               Gunter Schlageter and
               Lim Huat Seng},
  title     = {Bit-Sliced VLSI Algorithm for Search and Sort},
  booktitle = {Tenth International Conference on Very Large Data Bases, August
               27-31, 1984, Singapore, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1984},
  isbn      = {0-934613-16-8},
  pages     = {225-234},
  ee        = {db/conf/vldb/Tanaka84.html},
  crossref  = {DBLP:conf/vldb/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

For the high speed processing of databases, it is fundamental to introduce various VLSI architectures to the processing of basic functions. Especially, sort and batch search requires high speed modules. The VLSI algorithms of them must make use of the time necessary for the transfer of a large amount of data to and from the modules. These modules should be nonprogrammable in order to avoid serious overheads. However, they should be able to extend their capacity and wordlength by the connection of them.

This paper solves the problem of how to extend the wordlength of search and sort hardware modules. It proposes bit-sliced architectures of an interval search engine and a two-way-merge sorter. The slicing of these engines does not cause excessive overheads. The decrease of the slice length decreases the hardware complexity, and increases the flexibility of the modules. Therefore, it increases the feasibility of the VLSI implementation of these hardware modules.

Copyright © 1984 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Gunter Schlageter, Lim Huat Seng (Eds.): Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings. Morgan Kaufmann 1984, ISBN 0-934613-16-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BATC68]
Kenneth E. Batcher: Sorting Networks and Their Applications. AFIPS Spring Joint Computing Conference 1968: 307-314 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HIRS78]
Daniel S. Hirschberg: Fast Parallel Sorting Algorithms. Commun. ACM 21(8): 657-661(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MULL75]
David E. Muller, Franco P. Preparata: Bounds to Complexities of Networks for Sorting and for Switching. J. ACM 22(2): 195-201(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NASS79]
...
[PREP78]
...
[STON71]
...
[TANA80]
Yuzuru Tanaka, Yukoo Nozaka, Akinari Masuyama: Pipeline Searching and Sorting Modules as Components of a Data Flow Database Computer. IFIP Congress 1980: 427-432 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[THOM77]
Clark D. Thompson, H. T. Kung: Sorting on a Mesh-Connected Parallel Computer. Commun. ACM 20(4): 263-271(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TODD78]
...

Copyright © Tue Mar 16 02:21:57 2010 by Michael Ley (ley@uni-trier.de)