Partitioning and load balancing graphical shape data for parallel applications

An apparatus for partitioning and load balancing graphical shape data among computer systems interconnected through a network, the apparatus comprising:

• a graphics file comprising a plurality of cells and a prime cell having a plurality of prime transforms, each of the prime transforms including a plurality of cells;
• one parallel partitioning mechanism residing on each of a plurality of computers in the network, each of the plurality of computers comprising a data density map having a two-dimensional matrix of entries, said matrix organized as columns and rows such that each of said columns intersects one of said rows in one of said entries, each of said entries storing a data density value, a cell table having one entry of the plurality of cells in the graphics file, and an output frame, wherein the parallel partitioning mechanism for each computer system:
• determines a chip volume;
• divides the chip volume into a plurality of block and maps each of the blocks to one of the entries in data density map;
• partitions the data density map amongst the plurality of computer systems, thereby assigning each computer system a computer system of the chip volume, wherein each computer system volume is approximately the same;
• and
• copies a portion of the cells from the graphics file to an output frame, wherein the portion corresponds to one of the computer system volumes.

A method for partitioning graphical shape data, the method comprising the steps of:

• providing a graphics file;
• distributing the graphics file amongst a plurality of computer;
• determining a data density of the graphics file resident on the plurality of computers;
• partitioning the data density amongst a second plurality of processors, thereby assigning part of the graphics file to each processor:
• and for each processor, copying the part of the graphics file assigned to the processor to an output frame, wherein the graphics file comprises a plurality of cells, wherein each of plurality of cells describes graphical shape data occupying a cell volume, and wherein the step of determining a data density of the graphics file comprises the steps of:
• determining a chip volume into which each graphical shape data for each cell would fit;
• and
• mapping this chip volume into a data density map comprising a two-dimensional matrix of entries, said matrix organized as columns and rows such that each of said columns intersects one of said rows in one of said entries, each of said entries storing a data density value.

A method for partitioning and load balancing graphical shape data, the method comprising the steps of:

• providing a graphics file apportioned amongst a plurality of processors comprising a plurality of cells;
• mapping each of the cells to at least one of a plurality of entries in a two-dimensional matrix of said entries in a density map, said matrix organized as columns and rows such that each of said columns intersects one of said rows in one of said entries, each of said entries storing a data density value;
• performing the following steps, for each cell, to fill the plurality of entries in the data density map;
• determining a number of bytes in each cell;
• determining entries in the data density map to which the cell maps;
• averaging the number of bytes over the number of entries in the data density map to which the cell maps;
• and
• adding the average to each entry of the data density map to which the cell maps;
• partitioning the data density map amongst a second plurality of processors such that each processor is assigned a relatively even amount of the data density map;
• and
• performing the following steps for each of the partitions of the data density map:
• creating and initializing an output frame;
• and
• performing the following steps for each cell of the graphics file:
• determining if this cell is assigned to this partition;
• and
• if this cell is assigned to this partition, copying contents of this cell to the output frame.

A program product for partitioning and load balancing graphical shape data among computer systems interconnected through a network and connected to a graphics file comprising a plurality of cells and a prime cell having a plurality of prime transforms, each of the prime transforms including a plurality of cells, the program product tangibly embodying a program of machine-readable instructions executable by a computer system, the program product comprising:

• one parallel partitioning mechanism able to be distributed to each of a plurality of computers in the network, each parallel partitioning mechanism thereby creating a data density map having a two-dimensional matrix of entries, said matrix organized as columns and rows such that each of said columns intersects one of said rows in one of said entries, each of said entries storing a data density value, a cell table having one entry for each of the plurality of cells in the graphics file, and an output frame, wherein the parallel partitioning mechanism for each computer system:
• determines a chip volume;
• divides the chip volume into a plurality of blocks and maps each of the blocks to one of the entries in the data density map;
• partitions the data density map amongst a second plurality of computer systems, thereby assigning each computer system a computer system volume of the chip volume, wherein each computer system volume is approximately the same;
• and
• copies a portion of the cells from the graphics file to an output frame, wherein the portion corresponds to one of the computer system volumes;
• and
• signal bearing media bearing the parallel partitioning program.