A data-driven database model and its implementation on a highly-parallel architecture
Robert L. Hartmann · Medical Entomology and Zoology · 1987
The search for computer architectures utilizing large numbers of processing elements and their application to suitable problems has been a continual quest for many researchers. This dissertation presents results of an analysis of a multiprocessor architecture applied to the problem of database management. The database problem is first re-stated in terms of a new data model, the Active Graph Model, which employs a graphical representation for data (nodes) and relationships (arcs) in addition to concepts from the dataflow model of computation to exploit the parallel processing power of the architecture. The nodes of the graph are 'active' elements which respond to requests in the form of tokens traveling along the arcs. This data model and its query language are shown to be relationally complete and therefore equivalent in expressive power to the Relational Model. A mesh-connected array of processing elements forms the basis for the architecture. The nodes and arcs of the model are mapped onto the architecture and practical algorithms are defined for distributing requests, data manipulation, and for sorting and reporting of results. The functionality of these algorithms is verified and the performance characteristics of the system are measured through an implementation of the algorithms on simulated hardware using a standardized evaluation methodology. The results of the experiments demonstrate that large numbers of processors can be used effectively given a sufficiently large problem. Additionally, under-utilized processing capability can be used by multiple simultaneous requests. Finally, the system is not plagued by interprocessor communications bottlenecks which have been identified in other such systems.