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):

Report Date:

1981-08-01

Pagination or Media Count:

172.0

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 IO between the two sites. The ideal special-purpose device design is one that achieves a balance between computation and IO. We propose a model to study the IO complexity for sorting n numbers with any special-purpose hardware device of size s, and show a lower bound result of omega n log nlog 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.

Subject Categories:

  • Economics and Cost Analysis
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE