Efficient inter-processor communication in ray tracing

1. A multiprocessing computing system for ray tracing having reduced inter-processor communication, comprising:

an array of at least three general purpose processing elements interconnected by ring topology;

graphics data representing three dimensional scene of multiple objects;

plurality of cells forming a grid;

and a modular mapping scheme;

wherein the graphics data are mapped onto said grid of cells according to said modular mapping scheme;

there is a need to autonomously exchange elements of said data between a cell and any of its 6-connected neighboring cells;

wherein said autonomous exchange is done in a random way, without an agreed-upon timing of the transfer, and not in a centrally controlled way; and

said cells are designated processing elements, according to said modular mapping scheme;

thereby, when a cell is processed by its designated processing element, all cell's communication needs with its 6-connected neighboring cells are mapped to at most one hop along the ring, reducing the inter-processor communication.

2. The computing system of claim 1 wherein the autonomous exchange of data between two geographically neighboring cells translates to a communication neighborhood of the corresponding cell-designated general purpose processing elements on the ring, allowing reduced inteprocessor communication.

3. The computing system of claim 1 wherein each general purpose processing element assigned to a cell, is in a communication distance of at most one ring hop to a general purpose processing element assigned to any of the cell's six connected neighboring cells.

4. The computing system of claim 1 wherein a general purpose processing element is allocated all cells of a given module, handling one cell at a time, independently to other general purpose processing elements.

5. The computing system of claim 1 wherein said exchange of data from a sender-cell to a receiver-cell is performed by the general purpose processing element assigned to the sender-cell.

6. A method of reducing inter-processor communication in an array having at least three general purpose processing elements, when a processed graphics data represent a three dimensional scene of multiple objects, comprising the steps of:

connecting said processing elements by ring interconnection;

subdividing the three-dimensional data onto a grid of cells;

mapping said cells, according to a modular mapping scheme;

designating processing elements to said cells, according to modular mapping scheme;

thereby due to the said modular mapping, when a cell is processed by its designated processing element, all cell's communication needs are mapped to at most one hop along the ring, reducing the inter-processor communication.

7. The method of claim 6 wherein a geographical neighborhood between two data exchanging cells translates to a communication neighborhood between corresponding cell-designated general purpose processing elements, for reduced data communication.

8. The method of claim 6 wherein a general purpose processing element is allocated all cells of a given module, handling one cell at a time, independently to other general purpose processing elements.

9. The method of claim 6 wherein said exchange of data from a sender-cell to a receiver-cell, is communicated by the general purpose processing element designated to the sender-cell.