A neighbor connected processor network for performing relational algebra operations

ABSTRACT

In a data base computer consisting of cells with processing capability, the desired goal is to achieve an execution time - for each data base operation - to be inversely proportional to the number of cells. Using rings as a basic building block, we have constructed different intercell communication networks. The capacity of the communication network have been analyzed under the workload of relational algebra operations. A k-dimensional network of intersecting rings, each of 2 or 3 cells have been found to give the highest processing capacity per cell in the network. Here k is log2C, where C is the total number of cells. A simple wiring scheme for k-dimensional network of 2 cells per ring has been presented. For this type of network, we have also described the routing logic, and given an estimate of the queueing delay.

REFERENCES

• 1: K. Bratbergsengen: "Algebra operasjoner utfort ved sortering og fletting av relasjoner." Department of Computer Science, University of Trondheim, April 1978 (in Norwegian).
• 2: K. Bratbergsengen: "Sortering i et system hvor lagermodulene har forbindelse med et fast antall andre lagermoduler." ASTRA working paper no. 16. Dep. of Computer Science, University of Trondheim, May, 1978 (in Norwegian).
• 3: Karl Rottmann: "Mathematische Formelsammlung". Bibliographisches Institut, AG 1960.
• 4: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 5: C. H. Séquin , A. M. Despain , D. A. Patterson, Communication In X-TREE, A Modular Multiprocessor System, Proceedings of the 1978 annual conference, p.194-203, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804098]
• 6: J. Banerjee and D. K. Hsiao: "Parallel bitonic record sort - an effective algorithm for the realization of a post processor". Computer and Information Science Research Center. The Ohio State University, Columbus, Ohio 43210, March, 1979.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Special-purpose algebraic systems

General Terms:
Algorithms, Design, Performance