System and method for determining a cache optimized ordering of cells in an unstructured graph

• US 20040107312A1
• Filed: 10/16/2002
• Published: 06/03/2004
• Est. Priority Date: 10/16/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ruetsch, Gregory R.
• Granted Patent: US 7,269,542 B2
• Time in Patent Office: Days
• US Class Current: 711/113
• CPC Class Codes: G06F 2111/02 CAD in a network environment, e.g. collaborative CAD or distributed simulation
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

One embodiment of the present invention provides a system and method for determining a cache optimized ordering of cells in an unstructured graph. Cells bounding a region defined along a portion of a stored logically-defined grid are identified and each cell is added into an element of a level set array block in order of traversal through the region along the boundary. The level set array block is reordered for each additional cell in the data object that is contiguous to at least one such cell added previously to the level set array block. Each such additional cell is added into an element of the level set array block. Each cell remaining in the data object independent of any element in the level set array block is iteratively added.

Claims

1. A system for determining a cache optimized ordering of cells in an unstructured graph, comprising:

ad bounding module identifying cells laying on a specified portion of a boundary of a logically-defined grid for a stored unstructured graph;

a reordering module adding each identified cell in order of traversal along the specified portion of the boundary into an element of a provisional level set array block, and inserting one or more further cells between each sequential pair of cells, which are not contiguously-located in the logically-defined grid, into an element of the provisional level set array block, each further cell being located contiguous to at least one of the sequential pair of cells in the logically-defined grid; and

an iteration module iteratively identifying, adding and inserting each cell remaining in the logically-defined grid.

2. A system according to claim 1, wherein the data object comprises a shape having two dimensions.

3. A system according to claim 1, wherein the data object comprises a shape having more than two dimensions, further comprising:

a searching module finding each such additional cell in the data object that is contiguous in each dimension to the at least one such cell added previously to the level set array block.

4. A system according to claim 1, further comprising:

a preordering module dividing the data object into the cells with each such cell having a closed shape and sharing a common edge with at least one other such cell in the data object.

5. A system according to claim 1, further comprising:

a memory allocation module allocating the level set array block with a set of the elements at least equal to the number of the cells in the data object.

6. A system according to claim 1, wherein the data object comprises a structured polygon logically divided by regularly-spaced cells.

7. A system according to claim 1, wherein the data object comprises an unstructured polygon logically divided by irregularly-spaced cells.

8. A method for determining a cache optimized ordering of cells in an unstructured graph, comprising:

identifying cells laying on a specified portion of a boundary of a logically-defined grid for a stored unstructured graph;

adding each identified cell in order of traversal along the specified portion of the boundary into an element of a provisional level set array block;

inserting one or more further cells between each sequential pair of cells, which are not contiguously-located in the logically-defined grid, into an element of the provisional level set array block, each further cell being located contiguous to at least one of the sequential pair of cells in the logically-defined grid; and

iteratively identifying, adding and inserting each cell remaining in the logically-defined grid.

9. A method according to claim 8, wherein the data object comprises a shape having two dimensions.

10. A method according to claim 8, wherein the data object comprises a shape having more than two dimensions, further comprising:

finding each such additional cell in the data object that is contiguous in each dimension to the at least one such cell added previously to the level set array block.

11. A method according to claim 8, further comprising:

dividing the data object into the cells with each such cell having a closed shape and sharing a common edge with at least one other such cell in the data object.

12. A method according to claim 8, further comprising:

allocating the level set array block with a set of the elements at least equal to the number of the cells in the data object.

13. A method according to claim 8, wherein the data object comprises a structured polygon logically divided by regularly-spaced cells.

14. A method according to claim 8, wherein the data object comprises an unstructured polygon logically divided by irregularly-spaced cells.

15. A computer-readable storage medium holding instructions that when executed by a computer cause the computer to perform a method for determining a cache optimized ordering of cells in an unstructured graph, comprising:

identifying cells laying on a specified portion of a boundary of a logically-defined grid for a stored unstructured graph;

adding each identified cell in order of traversal along the specified portion of the boundary into an element of a provisional level set array block;

inserting one or more further cells between each sequential pair of cells, which are not contiguously-located in the logically-defined grid, into an element of the provisional level set array block, each further cell being located contiguous to at least one of the sequential pair of cells in the logically-defined grid; and

iteratively identifying, adding and inserting each cell remaining in the logically-defined grid.

16. A computer-readable storage medium according to claim 15, wherein the data object comprises a shape having two dimensions.

17. A computer-readable storage medium according to claim 15, wherein the data object comprises a shape having more than two dimensions, further comprising:

finding each such additional cell in the data object that is contiguous in each dimension to the at least one such cell added previously to the level set array block.

18. A computer-readable storage medium according to claim 15, further comprising:

dividing the data object into the cells with each such cell having a closed shape and sharing a common edge with at least one other such cell in the data object.

19. A computer-readable storage medium according to claim 15, further comprising:

allocating the level set array block with a set of the elements at least equal to the number of the cells in the data object.

20. A computer-readable storage medium according to claim 15, wherein the data object comprises a structured polygon logically divided by regularly-spaced cells.

21. A computer-readable storage medium according to claim 15, wherein the data object comprises an unstructured polygon logically divided by irregularly-spaced cells.

22. An apparatus for determining a cache optimized ordering of cells in an unstructured graph, comprising:

means for identifying cells laying on a specified portion of a boundary of a logically-defined grid for a stored unstructured graph;

means for adding each identified cell in order of traversal along the specified portion of the boundary into an element of a provisional level set array block;

means for inserting one or more further cells between each sequential pair of cells, which are not contiguously-located in the logically-defined grid, into an element of the provisional level set array block, each further cell being located contiguous to at least one of the sequential pair of cells in the logically-defined grid; and

means for iteratively identifying, adding and inserting each cell remaining in the logically-defined grid.