Research in Parallel Processing

STARTER: a Scalable and fault Tolerant parallel ARchitecture for daTabasEs and logic pRogramming

Federico Bassetti, Gopal Gupta

The technology of sequential computers has been pushed nearly to its limits, and there is a growing realization that parallel computers are the way to high-performance computing. A number of parallel computers are available today. These computers can be divided into two classes depending on their architecture: SIMD or MIMD. MIMD architectures can be further divided into two subclasses: those that have Uniform Memory Access (Shared Memory Multiprocessors) vs. those that have Non-Uniform Memory Access (Message Passing Multiprocessors). SIMD architectures are suitable for data-parallel programs, that is, those programs that have a regular computation structure. MIMD architectures on the other hand are suitable for control-parallel programs and programs with irregular computation structure. Among MIMD architectures, Shared Memory Multiprocessors are easy to program but are not scalable. On the other hand, Message Passing Computers are scalable but not easy to program. Distributed Shared Memory Computers have been built that provide the Uniform Memory Abstraction that are scalable, however, they turn out to be too complex and too expensive. In our view, an ideal architecture is one that:

  1. provides a Uniform Memory Abstraction with minimal overhead,
  2. is scalable to thousands of processors,
  3. is fault tolerant,
  4. is built using currently available technology
  5. can efficiently perform SIMD as well as MIMD computations.
Recently, an n-dimensional grid of buses (click here for an image) has been shown to possess all these properties [G94]. In this project, we aim to simulate this new architecture and study its performance over various complex benchmarks. The cache performance of this architecture will also be studied. This study will be used to devise new caching strategies to make this architecture more efficient.

An application area that we specially plan to investigate is that of parallel logic programming and parallel databases. We will study the performance of applications in areas of parallel logic programming and parallel databases on this new architectures, and use the results obtained to fine tune the parallel architecture. In other words, we will investigate the suitability of our parallel machine as a parallel database machine and as a parallel logic programming engine. In the rest of the paper we present an outline of this new architecture based on an n-dimensional grid of buses. We will also discuss our scheme for using this parallel machine as a parallel database machine and as a parallel logic programming engine.

Related Papers

Parallel Proc. Page Research Page Lab Home Page