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
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE