A neighbor connected processor network for performing relational algebra operations
Kjell Bratbergsengen, Rune Berg Larsen, Oddvar Risnes, Terje Aandalen · ACM SIGIR Forum · 1980
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 log 2 C, 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.