Patent Publication Number: US-2023162032-A1

Title: Estimating Throughput for Placement Graphs for a Reconfigurable Dataflow Computing System

Description:
RELATED APPLICATIONS AND DOCUMENTS 
     This application is related to and claims the benefit of (priority to) U.S. Provisional Application 63/282,159 filed on Nov. 22, 2021 entitled “Data-driven Cost Modeling for Placement and Routing in Dataflow Architecture Compilers,” (Attorney Docket No. SBNV1085USP1). 
     This application is also related to and claims the benefit of (priority to) U.S. Provisional Application 63/406,196 filed on Sep. 23, 2022 entitled “LEARNED COST MODELS FOR PERFORMANCE OPTIMIZATION ON DATAFLOW ARCHITECTURE,” (Attorney Docket No. SBNV1126USP1). 
     This application is also related to and claims the benefit of (priority to) U.S. Provisional Application 63/417,456 filed on Oct. 19, 2022 entitled “Performance Optimization of Dataflow Processors,” (Attorney Docket No. SBNV1126USP2). 
     This application is related to the following papers and commonly owned applications:
         U.S. Nonprovisional patent application Ser. No. 15/930,381, filed May 12, 2020, entitled “COMPUTATIONALLY EFFICIENT GENERAL MATRIX-MATRIX MULTIPLICATION (GEMM),” (Attorney Docket No. SBNV 1019-1);   U.S. Nonprovisional patent application Ser. No. 16/890,841, filed Jun. 2, 2020, entitled “ANTI-CONGESTION FLOW CONTROL FOR RECONFIGURABLE PROCESSORS,” (Attorney Docket No. SBNV 1021-1);   U.S. Nonprovisional patent application Ser. No. 17/216,647, filed Mar. 29, 2021, entitled “TENSOR PARTITIONING AND PARTITION ACCESS ORDER,” (Attorney Docket No. SBNV 1031-1);       

     All of the related application(s) and documents listed above are hereby incorporated by reference herein for all purposes. 
    
    
     BACKGROUND 
     The present subject matter relates to selecting and deploying placement graphs for reconfigurable coarse-grained computing systems—particularly those that support dataflow computing. 
     Reconfigurable processors can be configured to implement a variety of functions more efficiently or faster than might be achieved using a general-purpose processor executing a computer program. For example, coarse-grain reconfigurable architectures (CGRAs) are being developed in which the configurable units in the array are more complex than used in typical, more fine-grained FPGAs, and may enable faster or more efficient (e.g., dataflow) execution of various classes of functions. For example, CGRAs have been proposed that can enable implementation of energy-efficient accelerators for machine learning and artificial intelligence workloads. See, Prabhakar, et al., “Plasticine: A Reconfigurable Architecture for Parallel Patterns,” ISCA &#39;17, Jun. 24-28, 2017, Toronto, ON, Canada. 
     Despite the promise of CGRAs, evaluating and selecting placement graphs for the configurable units of a CRGA remains a challenge. 
     SUMMARY OF THE INVENTION 
     A computer-implemented method for estimating throughput for placement graphs includes obtaining a set of reference placement graphs for at least one computing task, determining a corresponding throughput value for each reference placement graph, configuring a graph neural network for each reference placement graph and training the graph neural network using each corresponding throughput value as a training target to produce a trained graph neural network. The method further includes configuring the trained graph neural network for a candidate placement graph corresponding to a target computing task, and using the trained graph neural network to estimate a throughput for the target computing task conducted on the reconfigurable dataflow computing system according to the candidate placement graph. 
     The method may also include generating configuration information that enables the reconfigurable dataflow computing system to conduct the target computing task according to the candidate placement graph, configuring the reconfigurable dataflow computing system using the configuration information, and conducting the target computing task with the reconfigurable dataflow computing system according to the candidate placement graph. A corresponding system and computer-readable medium are also disclosed herein. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    illustrates an example system including a coarse-grained reconfigurable (CGR) processor, a host, and a memory. 
         FIG.  2    illustrates an example of a computer, including an input device, a processor, a storage device, and an output device. 
         FIG.  3    illustrates example details of a CGR architecture including a top-level network (TLN) and two CGR arrays. 
         FIG.  4    illustrates an example CGR array, including an array of configurable nodes in an array-level network (ALN). 
         FIG.  5    illustrates an example of a pattern memory unit (PMU) and a pattern compute unit (PCU), which may be combined in a fused-control memory unit (FCMU). 
         FIG.  6    is a block diagram of a compiler stack implementation suitable for generating a configuration file for a CGR processor. 
         FIGS.  7 A- 7 E  illustrate various representations of an example user program corresponding to various stages of a compiler stack such as the compiler stack of  FIG.  6   . 
         FIG.  8 A  shows one example of a resource graph corresponding to at least one example of a dataflow computing grid. 
         FIGS.  8 B and  8 C  shows two examples of placement graphs suitable for the dataflow computing grid represented in  FIG.  8 A . 
         FIG.  8 D  is a block diagram illustrating one example of a placement graph selection and execution system suitable for reconfigurable dataflow computing. 
         FIG.  9    is a flowchart of one example of a placement graph selection method suitable for reconfigurable dataflow computing. 
         FIG.  10 A  is a block diagram of one example of a graph neural network suitable for estimating the throughput of placement graphs for a reconfigurable dataflow computing system. 
         FIG.  10 B  is a block diagram of one example of a set of embedding tables consistent with the graph neural network of  FIG.  10 A . 
     
    
    
     DETAILED DESCRIPTION 
     The following detailed description is made with reference to the figures. Example implementations are described to illustrate the technology disclosed, not to limit its scope, which is defined by the claims. Those of ordinary skill in the art will recognize a variety of equivalent variations on the description that follows. 
       FIGS.  1 - 7    depict at least one example of an environment wherein the disclosed technology may be deployed while  FIGS.  8 A- 10 B  depict details on various examples of the disclosed technology. 
     Traditional compilers translate human-readable computer source code into machine code that can be executed on a Von Neumann computer architecture. In this architecture, a processor serially executes instructions in one or more threads of software code. The architecture is static, and the compiler does not determine how execution of the instructions is pipelined, or which processor or memory takes care of which thread. Thread execution is asynchronous, and safe exchange of data between parallel threads is not supported. 
     High-level programs for machine learning (ML) and artificial intelligence (AI) may require massively parallel computations, where many parallel and interdependent threads (meta-pipelines) exchange data. Such programs are ill-suited for execution on Von Neumann computers. They require architectures that are optimized for parallel processing, such as coarse-grained reconfigurable (CGR) architectures (CGRAs) or graphic processing units (GPUs). The ascent of ML, AI, and massively parallel architectures places new requirements on compilers, including how computation graphs, and in particular dataflow graphs, are pipelined, which operations are assigned to which compute units, how data is routed between various compute units and memory, and how synchronization is controlled particularly when a dataflow graph includes one or more nested loops, whose execution time varies dependent on the data being processed. 
     TERMINOLOGY 
     As used herein, the phrase one of should be interpreted to mean exactly one of the listed items. For example, the phrase “one of A, B, and C” should be interpreted to mean any of: only A, only B, or only C. 
     As used herein, the phrases at least one of and one or more of should be interpreted to mean one or more items. For example, the phrase “at least one of A, B, and C” or the phrase “at least one of A, B, or C” should be interpreted to mean any combination of A, B, and/or C. The phrase “at least one of A, B, and C” means at least one of A and at least one of B and at least one of C. 
     Unless otherwise specified, the use of ordinal adjectives first, second, third, etc., to describe an object, merely refers to different instances or classes of the object and does not imply any ranking or sequence. 
     The following terms or acronyms used herein are defined at least in part as follows: 
     AGCU—address generator (AG) and coalescing unit (CU). 
     AI—artificial intelligence. 
     AIR—arithmetic or algebraic intermediate representation (notation). 
     ALN—array-level network. 
     Buffer—an intermediate storage of data. 
     CGR—coarse-grained reconfigurable. A property of, for example, a system, a processor, an architecture (see CGRA), an array, or a unit in an array. This property distinguishes the system, etc., from field-programmable gate arrays (FPGAs), which can implement digital circuits at the gate level and are therefore fine-grained configurable. 
     CGRA—coarse-grained reconfigurable architecture. A data processor architecture that includes one or more arrays (CGR arrays) of CGR units. 
     Compiler—a translator that processes statements written in a programming language to machine language instructions for a computer processor. A compiler may include multiple stages to operate in multiple steps. Each stage may create or update an intermediate representation (IR) of the translated statements. Compiler stages are illustrated with reference to  FIG.  6   . 
     Computation graph—some algorithms can be represented as computation graphs. As used herein, computation graphs are a type of directed graphs comprising nodes that represent mathematical operations/expressions and edges that indicate dependencies between the operations/expressions. For example, with machine learning (ML) algorithms, input layer nodes assign variables, output layer nodes represent algorithm outcomes, and hidden layer nodes perform operations on the variables. Edges represent data (e.g., scalars, vectors, tensors) flowing between operations. In addition to dependencies, the computation graph reveals which operations and/or expressions can be executed concurrently. 
     CGR unit—a circuit that can be configured and reconfigured to locally store data (e.g., a memory unit or a PMU), or to execute a programmable function (e.g., a compute unit or a PCU). A CGR unit includes hardwired functionality that performs a limited number of functions used in computation graphs and dataflow graphs. Further examples of CGR units include a CU and an AG, which may be combined in an AGCU. Some implementations include CGR switches, whereas other implementations may include regular switches. 
     CU—coalescing unit. 
     Data Flow Graph—a computation graph that includes one or more loops that may be nested, and wherein nodes can send messages to nodes in earlier layers to control the dataflow between the layers. 
     Datapath—a collection of functional units that perform data processing operations. The functional units may include memory, multiplexers, ALUs, SIMDs, multipliers, registers, buses, etc. 
     FCMU—fused compute and memory unit—a circuit that includes both a memory unit and a compute unit. 
     Graph—a collection of nodes connected by edges. Nodes may represent various kinds of items or operations, dependent on the type of graph. Edges may represent relationships, directions, dependencies, etc. 
     IC—integrated circuit—a monolithically integrated circuit, i.e., a single semiconductor die which may be delivered as a bare die or as a packaged circuit. For the purposes of this document, the term integrated circuit also includes packaged circuits that include multiple semiconductor dies, stacked dies, or multiple-die substrates. Such constructions are now common in the industry, produced by the same supply chains, and for the average user often indistinguishable from monolithic circuits. 
     Logical CGR array or logical CGR unit—a CGR array or a CGR unit that is physically realizable, but that may not have been assigned to a physical CGR array or to a physical CGR unit on an IC. 
     ML—machine learning. 
     PCU—pattern compute unit—a compute unit that can be configured to repetitively perform a sequence of operations. 
     PEF—processor-executable format—a file format suitable for configuring a configurable data processor. 
     Pipeline—a staggered flow of operations through a chain of pipeline stages. The operations may be executed in parallel and in a time-sliced fashion. Pipelining increases overall instruction throughput. CGR processors may include pipelines at different levels. For example, a compute unit may include a pipeline at the gate level to enable correct timing of gate-level operations in a synchronous logic implementation of the compute unit, and a meta-pipeline at the graph execution level to enable correct timing of node-level operations of the configured graph. Gate-level pipelines are usually hard wired and unchangeable, whereas meta-pipelines are configured at the CGR processor, CGR array level, and/or GCR unit level. 
     Pipeline Stages—a pipeline is divided into stages that are coupled with one another to form a pipe topology. 
     PMU—pattern memory unit—a memory unit that can store data according to a programmed pattern. 
     PNR—place and route—the assignment of logical CGR units and associated processing/operations to physical CGR units in an array, and the configuration of communication paths between the physical CGR units. 
     RAIL—reconfigurable dataflow unit (RDU) abstract intermediate language. 
     CGR Array—an array of CGR units, coupled with each other through an array-level network (ALN), and coupled with external elements via a top-level network (TLN). A CGR array can physically implement the nodes and edges of a dataflow graph. 
     SIMD—single-instruction multiple-data—an arithmetic logic unit (ALU) that simultaneously performs a single programmable operation on multiple data elements delivering multiple output results. 
     TLIR—template library intermediate representation. 
     TLN—top-level network. 
     Implementations 
     The architecture, configurability and dataflow capabilities of an array of CGR units enable increased compute power that supports both parallel and pipelined computation. A CGR processor, which includes one or more CGR arrays (arrays of CGR units), can be programmed to simultaneously execute multiple independent and interdependent dataflow graphs. To enable simultaneous execution, the dataflow graphs may need to be distilled from a high-level program and translated to a configuration file for the CGR processor. A high-level program is source code written in programming languages like Spatial, Python, C++, and C, and may use computation libraries for scientific computing, ML, AI, and the like. The high-level program and referenced libraries can implement computing structures and algorithms of machine learning models like AlexNet, VGG Net, GoogleNet, ResNet, ResNeXt, RCNN, YOLO, SqueezeNet, SegNet, GAN, BERT, ELMo, USE, Transformer, and Transformer-XL. 
     Translation of high-level programs to executable bit files is performed by a compiler. See, for example,  FIGS.  6  and  7 A- 7 E . While traditional compilers sequentially map operations to processor instructions, typically without regard to pipeline utilization and duration (a task usually handled by the hardware), an array of CGR units requires mapping operations to processor instructions in both space (for parallelism) and time (for synchronization of interdependent computation graphs or dataflow graphs). This requirement implies that a compiler for a CGRA must decide which operation of a computation graph or dataflow graph is assigned to which of the CGR units, and how both data and, related to the support of dataflow graphs, control information flows among CGR units, and to and from external hosts and storage. This process, known as “place and route”, is one of many new challenges posed to compilers for arrays of CGR units. 
       FIG.  1    illustrates an example coarse-grained reconfigurable architecture (CGRA) system  100  including a coarse-grained reconfigurable (CGR) processor  110  a compiler  160 , runtime processes  170 , a host  180 , and a memory  190 . CGR processor  110  includes a CGR array such as a CGR array  120 . CGR array  120  includes an array of configurable units in an array level network. CGR processor  110  further includes an IO interface  138 , and a memory interface  139 . CGR array  120  is coupled with IO interface  138  and memory interface  139  through a data bus  130  which may be part of a top-level network (TLN). Host  180  communicates with IO interface  138  using a system data bus  185 , and memory interface  139  communicates with memory  190  using a memory bus  195 . A configurable unit in the CGR array  120  may comprise a compute unit or a memory unit. A configurable unit in the CGR array  120  may also comprise a pattern memory unit (PMU), a pattern compute unit (PCU), or a fused-compute memory unit (FCMU). Further examples include a coalescing unit (CU) and an address generator (AG), which may be combined in an AGCU. A configurable unit may also be reconfigurable. 
     The configurable units in the CGR array  120  may be connected with an array-level network (ALN) to provide the circuitry for execution of a computation graph or a dataflow graph that may have been derived from a high-level program with user algorithms and functions. The high-level program may include a set of procedures, such as learning or inferencing in an artificial intelligence (AI) or machine learning (ML) system. More specifically, the high-level program may include applications, graphs, application graphs, user applications, computation graphs, control flow graphs, dataflow graphs, models, deep learning applications, deep learning neural networks, programs, program images, jobs, tasks and/or any other procedures and functions that may need serial and/or parallel processing. In some implementations, execution of the graph(s) may involve using multiple CGR processors  110 . In some implementations, CGR processor  110  may include one or more ICs. In other implementations, a single IC may span multiple CGR processors  110 . In further implementations, CGR processor  110  may include multiple arrays of configurable units  120 . 
     Host  180  may be, or include, a computer such as further described with reference to  FIG.  2   . Host  180  runs runtime processes  170 , as further referenced herein, and may also be used to run computer programs, such as compiler  160  further described herein with reference to  FIG.  9   . In some implementations, compiler  160  may run on a computer that is similar to the computer described with reference to  FIG.  2    but separate from host  180 . 
     CGR processor  110  may accomplish computational tasks by executing a configuration file  165 . Configuration file  165  may comprise a processor-executable format file suitable for configuring a CGR array  120  of a CGR processor  110 . For the purposes of this description, a configuration file corresponds to a dataflow graph, or a translation of a dataflow graph, and may further include initialization data. Compiler  160  compiles the high-level program to provide the configuration file  165 . In some implementations described herein, a CGR array  120  is configured by programming one or more configuration stores with all or parts of the configuration file  165 . A single configuration store may be at the level of the CGR processor  110  or the CGR array  120 , or a configurable unit may include an individual configuration store. The configuration file  165  may include configuration data for the CGR array  120  and the configurable units in the CGR array  120 , and link the computation graph to the CGR array  120 . Execution of the configuration file  165  by CGR processor  110  causes the array(s) of configurable units  120  ( s ) to implement the user algorithms and functions in the dataflow graph. 
     CGR processor  110  can be implemented on a single integrated circuit die or on a multichip module (MCM). An IC can be packaged in a single chip module or a multichip module. An MCM is an electronic package that may comprise multiple IC dies and other devices, assembled into a single module as if it were a single device. The various dies of an MCM may be mounted on a substrate, and the bare dies of the substrate are electrically coupled to the surface or to each other using for some examples, wire bonding, tape bonding or flip-chip bonding. 
       FIG.  2    illustrates an example of a computer  200 , including an input device  210 , a processor  220 , a storage device  230 , and an output device  240 . Although the example computer  200  is drawn with a single processor, other implementations may have multiple processors. Input device  210  may comprise a mouse, a keyboard, a sensor, an input port (for example, a universal serial bus (USB) port), and any other input device known in the art. Output device  240  may comprise a monitor, printer, and any other output device known in the art. Furthermore, part or all of input device  210  and output device  240  may be combined in a network interface, such as a Peripheral Component Interconnect Express (PCIe) interface suitable for communicating with CGR processor  110 . Input device  210  is coupled with processor  220  to provide input data, which an implementation may store in memory  226 . Processor  220  is coupled with output device  240  to provide output data from memory  226  to output device  240 . Processor  220  further includes control logic  222 , operable to control memory  226  and arithmetic and logic unit (ALU)  224 , and to receive program and configuration data from memory  226 . Control logic  222  further controls exchange of data between memory  226  and storage device  230 . Memory  226  typically comprises memory with fast access, such as static random-access memory (SRAM), whereas storage device  230  typically comprises memory with slow access, such as dynamic random-access memory (DRAM), flash memory, magnetic disks, optical disks, and any other memory type known in the art. At least a part of the memory in storage device  230  includes a non-transitory computer-readable medium (CRM  235 ), such as used for storing computer programs. 
       FIG.  3    illustrates example details of a CGR architecture  300  including a top-level network (TLN  330 ) and two CGR arrays (CGR array  310  and CGR array  320 ). A CGR array comprises an array of CGR units (e.g., PMUs, PCUs, FCMUs) coupled via an array-level network (ALN), e.g., a bus system. The ALN is coupled with the TLN  330  through several AGCUs, and consequently with I/O interface  338  (or any number of interfaces) and memory interface  339 . Other implementations may use different bus or communication architectures. 
     Circuits on the TLN in this example include one or more external I/O interfaces, including I/O interface  338  and memory interface  339 . The interfaces to external devices include circuits for routing data among circuits coupled with the TLN and external devices, such as high-capacity memory, host processors, other CGR processors, FPGA devices, and so on, that are coupled with the interfaces. 
     Each depicted CGR array has four AGCUs (e.g., MAGCU 1 , AGCU 12 , AGCU 13 , and AGCU 14  in CGR array  310 ). The AGCUs interface the TLN to the ALNs and route data from the TLN to the ALN or vice versa. 
     One of the AGCUs in each CGR array in this example is configured to be a master AGCU (MAGCU), which includes an array configuration load/unload controller for the CGR array. The MAGCU 1  includes a configuration load/unload controller for CGR array  310 , and MAGCU 2  includes a configuration load/unload controller for CGR array  320 . Some implementations may include more than one array configuration load/unload controller. In other implementations, an array configuration load/unload controller may be implemented by logic distributed among more than one AGCU. In yet other implementations, a configuration load/unload controller can be designed for loading and unloading configuration of more than one CGR array. In further implementations, more than one configuration controller can be designed for configuration of a single CGR array. Also, the configuration load/unload controller can be implemented in other portions of the system, including as a stand-alone circuit on the TLN and the ALN or ALNs. 
     The TLN is constructed using top-level switches (switch  311 , switch  312 , switch  313 , switch  314 , switch  315 , and switch  316 ) coupled with each other as well as with other circuits on the TLN, including the AGCUs, and external I/O interface  338 . The TLN includes links (e.g., L 11 , L 12 , L 21 , L 22 ) coupling the top-level switches. Data may travel in packets between the top-level switches on the links, and from the switches to the circuits on the network coupled with the switches. For example, switch  311  and switch  312  are coupled by link L 11 , switch  314  and switch  315  are coupled by link L 12 , switch  311  and switch  314  are coupled by link L 13 , and switch  312  and switch  313  are coupled by link L 21 . The links can include one or more buses and supporting control lines, including for example a chunk-wide bus (vector bus). For example, the top-level network can include data, request and response channels operable in coordination for transfer of data in any manner known in the art. 
       FIG.  4    illustrates an example CGR array  400 , including an array of CGR units in an ALN. CGR array  400  may include several types of CGR unit  401 , such as FCMUs, PMUs, PCUs, memory units, and/or compute units. For examples of the functions of these types of CGR units, see Prabhakar et al., “Plasticine: A Reconfigurable Architecture for Parallel Patterns”, ISCA 2017, Jun. 24-28, 2017, Toronto, ON, Canada. Each of the CGR units may include a configuration store  402  comprising a set of registers or flip-flops storing configuration data that represents the setup and/or the sequence to run a program, and that can include the number of nested loops, the limits of each loop iterator, the instructions to be executed for each stage, the source of operands, and the network parameters for the input and output interfaces. In some implementations, each CGR unit  401  comprises an FCMU. In other implementations, the array comprises both PMUs and PCUs, or memory units and compute units, arranged in a checkerboard pattern. In yet other implementations, CGR units may be arranged in different patterns. The ALN includes switch units  403  (S), and AGCUs (each including two address generators  405  (AG) and a shared coalescing unit  404  (CU)). Switch units  403  are connected among themselves via interconnects  421  and to a CGR unit  401  with interconnects  422 . Switch units  403  may be coupled with address generators  405  via interconnects  420 . In some implementations, communication channels can be configured as end-to-end connections, and switch units  403  are CGR units. In other implementations, switches route data via the available links based on address information in packet headers, and communication channels establish as and when needed. 
     A configuration file may include configuration data representing an initial configuration, or starting state, of each of the CGR units that execute a high-level program with user algorithms and functions. Program load is the process of setting up the configuration stores in the CGR array based on the configuration data to allow the CGR units to execute the high-level program. Program load may also require loading memory units and/or PMUs. 
     The ALN includes one or more kinds of physical data buses, for example a chunk-level vector bus (e.g., 512 bits of data), a word-level scalar bus (e.g., 32 bits of data), and a control bus. For instance, interconnects  421  between two switches may include a vector bus interconnect with a bus width of 512 bits, and a scalar bus interconnect with a bus width of 32 bits. A control bus can comprise a configurable interconnect that carries multiple control bits on signal routes designated by configuration bits in the CGR array&#39;s configuration file. The control bus can comprise physical lines separate from the data buses in some implementations. In other implementations, the control bus can be implemented using the same physical lines with a separate protocol or in a time-sharing procedure. 
     Physical data buses may differ in the granularity of data being transferred. In one implementation, a vector bus can carry a chunk that includes 16 channels of 32-bit floating-point data or 32 channels of 16-bit floating-point data (i.e., 512 bits) of data as its payload. A scalar bus can have a 32-bit payload and carry scalar operands or control information. The control bus can carry control handshakes such as tokens and other signals. The vector and scalar buses can be packet-switched, including headers that indicate a destination of each packet and other information such as sequence numbers that can be used to reassemble a file when the packets are received out of order. Each packet header can contain a destination identifier that identifies the geographical coordinates of the destination switch unit (e.g., the row and column in the array), and an interface identifier that identifies the interface on the destination switch (e.g., North, South, East, West, etc.) used to reach the destination unit. 
     A CGR unit  401  may have four ports (as drawn) to interface with switch units  403 , or any other number of ports suitable for an ALN. Each port may be suitable for receiving and transmitting data, or a port may be suitable for only receiving or only transmitting data. 
     A switch unit, as shown in the example of  FIG.  4   , may have eight interfaces. The North, South, East and West interfaces of a switch unit may be used for links between switch units using interconnects  421 . The Northeast, Southeast, Northwest and Southwest interfaces of a switch unit may each be used to make a link with an FCMU, PCU or PMU instance using one of the interconnects  422 . Two switch units in each CGR array quadrant have links to an AGCU using interconnects  420 . The AGCU coalescing unit arbitrates between the AGs and processes memory requests. Each of the eight interfaces of a switch unit can include a vector interface, a scalar interface, and a control interface to communicate with the vector network, the scalar network, and the control network. In other implementations, a switch unit may have any number of interfaces. 
     During execution of a graph or subgraph in a CGR array after configuration, data can be sent via one or more switch units and one or more links between the switch units to the CGR units using the vector bus and vector interface(s) of the one or more switch units on the ALN. A CGR array may comprise at least a part of CGR array  400 , and any number of other CGR arrays coupled with CGR array  400 . 
     A data processing operation implemented by CGR array configuration may comprise multiple graphs or subgraphs specifying data processing operations that are distributed among and executed by corresponding CGR units (e.g., FCMUs, PMUs, PCUs, AGs, and CUs). 
       FIG.  5    illustrates an example  500  of a PMU  510  and a PCU  520 , which may be combined in an FCMU  530 . PMU  510  may be directly coupled to PCU  520 , or optionally via one or more switches. PMU  510  includes a scratchpad memory  515 , which may receive external data, memory addresses, and memory control information (write enable, read enable) via one or more buses included in the ALN. PCU  520  includes two or more processor stages, such as SIMD  521  through SIMD  526 , and configuration store  528 . The processor stages may include ALUs, or SIMDs, as drawn, or any other reconfigurable stages that can process data. 
     Each stage in PCU  520  may also hold one or more registers (not drawn) for short-term storage of parameters. Short-term storage, for example during one to several clock cycles or unit delays, allows for synchronization of data in the PCU pipeline. 
     Referring now to  FIG.  6    which is a block diagram of a compiler stack  600  implementation suitable for generating a configuration file for a CGR processor. Referring also to  FIGS.  7 A- 7 E  which illustrate various representations of an example user program  710  corresponding to various stages of a compiler stack such as the compiler stack  600 . As depicted, compiler stack  600  includes several stages to convert a high-level program (e.g., user program  710 ) with statements  712  that define user algorithms and functions, e.g., algebraic expressions and functions, to configuration data for the CGR units. 
     Compiler stack  600  may take its input from application platform  610 , or any other source of high-level program statements suitable for parallel processing, which provides a user interface for general users. It may further receive hardware description  615 , for example defining the physical units in a reconfigurable data processor or CGRA processor. Application platform  610  may include libraries such as PyTorch, TensorFlow, ONNX, Caffe, and Keras to provide user-selected and configured algorithms. The example user program  710  depicted in  FIG.  7 A  comprises statements  712  that invoke various PyTorch functions. 
     Application platform  610  outputs a high-level program to compiler  620 , which in turn outputs a configuration file to the reconfigurable data processor or CGRA processor where it is executed in runtime processes  630 . Compiler  620  may include dataflow graph compiler  621 , which may handle a dataflow graph, algebraic graph compiler  622 , template graph compiler  623 , template library  624 , and placer and router (PNR)  625 . In some implementations, template library  624  includes RDU abstract intermediate language (RAIL) and/or assembly language interfaces for power users. 
     Dataflow graph compiler  621  converts the high-level program with user algorithms and functions from application platform  610  to one or more dataflow graphs. The high-level program may be suitable for parallel processing, and therefore parts of the nodes of the dataflow graphs may be intrinsically parallel unless an edge in the graph indicates a dependency. Dataflow graph compiler  621  may provide code optimization steps like false data dependency elimination, dead-code elimination, and constant folding. The dataflow graphs encode the data and control dependencies of the high-level program. 
     Dataflow graph compiler  621  may support programming a reconfigurable data processor at higher or lower-level programming languages, for example from an application platform  610  to C++ and assembly language. In some implementations, dataflow graph compiler  621  allows programmers to provide code that runs directly on the reconfigurable data processor. In other implementations, dataflow graph compiler  621  provides one or more libraries that include predefined functions like linear algebra operations, element-wise tensor operations, non-linearities, and reductions required for creating, executing, and profiling the dataflow graphs on the reconfigurable processors. Dataflow graph compiler  621  may provide an application programming interface (API) to enhance functionality available via the application platform  610 . 
     Algebraic graph compiler  622  may include a model analyzer and compiler (MAC) level that makes high-level mapping decisions for (sub-graphs of the) dataflow graph based on hardware constraints. It may support various application frontends such as Samba, JAX, and TensorFlow/HLO. Algebraic graph compiler  622  may also transform the graphs via autodiff and GradNorm, perform stitching between sub-graphs, interface with template generators for performance and latency estimation, convert dataflow graph operations to AIR operation, perform tiling, sharding (database partitioning) and other operations, and model or estimate the parallelism that can be achieved on the dataflow graphs. 
     Algebraic graph compiler  622  may further include an arithmetic or algebraic intermediate representation (AIR) stage that translates high-level graph and mapping decisions provided by the MAC level into explicit AIR/Tensor statements  720  and one or more corresponding algebraic graphs  725  as shown in  FIG.  7 B . In the depicted example, the algebraic graph compiler replaces the Softmax function specified in the user program  710  by its constituent statements/nodes (i.e., exp, sum and div). Key responsibilities of the AIR level include legalizing the graph and mapping decisions of the MAC, expanding data parallel, tiling, metapipe, region instructions provided by the MAC, inserting stage buffers and skip buffers, eliminating redundant operations, buffers and sections, and optimizing for resource use, latency, and throughput. 
     Template graph compiler  623  may translate AIR statements and/or graphs into TLIR statements  730  and/or graph(s)  735  (see  FIG.  7 C ), optimizing for the target hardware architecture, into unplaced variable-sized units (referred to as logical CGR units) suitable for PNR  625 . Meta-pipelines  732  that enable iteration control may be allocated for sections of the TLIR statements and/or corresponding sections of the graph(s)  735 . Template graph compiler  623  may add further information (name, inputs, input names and dataflow description) for PNR  625  and make the graph physically realizable through each performed step. Template graph compiler  623  may for example provide translation of AIR graphs to specific model operation templates such as for general matrix multiplication (GeMM). An implementation may convert part or all intermediate representation operations to templates, stitch templates into the dataflow and control flow, insert necessary buffers and layout transforms, generate test data and optimize for hardware use, latency, and throughput. 
     Implementations may use templates for common operations. Templates may be implemented using assembly language, RAIL, or similar. RAIL is comparable to assembly language in that memory units and compute units are separately programmed, but it can provide a higher level of abstraction and compiler intelligence via a concise performance-oriented domain-specific language for CGR array templates. RAIL enables template writers and external power users to control interactions between logical compute units and memory units with high-level expressions without the need to manually program capacity splitting, register allocation, etc. The logical compute units and memory units also enable stage/register allocation, context splitting, transpose slotting, resource virtualization and mapping to multiple physical compute units and memory units (e.g., PCUs and PMUs). 
     Template library  624  may include an assembler that provides an architecture-independent low-level programming interface as well as optimization and code generation for the target hardware. Responsibilities of the assembler may include address expression compilation, intra-unit resource allocation and management, making a template graph physically realizable with target-specific rules, low-level architecture-specific transformations and optimizations, and architecture-specific code generation. 
     Referring to  FIG.  7 D , the template graph compiler may also determine the control signals  740  and control gates  742  required to enable the CGR units (whether logical or physical) to coordinate dataflow between the CGR units on the communication fabric of a CGR processor. This process, sometimes referred to as stitching, produces a stitched template compute graph  745  with control signals  740  and control gates  742 . In the example depicted in  FIG.  7 D , the control signals  740  include write done signals  740 A and read done signals  740 B and the control gates  742  include ‘AND’ gates  742 A and a counting or ‘DIV’ gate  742 B. The control signals  740  and control gates  742  enable coordinated dataflow between the configurable units of CGR processors such as compute units, memory units, and AGCUs. 
     PNR  625  translates and maps logical (i.e., unplaced physically realizable) CGR units (e.g., the nodes of the logical compute graph  750  shown in  FIG.  7 E ) to a physical layout (e.g., the physical layout  755  shown in  FIG.  7 E ) on the physical chip level e.g., a physical array of CGR units. PNR  625  also determines physical data channels to enable communication among the CGR units and between the CGR units and circuits coupled via the TLN, allocates ports on the CGR units and switches, provides configuration data and initialization data for the target hardware, and produces configuration files, e.g., processor-executable format (PEF) files. It may further provide bandwidth calculations, allocate network interfaces such as AGCUs and virtual address generators (VAGs), provide configuration data that allows AGCUs and/or VAGs to perform address translation, and control ALN switches and data routing. PNR  625  may provide its functionality in multiple steps and may include multiple modules (not shown in  FIG.  6   ) to provide the multiple steps, e.g., a placer, a router, a port allocator, and a PEF file generator. PNR  625  may receive its input data in various ways. For example, it may receive parts of its input data from any of the earlier modules (dataflow graph compiler  621 , algebraic graph compiler  622 , template graph compiler  623 , and/or template library  624 ). In some implementations, an earlier module, such as template graph compiler  623 , may have the task of preparing all information for PNR  625  and no other units provide PNR input data directly. 
     Further implementations of compiler  620  provide for an iterative process, for example by feeding information from PNR  625  back to an earlier module, so that the earlier module can execute a new compilation step in which it uses physically realized results rather than estimates of or placeholders for physically realizable circuits. For example, PNR  625  may feed information regarding the physically realized circuits back to algebraic graph compiler  622 . 
     Memory allocations represent the creation of logical memory spaces in on-chip and/or off-chip memories for data required to implement the dataflow graph, and these memory allocations are specified in the configuration file. Memory allocations define the type and the number of hardware circuits (functional units, storage, or connectivity components). Main memory (e.g., DRAM) may be off-chip memory, and scratchpad memory (e.g., SRAM) is on-chip memory inside a CGR array. Other memory types for which the memory allocations can be made for various access patterns and layouts include cache, read-only look-up tables (LUTs), serial memories (e.g., FIFOs), and register files. 
     Compiler  620  binds memory allocations to unplaced memory units and binds operations specified by operation nodes in the dataflow graph to unplaced compute units, and these bindings may be specified in the configuration data. In some implementations, compiler  620  partitions parts of a dataflow graph into memory subgraphs and compute subgraphs, and specifies these subgraphs in the PEF file. A memory subgraph may comprise address calculations leading up to a memory access. A compute subgraph may comprise all other operations in the parent graph. In one implementation, a parent graph is broken up into multiple memory subgraphs and exactly one compute subgraph. A single parent graph can produce one or more memory subgraphs, depending on how many memory accesses exist in the original loop body. In cases where the same memory addressing logic is shared across multiple memory accesses, address calculation may be duplicated to create multiple memory subgraphs from the same parent graph. 
     Compiler  620  generates the configuration files with configuration data (e.g., a bit stream) for the placed positions and the routed data and control networks. In one implementation, this includes assigning coordinates and communication resources of the physical CGR units by placing and routing unplaced units onto the array of CGR units while maximizing bandwidth and minimizing latency. 
     A first example of accelerated deep learning is using a deep learning accelerator implemented in a CGRA to train a neural network. A second example of accelerated deep learning is using the deep learning accelerator to operate a trained neural network to perform inferences. A third example of accelerated deep learning is using the deep learning accelerator to train a neural network and subsequently perform inference with any one or more of the trained neural network, information from the trained neural network, and a variant of the same. 
     Examples of neural networks include fully connected neural networks (FCNNs), recurrent neural networks (RNNs), graph neural networks (GNNs), convolutional neural networks (CNNs), graph convolutional networks (GCNs), long short-term memory (LSTM) networks, autoencoders, deep belief networks, and generative adversarial networks (GANs). 
     An example of training a neural network is determining one or more weights associated with the neural network, such as by back-propagation in a deep learning accelerator. An example of making an inference is using a trained neural network to compute results by processing input data using the weights associated with the trained neural network. As used herein, the term ‘weight’ is an example of a ‘parameter’ as used in various forms of neural network processing. For example, some neural network learning is directed to determining parameters (e.g., through back-propagation) that are usable for performing neural network inferences. 
     A neural network processes data according to a dataflow graph comprising layers of neurons. Example layers of neurons include input layers, hidden layers, and output layers. Stimuli (e.g., input data) are received by an input layer of neurons and the computed results of the dataflow graph (e.g., output data) are provided by an output layer of neurons. Example hidden layers include rectified linear unit (ReLU) layers, fully connected layers, recurrent layers, graphical network layers, long short-term memory layers, convolutional layers, kernel layers, dropout layers, and pooling layers. A neural network may be conditionally and/or selectively trained. After being trained, a neural network may be conditionally and/or selectively used for inference. 
     Examples of ICs, or parts of ICs, that may be used as deep learning accelerators, are processors such as central processing unit (CPUs), CGR processor ICs, graphics processing units (GPUs), FPGAs, ASICs, application-specific instruction-set processor (ASIP), and digital signal processors (DSPs). The disclosed technology implements efficient distributed computing by allowing an array of accelerators (e.g., reconfigurable processors) attached to separate hosts to directly communicate with each other via buffers. 
       FIG.  8 A  shows one example of a resource graph  800  corresponding to at least one example of a dataflow computing grid. As depicted, the resource graph  800  comprises nodes  802  connected with edges  804 . The nodes  802  represent configurable units including compute units ‘C’, memory units ‘M’ and switch units ‘5’. The edges  804  represent direct physical connections that are able to support dataflow between the configurable units. 
       FIGS.  8 B and  8 C  show two examples of placement graphs  810  suitable for the dataflow computing grid represented in  FIG.  8 A . The placement graphs  810  are essentially subgraphs of the resource graph  800  that could be placed at a variety of positions and orientations on the resource graph  800 . For pedagogical purposes, the depicted edges of the placement graphs are provided with labeled arrows that indicate the flow of data between the configurable units. The depicted examples  810  are for a matrix operation such as matrix multiplication or convolution that operates on two input matrices (labeled A and B in the placement graphs) and computes a result matrix (labeled ‘R’ in the placement graphs). Mathematically the matrix operation could be represented with the equation R=f(A,B). The matrix operation may correspond to an executable sub-graph of a compute graph. 
     Each of the placement graphs  810  shown in  FIGS.  8 B and  8 C  corresponds to a dataflow solution (e.g., for an executable subgraph of a compute graph corresponding to a compute task) that uses two compute units and three memory units. and adjacent switch units. In particular, a memory unit ‘M 1 ’ flows matrix ‘A’ data to the compute units ‘C 1 ’ and ‘C 2 ’ and a memory unit ‘M 2 ’ (concurrently) flows matrix ‘B’ data to the same compute units. Concurrent with computation, each of the compute units ‘C 1 ’ and ‘C 2 ’ flow matrix ‘R’ result data to the memory unit ‘M 3 ’. 
     While both placement graphs  810  have identical functional assignments (tasks) for the compute units and memory units, dataflow for the placement graph  810  shown in  FIG.  8 B  may suffer from congestion at the physical connection  815  that bears data traffic for both matrix ‘A’ and matrix ‘B’. In contrast, the placement graph  810  shown in  FIG.  8 C  avoids bearing traffic for both matrix ‘A’ and matrix ‘B’ on the same physical connection. Consequently, the example placement graphs shown in  FIGS.  8 B and  8 C  may have different throughput rates despite having the same functional assignments for the compute units and memory units. One of skill in the art will also appreciate that the ability to estimate the throughput of a placement graph could improve the placement graph evaluation and selection process. 
       FIG.  8 D  is a block diagram illustrating one example of a placement graph selection and execution system  820  suitable for reconfigurable dataflow computing. As depicted, the placement graph selection and execution system  820  includes an allocation module  825 , a place and route module  830 , a configuration module  835 , an RDU control module  840 , and one or more RDUs  850  comprising a communication fabric  860 , memory units  870  and compute units  880 . The placement graph selection and execution system  820  enables evaluation and selection of placement graphs and deployment of those placement graphs on the configurable units of the RDUs  850 . 
     The allocation module  825  may allocate virtual compute units and memory units to a computing task or a portion thereof. The computing task may be represented with a compute graph that indicates the mathematical operations that are to be executed. The allocation module  825  may function in conjunction with a partitioner that partitions the compute graph into executable sub-graphs and inserts virtual memory units (i.e., buffers) into the compute graph that enables dataflow execution of the sub-graphs on reconfigurable dataflow processing units such as the RDUs  850 . 
     The place and route module  830  may generate various placement graphs corresponding to an executable sub-graph and select the placement graph that best meets the objectives and resources of the computing system  820 . The placement graphs may specify physical compute units, memory units and switch units that correspond to the virtual units of the executable sub-graph. The specified physical compute units, memory units and switch units may be neighbors in a computing grid as indicated by the resource graph  800 . 
     In the depicted example, the place and route module  830  includes a training module  832  and an estimation module  834 . The training module  832  may train a graph neural network (not shown) on various examples of placement graphs and metrics collected for those placement graphs. For example, the training module  832  may use throughput data collected from executing the various placement graphs on a target system. The collected throughput data may be used as training targets to facilitate training the graph neural network. Training may require configuring the graph neural network for each placement graph in the training set. 
     Once trained, the graph neural network may be used to estimate the metrics of placement graphs that were not part of the training set of reference placement graphs. For example, the throughput of candidate placement graphs for an executable sub-graph may be estimated and used in determining a selected placement graph for the executable sub-graph. Estimating may require configuring the graph neural network for each placement graph that is estimated. 
     The configuration module  835  may generate configuration information for the configuration units specified in the selected placement graphs. The RDU control module  850  may communicate the configuration information to the RDUs  850  and initiate dataflow in the computing grid. The communication fabric  860  may comprise switch units (not shown) that enable communication between the RDU control module  850  and memory units  870  and compute units  880  within the RDU(s)  860 . One of skill in the art will appreciate that the placement graphs specified for execution may be relocated at runtime to a currently available RDU and/or a currently available region with a computing grid (e.g., tile) of an RDU. The relocation may preserve the relative positions and connectivity of the configurable units specified by the placement graphs. 
       FIG.  9    is a flowchart of one example of a placement graph selection method  900  suitable for reconfigurable dataflow computing. As depicted, the placement graph selection method  900  includes obtaining ( 910 ) a set of reference placement graphs for one or more computing tasks, determining ( 920 ) a throughput value for each reference placement graph, configuring and training ( 930 ) a graph neural network, estimating ( 940 ) the throughput for one or more candidate placement graphs, selecting ( 950 ) a placement graph, generating ( 960 ) configuration information and conducting ( 970 ) the computing task corresponding to the selected placement graph. While the depicted method illustrates estimating a throughput metric for candidate placement graphs, the method may be adapted to estimate other placement graph metrics such as bandwidth and resource utilization. 
     Obtaining ( 910 ) a set of reference placement graphs may include collecting a set of reference placement graphs that correspond to a target computing system such as a reconfigurable dataflow computing system. The reference placement graphs may correspond to one or more computing tasks. Determining ( 920 ) a throughput value for each reference placement graph may include conducting the computing task(s) on the reconfigurable dataflow computing system using each reference placement graph and measuring the corresponding throughput. 
     Configuring and training ( 930 ) a graph neural network may include configuring the embedding and aggregation stages of graph neural network to correspond to each reference placement graph (for more information, see  FIGS.  10 A and  10 B  and the associated description) and training the graph neural network using each corresponding throughput value as a training target to produce a trained graph neural network. Estimating ( 940 ) the throughput for one or more candidate placement graphs may include configuring the trained graph neural network for each candidate placement graph and estimating the corresponding throughput using the trained graph neural network. 
     Selecting ( 950 ) a placement graph may include using the estimated throughput values along with resource requirements for each corresponding candidate placement graph to determine the selected placement graph from among the candidate placement graphs. Selecting ( 950 ) may include using the trained graph neural network produced in step  930  to produce the estimate throughput values in conjunction with a place-and-route (PNR) process such as conducted by the PNR module  625  shown in  FIG.  6   . 
     Generating ( 960 ) configuration information may include generating configuration information according to selected placement graph. Conducting ( 970 ) the computing task may include conducting the computing task with the reconfigurable dataflow computing system according to selected placement graph. Conducting ( 970 ) the computing task may involve conducting a set of dataflow sub-tasks that are executed in topological (i.e., dependency) order as defined by a compute graph or user program corresponding to the selected placement graph. Conducting the dataflow sub-tasks may include leveraging both pipelined and parallel configurable units that execute the computing task. 
       FIG.  10 A  is a block diagram of one example of a graph neural network  1000  suitable for estimating placement graph metrics such as throughput in a reconfigurable dataflow computing system. The depicted graph neural network  1000  includes an embedding stage  1000 A, an aggregation stage  1000 B and a regressor stage  1000 C. As will be subsequently described, the embedding stage  1000 A and the aggregation stage  1000 B of the graph neural network  1000  may be configured for specific placement graphs during training and when estimating placement graph metrics. In contrast, the regressor stage  1000 C is independent of the placement graph and need not be configured for the placement graph being trained on, or estimated for. 
     The embedding stage  1000 A includes a branch  1002  for each configuration unit in a placement graph whether a reference placement graph used during training or a candidate placement graph used for estimating. Each branch  1002  includes an attribute register  1010 , a set of embedding tables  1020  and a linear transform module  1030 . 
     The attribute register  1010  receives and stores a set of attributes for each configuration unit in a placement graph. Each attribute may be an index and need not be descriptive. Examples of attributes include a configurable unit type, a dataflow task, an end-to-end (e2e) attribute and a routing length. The configurable unit type specifies the type of configurable unit such as a compute unit, memory unit or switch unit. The dataflow task identifies the task assigned to the configurable unit. The e2e attribute indicates a sink unit&#39;s readiness to receive incoming packets end-to-end from the source. The higher the readiness, the more spaces the unit will have to receive data. The routing length indicates the traveling latency from sender to receiver. 
     Referring now to  FIG.  10 B  as well as  10 A, each set of embedding tables  1020  includes a table for each attribute within the attribute register  1010 . Within each attribute table a feature vector may be stored for each possible value for that attribute. For example, as shown in the example illustrated in  FIG.  10 B , if there are three possible configuration unit types three feature vectors would be stored in the configuration unit type embedding table  1020 A. Similarly, if there are 10 possible dataflow tasks, 10 feature vectors would be stored in the dataflow task embedding table  1020 B. Lastly, with 5 possible routing lengths 5 feature vectors would be stored in the routing length embedding table  1020 C. One of skill in the art will appreciate that the depicted embedding tables  1020  could each be a portion of a larger table. 
     Each of the linear transform modules  1030  may receive a feature vector for each of the attributes in the attribute register  1010  (e.g., as a combined feature vector) and generate a composite feature vector therefrom. The length of the composite feature vector may be different than individual or combined attribute feature vectors. In some cases, the linear transform modules  1030  are multi-layer perceptron&#39;s. 
     One of skill in the art will appreciate that each branch  1002  may have the same set of embedding tables  1020  with identical feature vector entries as well at the same linear transform module  1030  with identical (transformation) weights. Consequently, during training the learning that occurs to the feature vectors stored in the embedding tables  1020  and the weights used in the linear transform module  1030  of each branch  1002  results in training for every branch  1002 . 
     The aggregation stage  1000 B includes a graph layer  1040  and multiple message passing layers  1050  and a reduction layer  1060 . The graph layer  1040  receives the composite feature vector for each configuration unit and stores it in a corresponding node in the graph neural network. The graph layer  1040  is also configured with the connectivity information from the placement graph being trained or estimated. The message passing layers  1050  leverage that connectivity information to exchange and aggregate the composite feature vectors. For example, the composite feature vectors may be exchanged between configuration units that are neighbors within the placement graph and the feature vector with the maximum value may be retained. By conducting m passes of aggregation, each node in the graph neural network will retain the maximum (i.e., aggregated) composite feature vector that is within distance m within the graph neural network. The reduction layer  1060  averages all of the aggregated composite feature vectors to produce an average feature vector for the entire (reference or candidate) placement graph. 
     The regressor stage  1000 C includes multiple perceptron layers  1070 . The perceptron layers produce a metric for the placement graph such as estimated throughput. During training the estimated (throughput) metric is compared with the measured (throughput) metric and the error is backpropagated to update the weights in the perceptron layers  1070 , the linear transform modules  1030  and the entries in the embedding tables  1020 . One of skill in the art will appreciate that initially, before training commences, the weights and embedding table entries may be set to random values. 
     One of skill in the art will appreciate that the depicted graph neural network  1000  leverages learning for the configuration units individually within a placement graph as well as the topology of the placement graph as a whole. 
     The examples disclosed herein can include one or more features, alone or in combination. The examples disclosed herein include a system for estimating throughput for placement graphs for a reconfigurable dataflow computing system that includes:
         a training module configured to obtain a set of reference placement graphs for one or more computing tasks   the training module configured to conduct the computing task(s) on the reconfigurable dataflow computing system using each reference placement graph of the set of reference placement graphs to determine a corresponding throughput value for each reference placement graph   the training module configured to train a graph neural network using each corresponding throughput value as a training target to produce a trained graph neural network   an estimation module configured to configure the trained graph neural network for a candidate placement graph corresponding to a target computing task   the estimation module configured to use the trained graph neural network to estimate a throughput for the target computing task conducted on the reconfigurable dataflow computing system according to the candidate placement graph       

     Optional features for the above system include:
         a configuration module configured to generate configuration information that enables the reconfigurable dataflow computing system to conduct the target computing task according to the candidate placement graph
           an RDU control (runtime) module configured to configure the reconfigurable dataflow computing system using the configuration information
               the RDU control module configured to launch execution of the target computing task with the reconfigurable dataflow computing system according to the candidate placement graph   
               wherein the configuration information incorporates a selected routing for the candidate placement graph   
           wherein nodes in a placement graph used for training or estimating correspond to a set of configurable units
           wherein the set configurable units comprises one or more compute units, one or more memory units and one or more switch units   wherein an embedding stage of the graph neural network and the trained graph neural comprises a branch for each configurable unit of the set of configurable units
               wherein inputs to each branch of the embedding stage comprise a set of configuration unit attributes for a configuration unit of the set of configurable units
                   wherein the set of configuration unit attributes comprise one or more of configurable unit type, a dataflow task, an e2e attribute and a routing length   wherein each branch of the embedding stage uses a set of embedding tables comprising an embedding table for each configuration unit attribute of the set of configuration unit attributes   wherein each branch of the embedding stage generates a composite feature vector from a set of embedding vectors provided by the set of embedding tables used by the branch   wherein the feature vector is generated using a multi-layer perceptron   wherein the set of embedding tables comprise one or more of a configurable unit type table, a dataflow task table, an e2e attribute table and a routing length table   
                   
               wherein the graph neural network and the trained graph neural network comprise a graph aggregation stage
               wherein the graph aggregation stage determines an aggregated feature vector for each node in the placement graph to produce aggregated feature vectors
                   wherein the graph aggregation stage determines the aggregated feature vectors by exchanging messages between each pair of connected nodes in the placement graph   wherein the graph aggregation stage conducts two or more passes of exchanging messages   wherein the graph aggregation stage averages the aggregated feature vectors to produce an average feature vector for the placement graph   wherein the regressor stage estimates the throughput for the placement graph from the average feature vector using a multi-layer perceptron   
                   
               
           wherein the training module updates weights within the regressor stage and the embedding stage of the graph neural network via backpropagation       

     The embodiments disclosed herein include a method for estimating throughput for placement graphs for a reconfigurable dataflow computing system, the method comprising:
         obtaining a set of reference placement graphs for at least one computing task   determining a corresponding throughput value for each reference placement graph   configuring a graph neural network for each reference placement graph and training the graph neural network using each corresponding throughput value as a training target to produce a trained graph neural network   configuring the trained graph neural network for a candidate placement graph corresponding to a target computing task   using the trained graph neural network to estimate a throughput for the target computing task conducted on the reconfigurable dataflow computing system according to the candidate placement graph       

     Optional features for the above method include:
         wherein determining a corresponding throughput value for each reference placement graph comprises executing a computing task on the reconfigurable dataflow computing system using the reference placement graph   generating configuration information that enables the reconfigurable dataflow computing system to conduct the target computing task according to the candidate placement graph
           configuring the reconfigurable dataflow computing system using the configuration information
               conducting the target computing task with the reconfigurable dataflow computing system according to the candidate placement graph   
               wherein the configuration information incorporates a selected routing for the candidate placement graph   
           wherein nodes in a placement graph used for training or estimating correspond to a set of configurable units
           wherein the set configurable units comprises one or more compute units, one or more memory units and one or more switch units   wherein an embedding stage of the graph neural network and the trained graph neural comprises a branch for each configurable unit of the set of configurable units
               wherein inputs to each branch of the embedding stage comprise a set of configuration unit attributes for a configuration unit of the set of configurable units
                   wherein the set of configuration unit attributes comprise one or more of configurable unit type, a dataflow task, an e2e attribute and a routing length   wherein each branch of the embedding stage uses a set of embedding tables comprising an embedding table for each configuration unit attribute of the set of configuration unit attributes   
                   
               
               

     As will be appreciated by those of ordinary skill in the art, aspects of the various embodiments described herein may be embodied as a system, device, method, or computer program product apparatus. Accordingly, elements of the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, or the like) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “apparatus,” “circuit,” “circuitry,” “module,” “computer,” “logic,” “FPGA,” “unit,” “system,” or other terms. Furthermore, aspects of the various embodiments may take the form of a computer program product embodied in one or more computer-readable medium(s) having computer program code stored thereon. The phrases “computer program code” and “instructions” both explicitly include configuration information for a CGRA, an FPGA, or other programmable logic as well as traditional binary computer instructions, and the term “processor” explicitly includes logic in a CGRA, an FPGA, or other programmable logic configured by the configuration information in addition to a traditional processing core. Furthermore, “executed” instructions explicitly includes electronic circuitry of a CGRA, an FPGA, or other programmable logic performing the functions for which they are configured by configuration information loaded from a storage medium as well as serial or parallel execution of instructions by a traditional processing core. 
     Any combination of one or more computer-readable storage mediums may be utilized. A computer-readable storage medium may be embodied as, for example, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or other like storage devices known to those of ordinary skill in the art, or any suitable combination of computer-readable storage mediums described herein. In the context of this document, a computer-readable storage medium may be any tangible medium that can contain, or store, a program and/or data for use by or in connection with an instruction execution system, apparatus, or device. Even if the data in the computer-readable storage medium requires action to maintain the storage of data, such as in a traditional semiconductor-based dynamic random-access memory, the data storage in a computer-readable storage medium can be considered to be non-transitory. A computer data transmission medium, such as a transmission line, a coaxial cable, a radio-frequency carrier, and the like, may also be able to store data, although any data storage in a data transmission medium can be said to be transitory storage. Nonetheless, a computer-readable storage medium, as the term is used herein, does not include a computer data transmission medium. 
     Computer program code for carrying out operations for aspects of various embodiments may be written in any combination of one or more programming languages, including object-oriented programming languages such as Java, Python, C++, or the like, conventional procedural programming languages, such as the “C” programming language or similar programming languages, or low-level computer languages, such as assembly language or microcode. In addition, the computer program code may be written in VHDL, Verilog, or another hardware description language to generate configuration instructions for an FPGA, CGRA IC, or other programmable logic. The computer program code if converted into an executable form and loaded onto a computer, FPGA, CGRA IC, or other programmable apparatus, produces a computer implemented method. The instructions which execute on the computer, FPGA, CGRA IC, or other programmable apparatus may provide the mechanism for implementing some or all of the functions/acts specified in the flowchart and/or block diagram block or blocks. In accordance with various implementations, the computer program code may execute entirely on the user&#39;s device, partly on the user&#39;s device and partly on a remote device, or entirely on the remote device, such as a cloud-based server. In the latter scenario, the remote device may be connected to the user&#39;s device through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). The computer program code stored in/on (i.e. embodied therewith) the non-transitory computer-readable medium produces an article of manufacture. 
     The computer program code, if executed by a processor, causes physical changes in the electronic devices of the processor which change the physical flow of electrons through the devices. This alters the connections between devices which changes the functionality of the circuit. For example, if two transistors in a processor are wired to perform a multiplexing operation under control of the computer program code, if a first computer instruction is executed, electrons from a first source flow through the first transistor to a destination, but if a different computer instruction is executed, electrons from the first source are blocked from reaching the destination, but electrons from a second source are allowed to flow through the second transistor to the destination. So, a processor programmed to perform a task is transformed from what the processor was before being programmed to perform that task, much like a physical plumbing system with different valves can be controlled to change the physical flow of a fluid.