Methods, apparatus, and articles of manufacture to reorder N-dimensional sparse data into groups of data elements that can be collocated in a memory

Exemplary embodiments maintain spatial locality of the data being processed by a sparse CNN. The spatial locality is maintained by reordering the data to preserve spatial locality. The reordering may be performed on data elements and on data for groups of co-located data elements referred to herein as “chunks”. Thus, the data may be reordered into chunks, where each chunk contains data for spatially co-located data elements, and in addition, chunks may be organized so that spatially located chunks are together. The use of chunks helps to reduce the need to re-fetch data during processing. Chunk sizes may be chosen based on the memory constraints of the processing logic (e.g., cache sizes).

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a U.S. patent application claiming the benefit of and priority to Indian Patent Application No. 202041018794, filed May 2, 2020, which is hereby incorporated by reference in its entirety.

TECHNICAL FIELD

The present application relates to data processing and more particularly to sparse neural network data processing.

BACKGROUND

Convolutional Neural Networks (CNNs) commonly are used in applications like image processing and speech processing. CNNs may be used with data of different dimensionality. As the dimensions of the data increase, the computational requirements placed on the CNN become greater. Sometimes the computational burden becomes too intensive and time-consuming for the hardware for executing the CNN, given the real time constraints that may be imposed by underlying applications (e.g., autonomous applications). Sparse CNNs are used with some data to help ease the computational burden. With sparse CNNs not all of the input voxels in an input point cloud are occupied. Hence only the occupied voxels in the input data need to be processed.

DETAILED DESCRIPTION

One of the difficulties with N-dimensional (where N is a positive integer) sparse CNNs relates to the loss of spatial locality of data when certain operations are performed. Operations require spatial locality in the data for faster computation of operations. The sparse nature of sparse N-dimensional data inherently causes loss of spatial locality since only active voxels are stored. The data must be loaded into memory of the processing logic (e.g., graphics processing unit (GPU), hardware accelerator, central processing unit (CPU), etc.) to perform the operations, like convolution. The processing logic typically is bound by constrained memory sizes, and hence need to optimize dataflows (tile-size/loop-order) for efficient and fast execution. An N-dimensional convolution operation of kernel size k (k>1) requires participation of voxels in the k-neighborhood. To optimize for spatial reuse, ordering of the elements becomes critical to contain data transfers. If the data loaded into memory is not for spatially co-located voxels, the processing logic has to load the data for spatially co-located voxels into the memory. For example, the data must be fetched from off chip or may need to be fetched from a slower memory level. The fetching of the data that has not been loaded into the memory may be time-consuming and slow down overall performance by the sparse CNN.

Exemplary embodiments may address this problem by maintaining spatial locality of the data being processed by a sparse CNN. The spatial locality is maintained by reordering the data to preserve spatial locality. The reordering may be performed on data elements and on data for groups of co-located data elements referred to herein as “chunks”. Thus, the data may be reordered into chunks, where each chunk contains data for spatially co-located data elements, and in addition, chunks may be organized so that spatially located chunks are together. The use of chunks helps to reduce the need to re-fetch data during processing. Chunk sizes may be chosen based on the memory constraints of the processing logic (e.g., cache sizes). Moreover, the reordering of the chunks helps to reduce the need for re-fetching across chunks. For example, if a cache will hold two chunks, two chunks that are spatially co-located may be loaded into the cache to reduce the need for re-fetching for the cache. The chunk size may also be selected to account for the constraints across a memory hierarchy (e.g., L1cache size, L2cache size and L3cache size).

The exemplary embodiments may adjust for changes in resolution in layers of the CNN on a per layer basis so that a wholesale reordering of data is not required.

Unlike conventional approaches like raster scanning to inputting point cloud data for processing by a sparse CNN, the approach of the exemplary embodiments is agnostic to orientation. The spatial re-ordering of the data in the exemplary embodiments works equally well with different orientations. provides equal weightage to all neighbors in each of the NDdirections, thus being invariant to the surface orientation.

FIG.1depicts a high-level diagram100of an illustrative sparse CNN104. The sparse CNN104receives input102for processing. The input102may be viewed as a sparse point cloud of data elements. Data such as images and voice data may lend themselves to this type of representation. For illustrative purposes herein the discussion will focus on the case where the data elements are voxels. Each voxel is associated with a point in a point cloud space, and there are features or channels associated with each voxel. The data elements, however, may have different dimensionality. As such, the input102data may be of different dimensions. For example, the input may be for a two-dimensional image, and thus, there is color data for each pixel in the image. For sparse data, data elements in the input104have associated coordinates, but not all of the data elements in the input104are occupied (i.e., have data to be processed). The input102is processed by the sparse CNN by successive layers. An input layer I receives the input data and passes the data onto convolutional layer C1, which performs a convolution operation on the data. Convolutional layer C2is a strided convolutional layer that down samples the data. Convolutional layer C3performs a convolution operation on the down sampled data. A next layer OC performs a different type of computation on the data, such as a convolutional-like operation or other type of operation. The data may then pass through pooling layers that down sample the data. Strided convolutional layers can also be used to down sample. The sparse CNN then has an output layer O that outputs the output106. Depending on the sparse CNN, the output might, for instance, identify the likelihood that the image is a particular thing (e.g., an airplane, an arrow, etc.) or possesses a given feature. This example is not limited to object detection but instead may perform other visual artificial intelligence applications.

It should be appreciated that the sparse CNN104ofFIG.1is intended to illustrative and not limiting. The sparse CNN104may contain different layers organized in different manners than shown. For example, there may be a different number of convolutional layers, and pooling layers may be interspersed among the convolutional layers.

FIG.2depicts a high-level view of a computing environment200suitable for executing a sparse CNN, such as the sparse CNN104shown inFIG.1. The computing environment200includes the computer-executable instructions for the CNN model202. These instructions may be executed by processing logic204to perform the functionality for the sparse CNN. The processing logic204may include one or more processors206. The processors may include GPUs, CPUs, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs) and/or other varieties of processors. The processing logic204may include hardware accelerator(s)208that help to accelerate execution of the CNN model202. The accelerator(s)208may include processors such as described above, memory and other circuitry.

FIG.3depicts a block diagram300illustrating reordering of input data elements. In this case the input data is for sparse voxels302. The data for the sparse voxels302is subject to reordering304to produce a chunk306in the exemplary embodiments.FIG.4depicts an example of sparse voxels in a 4×4 grid of data. Only the elements with values (i.e., 10, 48, 17 and 100) are occupied and processed. The other elements with no values are not processed. The chunk306is then passed to the processing logic308and stored in a memory310used by the processing logic for processing.

The reordering may work with an input list of voxels Vinwhich contains voxels viHence, Vinmay be expressed as Vin=[vi], where viis dimensional location/index of the ith voxel in Vin. An occupancy map M may be defined. The occupancy map M maps a tuple of indices of each occupied voxel to the index of the voxel in then list Vin and is undefined everywhere else.
M(vi)=i∀vi∈Vin.

In order to perform the reordering, the neighbors of occupied voxels need to be determined. For a convolutional operation of kernel size k, BD(k) represents the list of zero centered offsets of a cube of size k, where D is the number of dimensions the operation is conducted in (e.g., D=2 for images but D=3 for point clouds). The neighbors of a voxel can be defined as
ND(k,vi)=[vi+b∀b∈BD(k)].

An adjacency list A may be created to encompass neighbor information for each voxel as:
A(M(vi))=[M(vj)∀vj∈ND(k,vi)].

As part of the reordering, a starting voxel must be selected. One option is to start at a corner so as to constrain the directions in which a neighbor may be found. The starting voxel may be selected as a voxel with a minimum number of neighbors. Other heuristics may also be used to select the starting voxel.

The reordering may operate on a graph. The graph G may be constructed using the adjacency list A. In the graph G, vertices are the active voxels and edges capture adjacency between neighbors. The presence of an edge indicates participation of a voxel in a convolution operation of the neighbor and vice versa. This captures colocation.

The reordering starts with the starting voxel, and the reordering conducts a breadth first search of neighbors. The data for the starting voxel and the neighbors is added to a chunk. The process is repeated until the chunk is full (i.e., has hit a memory size or other maximum size constraint)

FIG.5Adepicts a flowchart500of the steps that may be performed to realize the reordering of data for the voxels. This flowchart500will be described in conjunction with the diagram540ofFIG.5B. In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.5Ato reorder data as described herein.

There are two items502and504shown inFIG.5Athat may be stored in memory. Item502is a value that specifies a single level maximum memory size. Item504is a rule book that stores the adjacency information (see adjacency map inFIG.5B). The process begins, with finding the starting voxel as was described above (506). The starting voxel is added to a processing queue542(FIG.5B) (508), which holds the voxels that need to be processed. The next element in the processing queue542is popped (see1inFIG.5B) (510). If the starting voxel is the next voxel in the processing queue, the starting voxel is popped off. A check is then made whether the voxels in the current chunk546exceed the maximum single level memory size (512) (see5inFIG.5B). This check prevents the chunk546from exceeding a maximum size. If the chunk546were bigger than the maximum size, the chunk might not fit into a memory structure.

If the check (512) indicates that the chunk546has reached the maximum size, the chunk546is sent to be processed by the CNN (514) (see6binFIG.5B). This entails loading the chunk564into memory of the processing logic for the CNN as discussed above. The processing queue542is then cleared (516) to be ready to build a next chunk. If the entire rule book (e.g, adjacency matrix544) is processed (518), the reordering is complete. If not, the processing begins for a next chunk starting at (506) (see6ainFIG.5B).

If in (512) it is determined that the maximum size has not been reached, then a loop of operations is performed for each neighbor of the starting voxel (see6aofFIG.5B). If all the neighbors for a current voxel have been processed (522), the next element in the processing queue542is popped (510) (see1inFIG.5B) and processing repeats with (512). If in (522) not all neighbors have been examined, a check is performed whether the current neighbor has been processed (524). If the current neighbor has been processed, it is dropped from further processing (see2binFIG.5B). However, if the current neighbor has not been processed, the current neighbor is added to the current chunk546(530) (see2ainFIG.5B). The neighbors of the current neighbor are added to the processing queue (see3and4inFIG.5B), and the loop repeats for the next neighbor at (520). If at (524), the current neighbor has been processed, a check is made whether the current neighbor has been processed before in a previous chunk (526). If so, the chunk linkage is stored. This chunk linkage information is used to identify spatially co-located chunks, as will be described in more detail below. If the current neighbor was not processed before in a previous chunk, the process repeats for the next neighbor at (520).

FIG.6shows an example600of the processing of data per the approach ofFIG.5A. The process may have already processed the data for the voxels for a previous chunk604and is processing for a current chunk602. Data for voxel a is added to the current chunk followed by neighbor b. The neighbor of voxel b are c and d, which are added to the chunk. Then, voxels e and f are added as they are neighbors of voxel c and d. Voxel g is added as a neighbor of voxel e, and voxel h is added as a neighbor of voxel f. Voxel p is not added because it has already been added to the previous chunk604. In this example, 8 voxels constitute the maximum size for a chunk, and thus the current chunk is full when the voxel g is added to the chunk.

FIG.7shows an example700of chunks and chunk linkages. A chunk702containing nodes a-h has a chunk linkage at704, the edge from node c to node p. A chunk linkage706is also between nodes g and j and nodes h and i.

FIG.8Adepicts a plot800of data transfers across memory sizes for three different approaches in an experiment that was performed on a point cloud for an airplane from the ShapeNet database. Curve802reflects the data transfers across memory sizes for the approach described herein of reordering for a single level of memory. Curve804reflects the data transfers across memory sizes where the data is ordered by raster scanning, and curve806reflects the memory transfers across memory sizes where the data is unordered. As can be seen, the reordering described herein aided in reducing data transfers across memory sizes.FIG.8Bshows a plot820of the speed up of this reordering approach relative to the raster scanning approach (see curve822) and the unordered data approach (see curve824) for ShapeNet data sets. This plot820shows that by exploiting spatial co-location, the exemplary embodiments may reduce memory transfer and produce a speed up in processing.

As was mentioned above, there are a number of reordering options with the exemplary embodiments.FIG.9shows a flowchart900for a first option. In this first option, reordering is performed only for the voxels (902).FIG.10shows a flowchart1000for a second option for reordering. In this second option, the reordering is performed on the voxel basis to yield chunks (1002). Then, the chunks are subject to reordering as well (1004). The reordering of chunks is helpful when there is a memory hierarchy and one wishes to have spatially collocated chunks in a memory level. This reduces the need for memory fetches from the respective memory levels.

In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.9orFIG.10to select reordering options as described herein.

FIG.11depicts an example of a system1100having a memory hierarchy. The system1100includes a package1102, such as integrated circuit, that contain processing logic1104is for executing the sparse CNN. The processing logic1104may take the form like that discussed above for the processing logic204ofFIG.2. The processing logic has access to several levels of memory. The levels of memory range from registers1106, an L1cache1108, an L2cache1110, an L3cache1102and main memory1104. Each successive level of memory is larger and slower. Thus, the registers1106are fastest but smallest, whereas the main memory is slowest but largest. One of the aims of the reordering may be to avoid the need for fetching off a given memory level that is being used.

FIG.12depicts a flowchart of the steps that may be performed to reorder the chunks. In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.12to reorder chunks as described herein. The depicted steps see to hierarchically group the chunks at each memory level to provide spatial locality and to have reuse. The process uses three inputs1202,1204and1206, shown in FIG.12. The list of chunk linkages1202and the chunks list1204resulting from the voxel reordering are used. The memory sizes of the respective memory levels1206is also used.

For each memory interface (i.e., each level of memory) (1208), a process is performed. Initially, a check is made whether all levels have been processed (1210). If so, the process is complete. If not, then the memory size for the current memory level is compared to the size of the memory level for the previous memory level to generate a ratio to know how many chunks fit into the current memory level (1212). Next, the reordering approach ofFIG.5is applied (1214) to the chunks of the previous level rather than the voxels with the chunk linkages serving as the adjacency information. The result is a grouped chunk list for the memory level along with chunk linkages (1216). The process is then repeated for the next memory level until all memory levels are processed. The resulting grouped chunk lists for each memory level (1218) may be used in loading chunks into the respective memory levels.

Consider the example of a memory hierarchy like that shown inFIG.11. The chunk size may be fixed to be the size of the registers1106. Suppose that the L1cache1108is 4 times the size of the registers1106. The chunks would be reordered to attempt to group the chunks by groups of 4 spatially co-located chunks. Then, the same process is repeated for the L2cache1110, the L3cache1112and the main memory1114if desired.

FIG.13shows an example of such chunk reordering. The chunks1302as subject to reordering1304to produce reordered chunks that are grouped for the respective memory levels. Hence, chunk1318is stored in memory1316, and grouped spatially co-located chunks1308and1310are stored in memory1312for use by the processing logic1314. The grouped chunk list for the memory1312groups chunks1308and1310. The grouped chunk lists may be used by each level to figure out what chunks to load together based on the memory size for the level.

FIG.14Adepicts the results of applying the approach of reordering both the voxels into chunks and the chunks into spatially located groups for multiple memory levels to the airplane data set from ShapeNet. As can be seen from the plot1400ofFIG.14A, the curve1402depicts the memory transfers where the reordering approach described herein is performed once for voxels (designated as T1herein). Curve1406depicts the memory transfers where the reordering approach described herein is applied for voxels for level L0and level L1separately (designated as T2herein), and curve1404depicts the memory transfers for the approach described herein for reordering of voxels at a first level and subsequent reordering of chunks for subsequent levels as described herein (designated as T3herein).

The reordering strategy (T1) of curve1402does not incur overheads for processing for multiple memory-levels, but also compromises on data transfers, while the strategy (T2) of curve1406entails the costly task of repeating the reordering of voxels for every memory level, resulting in high performance. The approach (T2) of curve1406, however, largely is not feasible, as it would result in two incoherent/different point clouds at each level of the hierarchy. The reason for the approach (T2) of curve1406being the lowest in data transfers is because the reordering of voxels done specially for that level would be the most optimal one for that level, but this ordering may be inconsistent when looked in the purview of all of the memory levels, and hence this approach is not feasible in practice either. By inconsistent, it is meant that since the ordering of various levels are done differently in the approach (T2) of curve1406, the overall functioning may not cohere.

FIG.14Bdepicts a plot of the speed up resulting from the decreased memory transfers relative to the approach (T2) of applying the reordering of voxels for each level relative to the approach (T1) of applying the reordering of voxels for only a first level (curve1412) and the approach (T2) of applying the reordering of voxels for each level relative to the approach (T3) of applying reordering of voxels for a first level and applying reordering of chunks for all subsequent levels (curve1414).

Given that the approach T2is not feasible and the approach T1has higher data transfers, the approach T3may be a good compromise that provides improved performance while being feasible.

The reordering of the exemplary embodiments may be applied to a single level, such as to an input of a convolutional layer.FIG.15depicts a flowchart1500where the reordering is applied to a single layer of the sparse CNN (1502). In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.15to reorder a single layer of a CNN as described herein. The reordering may be applied to the input sparse data for the first convolutional layer or for another layer. Alternatively, as depicted in the flowchart1600ofFIG.16, the reordering may be applied to multiple layers. In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.16to reorder multiple layers of a CNN as described herein. As is shown inFIG.16, the data is obtained for a next level to be reordered (1602). The reordering is applied such as has been described above (1604). If this is the last level for the reordering to be applied (1606), the reordering is done. Otherwise, the process repeats with the next level to be reordered at (1602).

An extension may be provided for preserve the spatial reordering as resolution changes along the layers of the sparse CNN. With resolution changes there is a possibility of degeneracy wherein an input voxel may degenerate into multiple output voxels. For example, a strided convolution of stride2over an input data map, depending upon where a voxel index lies, the active voxel may contribute to a varying number of outputs. If any of the voxel indices are odd, they will have a degeneracy of two and contribute to two outputs. For three-dimensional data, the input voxel may contribute to 1, 2, 4 or 8 outputs. The extension incrementally reorders the input spatial order and computes the possibility of degeneracy due to the change in resolution. Then, the extension serially pushes unique output voxels into a list.

FIG.17shows a flowchart1700for the extension with three-dimensional data. The input is reordered input voxels (1702). In some examples, processing logic204(e.g., processor(s)206, accelerator(s)208, or the like) may execute instructions (such as CNN model202, or CNN execution instructions, or the like) to implement operations described with respect toFIG.17to reorder three-dimensional data. The process iterates over every voxel v (1704). The process checks if all voxels have been processed (1706). If so, the process is complete. If not, the process checks whether the v.x (i.e., the x coordinate of v) is odd (1708). If so, the output values of x have two possible values and a flag_x is set as true (1710). Otherwise, v.x is even, and the output voxels have one possible value, and the flag_x is set as false (1712). Checks of whether v.y is odd (1713) and whether v.z is odd (1715) are made. If v.y is odd, there are two possible output values and a flag_y is set as true (1714); otherwise, there is one possible output value and a flag_y is set as false (1716). Similarly, if v.z is odd, there is one possible output value and a flag_z is set as true (1718); otherwise there is one possible output value and flag_z is set as false (1720). In steps (1722), (1726), (1730) and (1734), a check is made whether all the flags are true, two of the flags are true, one of the flags are true or if none of flags are true, respectively. If all three flags are true, 8 output voxels are computed (1724). If two flags are true, 4 output voxels are computed (1728), if one flag is set, two output voxels are computed (1732) and if no flags are set, 1 output voxel is calculated (1736).

The extension then iterates over candidate output voxels (1738) and checks whether all candidate output voxels have been processed (1740). If not, the next input voxel is processed starting at (1704). If so, a check is made whether the candidate output voxel has been processed before (1742). If so, no further processing is needed. If not, the candidate output voxel is pushed into the output voxel list (1744). The result of the process is reordered output voxels (1746).

FIG.18Adepicts a computing environment1800suitable for performing the reordering. The computing environment includes processing logic1802. The processing logic1802may include one or more GPUs, FPGAs, CPUs, processing clusters, etc. The processing logic1802has access to computer-readable storage1804. The computer-readable storage1804may include instructions for execution by the processing logic1802.FIG.18Bshows illustrative items stored in the computer-readable storage1804may include instructions for performing the reordering of voxels1806and instructions for performing the reordering of chunks1808. The data held in the computer-readable storage may include Vin1810, the rule book1812and chunk list(s)1814. The data may also include the occupancy map MO1816, the processing queue1818, chunk linkages1820and the processed before lists1822. Other components may be included in the computing environment1800.

A data processing system suitable for storing and/or executing program code will include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code must be retrieved from bulk storage during execution. The term “code” covers a broad range of software components and constructs, including applications, drivers, processes, routines, methods, modules, firmware, microcode, and subprograms. Thus, the term “code” may be used to refer to any collection of instructions which, when executed by a processing system, perform a desired operation or operations.

Logic circuitry, devices, and interfaces herein described may perform functions implemented in hardware and implemented with code executed on one or more processors. Logic circuitry refers to the hardware or the hardware and code that implements one or more logical functions. Circuitry is hardware and may refer to one or more circuits. Each circuit may perform a particular function. A circuit of the circuitry may comprise discrete electrical components interconnected with one or more conductors, an integrated circuit, a chip package, a chip set, memory, or the like. Integrated circuits include circuits created on a substrate such as a silicon wafer and may comprise components. And integrated circuits, processor packages, chip packages, and chipsets may comprise one or more processors.

Processors may receive signals such as instructions and/or data at the input(s) and process the signals to generate the at least one output. While executing code, the code changes the physical states and characteristics of transistors that make up a processor pipeline. The physical states of the transistors translate into logical bits of ones and zeros stored in registers within the processor. The processor can transfer the physical states of the transistors into registers and transfer the physical states of the transistors to another storage medium.

A processor may comprise circuits to perform one or more sub-functions implemented to perform the overall function of the processor. One example of a processor is a state machine or an application-specific integrated circuit (ASIC) that includes at least one input and at least one output. A state machine may manipulate the at least one input to generate the at least one output by performing a predetermined series of serial and/or parallel manipulations or transformations on the at least one input.

An apparatus, comprising: processing logic and memory coupled to the processing logic, the memory for storing instructions that when executed by the processing logic cause the processing logic to: reorder N-dimensional sparse convolutional neural network data for data elements into a chunk of data for spatially collocated data elements, where N is a positive integer and wherein the reordering comprises: identifying occupied neighbors of an occupied data elements in the data elements, and identifying adjacencies among the identified neighbors; and forward the chunk for convolutional neural network processing.

The apparatus of claim1, wherein the instructions for the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprise instructions for using the identified adjacencies to identify a starting data element, putting the starting data element in a processing queue and adding data for the starting element to the chunk.

The apparatus of claim1, wherein the instructions for the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprise instructions for identifying ones of the identified occupied neighbors that are adjacent to the starting data element using the identified adjacencies and adding the identified occupied neighbors that are adjacent to the processing queue.

The apparatus of claim3, wherein the instructions for the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprise instructions for popping data elements from the processing queue and adding the popped data elements to the chunk if the data elements have not been added to the chunk yet.

The apparatus of claim4, wherein the instructions for the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprise instructions for continuing to add data elements that are adjacent to data elements that have already been added to the chunk until a maximum size for the chunk is reached by repeating in sequence: identifying ones of the identified occupied neighbors that are adjacent to the starting data element using the identified adjacencies and adding the identified occupied neighbors that are adjacent to the processing queue and one by one popping data elements from the processing queue and adding the data elements to the chunk if they have not been added to the chunk or another chunk.

The apparatus of claim5, wherein the starting data element is one of the data elements with a fewest number of adjacencies and wherein when the maximum size for the chunk is reached, starting data element for a next chunk is chosen from among data elements in the processing queue that has a fewest adjacencies.

The apparatus of claim6, wherein the maximum size for the chunk is based on a size of a memory.

The apparatus of claim1, wherein the memory further stores instructions that when executed by the processing logic cause the processing logic to: create a graphical representation of occupied data elements where each node of the graphical representation represents an occupied one of the data elements and each edge represents an adjacency of data elements represented by ones of the nodes that the edge connects.

The apparatus of claim8, wherein identifying ones of the identified occupied neighbors proceeds in a breadth first fashion of the graphical representation beginning with the starting data element.

The apparatus of claim1, wherein the convolutional neural network processing is a convolutional operation.

The apparatus of claim1, wherein the memory additionally stores instructions that when executed by the processing logic cause the processing logic to reorder N-dimensional sparse convolutional neural network data for additional data elements into additional chunks of data for spatially co-located data elements and reorder the chunks by spatial locality.

The apparatus of claim11, wherein the reordering of the chunks groups the chunks into groups for a memory level and a size of the groups is dictated by a memory size of the memory level.

A method performed by a processor, comprising: reordering N-dimensional sparse convolutional neural network data for data elements into a chunk of data for spatially co-located data elements, where N is a positive integer and wherein the reordering comprises: identifying occupied neighbors of an occupied data elements in the data elements, and identifying adjacencies among the identified neighbors; and forwarding the chunk for convolutional neural network processing.

The method of claim13, further comprising maintaining a processing queue that has entries for the occupied data elements.

The method of claim14, wherein the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprises using the identified adjacencies to identify a starting data element, putting the starting data element in the processing queue and adding data for the starting data element to the chunk.

The method of claim15, wherein the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprises identifying ones of the identified occupied neighbors that are adjacent to the starting data element using the identified adjacencies and adding the identified occupied neighbors that are adjacent to the processing queue.

The method of claim16, wherein the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprise popping data elements from the processing queue and adding the popped data elements to the chunk if the data elements have not been added to the processing queue yet.

The method of claim17, wherein the reordering the N-dimensional sparse convolutional neural network data for the data elements further comprises continuing to add data elements that are adjacent to data elements that have already been added to the chunk until a maximum size for the chunk is reached by repeating in sequence: identifying ones of the identified occupied neighbors that are adjacent to the starting data element using the identified adjacencies and adding the identified occupied neighbors that are adjacent to the processing queue and one by one popping data elements from the processing queue and adding the data elements to the chunk if they have not been added to the chunk or another chunk.

The method of claim18, wherein the starting data element is one of the data elements with a fewest number of adjacencies and wherein the method further comprises, when the maximum size is reached for the chunk, starting data element for a next chunk is chosen from among data elements in the processing queue that has a fewest adjacencies.

The method of claim18, further comprising creating a graphical representation of occupied data elements where each node of the graphical representation represents an occupied one of the data elements and each edge represents an adjacency of data elements represented by ones of the nodes that the edge connects.

The method of claim20, wherein identifying ones of the identified occupied neighbors proceeds in a breadth first fashion of the graphical representation beginning the starting data element.

The method of claim18, further comprising: reordering N-dimensional sparse convolutional neural network data for additional data elements into additional chunks of data for spatially co-located data elements; and reordering the additional chunks of data for spatial locality.

The method of claim22, wherein the reordering of the chunks groups the chunks into groups for a memory level and a size of the groups is dictated by a memory size of the memory level.

The method of claim13, wherein the data elements are voxels.

A non-transitory computer-readable storage medium comprising instructions that when executed by processing logic, cause the computing device to: reorder N-dimensional sparse convolutional neural network data for data elements into a chunk of data for spatially co-located data elements, where N is a positive integer and wherein the reordering comprises: identifying occupied neighbors of an occupied data elements in the data elements, and identifying adjacencies among the identified neighbors; and forward the chunk for convolutional neural network processing.