Back to results
US 12,217,331 B2Granted
Optimizing grid-based compute graphs
AssigneeNVIDIA Corporation
InventorShekhar Dwivedi
Life of this patent
Estimating the term…
Abstract
Disclosed are apparatuses, systems, and techniques that enable compressed grid-based graph representations for efficient implementations of graph-mapped computing applications. The techniques include but are not limited to selecting a reference grid having a plurality of blocks, assigning nodes of the graph to blocks of the grid, and generating a graph representation that maps directions, relative to the reference grid, of nodal connections of the graph.
Claims22
A method comprising:
- obtaining, using a first memory device, a first representation of a graph, wherein the graph maps a plurality of entities associated with a computing program, and wherein the first representation identifies a plurality of nodes of the graph and a plurality of nodal connections of the graph;
- selecting, using a processing device and based at least on the first representation, a reference grid (RG);
- generating, using the processing device, a second representation of the graph, the second representation comprising, for each block of at least a subset of a plurality of blocks of the RG, presence or absence of the nodal connections, along each of a plurality of RG directions, of one or more nodes of the plurality of nodes of the graph, wherein the one or more nodes are assigned to a respective block;
- and
- performing, using the second representation, one or more operations of the computing program.
2 more elements
A system comprising:
- a memory device;
- and
- one or more processing devices, communicatively coupled to the memory device, to:
- obtain, using the memory device, a first representation of a graph, wherein the graph maps a plurality of entities associated with a computing program, and wherein the first representation identifies a plurality of nodes of the graph and a plurality of nodal connections of the graph;
- select, using the first representation, a reference grid (RG);
- generate a second representation of the graph, the second representation comprising, for each block of at least a subset of a plurality of blocks of the RG, presence or absence of the nodal connections, along each of a plurality of RG directions, of one or more nodes of the plurality of nodes of the graph, wherein the one or more nodes are assigned to a respective block;
- and
- perform, using the second representation, one or more operations of the computing program.
5 more elements
A processor comprising:
- one or more processing units to:
- obtain a first representation of a graph, wherein the graph maps a plurality of entities associated with a computing program, and wherein the first representation identifies a plurality of nodes of the graph and a plurality of nodal connections of the graph;
- select, using the first representation, a reference grid (RG);
- generate a second representation of the graph, the second representation comprising, for each block of at least a subset of a plurality of blocks of the RG, presence or absence of the nodal connections, along each of a plurality of RG directions, of one or more nodes of the plurality of nodes of the graph, wherein the one or more nodes are assigned to a respective block;
- and
- perform, using the second representation, one or more operations of the computing program.
3 more elements
Dependencies are inferred from the claim text.