Patent Description:
Graphs, particularly unstructured graphs, may be difficult for a machine to process. For example, comparing two graphs to determine if they are similar may be difficult to perform programmatically. Nodes and edges may be labeled differently, presented in varying orders, and assigned different weights (but in proportion), which may result in two similar graphs appearing different.

A need remains to extract features from a graph for later use.

<NPL> discloses a High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks.

<NPL>, discloses an Accelerator for Compressed-sparse Convolutional Neural Networks <NPL>, discloses an automation framework for generating customized accelerators on FPGA platforms for various GNN models and workloads. <NPL>, discloses an Autotuning-Workload-Rebalancing GCN to accelerate GCN inference.

The invention is set out in independent claims <NUM> and <NUM>.

Preferred aspects of the invention are set out in the dependent claims.

The drawings described below are examples of how embodiments of the disclosure may be implemented, and are not intended to limit embodiments of the disclosure. Individual embodiments of the disclosure may include elements not shown in particular figures and/or may omit elements shown in particular figures. The drawings are intended to provide illustration and may not be to scale.

Reference will now be made in detail to embodiments of the disclosure, examples of which are illustrated in the accompanying drawings. In the following detailed description, numerous specific details are set forth to enable a thorough understanding of the disclosure. It should be understood, however, that persons having ordinary skill in the art may practice the disclosure without these specific details.

For example, a first module could be termed a second module, and, similarly, a second module could be termed a first module, without departing from the scope of the disclosure.

The terminology used in the description of the disclosure herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the disclosure. As used in the description of the disclosure and the appended claims, the singular forms "a", "an", and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. The components and features of the drawings are not necessarily drawn to scale.

One way to extract information from a graph that may be used to compare graphs or otherwise use graphs is called Graph Convolutional Networks (GCN). GCN involves extracting features from the graph by aggregating elements, performing a feature transformation on the aggregated elements, then performing activation to produce features. This process may be performed two or more times to extract the desired features.

Embodiments of the disclosure use an accelerator to implement GCN. A multiplication module performs multiplication of elements in parallel, and an accumulate and aggregate (ACG) module performs feature extraction from the data provided by the multiplication module. Multiple multiplication modules and ACG models are used to implement more than one layer, as desired.

The multiplication module may include an arbiter to select elements to be processed and a single instruction, multiple data processing element (SIMD PE) to perform the processing. The arbiter may determine whether a particular element may attempt to read a value that has not yet been written (which may be termed a data dependency) and may insert a bubble to delay the operation on that element.

The ACG module may include SIMD PEs to execute the accumulate and aggregate operations based on the data provided by the multiplication module. The ACG module may also include a rectified linear unit (ReLU) to perform activation: that is, to isolate only the positive values (and replace negative values with zeroes). The ACG module may also include a pruner to remove any zero values in the data (which may be either returned from the accelerator or provided to the multiplication module in the next layer).

The accelerator includes a pre-fetcher. The pre-fetcher retrieves data for the graph from memory and buffer the data in the accelerator. This process may reduce the execution time by minimizing the number of accesses to the memory. The pre-fetcher may also pre-fetch the data in a manner that may improve performance. For example, when performing matrix multiplication A × B for matrices A and B, the values in a column of matrix A may be pair-wise multiplied with a row of matrix B, after which the pair-wise products may be summed. Thus, pre-fetcher may retrieve data in a particular order (retrieving matrix A in column order and matrix B in row order).

Finally, a pre-processor performs pre-processing on the data. This pre-processing includes removing any zeroes (similar to the operation of the pruner). This pre-processing may also involve re-ordering the data to help address possible data dependencies by attempting to ensure that different operations that may involve the same element are performed in different cycles, which may factor in the latency of processing elements.

<FIG> shows a machine including an accelerator to extract features from a graph, according to embodiments of the disclosure. In <FIG>, machine <NUM>, which may also be termed a host or a system, may include processor <NUM>, memory <NUM>, and storage device <NUM>. Processor <NUM> may be any variety of processor. (Processor <NUM>, along with the other components discussed below, are shown outside the machine for ease of illustration: embodiments of the disclosure may include these components within the machine. ) While <FIG> shows a single processor <NUM>, machine <NUM> may include any number of processors, each of which may be single core or multicore processors, each of which may implement a Reduced Instruction Set Computer (RISC) architecture or a Complex Instruction Set Computer (CISC) architecture (among other possibilities), and may be mixed in any desired combination.

Processor <NUM> may be coupled to memory <NUM>. Memory <NUM> may be any variety of memory, such as flash memory, Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), Persistent Random Access Memory, Ferroelectric Random Access Memory (FRAM), or Non-Volatile Random Access Memory (NVRAM), such as Magnetoresistive Random Access Memory (MRAM) etc. Memory <NUM> may also be any desired combination of different memory types, and may be managed by memory controller <NUM>. Memory <NUM> may be used to store data that may be termed "short-term": that is, data not expected to be stored for extended periods of time. Examples of short-term data may include temporary files, data being used locally by applications (which may have been copied from other storage locations), and the like.

Processor <NUM> and memory <NUM> may also support an operating system under which various applications may be running. These applications may issue requests (which may also be termed commands) to read data from or write data to either memory <NUM>. When storage device <NUM> is used to support applications reading or writing data via some sort of file system, storage device <NUM> may be accessed using device driver <NUM>. While <FIG> shows one storage device <NUM>, there may be any number (one or more) of storage devices in machine <NUM>.

While <FIG> uses the generic term "storage device", embodiments of the disclosure may include any storage device formats that may benefit from the use of computational storage units, examples of which may include hard disk drives and Solid State Drives (SSDs). Any reference to "SSD" below should be understood to include such other embodiments of the disclosure.

Machine <NUM> may also include accelerator <NUM> (which may also be termed a device). As discussed below, accelerator <NUM> may support feature extraction from graphs (which may be stored in memory <NUM> or storage device <NUM>, or on another machine accessed across a network (not shown in <FIG>). Accelerator <NUM> is shown as communicating with memory <NUM>, but if the graph is stored somewhere other than memory <NUM>, accelerator <NUM> may communicate with the other storage location (such as storage device <NUM>).

Accelerator <NUM> may be implemented using any desired hardware. For example, accelerator <NUM> may be implemented using a Field Programmable Gate Array (FPGA), an Application-Specific Integrated Circuit (ASIC), a central processing unit (CPU), a graphics processing unit (GPU), a general purpose GPU (GPGPU), a Data Processing Unit (DPU), or a Tensor Processing Unit (TPU), to name a few possibilities. Accelerator <NUM> may also use a combination of these elements to implement accelerator <NUM>. Finally, accelerator <NUM> may be implemented as a computational storage unit, which may be used to support operations on storage device <NUM> (which may be beneficial if the graph is stored on storage device <NUM> rather than memory <NUM>).

Machine <NUM> may also include pre-processor <NUM>, which may be, for example, software executed by processor <NUM> or a component within accelerator <NUM>. Pre-processor <NUM> may remove zeroes from the data and re-order the data to remove data dependencies. More generally, pre-processor <NUM> may modify the data in any desired manner: for example, re-ordering the data, changing values in the data, adding values to the data, and/or removing values from the data. Pre-processor <NUM> is discussed further with reference to <FIG> below.

<FIG> shows details of machine <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, typically, machine <NUM> includes one or more processors <NUM>, which may include memory controllers <NUM> and clocks <NUM>, which may be used to coordinate the operations of the components of the machine. Processors <NUM> may also be coupled to memories <NUM>, which may include random access memory (RAM), read-only memory (ROM), or other state preserving media, as examples. Processors <NUM> may also be coupled to storage devices <NUM>, and to network connector <NUM>, which may be, for example, an Ethernet connector or a wireless connector. Processors <NUM> may also be connected to buses <NUM>, to which may be attached user interfaces <NUM> and Input/Output (I/O) interface ports that may be managed using I/O engines <NUM>, among other components.

<FIG> shows a view of the process of feature extraction from an example graph, according to embodiments of the disclosure. In <FIG>, graph <NUM> is shown. A graph like graph <NUM> may be thought of as a set of nodes and edges. Each node may be identified in some way, so as to distinguish two nodes in the graph. For example, graph <NUM> is shown as including nodes identified using numbers <NUM> through <NUM>. Although not shown in <FIG>, nodes may have weights associated with them (to indicate a cost of the node itself): the nodes in graph <NUM> are unweighted (which may be modeled as a weight of zero). Collectively, the weights may be identified as weight data.

Edges may connect nodes in the graph. For example, graph <NUM> has edges connecting nodes <NUM> and <NUM>, nodes <NUM> and <NUM>, nodes <NUM> and <NUM>, and nodes <NUM> and <NUM>. Although not shown in <FIG>, edges may also have weights associated with them (to indicate a cost of traversing the node): the edges in graph <NUM> are unweighted (which may be modeled as a weight of zero).

In graph <NUM>, the edges are undirected. That is, an edge may be traversed in either direction: for example, it does not matter if the edge connecting nodes <NUM> and <NUM> is used to traverse from node <NUM> to node <NUM>, or from node <NUM> to node <NUM>. But in some graphs, edges may be directed, meaning that the edge may be traversed only in one direction, from source to sink (or destination). A directed edge may be analogized to a one-way street, whereas an undirected edge may be analogized to a two-way street: a one-way street may be driven in only one direction, and to travel from the sink to the source may not be done backward along the directed edge.

In a city, not every pair of street intersections is connected by a street. In the same way, not every pair of nodes in a graph may have an edge connecting them. For example, in graph <NUM> there is no edge connecting nodes <NUM> and <NUM>. A path may be understood as a sequence of edges (directed or undirected, depending on the type of edges in the graph) that connects pairs of nodes in a sequence, enabling traversal from a source node to a sink node. For example, in graph <NUM> there is a path from node <NUM> to node <NUM> by traversing the edges between nodes <NUM> and <NUM>, nodes <NUM> and <NUM>, and nodes <NUM> and <NUM>, even if there is no edge connecting nodes <NUM> and <NUM> directly.

If every pair of nodes in an undirected graph include some path that connects them, then the graph may be termed a connected graph; otherwise, the graph may be termed disconnected. Graph <NUM> is an undirected graph, and as may be seen, there is a path connecting any two nodes in graph <NUM>: thus, graph <NUM> is a connected graph. For directed graphs, the terminology is slightly different: a directed graph may be termed weakly connected if there is an undirected path (that is, a sequence of edges, but ignoring the edge directions) connecting any two nodes, and may be termed strongly connected if there is a directed path (that is, a sequence of edges that considers the direction of the edges) connecting any two nodes; if there is a pair of nodes for which no directed or an undirected path connects the nodes, then the directed graph may be termed disconnected. Note that any directed graph that is strongly connected is also weakly connected: the reverse is not necessarily true. Also note that for a directed graph, the existence of a directed path from node A to node B does not necessarily mean that there exists a directed path from node B to node A, which must be checked separately to determine if the directed graph is strongly connected.

In a computer system, graphs may be represented as a list of node identifiers (which may be paired with weights, if the nodes are weighted) and a list of edges pairing the two nodes that are connected by the edge (which may also be paired with weights, if the edges are weighted). These lists may be represented using any desired data structure: for example, linked lists, arrays, tables, etc. are various data structures that may be used to store the information that represents the graph. For directed graphs, the order of the nodes may represent the direction: for example, an edge represented using the pair (A, B) may be understood to represent an edge with node A as the source node and node B as the sink node. For undirected graphs, a single pair (A, B) may be used to represent the edge, or two pairs (A, B) and (B, A) may be used so that the order of the nodes does not affect searching for an edge. Note that edges may also be represented using a two-dimensional table, with a one (or a weight) representing the presence of an edge between the associated nodes (identified by the row and column of the value), and a zero (or some other accepted value, such as an infinite (or very high) cost) may be used to represent the lack of an edge between the two associated nodes. When such a table is used, for an undirected graph, values indicating the presence of an edge may be stored twice, to represent both pairs (A, B) and (B, A): in other words, the table may be symmetric around one of the diagonals of the table. Such a table representing edges in a directed graph, on the other hand, might not be symmetric unless the graph includes every edge in each direction.

<FIG> shows a first way to represent graph <NUM> of <FIG> in a computer system, according to embodiments of the disclosure. In <FIG>, graph <NUM> of <FIG> is shown as including list <NUM> of nodes, and list <NUM> of edge pairs. Note that in list <NUM>, each edge of graph <NUM> of <FIG> is represented twice, once for each "direction" (since graph <NUM> of <FIG> is undirected). This may simplify finding a path through graph <NUM> of <FIG>: if a search through graph <NUM> of <FIG> is currently at node <NUM> and looking to reach node <NUM>, list <NUM> may be searched for an edge between nodes <NUM> and <NUM> without having to reverse their order. But if it is desirable to reduce the storage space to represent the graph, then list <NUM> of <FIG> may be used instead (but in that case, searching through graph <NUM> of <FIG> may involve searching for edges that include the current node as either the source or sink of each edge).

<FIG> shows a third way to represent graph <NUM> of <FIG> in a computer system, according to embodiments of the disclosure. In <FIG>, list <NUM> of nodes is the same as in <FIG>. But instead of storing the edges as list <NUM> of <FIG> or <NUM> of <FIG>, table <NUM> may be used. Each row and column in table <NUM> includes an identifier for each node in list <NUM>. For each pair of nodes, one node identifier may be used to select a row in table <NUM>, and the other node identifier may be used to select a column in table <NUM>. At the intersection of that row and that column, a value of one may indicate that the nodes are connected by an edge; a value of zero may indicate that the nodes are not connected. Note, as discussed above, that table <NUM> is symmetric around the main diagonal of table <NUM> (running from row one, column five to row five, column five): whatever value may be found in row i, column j may also be found in row j, column i.

Returning to <FIG>, because nodes may be assigned different identifiers in different graphs, nodes may be identified in different orders in different graphs, edges may be presented in different orders in different graphs, edges may be assigned different weights in different graphs, etc., it may be difficult to compare two graphs to determine if they are similar. For example, two graphs with the same sets of nodes and edges, but where one graph has weights assigned to the edges that are twice the value of the weights assigned to the edges in the other graph, may not appear to be similar. But multiplying the edge weights by a constant value does not change the least-cost path between two nodes: the least-cost path P in one graph is the same least-cost path in the other graph. Similarly, changing the node identifiers may make the graphs appear different, but the least-cost paths remain the same.

Using graph convolutional networks (GCNs), it may be possible to extract features of graph <NUM>. These features may then be compared with features of other graphs to determine if the graphs are similar, even though the graphs might use different identifiers, different orders of information, different weights, etc. GCNs may also be used in deep learning techniques, machine learning, artificial intelligence, etc. GCNs may be used to extract the node embeddings in a graph, where each node embedding may contain information on the role of its respective node in the graph. A GCN may consist of multiple layers in which the embeddings of the nodes are propagated within them until rich information of the input graph is derived. In each layer, the node embeddings may be updated by gathering their neighbors' embeddings (Aggregation) and passing their weighted summation through a filter (Feature Transformation). To introduce non-linearity to the model, an activation function in the form of rectified linear unit (ReLU) may be used at the end of each layer.

<FIG> illustrates this process. Node embeddings <NUM>-<NUM> through <NUM>-<NUM> (which may be referred to collectively as node embeddings <NUM>) may be established, respectively, for each of the nodes in graph <NUM>. Node embeddings <NUM> may be thought of as vectors of some predetermined length. Node embeddings <NUM> may be initially assigned random values as the coordinates of the vector, letting the GCN establish their final values, or more specific values may be assigned to node embeddings <NUM>. While <FIG> shows each node embedding as including four coordinates/values, embodiments of the disclosure may include any number (one or more) of coordinates/values in a node embedding.

In aggregation, the node embeddings are updated based on the node embeddings of neighbor nodes (that is, the nodes connected to a given node by an edge). Thus, for example, in graph <NUM> node <NUM> is a neighbor of node <NUM>, node <NUM> is a neighbor of nodes <NUM>, <NUM>, and <NUM>, node <NUM> is a neighbor of node <NUM>, node <NUM> is a neighbor of nodes <NUM> and <NUM>, and node <NUM> is a neighbor of node <NUM>. Note that a node is also a neighbor of itself (even though there might not be an edge representing this relationship in graph <NUM>). Thus, for example, node embedding <NUM>-<NUM> for node <NUM> is updated based on node embeddings <NUM>-<NUM> and <NUM>-<NUM>.

In feature transformation, a weighted summation of the node embeddings may be passed through a filter. This feature transformation may consider the values of all coordinates within the node embedding. Thus, for example, node embedding <NUM>-<NUM> may be the result of feature transformation of node embedding <NUM>-<NUM>.

Finally, the node embeddings may be subject to activation. Activation may involve a rectified linear unit (ReLU), which may introduce non-linearity into the model. In addition, activation may involve eliminating any non-positive values in the node embeddings, by replacing non-positive values with zeroes. Thus, node embedding <NUM>-<NUM> may be the result of applying a ReLU to node embedding <NUM>-<NUM> and eliminating any non-positive values from node embedding <NUM>-<NUM>.

While <FIG> shows the process of aggregation, feature transformation, and activation occurring only once, embodiments of the disclosure may support any number (one or more) iterations of this sequence: each such sequence may be termed a layer. Thus, for example, node embedding <NUM>-<NUM> may be used as the input for node <NUM> in an activation operation in a second layer, with the results of activation of other node embeddings similarly being used as input to an activation operation in a second layer. Note that if multiple layers are performed, embodiments of the disclosure may enable varying parameters within the layer. For example, different weights may be used in different layers, different aggregation, feature transformation, and/or activation operations may be used in different layers, and so on.

<FIG> shows accelerator <NUM> of <FIG> that is used to extract features from graph <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, accelerator <NUM> is shown as including control unit <NUM>, pre-fetcher <NUM>, and GCN layers <NUM>-<NUM> and <NUM>-<NUM> (which may be referred to collectively as GCN layers <NUM> or just layers <NUM>). Control unit <NUM> may signal pre-fetcher <NUM> and GCN layers <NUM> to execute certain operations. To distinguish data flow from control flow, data flow is shown using solid arrows, and control flow is shown using dashed arrows.

As mentioned above, pre-fetcher <NUM> fetches data for the graph from memory <NUM> (or storage device <NUM> of <FIG> or some other component if the data for the graph is stored therein, and even potentially from some storage within accelerator <NUM>). Pre-fetcher <NUM> stores data in one or more buffers (not shown in <FIG>), such as on-chip buffers or caches, in accelerator <NUM>. In this manner, load or store requests to memory <NUM> may be minimized with data being transferred between components internally to accelerator <NUM>, which may result is faster overall operation. Pre-fetcher <NUM> may operate to load data from memory <NUM> in a manner that may be most efficient for the operations of pre-fetcher <NUM>. As discussed above, since matrix multiplication may involve multiplying a column of one matrix with a row of another matrix, pre-fetcher <NUM> may load data for the graph from memory <NUM> in a manner that reads some data (for example, node embeddings) in column order and other data (for example, weights) in row order, to expedite matrix multiplication.

The buffers into which pre-fetcher <NUM> may load data may include one or more first in, first out (FIFO) queues (not shown in <FIG>). Pre-fetcher <NUM> may store data values in the FIFO queues in a round robin fashion, with the first value being placed in the first FIFO queue, the second value being placed in the second FIFO queue, and so on. The FIFO queues are discussed further with reference to <FIG> below.

In some embodiments of the disclosure, the buffers into which pre-fetcher <NUM> may load data may be sufficient in size to store all data for the graph. In such embodiments, the graph may be relatively small. If the graph is of sufficient size, the buffers in accelerator <NUM> might be insufficient to store all of the data for the graph. In such embodiments of the disclosure, pre-fetcher <NUM> may pre-fetch as much data for the graph as possible (while optimizing operations as much as possible), and may leave other data in memory <NUM> to be retrieved later: for example, when some data from the buffers in accelerator <NUM> has been processed and is no longer needed. If the buffers in accelerator <NUM> are not large enough to store all the data for the graph, accelerator <NUM> may write some data back to memory <NUM> to free up space in the buffers for other data, which may necessitate reading that data back from memory <NUM> at a later time.

GCN layers <NUM> include two modules: multiplication modules <NUM>-<NUM> and <NUM>-<NUM> (which may be referred to collectively as multiplication modules <NUM>) and accumulate and aggregate (ACG) modules <NUM>-<NUM> and <NUM>-<NUM> (which may be referred to collectively as ACG modules <NUM>). Multiplication modules <NUM> perform a matrix multiplication, and ACG modules <NUM> perform an accumulate and aggregate operation. Together, multiplication modules <NUM> and ACG modules <NUM> may implement a feature transformation. ACG modules <NUM> may also perform activation, which may include a non-linear function applied to the node embeddings.

Multiplication modules <NUM> and ACG modules <NUM> may begin operations as soon as they have enough data from their sources to begin. For example, multiplication module <NUM>-<NUM> does not have to wait for pre-fetcher <NUM> to pre-fetch all the data for the graph from memory <NUM>: provided enough data has been pre-fetched that multiplication module <NUM>-<NUM> may begin, multiplication module <NUM>-<NUM> may begin operation at any time. Similarly, ACG module <NUM>-<NUM> does not need to wait for multiplication module <NUM>-<NUM> to complete all of its operations: all that is needed is that ACG module <NUM>-<NUM> has enough data to begin its operations. Similarly, GCN layer <NUM>-<NUM> does not need to wait until ACG module <NUM>-<NUM> has completed its operations to begin, provided enough data is available. This concept is discussed further with reference to <FIG> below.

<FIG> shows accelerator <NUM> as including two GCN layers <NUM>. But embodiments of the disclosure may include any number (one or more) of GCN layers <NUM>, with three to four GCN layers being typical, and with eight GCN layers as a reasonable (but not limiting) upper bound. Once the last GCN layer <NUM> has completed its processing, the last GCN layer <NUM> may write its output back to memory <NUM> (or a different storage location, as desired), for later use in other processing. In addition, while <FIG> suggests that each layer may be separate from other layers (and include its own multiplication module <NUM> and/or ACG module <NUM>), embodiments of the disclosure may include feeding data output from one GCN layer <NUM> back into itself for another iteration. Such embodiments of the disclosure may reduce the hardware used in accelerator <NUM> by reusing the implementation of GCN layers <NUM>.

Host machine <NUM>, aside from including memory <NUM>, may also include pre-processor <NUM>. Pre-processor <NUM> may read data for the graph from memory <NUM> and may pre-process the data. This pre-processing may include removing zeroes (or other values) from the data (to avoid unnecessary calculations), adding values to the data, changing values in the data, and/or re-ordering the data so that multiple data operations that might update the same value may be executed in cycles sufficiently far enough apart to avoid data dependencies, as data dependencies may result in a slower overall operation. Determining how far apart data may be moved may be a function of the number of cycles needed for a processing to complete its operation on a particular data. For example, if it takes five cycles (this number is selected arbitrarily for purposes of the example, and may be replaced with other numbers as desired/appropriate) for a processing element to complete its operation, pre-processor <NUM> may re-order data that might update the same value so that the data may be at least five cycles away from each other in terms of processing. Pre-processor <NUM> may store the pre-processed data back into memory <NUM>, or into another storage location: for example, storage device <NUM> of <FIG>, or storage within accelerator <NUM> (not shown in <FIG>).

While <FIG> shows pre-processor <NUM> and memory <NUM> as being in machine <NUM>, embodiments of the disclosure may locate pre-processor <NUM> and/or memory <NUM> in other locations. For example, pre-processor <NUM> and/or memory <NUM> may be implemented within accelerator <NUM>. That is, accelerator <NUM> may include a component (such as a dedicated FPGA, ASIC or other equivalent component) that may implement the operations of pre-processor <NUM>. Or, some other component of accelerator <NUM>, such as a pruner in ACG module <NUM>, may be used to carry out the operations of pre-processor <NUM>. Or, accelerator <NUM> may include a processor (for example, as part of control unit <NUM>) that may execute software to implement the operations of pre-processor <NUM>. That <FIG> shows pre-processor <NUM> and memory <NUM> as being part of machine <NUM> is merely an exemplary placement of pre-processor <NUM> and memory <NUM>. In addition, the elements of accelerator <NUM> (control unit <NUM>, pre-fetcher <NUM>, multiplication modules <NUM>, and ACG modules <NUM>) may be individually implemented as software, hardware, or a combination of both. For example, control unit <NUM> may be implemented as an FPGA, pre-fetcher <NUM> may be implemented as an ASIC, and multiplication modules <NUM> and ACG modules <NUM> may be implemented using software to be executed by a processor.

<FIG> shows details of multiplication module <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, multiplication module <NUM> may include arbiter <NUM>, weight buffer <NUM>, and two-dimensional (2D) single instruction, multiple data processing element (SIMD PE) <NUM>.

Arbiter <NUM> may select values to be processed by 2D SIMD PE <NUM> from FIFO queues <NUM>-<NUM> through <NUM>-<NUM> (which may be referred to collectively as FIFO queues <NUM>). The values may be placed in FIFO queues <NUM> by pre-fetcher <NUM> of <FIG> (if multiplication module <NUM> is in the first GCN layer <NUM> of <FIG> of accelerator <NUM> of <FIG>) or by a pruner that is part of ACG module <NUM> of <FIG>. The pruner is discussed further with reference to <FIG> below.

The reason to include FIFO queues <NUM> may not be apparent. After all, if pre-processor <NUM> of <FIG> has properly pre-processed the data for the graph, then the data for the graph should not contain any zeroes and should be re-ordered so that no data dependencies exist. But while that fact may be true after pre-processor <NUM> of <FIG> has pre-processed the data, that fact might not be true in subsequent GCN layers. That is, in GCN layer <NUM>-<NUM> of <FIG>, multiplication module <NUM>-<NUM> might access data that includes zeroes, or now has data dependencies. The pruner that is part of ACG module <NUM> of <FIG>, as discussed with reference to <FIG> below, may eliminate zeroes from the data for the graph for use in subsequent GCN layers <NUM> of <FIG>, but data dependencies might still exist. By using FIFO queues <NUM>, if arbiter <NUM> determines that a data dependency exists, arbiter <NUM> may leave that data in its FIFO queue for one or more cycles, to try and resolve the data dependency. Data dependencies are discussed further with reference to <FIG> below.

The number of FIFO queues <NUM> may vary, depending on the implementation. In some embodiments of the disclosure, the number of FIFO queues <NUM> may be equal to or exceed the number of PEs in 2D SIMD PE <NUM>.

Arbiter <NUM> may read data from FIFO queues <NUM>. If the data is non-zero (which it ought to be, if pre-processor <NUM> of <FIG> and the pruner of ACG module <NUM> of <FIG> have operated correctly), then arbiter <NUM> may determine whether a particular value would update data that is already being updated by another processing element. If so, then arbiter <NUM> may insert a bubble (that is, instruct the processing element that would have been handling that value) to do no operation (a no-op) instead. The operations of arbiter <NUM> are discussed further with reference to <FIG> below.

Weight buffer <NUM> may store information about weights <NUM> (which may also be termed weight data) used in the feature transformation. Weights <NUM> may be pre-fetched by pre-fetcher <NUM> of <FIG> so that they may be accessed from within accelerator <NUM> of <FIG> (rather than being read from memory <NUM> of <FIG>). While <FIG> suggests that weights <NUM> may be just a vector (a one-dimensional set of weights), embodiments of the disclosure may include weights <NUM> as two-dimensional data (with the data being provided to multiplication module <NUM> according to some ordering).

2D SIMD PE <NUM> may be a two-dimensional array of processing elements. As the name implies, the same instruction(s) may be applied to each processing element in 2D SIMD PE <NUM>, but applied to different data. As seen in the blowup of the figure, 2D SIMD PE <NUM> may include processing elements <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> (which may be referred to collectively as processing elements <NUM>). Processing elements <NUM>-<NUM> through <NUM>-<NUM> may form a row of processing elements in 2D SIMD PE <NUM>, with other rows formed by other processing elements (up through the row including processing elements <NUM>-<NUM> through <NUM>-<NUM>). In addition, processing elements <NUM>-<NUM> through <NUM>-<NUM> may form a column of processing elements in 2D SIMD PE <NUM>, with other columns formed by other processing elements (up through the column including processing elements <NUM>-<NUM> through <NUM>-<NUM>).

Each processing element <NUM> in 2D SIMD PE <NUM> may, for example, perform one multiplication as part of an overall matrix multiplication. 2D SIMD PE <NUM> is functionally equivalent to a set of one-dimensional row-oriented SIMD PEs (as may be formed by processing elements <NUM>-<NUM> through <NUM>-<NUM> or processing elements <NUM>-<NUM> through <NUM>-<NUM>), a set of one-dimensional column-oriented SIMD PEs (as may be formed by processing elements <NUM>-<NUM> through <NUM>-<NUM> or processing elements <NUM>-<NUM> through <NUM>-<NUM>), or even just a set of SIMD PEs without any "dimensional organization". The term 2D SIMD PE should be understood as including such sets.

Once arbiter has assigned operations to processing elements in 2D SIMD PE <NUM>, 2D SIMD PE <NUM> may begin its operations, even if there might be other data waiting to be loaded and processed (that is, values still in FIFO queues <NUM>). This may occur potentially even if not every processing element in 2D SIMD PE <NUM> has had values loaded into it for processing. For example, it may be that processing element <NUM>-<NUM> may be able to perform its computation even if processing elements <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> do not yet have their data. But eventually, 2D SIMD PE <NUM> should output one value for each processing element (at least, within each interval used by 2D SIMD PE <NUM> to process values: each GCN layer may involve multiple such intervals to complete all computations).

In some embodiments of the disclosure, it may be possible to provide data from FIFO queues <NUM> and/or weights <NUM> to two or more processing elements <NUM> at the same time. In such embodiments of the disclosure, processing elements <NUM> may be able to begin their computations at the same time. But in some embodiments of the disclosure, providing data to processing elements <NUM> is done one processing element at a time, with each processing element <NUM> receiving its data in a different cycle. In such embodiments of the disclosure, different processing elements <NUM> may start computations at different times.

At this point, it may be helpful to clarify some terminology. The term "cycle" is meant to refer to the time required by the hardware used to implement accelerator <NUM> of <FIG> to carry out a single instruction (similar to a cycle of a CPU). Note that while a cycle may depend on the underlying hardware, a cycle is a unit of time. For example, a processor that operates at <NUM> megahertz (MHz) performs <NUM>,<NUM>,<NUM> cycles per second, which means that each cycle is <NUM> seconds (which may also be expressed as <NUM>×<NUM>-<NUM> seconds, or <NUM> nanoseconds (ns)). The term "interval" is meant to refer to the time required for such a processor to complete a particular sequence of operations, each of which may require one or more cycles to complete. For example, the time required for processing elements <NUM> to perform computations on input data might take five cycles: this number of cycles may be understood to be an interval. (As above, the number five used above is merely exemplary, and the number of cycles used by processing elements <NUM> to perform computations may be greater or smaller than five. ) The term "iteration" is meant to refer to the operation of GCN layers <NUM> of <FIG>. A particular GCN layer <NUM> of <FIG> may take a single iteration to carry out its operations. Note that in some embodiments of the disclosure a single GCN layer <NUM> of <FIG> may be used multiple times (for example, if the operations performed in two GCN layers are identical but for the data on which the operations are performed): each such use of GCN layer <NUM> of <FIG> may be thought of as an iteration. Thus, an iteration may involve one or more intervals, and an interval may involve one or more cycles.

It has been mentioned above both that processing may begin as soon as sufficient data has been loaded and that data dependencies may exist. <FIG> illustrates how these situations may occur.

Consider the situation where an outer-product matrix multiplication is being performed on matrices <NUM> and <NUM>, to produce matrix <NUM>. To determine output value <NUM>, values <NUM> and <NUM> are multiplied, then values <NUM> and <NUM> are multiplied, then values <NUM> and <NUM> are multiplied, and so on. Once all these individual multiplications have been performed, the results may be summed, which is output value <NUM>.

When performing the mathematics manually, consideration is generally not given to the process. But when the calculation is performed by a machine, there are a number of different computations that may be updating a particular location. More particularly, processing elements <NUM> of <FIG> that are involved in updating output value <NUM> may operate by individually multiplying a pair of input values (such as values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM>), then using the product to increase output value <NUM>. But increasing output value <NUM> may involve reading output value <NUM> into processing elements <NUM> of <FIG>, performing the addition, then writing the updated value back to output value <NUM>. If two (or more) processing elements <NUM> of <FIG> attempt this update at the same time, the result might be incomplete. For example, both processing elements might read output value <NUM> at the same time and independently write their values back out. Whichever write operation completes second may therefore miss the update by the first write operation, resulting in an incorrect value. Thus, there may be a data dependency between those two computations.

The solution to this data dependency may be to schedule calculations that update output value <NUM> in different intervals. That is, one interval may update output value <NUM> based on the product of values <NUM> and <NUM>, the next interval may update output value <NUM> based on the product of values <NUM> and <NUM>, the next interval may update output value <NUM> based on the product of values <NUM> and <NUM>, and so on. In this manner, data dependencies may be addressed.

With this information, the operation of pre-processor <NUM> of <FIG>, in terms of re-ordering data for the graph, may be understood. Assume that 2D SIMD PE <NUM> of <FIG> includes n processing elements <NUM>. If two different values may be used to update the same value, then the two values have a data dependency. If the two different values are within n values of each other in the order of the data, then both values could end up being processed in the same interval. Since this situation could result in incorrect calculations (due to the possibility of one update being lost when another update to the same value in the same interval occurs), it is helpful for different values that are used to update the same value be in different intervals. The values may be spaced far enough apart that two processing elements may avoid updating the same value at the same time: this result may be achieved, for example, by spacing the values at least n × l values apart, where l is the number of cycles a processing element may need (that is, the length of an interval, or alternatively the latency of the processing element) to process a value.

Values <NUM>, <NUM>, and <NUM>, in combination with values <NUM>, <NUM>, and <NUM>, may also be used to update output value <NUM>; and value <NUM>, <NUM>, and <NUM>, in combination with values <NUM>, <NUM>, and <NUM>, may be used to update output value <NUM>. These operations do not affect computations to update output value <NUM>. Thus, while updates to output value <NUM> may be calculated in non-overlapping intervals to avoid data dependencies, there is no problem with performing operations on, for example, values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM> in parallel, as these operations update output values <NUM>, <NUM>, and <NUM> respectively (with similar parallel operations possible for other operations that do not update the same output values). In other words, one interval may involve operations on values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM>, to update values <NUM>, <NUM>, and <NUM> respectively, a later interval may involve operations on values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM> to update values <NUM>, <NUM>, and <NUM> respectively, yet another later interval may involve operations on values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM> to update values <NUM>, <NUM>, and <NUM> respectively, and so on. Note that these intervals may be non-overlapping: for example, if each interval includes five cycles, then the interval where values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM> update values <NUM>, <NUM>, and <NUM>, respectively, may start five cycles after the interval where values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM>, update values <NUM>, <NUM>, and <NUM> respectively, and five cycles before the interval where values <NUM> and <NUM>, values <NUM> and <NUM>, and values <NUM> and <NUM> update values <NUM>, <NUM>, and <NUM> respectively. Thus, data from FIFO queue <NUM>-<NUM> may be stored as value <NUM> in one processing element, data from FIFO queue <NUM>-<NUM> may be stored as value <NUM> in another processing element, and so on, to leverage available parallel computations.

<FIG> shows details of arbiter <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, arbiter <NUM> may include next turn identifier <NUM>, previous cycle identifier <NUM>, current cycle identifier <NUM>, and dependency window <NUM>. Next turn identifier <NUM> may identify the next FIFO queue <NUM> of <FIG> from which arbiter <NUM> may read data for processing.

It may be unclear why arbiter <NUM> would keep track of the next FIFO queue <NUM> from which to read data. After all, arbiter <NUM> might simply read data from each FIFO queue <NUM> in turn until all data has been read. Or, arbiter <NUM> might read data until all processing elements <NUM> of <FIG> have data, then wait for an interval to complete, then read more data to fill processing elements <NUM> of <FIG>, again, and so in, in which case all arbiter <NUM> would need to know is how many processing elements <NUM> of <FIG> are in multiplication module <NUM> of <FIG>. But these conclusions have some hidden assumptions that are not necessarily correct. In the first case, if the amount of data is greater than will fit in processing elements <NUM> of <FIG>, then arbiter <NUM> may have to wait until it may read for data; or if arbiter <NUM> may read data from FIFO queue <NUM> faster than pre-fetcher <NUM> of <FIG> (for the first GCN layer <NUM> of <FIG>) or ACG module <NUM> of <FIG> of the previous GCN layer (for later GCN layers <NUM> of <FIG>) may provide the data. In that case, arbiter <NUM> may have to remember which FIFO queue <NUM> should be read next: next turn identifier <NUM> may provide this information for when arbiter <NUM> may next read data from FIFO queues <NUM> of <FIG>. In the second case, the assumption might be reasonable for the first GCN layer <NUM> of <FIG>; but after the first GCN layer <NUM> of <FIG>, it may be that new zeroes are in the data for the graph and may be skipped. If those zeroes should be identified by arbiter <NUM>, those zeroes may be skipped, and arbiter <NUM> may actually access more values from FIFO queues <NUM> of <FIG> than there are processing elements <NUM> of <FIG>. Thus, it is not reasonable to assume that in each cycle (or interval, depending on how many values may be provided to processing elements at the same time) arbiter <NUM> may read only as many values as there are processing elements <NUM> of <FIG>.

In addition, the above discussion treats each processing element <NUM> of <FIG> as "locked" during its operation, unable to do anything else until it finishes its processing. But in some embodiments of the disclosure, processing elements <NUM> of <FIG> may operate in a pipelined manner. That is, processing elements <NUM> of <FIG> may be thought of as including two or more stages, each of which produces a partial or intermediary result, which is then used by the next stage of the pipeline. In such embodiments of the disclosure, it may be wasteful to let one stage of processing elements <NUM> of <FIG> do nothing while other stages of processing elements <NUM> of <FIG> are performing computations. For example, updating output value <NUM> of <FIG> may involve multiplying values <NUM> and <NUM> of <FIG>, then reading the current value of output value <NUM> of <FIG>, then increasing the current value of output value <NUM> of <FIG> by the product of values <NUM> and <NUM> of <FIG>: this sum may then be written to output value <NUM> of <FIG> as the result. This sequence may be thought of as three stages: multiplying values <NUM> and <NUM> of <FIG>; reading the current value of output value <NUM> of <FIG>, and adding the current value of output value <NUM> of <FIG> and the product computed in stage <NUM> (there may be other ways to divide these operations into stages: embodiments of the disclosure are intended to include all such variations). But after values <NUM> and <NUM> of <FIG> have been multiplied, the first stage of processing elements <NUM> of <FIG> may be tasked to perform another multiplication of other values. Thus, processing elements <NUM> of <FIG> may receive data in each cycle, even if the interval required for processing element <NUM> of <FIG> to complete all its operations may be more than one cycle.

If multiple operations that might involve updating a particular output value were being processed at the same time, there could be a data dependency. For example, consider the situation where values <NUM> and <NUM> of <FIG> are input to a particular processing element <NUM> of <FIG> in one cycle, and values <NUM> and <NUM> of <FIG> are input to the same processing element <NUM> of <FIG> in the next cycle. At the same time that stage one is multiplying values <NUM> and <NUM> of <FIG>, stage two may be reading output value <NUM> of <FIG> to increase output value <NUM> of <FIG> by the product of values <NUM> and <NUM> of <FIG>. But in the next cycle, stage two of the particular processing element <NUM> of <FIG> may attempt to read output value <NUM> of <FIG> while stage three of the particular processing element <NUM> of <FIG> may be increasing output value <NUM> of <FIG> by the product of values <NUM> and <NUM> of <FIG>. Depending on which operation happens "first" (despite the fact that the operations are meant to occur in parallel, the operations might occur in one order or the other, which might not be predictable), the "current" value of output value <NUM> of <FIG> read in stage two of the particular processing element <NUM> of <FIG> might or might not reflect the increase by the product of values <NUM> and <NUM> of <FIG> being performed in stage three of the particular processing element <NUM> of <FIG>. In other words, the increase to output value <NUM> of <FIG> by the product of values <NUM> and <NUM> of <FIG> might be lost if stage two of the particular processing element <NUM> of <FIG> accesses output value <NUM> of <FIG> at the "wrong" time. In this situation, the various updates to output value <NUM> of <FIG> may be scheduled far enough apart (based on the latency of processing elements <NUM> of <FIG>) to avoid such a data dependency. For example, the particular processing element <NUM> of <FIG> might be scheduled to update output value <NUM> of <FIG> in one cycle, then output value <NUM> of <FIG> in the next cycle, then output value <NUM> of <FIG> in the third cycle. At this point, any data in the particular processing element <NUM> of <FIG> would not be updating output value <NUM> of <FIG>, and therefore there would not be a data dependency to schedule another update to output value <NUM> of <FIG>.

Previous cycle identifier <NUM> may be used to determine the last cycle in which a particular feature was updated. Thus, previous cycle identifier <NUM> may be a vector, rather than a single value, storing information for each processing element <NUM> of <FIG>. Current cycle identifier <NUM> may be used to determine the current cycle of multiplication module <NUM> of <FIG>. Dependency window <NUM> may be determined using the number of cycles needed by processing elements <NUM> of <FIG> to finish computations (that is, the latency of processing elements <NUM> of <FIG>). By comparing previous cycle identifier <NUM> with current cycle identifier <NUM> and dependency window <NUM>, it may be possible to determine whether there may be a data dependency: if the difference between previous cycle identifier <NUM> for a particular feature and current cycle identifier <NUM> is less than or equal to dependency window <NUM>, then it is possible that updating this feature could result in a data dependency. Arbiter <NUM> may then insert a bubble (a no-op) into the processing element rather than moving the value from FIFO queue <NUM> of <FIG> into processing element <NUM> of <FIG> and track that the value in question is waiting to be processed. But if the difference between previous cycle identifier <NUM> and current cycle identifier <NUM> is greater than dependency window <NUM>, then arbiter <NUM> may load the value from FIFO queue <NUM> of <FIG> into processing element <NUM>, and may update previous cycle identifier <NUM> for that feature to equal current cycle identifier <NUM>. Note that if arbiter <NUM> inserts a bubble into processing element <NUM> of <FIG>, this fact does not mean that the data is removed from FIFO queue <NUM> of <FIG>: the data may remain in FIFO queue <NUM> of <FIG>, or may be stored in a buffer within arbiter <NUM> until the data dependency has been resolved.

Current cycle identifier <NUM> may be updated based on clock <NUM> of <FIG> as cycles pass. Previous cycle identifier <NUM> may be updated at the time the arbiter <NUM> reads data from FIFO queues <NUM> of <FIG>.

While it may seem that arbiter <NUM> may operate one value at a time, this assumption is not correct. In fact, arbiter <NUM> may access some set of values from FIFO queues <NUM> of <FIG> in parallel, and may store those values in processing elements <NUM> of <FIG> (or insert bubbles into processing elements <NUM> of <FIG>) in parallel. Arbiter <NUM> may actually read enough values from FIFO queues <NUM> of <FIG> to fill 2D SIMD PE <NUM> of <FIG>. Note that this number of values may be less than the number of processing elements <NUM> of <FIG>. For example, as noted above, arbiter <NUM> may track certain values as not having been loaded into processing elements <NUM> of <FIG>. These elements, already read from FIFO queues <NUM> of <FIG>, are waiting for processing in the next iteration. Thus, if 2D SIMD PE <NUM> of <FIG> has n processing elements <NUM> of <FIG>, and there are w elements waiting for processing (as described above), then arbiter <NUM> may only read n - w elements from FIFO queues <NUM> of <FIG>: between those read elements and the w waiting elements, arbiter <NUM> will have enough values to fill processing elements <NUM> for another iteration.

<FIG> shows details of ACG module <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, ACG module <NUM> is shown as including two 2D SIMD PEs <NUM> and <NUM>, two buffers <NUM> and <NUM>, ReLU <NUM>, and pruner <NUM>. 2D SIMD PEs <NUM> and <NUM> are similar to 2D SIMD PE <NUM> of <FIG>, although 2D SIMD PEs <NUM> and <NUM> may carry out different operations: 2D SIMD PE <NUM> may perform an accumulate operation and 2D SIMD PE <NUM> may perform a multiply and accumulate operation (and operate on edge data for the graph rather than node data for the graph, as shown by the second data input to 2D SIMD PE <NUM>). Similar to 2D SIMD PE <NUM> of <FIG>, 2D SIMD PEs <NUM> and <NUM> may begin to operate as soon as there is sufficient data available, rather than waiting for all processing elements <NUM> of <FIG> in 2D SIMD PEs <NUM> and <NUM> to have data.

Buffers <NUM> and <NUM> may be used to store the outputs of 2D SIMD PEs <NUM> and <NUM> within ACG module <NUM> for further processing: as may be seen in <FIG>, buffer <NUM> may store intermediate feature calculations from 2D SIMD PE <NUM> which may in turn be used as input to 2D SIMD PE <NUM>, and buffer <NUM> may store feature calculations from 2D SIMD PE <NUM>, which may in turn be used as input to ReLU <NUM>.

At the end of each GCN layer <NUM> of <FIG>, there may be an activation function. The activation function may be in the form of ReLU <NUM> may be used to activate features from buffer <NUM>. ReLU <NUM> may use a non-linear function, such as, for example, a function that determines the maximum of the input value or zero, to perform activation.

Pruner <NUM> may prune any zeroes from the features as processed by ReLU <NUM>. Note that ReLU <NUM> may replace negative values with zeroes; pruner <NUM> may then remove zeroes (or other values) from the data for the graph. Pruner <NUM> may also modify the data for the graph: for example, adding values or changing values. Pruner <NUM> may also place (non-zero) data for the graph in FIFO queues <NUM> of <FIG> for use in the next GCN layer <NUM> of <FIG>.

Note that in some embodiments of the disclosure, the final GCN layer <NUM> of <FIG>, the output of ACG module <NUM> may be complete: that is, with zeroes included. By including the zeroes in the output of ACG module <NUM>, the feature extraction may be more complete (as later uses of the features may expect the zeroes to be present). Thus, pruner <NUM> might be omitted (or not used) in ACG module <NUM> of the final GCN layer <NUM> of <FIG>. But in other embodiments of the disclosure, pruner <NUM> may operate even in ACG module <NUM> of the final GCN layer <NUM> of <FIG>, provided enough information is provided for the zeroes to be reintroduced if needed (for example, by identifying which elements in the output matrix include the data output by pruner <NUM>, or by identifying which elements in the output matrix would be zero).

<FIG> shows an example flowchart of an example procedure for operations of pre-processor <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, pre-processor <NUM> of <FIG> may read elements from memory <NUM> of <FIG>. At block <NUM>, pre-processor <NUM> of <FIG> may identify and remove any zero elements (or other values). Pre-processor <NUM> of <FIG> may also make other modifications to the data for the graph, such as changing values in the data or adding values to the data. At block <NUM>, pre-processor <NUM> of <FIG> may re-order elements so as to avoid any data dependencies. Finally, at block <NUM>, pre-processor <NUM> of <FIG> may write the pre-processed data for the graph back into memory <NUM> of <FIG>, for reading by pre-fetcher <NUM> of <FIG>.

<FIG> shows an example flowchart of an example procedure for operations of pre-fetcher <NUM> of <FIG> and/or pruner <NUM> of <FIG>, according to embodiments of the disclosure. At block <NUM>, pre-fetcher <NUM> of <FIG> and/or pruner <NUM> of <FIG> may read elements. Pre-fetcher <NUM> of <FIG> may fetch elements from memory <NUM> of <FIG>, whereas pruner <NUM> of <FIG> may fetch elements from a buffer or cache within ACG module <NUM> of <FIG>. The number of elements that may be fetched may vary with the implementation: for example, pre-fetcher <NUM> of <FIG> and/or pruner <NUM> of <FIG> may fetch at least as many elements as there are processing elements <NUM> of <FIG> in multiplication module <NUM> of <FIG> of the next GCN layer <NUM> of <FIG>. At block <NUM>, pre-fetcher <NUM> of <FIG> and/or pruner <NUM> of <FIG> may check to see if elements are non-zero. Note that if desired, block <NUM> may be performed in parallel for all elements pre-fetched, to leverage the parallelism supported by accelerator <NUM> of <FIG>. At block <NUM>, if the elements are non-zero, then the elements may be written to appropriate FIFO queues <NUM> of <FIG>. (Note that if pre-processor <NUM> of <FIG> has eliminated zeroes from the data from the graph, then pre-fetcher <NUM> of <FIG> may proceed to block <NUM> without performing the check in block <NUM>, as the check in block <NUM> may always return a true result. ) Blocks <NUM> and <NUM> may also be generalized: pre-processor <NUM> of <FIG> and/or pruner <NUM> of <FIG> may change values in the data, add values to the data, or remove values other than zero from the data.

<FIG> shows an example flowchart of an example procedure for operations of arbiter <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, arbiter <NUM> of <FIG> may fetch elements from FIFO queues <NUM> of <FIG>. This operation may include "fetching" elements previously fetched by kept due to data dependencies. The number of elements actually fetched from FIFO queues <NUM> of <FIG> may therefore be the difference between the number of processing elements <NUM> of <FIG> and the number of elements waiting for processing from previous cycles. At block <NUM>, arbiter <NUM> of <FIG> may check to see if a data dependency is found in of the elements fetched in block <NUM>. Note that if desired, block <NUM> may be performed in parallel for all elements fetched, to leverage the parallelism supported by accelerator <NUM> of <FIG>. If a data dependency is found, then at block <NUM> arbiter <NUM> of <FIG> may insert a bubble (a no-op) into 2D SIMD PE <NUM> of <FIG>; otherwise, at block <NUM> arbiter <NUM> of <FIG> may insert the element into 2D SIMD PE <NUM> of <FIG>. (Note that if pre-processor <NUM> of <FIG> has re-ordered data from the graph to eliminate data dependencies, then arbiter <NUM> of <FIG> may proceed to block <NUM> without performing the check in block <NUM> or the operations in block <NUM>, as the check in block <NUM> may always return a false result. Thus, if arbiter <NUM> of <FIG> is in the first GCN layer <NUM> of <FIG>, then arbiter <NUM> of <FIG> may omit blocks <NUM> and <NUM>. ) As discussed above with reference to <FIG>, if arbiter <NUM> of <FIG> inserts a bubble into 2D SIMD PE <NUM> of <FIG>, then the data that otherwise might have been inserted into 2D SIMD PE <NUM> of <FIG> may remain in FIFO queue <NUM> of <FIG> or be stored in a buffer within arbiter <NUM> of <FIG> for later processing when the data dependency has been resolved.

<FIG> shows a flowchart of an example procedure for accelerator <NUM> of <FIG> to determine features of the graph of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, accelerator <NUM> of <FIG> may load node data for graph <NUM> of <FIG> into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, multiplication module <NUM> of <FIG> may execute a multiplication operation on the node data for graph <NUM> of <FIG> loaded in 2D SIMD PE <NUM> of <FIG>, to produce a product.

At block <NUM>, accelerator <NUM> of <FIG> may load the product into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may execute an accumulate operation on the product in 2D SIMD PE <NUM> of <FIG> to produce an intermediate feature, which may be stored in intermediate features buffer <NUM> of <FIG>.

At block <NUM>, accelerator <NUM> of <FIG> may load the intermediate feature into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, accelerator <NUM> of <FIG> may also load edge data for graph <NUM> of <FIG> into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may execute a multiply and accumulate operation on the intermediate feature and the edge data for graph <NUM> of <FIG> in 2D SIMD PE <NUM> of <FIG> to produce a feature, which may be stored in features buffer <NUM> of <FIG>.

Finally, at block <NUM>, pruner <NUM> of <FIG> may prune a zero from the feature to produce an output data. More generally, pruner <NUM> of <FIG> may modify the data in any desired way: by adding a value to the data, changing a value in the data, or removing a value (which may be non-zero) from the data. This output data may be written to memory <NUM> of <FIG> and may be used by various applications running on machine <NUM> of <FIG>.

<FIG> shows a flowchart of an alternative example procedure for accelerator <NUM> of <FIG> to determine features of the graph of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, pre-processor <NUM> of <FIG> may pre-process data for graph <NUM> of <FIG>. At block <NUM>, pre-fetcher <NUM> of <FIG> may pre-fetch data for graph <NUM> of <FIG>. This data may include, for example, node data, edge data, and weights. At block <NUM>, multiplication module <NUM> of <FIG> may implement a multiplication operation on some of the data for graph <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may implement an accumulate and aggregate operation on data for graph <NUM> of <FIG>. Finally, at block <NUM>, if there are more GCN layers to execute, control may return to block <NUM> to process another layer; otherwise, operations may complete.

<FIG> shows a flowchart of an example procedure for pre-processor <NUM> of <FIG> to pre-process graph <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, pre-processor <NUM> of <FIG> may load data for graph <NUM> of <FIG> from, for example, memory <NUM> of <FIG>. At block <NUM>, pre-processor <NUM> of <FIG> may prune zeroes from the data for graph <NUM> of <FIG> (or more generally, may modify the data for graph <NUM> of <FIG>, by adding values, changing values, and/or removing values, which may be non-zero, from the data for graph <NUM> of <FIG>). At block <NUM>, pre-processor <NUM> of <FIG> may re-order data to remove data dependencies. Finally, at block <NUM>, pre-processor <NUM> of <FIG> may store the pre-processed data for graph <NUM> of <FIG> back into, for example, memory <NUM> of <FIG>.

<FIG> shows a flowchart of an alternative example procedure for pre-fetcher <NUM> of <FIG> to pre-fetch data for graph <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, pre-fetcher <NUM> of <FIG> may pre-fetch data for graph <NUM> of <FIG> from, for example, memory <NUM> of <FIG>. At block <NUM>, pre-fetcher <NUM> of <FIG> may store the data for graph <NUM> of <FIG> in a buffer or cache in accelerator <NUM> of <FIG>.

<FIG> shows a flowchart of an example procedure for multiplication module <NUM> of <FIG> to perform a multiplication operation using data of graph <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, arbiter <NUM> of <FIG> may load an element from FIFO queues <NUM> of <FIG>. At block <NUM>, arbiter <NUM> of <FIG> may determine a processing element involves a data dependency: that is, the element is used to update a value that is also being updated by another element currently being processed. If so, then at block <NUM> arbiter <NUM> of <FIG> may insert a bubble into 2D SIMD PE <NUM> of <FIG>; otherwise, at block <NUM>, arbiter <NUM> of <FIG> may insert the element into 2D SIMD PE <NUM> of <FIG>.

Either way, at block <NUM>, arbiter <NUM> of <FIG> may load weight(s) into 2D SIMD PE <NUM> of <FIG>, and at block <NUM>, multiplication module <NUM> of <FIG> may execute a multiplication operation using 2D SIMD PE <NUM> of <FIG>.

<FIG> shows a flowchart of an example procedure for ACG module <NUM> of <FIG> to perform an accumulate and aggregate operation using data of graph <NUM> of <FIG>, according to embodiments of the disclosure. In <FIG>, at block <NUM>, ACG module <NUM> of <FIG> may load the output of multiplication module <NUM> of <FIG> into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may execute an accumulate operation using 2D SIMD PE <NUM> of <FIG>, which may be stored in intermediate features buffer <NUM>.

At block <NUM>, ACG module <NUM> of <FIG> may load the features from intermediate features buffer <NUM> into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may also load edge data for graph <NUM> of <FIG> into 2D SIMD PE <NUM> of <FIG>. At block <NUM>, ACG module <NUM> of <FIG> may execute a multiply and accumulate operation using 2D SIMD PE <NUM> of <FIG>, which may be stored in features buffer <NUM>.

At block <NUM>, ReLU <NUM> of <FIG> may perform activation on the features in features buffer <NUM>. Finally, at block <NUM>, pruner <NUM> of <FIG> may prune any zeroes from the activated features (or more generally, pruner <NUM> of <FIG> may modify the data for graph <NUM> of <FIG>, by adding values, changing values, and/or removing values, which may be non-zero, from the data for graph <NUM> of <FIG>).

In <FIG>, some embodiments of the disclosure are shown. But a person skilled in the art will recognize that other embodiments of the disclosure are also possible, by changing the order of the blocks, by omitting blocks, or by including links not shown in the drawings. All such variations of the flowcharts are considered to be embodiments of the disclosure, whether expressly described or not.

Embodiments of the disclosure include an accelerator for performing graph convolutional networks (GCNs). The accelerator may eliminate zero elements, which may expedite overall operation. The accelerator may identify data dependencies and either eliminate them (as part of pre-processing) or prevent data dependencies from introducing errors (by inserting a bubble where a data dependency might occur). The accelerator may minimize accessing graph data from the memory, also thereby potentially expediting operation, as accesses to memory may be slower that accesses to buffers within the accelerator.

The following discussion is intended to provide a brief, general description of a suitable machine or machines in which certain aspects of the disclosure may be implemented. The machine or machines may be controlled, at least in part, by input from conventional input devices, such as keyboards, mice, etc., as well as by directives received from another machine, interaction with a virtual reality (VR) environment, biometric feedback, or other input signal. As used herein, the term "machine" is intended to broadly encompass a single machine, a virtual machine, or a system of communicatively coupled machines, virtual machines, or devices operating together. Exemplary machines include computing devices such as personal computers, workstations, servers, portable computers, handheld devices, telephones, tablets, etc., as well as transportation devices, such as private or public transportation, e.g., automobiles, trains, cabs, etc..

The machine or machines may include embedded controllers, such as programmable or non-programmable logic devices or arrays, Application Specific Integrated Circuits (ASICs), embedded computers, smart cards, and the like. The machine or machines may utilize one or more connections to one or more remote machines, such as through a network interface, modem, or other communicative coupling. Machines may be interconnected by way of a physical and/or logical network, such as an intranet, the Internet, local area networks, wide area networks, etc. One skilled in the art will appreciate that network communication may utilize various wired and/or wireless short range or long range carriers and protocols, including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE) <NUM>, Bluetooth®, optical, infrared, cable, laser, etc..

Embodiments of the present disclosure may be described by reference to or in conjunction with associated data including functions, procedures, data structures, application programs, etc. which when accessed by a machine results in the machine performing tasks or defining abstract data types or low-level hardware contexts. Associated data may be stored in, for example, the volatile and/or non-volatile memory, e.g., RAM, ROM, etc., or in other storage devices and their associated storage media, including hard-drives, floppy-disks, optical storage, tapes, flash memory, memory sticks, digital video disks, biological storage, etc. Associated data may be delivered over transmission environments, including the physical and/or logical network, in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in a compressed or encrypted format. Associated data may be used in a distributed environment, and stored locally and/or remotely for machine access.

Embodiments of the disclosure may include a tangible, non-transitory machine-readable medium comprising instructions executable by one or more processors, the instructions comprising instructions to perform the elements of the disclosures as described herein.

The various operations of methods described above may be performed by any suitable means capable of performing the operations, such as various hardware and/or software component(s), circuits, and/or module(s). The software may comprise an ordered listing of executable instructions for implementing logical functions, and may be embodied in any "processor-readable medium" for use by or in connection with an instruction execution system, apparatus, or device, such as a single or multiple-core processor or processor-containing system.

The blocks or steps of a method or algorithm and functions described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a tangible, non-transitory computer-readable medium. A software module may reside in Random Access Memory (RAM), flash memory, Read Only Memory (ROM), Electrically Programmable ROM (EPROM), Electrically Erasable Programmable ROM (EEPROM), registers, hard disk, a removable disk, a CD ROM, or any other form of storage medium known in the art.

Having described and illustrated the principles of the disclosure with reference to illustrated embodiments, it will be recognized that the illustrated embodiments may be modified in arrangement and detail without departing from such principles, and may be combined in any desired manner. And, although the foregoing discussion has focused on particular embodiments, other configurations are contemplated. In particular, even though expressions such as "according to an embodiment of the disclosure" or the like are used herein, these phrases are meant to generally reference embodiment possibilities, and are not intended to limit the disclosure to particular embodiment configurations. As used herein, these terms may reference the same or different embodiments that are combinable into other embodiments.

Claim 1:
A system, comprising:
a host processor (<NUM>);
a host memory coupled to the host processor (<NUM>);
a pre-processor (<NUM>); and
a device implemented in hardware, comprising:
a first Graph Convolutional Network, GCN, layer (<NUM>-<NUM>) including:
a multiplication module (<NUM>; <NUM>-<NUM>) to perform a multiplication based on at least a node data for a graph or a weight data stored in a buffer in the device, and
an accumulation and aggregation, ACG, module (<NUM>) to perform accumulation and aggregation based at least in part on the multiplication module (<NUM>; <NUM>-<NUM>) or an edge data for the graph;
a second GCN layer (<NUM>-<NUM>) including:
a second multiplication module (<NUM>; <NUM>-<NUM>) to perform a multiplication based on at least the output of the accumulation and aggregation module, and
a second ACG module (<NUM>; <NUM>-<NUM>) to perform accumulation and aggregation based at least in part on the second multiplication module or an edge data for the graph; and
a control unit (<NUM>) implemented as a Field Programmable Gate Array, FPGA, to manage the multiplication modules (<NUM>; <NUM>-<NUM>, <NUM>-<NUM>) and the ACG modules (<NUM>; <NUM>-<NUM>, <NUM>-<NUM>) of the first and second GCN layers (<NUM>-<NUM>, <NUM>-<NUM>),
wherein the pre-processor (<NUM>) is configured to modify a value in the node data for the graph, and wherein the pre-processor (<NUM>) is executed at least in part on the host processor (<NUM>), and wherein the pre-processor is configured to remove a zero from the node data for the graph,
wherein:
the device further comprises a pre-fetcher (<NUM>) to retrieve the modified node data for the graph and the weight data from the memory (<NUM>) of the host processor (<NUM>); and
the control unit (<NUM>) is configured to manage the pre-fetcher (<NUM>), and
wherein pre-fetching the node data for the graph includes storing the node data for the graph in a buffer in the device.