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}
}
BibTeX

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 ... BibTeX

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 BibTeX

References

[BATC68]
Kenneth E. Batcher: Sorting Networks and Their Applications. AFIPS Spring Joint Computing Conference 1968: 307-314 BibTeX
[HIRS78]
Daniel S. Hirschberg: Fast Parallel Sorting Algorithms. Commun. ACM 21(8): 657-661(1978) BibTeX
[MULL75]
David E. Muller, Franco P. Preparata: Bounds to Complexities of Networks for Sorting and for Switching. J. ACM 22(2): 195-201(1975) BibTeX
[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 BibTeX
[THOM77]
Clark D. Thompson, H. T. Kung: Sorting on a Mesh-Connected Parallel Computer. Commun. ACM 20(4): 263-271(1977) BibTeX
[TODD78]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:22 2009