Accession Number : ADA112542
Title : On a High-Performance VLSI Solution to Database Problems.
Descriptive Note : Interim rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Song,Siang Wun
PDF Url : ADA112542
Report Date : Aug 1981
Pagination or Media Count : 172
Abstract : This thesis explores the design and use of custom-made VLSI hardware in the area of database problems. Our effort differs from most previous ones in that we search for structures and algorithms, directly implementable on silicon, for the solution of computation-intensive database problems. The types of target database systems include the general database management systems and the design database systems. The thesis deals mainly with database systems of the relational model. One common view concerning special-purpose hardware usage is that it performs a specific task. The proposed device is not a hardware solution to a specific problem, but provides a number of useful data structures and basic operations. It can be used to improve the performance of any sequential algorithm which makes extensive use of such data structures and basic operations. The design is based on a few basic cells, interconnected together in the form of a complete binary tree. The proposed device can handle all the basic relational operations: select, join, project, union, and intersection. With a special-purpose device of limited size attached to a host, the overall performance may ultimately be dictated by the I/O between the two sites. The ideal special-purpose device design is one that achieves a balance between computation and I/O. We propose a model to study the I/O complexity for sorting n numbers with any special-purpose hardware device of size s, and show a lower bound result of omega (n log n/log s). We present an optimal design achieving this bound. An important finding is that for practical ranges on the quantity of data to be sorted, systolic sorting devices of small sizes can beat fast sequential sorting algorithms.
Descriptors : *Data bases, *Data management, *Computer applications, *Integrated circuits, Design to cost, Algorithms, Silicon, Performance(Engineering), Interfaces, Theses, Three dimensional, Circuits, Computer architecture, Sizes(Dimensions), Quantity, Sorting, Range(Extremes), Input output devices, Computations, Balance
Subject Categories : Economics and Cost Analysis
Distribution Statement : APPROVED FOR PUBLIC RELEASE