System and method for determining a cache optimized ordering of cells in an unstructured graph
First Claim
1. A system for determining a cache optimized ordering of cells in an unstructured graph, wherein the unstructured graph is a computer-generated file that is loaded from storage into memory, the system comprising:
- a bounding module identifying cells laying on a specified portion of a boundary of a logically-defined grid for the unstructured graph, wherein the unstructured graph comprises a shape having more than two dimensions;
a reordering module adding each identified cell along the specified portion of the boundary into an element of a provisional level set array block, inserting one or more further cells that lie between each non-contiguous pair of cells in the logically-defined grid into an element of the provisional level set array block, wherein each further cell is contiguous in the logically defined grid to at least one of the cells in the provisional level set array block, and ordering the cells in the provisional level set array block such that traversal through the provisional array results in a traversal through contiguous cells in the logically defined grid for the unstructured graph;
a searching module finding each additional cell in the unstructured graph that is contiguous in each dimension to the at least one cell added previously to the level set array block; and
an iteration module repeating the steps of identifying, adding, inserting, and ordering each cell remaining in the logically-defined grid into the provisional level set array block, wherein, upon termination of the iteration, the provisional level set array is a computer-generated file such that the order specified by the provisional level set array block for accessing the cells in the unstructured graph is a regular cell ordering, wherein the ordering ensures increased spatial and temporal data locality resulting in cache-friendly run-time behavior that increases program performance.
2 Assignments
0 Petitions
Accused Products
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.
14 Citations
19 Claims
-
1. A system for determining a cache optimized ordering of cells in an unstructured graph, wherein the unstructured graph is a computer-generated file that is loaded from storage into memory, the system comprising:
-
a bounding module identifying cells laying on a specified portion of a boundary of a logically-defined grid for the unstructured graph, wherein the unstructured graph comprises a shape having more than two dimensions; a reordering module adding each identified cell along the specified portion of the boundary into an element of a provisional level set array block, inserting one or more further cells that lie between each non-contiguous pair of cells in the logically-defined grid into an element of the provisional level set array block, wherein each further cell is contiguous in the logically defined grid to at least one of the cells in the provisional level set array block, and ordering the cells in the provisional level set array block such that traversal through the provisional array results in a traversal through contiguous cells in the logically defined grid for the unstructured graph; a searching module finding each additional cell in the unstructured graph that is contiguous in each dimension to the at least one cell added previously to the level set array block; and an iteration module repeating the steps of identifying, adding, inserting, and ordering each cell remaining in the logically-defined grid into the provisional level set array block, wherein, upon termination of the iteration, the provisional level set array is a computer-generated file such that the order specified by the provisional level set array block for accessing the cells in the unstructured graph is a regular cell ordering, wherein the ordering ensures increased spatial and temporal data locality resulting in cache-friendly run-time behavior that increases program performance. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for determining a cache optimized ordering of cells in an unstructured graph, wherein the unstructured graph is a computer-generated file that is loaded from storage into memory, the method comprising:
-
identifying cells laying on a specified portion of a boundary of a logically-defined grid for the unstructured graph, wherein the unstructured graph comprises a shape having more than two dimensions; adding each identified cell along the specified portion of the boundary into an element of a provisional level set array block; inserting one or more further cells that lie between each non-contiguous pair of cells in the logically-defined grid into an element of the provisional level set array block, wherein each further cell is contiguous in the logically defined grid to at least one of the cells in the provisional level set array block; ordering the cells in the provisional level set array block such that traversal through the provisional array results in a traversal through contiguous cells in the logically defined grid for the unstructured graph; finding each additional cell in the unstructured graph that is contiguous in each dimension to the at least one cell added previously to the level set array block; and repeating the steps of identifying, adding, inserting, and ordering each cell remaining in the logically-defined grid into the provisional level set array block, wherein, upon termination of the iteration, the provisional level set array is a computer-generated file such that the order for accessing the cells in the unstructured graph is a regular cell ordering, wherein the ordering ensures increased spatial and temporal data locality resulting in cache-friendly run-time behavior that increases program performance. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. 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, wherein the unstructured graph is a computer-generated file that is loaded from storage into memory, wherein the computer-readable storage medium includes one of a volatile memory, a non-volatile memory, a disk drive, a magnetic tape, a compact disc, a digital versatile disk, and a digital video disk, the method comprising:
-
identifying cells laying on a specified portion of a boundary of a logically-defined grid for the unstructured graph, wherein the unstructured graph comprises a shape having more than two dimensions; adding each identified cell along the specified portion of the boundary into an element of a provisional level set array block; inserting one or more further cells that lie between each non-contiguous pair of cells in the logically-defined grid into an element of the provisional level set array block, wherein each further cell is contiguous in the logically defined grid to at least one of the cells in the provisional level set array block; ordering the cells in the provisional level set array block such that traversal through the provisional array results in a traversal through contiguous cells in the logically defined grid for the unstructured graph; finding each additional cell in the unstructured graph that is contiguous in each dimension to the at least one cell added previously to the level set array block; and repeating the steps of identifying, adding, inserting, and ordering each cell remaining in the logically-defined grid into the provisional level set array block, wherein, upon termination of the iteration, the provisional level set array is a computer-generated file such that the order for accessing the cells in the unstructured graph is a regular cell ordering, wherein the ordering ensures increased spatial and temporal data locality resulting in cache-friendly run-time behavior that increases program performance. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. An apparatus for determining a cache optimized ordering of cells in an unstructured graph, wherein the unstructured graph is a computer-generated file that is loaded from storage into memory, the apparatus comprising:
-
means for identifying cells laying on a specified portion of a boundary of a logically-defined grid for the unstructured graph, wherein the unstructured graph comprises a shape having more than two dimensions; means for adding each identified cell 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 that lie between each non-contiguous pair of cells in the logically-defined grid into an element of the provisional level set array block, wherein each further cell is contiguous in the logically defined grid to at least one of the cells in the provisional level set array block; means for ordering the cells in the provisional level set array block such that traversal through the provisional array results in a traversal through contiguous cells in the logically defined grid for the unstructured graph; means for finding each additional cell in the unstructured graph that is contiguous in each dimension to the at least one cell added previously to the level set array block; and means for repeating the steps of identifying, adding, inserting and ordering each cell remaining in the logically-defined grid into the provisional level set array block, wherein, upon termination of the iteration, the provisional level set array is a computer-generated file such that the order for accessing the cells in the unstructured graph is a regular cell ordering, wherein the ordering ensures increased spatial and temporal data locally resulting in cache-friendly run-time behavior that increases program performance.
-
Specification