Method and apparatus for an inter-cell shortest communication
Novel method and system for distributed database ray-tracing is presented, based on modular mapping of scene-data among processors. Its inherent properties include matching between geographical proximity in the scene with communication proximity between processors.
1. A multiprocessing computing system having reduced inter-processor communication, comprising:
an array of at least three processing elements interconnected by a ring topology;
a three-dimensional data;
a three-dimensional uniform grid of cells;
wherein said data is mapped onto said grid of cells by way of modular mapping scheme; and
each cell is assigned a processing element, according to said modular mapping scheme; and
each cell exchanges said elements of said data with its 6-connected neighboring cells;
thereby, when a cell is processed by its assigned processing element, all the data with its 6-connected neighboring cells is interchanged by the cells' assigned processors through at most one hop along the ring, representing a shortest physical path between the cells.
2. The computing system of claim 1 , wherein the exchange of data by a cell needs not be synchronized with its geographically neighboring cells.
3. The computing system of claim 1 , wherein said exchange of data from a sender-cell to a receiver-cell, is performed by the processing element designated to the sender-cell.
4. The computing system of claim 1 , wherein said processing element designated to a cell is in a communication distance of at most one ring hop to processing element assigned to any of the cell's six connected neighboring cells.
5. A method of reducing inter-processor communication in a multiprocessing system of at least three processing elements, wherein a processed data three-dimensional, comprising the steps of:
connecting said processing elements by a ring interconnection;
partitioning the data onto a uniform grid of cells;
mapping said cells, according to a modular mapping scheme;
assigning the processing elements to said cells, according to the modular mapping scheme;
thereby a modularly mapped cell exchanges data with each of its 6-connected neighboring cells via a shortest physical path consisting of at most one hop along the ring.
6. The method of claim 5 , wherein the exchange of data needs not be synchronized by the cell with its geographically neighboring cells.
7. The method of claim 5 , wherein said exchange of data from a sender-cell to a receiver-cell is performed by the processing element assigned to the sender-cell.
8. The method of claim 5 , wherein said processing element assigned to a cell, is in a communication distance of at most one ring hop to processing element assigned to any of the cell's six connected neighboring cells.