Device array topology configuration and source code partitioning for device arrays

An array of field programmable gate array (FPGA) devices configured for execution of a source code. The array includes two or more FPGA devices, a host processor, and a host interface logic. The FPGA devices are configured to execute a parallelized portion of the source code partitioned among the FPGA devices based on data rates of computing elements of the source code, computational performance of the FPGA devices, the input/output (I/O) bandwidth of the FPGA devices. The FPGA devices include a memory bank addressable by a global memory address space for the array and an array interconnect that enables the computing elements executed by each of the FPGA devices to be programmed with a uniform address space of a global memory of the array and utilization of the global memory by the FPGA devices. The host interface logic connects the host processor with one of the FPGA devices.

FIELD

The embodiments discussed herein are generally related to device array topology configuration and source code partitioning for the device arrays. In particular, some embodiments related to array topology configuration for arrays of field programmable gate array (FPGA) devices and source code partitioning for arrays of FPGA devices.

BACKGROUND

Heterogeneous computing and parallel code acceleration has been advancing for general purpose processors (GPPs), graphical processing units (GPUs), digital signal processors (DSPs), and field programmable gate array (FPGA) devices. These advances in heterogeneous computing and parallel code acceleration have led to development in parallel software languages such as OpenCL and CUDA. Some of the parallel software languages (e.g., OpenCL) are portable across one or more acceleration platforms while other (e.g., CUDA) are proprietary a type of GPUs. In addition, high level synthesis (HLS) for FPGA devices has advanced to enable creation of accelerated computing systems from C/C++ code. However, heterogeneous computing and parallel code acceleration is limited by hardware implementation in which such computing is performed.

SUMMARY

According to an aspect of an embodiment, an array of field programmable gate array (FPGA) devices is configured for execution of a source code. The array includes two or more FPGA devices, a host processor, and a host interface logic. The FPGA devices are configured to execute a parallelized portion of the source code that is partitioned among the FPGA devices based on data rates of computing elements of the source code, computational performance of the FPGA devices, the input/output (I/O) bandwidth of the FPGA devices. Two or more of the FPGA devices include a memory bank that is addressable by a global memory address space for the array and includes an array interconnect configured to enable the computing elements that are executed by each of the FPGA devices to be programmed with a uniform address space of a global memory of the array and utilization of the global memory by each of the FPGA devices. The host interface logic is configured to connect the host processor with one or more of the FPGA devices.

all arranged in accordance with at least one embodiment described herein.

DESCRIPTION OF EMBODIMENTS

Heterogeneous systems are generally limited to a single field programmable gate array (FPGA) device. Although multiple parallel programs or kernels may be executing inside the FPGA device, which may provide significant acceleration comparable to a graphical processing unit (GPU), the performance of the heterogeneous system may be limited by a size of programmable logic fabric and finite dedicated resources of the single FPGA device. The limited performance of the single FPGA device may be undesirable for development of solutions to parallel tasks and applications that involve larger memory and faster parallel execution. Programmable logic devices such as FPGA devices are inherently free from the size limitations that may be present in semiconductor devices.

A GPU-based system can include several GPU units. However, these GPU units are generally connected by a proprietary scalable link interface (SLI) or a CrossFire interconnect. These GPU-based systems may be also limited by a maximum number of GPUs as determined by a vendor. The maximum number of GPUs may not be increased.

Accordingly, some embodiments described herein include multiple programmable logic devices such as FPGA devices (hereinafter “member devices” or “FPGA devices”) implemented in heterogeneous computing systems. The heterogeneous computing systems may include, for instance, arrays of the devices. The arrays may include two-dimensional, three-dimensional, n-dimensional, or other array topologies such as cluster topologies. The arrays may include additional logic and an interconnect between the devices. The additional logic and the interconnect may expand global memory of each of the devices and maintain a unified address memory space or a unified kernel global memory address space for the array. The arrays may be configured according to a parallel programming task.

In some embodiments, the global memory address space may be expanded for a host processor that interfaces with the array. Accordingly, the array may operate with a shared virtual memory that includes external memory banks and/or local memory blocks of one or more the FPGA devices in the array.

A source code may be partitioned for parallel execution by the array. In some embodiments, a topology determining and source code partitioning module (topology/partitioning module) is implemented to partition the source code. The topology/partitioning module may include a code-in code-out type module that may be configured to convert a single code segment or original kernel code into a multiple code segments or segmented kernels to be executed by the individual member devices of the array. One or more of the code segments or the segmented kernels may then be compiled into a hardware circuit by a single device flow. In some embodiments, compiling the code segments or the segmented kernels may be accomplished as described in Desh Singh et al, Tutorial: Harnessing the Power of FPGA Using Alter's OpenCL Compiler, Altera, 2013 and Altera SDK for OpenCL Programming Guide, OCL002-13.1.0, 2013.11.04.

Some embodiments disclosed herein related to a tool that enables design of the arrays described above. The array may be designed based on one or more processing specifications and an optimal partitioning of a source code among member devices that may be included in the array.

In some embodiments, the topology/partitioning module may optimize a number of work items and a number of compute units for a particular source code. Using the optimized number of work items and/or compute units, an array configuration may be formulated. Specifically, the number of work items and a number of compute units may be optimized to maximize resource utilization of each device of the array. The topology/partitioning module may include an autonomous mode and an interactive mode with graphical user interface (GUI). These and other embodiments are described with reference to the appended drawings.

FIG. 1illustrates an example FPGA device150that may be implemented in a heterogeneous computing system (system)100. The system100generally includes the FPGA device150, along with a host processor101and external memory banks104A-104C (generally, external memory bank104or external memory banks104). The FPGA device150may include a global memory arbiter and interconnect (global interconnect)102. The global interconnect102may connect to a host interface152, memory controllers103A-103C (generally, memory controller103or memory controllers103), and the array interconnect111. Additionally, the FPGA device150may include a local memory arbiter and interconnect (local interconnect)106. The local interconnect106may connect to local memory blocks107A-107C (generally, local memory block107or local memory blocks107).

The external memory banks104may be utilized during processes performed by or initiated by the host processor101. Accordingly, the global interconnect102may enable the host processor101to access the external memory banks104via the host interface152and one or more memory controllers103. Examples of the external memory banks104may include double data rate (DDR) memory banks, quad data rate (QDR) memory banks, or any other suitable memory bank.

The system100may execute a parallel portion of a source code, a portion of which is generally indicated by item number170and referred to as source code170. Execution of the source code170may be performed by executing one or more kernels or groups of kernels105A-105C (generally, kernel105or kernels105) and/or one or more pipes110A-110C (generally, pipe110or pipes110). The kernels105may load data and store data to and from the external memory banks104. Additionally, the kernels105may load data and store data to and from local memory blocks107via the local interconnect106. The pipes110may be used to communicate data between the kernels105. Additionally, the global interconnect102and the local interconnect106may have an arbitration logic that resolves the contentions during simultaneous access requests by the host processor101, the kernels105, and the array interconnect111.

The array interconnect111and/or the high speed serial link112(inFIG. 1, HS serial links112), enable access to external memory banks104and local memory blocks107of other FPGA devices and processes implemented by remote host processors. For example, in some embodiments, without the array interconnect111or high speed serial link112, the FPGA device150may be limited to the local memory blocks107of the FPGA device150. Additionally, the FPGA device150may be limited to processes implemented by or controlled by the host processor101. The array interconnect111and/or the high speed serial link112may be configured to connect or communicative couple the FPGA device150to one or more other FPGA devices.

For example, the array interconnect111and/or the high speed serial link112may include one or more ports. The ports may connect the FPGA device150to one or more other FPGA devices or to cards with FPGA devices to form arrays, which may be capable of executing the source code170. In some embodiments, the source code170may be segmented into the kernels105. A portion of the kernels105segmented from the source code170including a first kernel105A and a second kernel105B may be implemented by the FPGA device150, while other of the kernels105may be implemented by other FPGA devices in the array. Processing the kernels105in the FPGA device150may be performed using the local interconnect106, the local memory blocks107, the global interconnect102, the external memory banks104, or some combination thereof. Moreover, the first and second kernels105A and105B may be implemented using input data communicated from another member device in the array and/or may communicate output data resulting from execution of the first and second kernels105to the other member devices of the array.

The array interconnect111can be implemented using a global memory address expansion protocol. The global memory address expansion protocol may extend the physical global memory address of the FPGA device150into virtual or physical addresses of the entire array. This address translation may enable a unified address memory space for the array. In some embodiments, the array interconnect111can be implemented per specification of one or more known standards, for example, Infiniband or a custom interconnect protocol.

The ports in the array interconnect111and/or the high speed serial link112may utilize electrical or optical serial connection. The optical serial connection may be useful for extending an array beyond a physical size of a card cage, equipment rack, data room, or beyond a single geographical location. The array interconnect111may have a broadcast capability to replicate the data from the host processor101or any individual FPGA device to some or all of the FPGA devices of the array. This capability may reduce latency of data exchange during initialization and normal operation.

In the depicted embodiment, the FPGA device150includes memory logic that further includes a first external memory bank104A, a second external memory bank104B, and a Kth external memory bank104C. Similarly, the memory logic of the FPGA device150includes a first memory controller103A, a second memory controller103B, and a Kth memory controller103C. Similarly still, the memory logic includes a first local memory block107A, a second local memory block107B, and an Mth local memory block107C. Inclusion of the Kth and Mth component along with the ellipses is meant to indicate that the memory logic may include more than three external memory banks104, more than three memory controllers103, more than three local memory blocks107, or some combination thereof. Additionally, in the depicted embodiment, the FPGA device150includes the array interconnect111, the high-speed serial link112, the global interconnect102, the memory controllers103, and the local interconnect106as separate components. In some embodiments, one or more of these components and/or functions attributed to these components may be combined into few components or may be separated into more individual components.

FIG. 2illustrates an example array200that may include one or more of the FPGA devices150ofFIG. 1. The array200includes eight of the FPGA devices150discussed with reference toFIG. 1. The FPGA devices150are interconnected into a two-dimensional array include two rows and four columns. As used herein the convention [number row×number of columns] is used to describe two dimensional arrays. For example, the array200is a [2×4] array. The array200resides on two cards201. Each of the cards201includes a [2×2] array of FPGA devices150. The FPGA devices150may include ports202. The ports202may be configured to expand global memory of each of the FPGA devices150. Additionally, the ports202may be utilized to expand the array200by adding additional cards (e.g., card201) having one or more FPGA devices.

In some embodiments, the array200may include more than eight or fewer than eight FPGA devices150, which may be determined based on the data rates of computing elements of the source code, computational performance of the FPGA devices150, the input/output (I/O) bandwidth of the FPGA devices150. The array200may take other topologies and dimensions. Some details of these arrays are discussed with reference toFIGS. 7-10.

One or more of the FPGA devices150may include the host interface152to interface with the host processor101. An example of the host interface152may include a peripheral component interconnect express (PCIe) endpoint logic or another suitable logic. In addition, one or more of the FPGA devices150may include framer logic205. The framer logic205may be configured to interface with an optical transport network and/or an optical transport network interface204(inFIG. 2, “optical network interface204”). An example of the framer logic205may include an optical transport network (OTN) framer and an associated Generic Framing Procedure (GFP) of a client signal such as user datagram protocol/transmission control protocol (UDP/TCP) stack for 1 GE-100 GE Ethernet. Additionally still, one or more of the FPGA devices150may include network interface logic207to interface with an optical data network interface206and associated forwarding data plane and control plane protocol such as OpenFlow. Other telecomm, data, storage interfaces such as Fiber Channel and custom communication protocols can have connections to the array200and/or one or more of the FPGA devices150included therein.

One or more of the FPGA devices150may be coupled to one or more of the external memory banks104as described with reference toFIG. 1. The external memory banks104may be allocated entirely or partially to a global memory, which may be addressable by a unified address memory space of the array200. Having global memory interconnect reduces interface of the host processor101to the array200. Accordingly, in some embodiments, only one of the FPGA devices150is connected to the host processor101. In other embodiments more than one of the FPGA devices150may be connected to the host processor101. In embodiments having multiple FPGA devices150connected to the host processor101, multiple types of connections may be implemented between the FPGA devices150and the host processor101(e.g., PCIe and the like). Similarly, embodiments of the array200may include one or more of the FPGA devices150that may be connected to the optical network204and/or the optical data interface206via multiple types of the connections.

In the array200, one or more processes may occur sequentially. In addition the processes may occur in parallel. For example, in the example array200depicted inFIG. 2, a dataflow direction250may be a direction in which processes occur sequentially. In addition, one or more of the processes may occur in one or more parallel process directions252. In the embodiment ifFIG. 2, there is only one parallel process direction252. However, arrays including larger directions may include multiple parallel process directions252.

In some embodiments, the dataflow direction250is orthogonal to the parallel process direction252. Such processing may have a dominant dataflow direction250in the array200. Accordingly, partitioning of source code among the FPGA devices150may include multiple instructions among kernels, parallel execution by multiple kernels, kernel vectorization, generic loop unrolling with indexing, or some combination thereof in the dataflow direction250and/or the parallel process direction252. In some embodiments, the vectorization of the source code may be performed in the dataflow direction250. In the parallel process direction252, generic loop unrolling with indexing may be performed during the partitioning. The indexing may correspond to individual packets or to a simple kernel replication, for example.

Some examples of the processing with dominant data direction may include deep packet inspection, data search and information filtering algorithms at line rate. The data search algorithm may be executed by the FPGA device150on a real-time network traffic. The data search algorithm may be replicated by broadcasting it to one or more parallel kernels in the array200. One or more data search patterns may be preloaded into the local or global memory (e.g.,107and104, respectively). Thus, a data search algorithm performed by the array200may be conducted substantially simultaneously for one or more data patterns. Such data search algorithm may be performed in parallel or sequential fashion on the live traffic as well as on recorded data collected from the live traffic at prior time.

FIG. 3is a block diagram of an example partitioning of a source code300that may be implemented by a computing device320. Partitioning the source code300may include a process by which parallelized portions302of the source code300are allocated to one or more FPGA devices306and308in an array topology354(“topology354” inFIG. 3). For example, in the example shown inFIG. 3, the array topology354includes a first column FPGA device306and a second column FPGA device308. The first column FPGA device306and the second column FPGA device308are collectively referred to as FPGA device306/308. The FPGA devices306/308may be substantially similar to the FPGA device150discussed elsewhere herein. As depicted inFIG. 3, the first column FPGA device306may be coupled to the second column FPGA device308via the array interconnect111. The coupling between the first column FPGA device306and the second column FPGA device308may enable data and memory transfers between the first column FPGA device306and the second column FPGA device308via the array interconnect111. The first column FPGA device306, the second column FPGA device308, and the array interconnect111may be included in the array topology354.

A topology/partitioning module322may receive as input the source code300and one or more processing specifications310. The topology/partitioning module322may partition the source code300based on the processing specification310. Additionally, the topology/partitioning module322may be configured to determine the array topology354that is configured to execute the source code300according to the partitioning and the processing specifications310. Some examples of the processing specifications310may include a number of packets per second arriving at a network node, a number of packets leaving a network node, a number of parallel data storage interfaces that are concurrently active, an instantaneous bit-rate of a storage data stream, an aggregate amount of data per second at an input to the array, and a speed at which an answer is required to be derived.

Additionally, the topology/partitioning module322may be configured to segment or re-segment the parallelized portion302of the source code300. The segmenting the parallelized portion302may generate a computing element such as kernels350A-350E (generally, kernel350or kernels350, inFIG. 3, K1, K2, K3, K4and KN). The kernels350may then may be executed by the FPGA devices306/308. The topology/partitioning module322may also be configured to determine whether to include additional code between the kernels350. For example, as depicted inFIG. 3, pipes352A-352E (generally, a storage element such as FIFO or a register or a pipe352or pipes352) may be added to provide communication of intermediate results between the kernels350.

For example, the topology/partitioning module322may partition the kernels350among the FPGA device306/308in the array topology354. However, in some circumstances, the array topology354cannot meet one or more processing specification. In these circumstances, the topology/partitioning module322may modify the array topology354by adding one or more FPGA devices306/308, adding a row of FPGA devices306/308, adding a column of FPGA devices306/308, or otherwise modification to the array topology354such that the processing specification can be met. Additionally or alternatively, the topology/partitioning module322may segment the parallelized portion302into more kernels350, which may help meet the processing specifications310. Additionally or alternatively, the topology/partitioning module322may include one or more storage elements such as first in, first outs (FIFOs) or pipes352, which may help meet the processing specifications310. Although only pipes352are depicted inFIG. 3, one or more of the pipes352may be substituted for or include one or more FIFOs.

The topology/partitioning module322may be configured to partition the source code300and determine the array topology354according to a maximum speedup factor. The maximum speedup factor may be based on optimization among data rates330A-330H (generally, data rate330or data rates330), computational capabilities of the FPGA devices306/308, and I/O pipe bandwidth (330A and330C but not330B) in the FPGA devices306/308. InFIG. 3, the data rates330are represented in by item numbers pointing to arrows connecting to pipes352and the kernels350that represent a dataflow direction.

The topology/partitioning module322may analyze the source code300to determine the data rates330as executed by the array topology354while taking into consideration computational performance and/or I/O pipe bandwidth of the FPGA devices306/308. Based on the data rates330, the computational performance of the FPGA devices306/308, the I/O pipe bandwidth of the FPGA devices306/308, or some combination thereof, the topology/partitioning module322may derive optimal utilization of the FPGA devices306/308, whether to include the pipes352, and whether to modify the array topology354.

FIG. 3depicts a partitioning of the source code300. The source code300may include a computation sequence such as those found in the communication signal chains. The source code300may include the parallelized portion302and a serialized portion304. The serialized portion304may be performed by a host processor such as the host processor101ofFIG. 1. The topology/partitioning module322may segment the parallelized portion302into the kernels350, which may be partitioned by the topology/partitioning module322to be executed by the FPGA devices306/308.

The pipes352may be configured to control the data rate330between the kernels350. In general, execution of the source code300and accordingly execution of one or more kernels350may involve exchange of input/output data samples or intermediate results from one kernel350to one or more subsequent kernels350and/or between the FPGA devices306/308. The data rates330between the kernels350may vary. For example, a first kernel350A may include a multiplication computation of two one-byte numbers. An intermediate result of the first kernel350A may be a two-byte number, which may be input to a second kernel350B. The second kernel350B may include a same sampling frequency as the first kernel350A, however the second kernel350B may be receiving a number that is twice the length. Accordingly, a first pipe352A and/or a second pipe352B may be included to synchronize and/or buffer the data rates330A and/or330B of the first and second kernels350A and350B.

Storage element may be added between the kernels350. For example, the storage element can be a memory location in a first in, first out (FIFO) or a digital flip-flop. In the depicted embodiment, the pipe352may be implemented as a FIFO, and may accordingly include multiple storage elements. In some embodiments, the storage elements may include similar components implemented between the kernels350.

In the array topology354, the pipes352are included prior to each of the kernels350. The topology/partitioning module322may determine whether to include the pipes352based on the data rates330, the computational performance of the FPGA devices306/308, the I/O pipe bandwidth of the FPGA devices306/308, or some combination thereof. Accordingly, in some embodiments, one or more kernels350may not be preceded by one of the pipes350

The exchange of samples, data or intermediate results of computations between the FPGA devices306/308may be performed by the array interconnect111. The array interconnect111may include a low latency and high-speed interconnect as well as dedicated dataflow interconnect. The array interconnect111may also be utilized by a global memory. In some embodiments, samples and intermediate results may have to have higher priority over global memory accesses. However, global memory access rate and expected dataflow rate are evaluated by topology/partitioning module322to make the decision whether to permit sharing of the interconnect111or to direct dataflow to the dedicated interconnect. The array interconnect111may be configured to have small footprint. Some additional details of an example array interconnect111are provided elsewhere herein.

One or more synchronization kernels (inFIG. 3, “K_sync”)372A and372B (generally, synchronization kernel372or synchronization kernels372) may be included in the array topology354. In some embodiments, each of the first column FPGA device306and the second column FPGA device308may include one of the synchronization kernels372A or372B. One of the synchronization kernels372A or372B may include a slave synchronization kernel that may be configured to synchronize intermediate results between two or more of the kernels350. Additionally, one of the synchronization kernels372A or372B may include a master synchronization kernel configured with synchronization information pertaining to the slave synchronization kernel and to further synchronize the slave synchronization kernel with the kernels350in the array topology354.

For example, in the depicted embodiment, a first synchronization kernel372A may be a master synchronization kernels and a second synchronization kernel372B may be a slave synchronization kernels. Accordingly, the first synchronization kernel372A may synchronize the second synchronization kernel372B with the kernels350.

The second synchronization kernel372B may be configured to synchronize a multiplexer390. For example, the second synchronization kernel372B may synchronize the multiplexer390to coordinate received intermediate results from the second kernel350B and/or the array interconnect111and control the data rates330D,330F, and330H to a third kernel350C through a Nth kernel350E. The second synchronization kernel372B may be aware of the changes to the upstream data rates (e.g.,330A-330C) and/or downstream data rates (e.g.,330D-330I) and may adjust the data rates330D,330F, and330H accordingly.

The third through the Nth kernels350C-350E may operate at one or more input data rates330D,330F, and330H which may be slower than the input data rate. In some embodiments, one or more of the data rates330D,330F, and330H may be substantially similar. For example, the data rates330D,330F, and330H may be the data rate330C divided by a number of kernels350downstream of the multiplexer390(e.g., inFIG. 3,330C/n−2) and output one or more results at the data rates330E,330G and330I that may be proportional to an input and an output with possible data format width increase (e.g. increase in precision).

In some embodiments, the data rates330D,330F, and330H may be individualized for one or more of the kernels350downstream of the multiplexer390. The third kernel350C through the Nth kernel350E may output a result of the parallelized portion302of the source code300. Accordingly, the array topology354may have a predominant dataflow direction.

Throughout the array topology354, various data rates330may exist. The data rates330may be based on the kernels350segmented from the parallelized portion302. Thus, a total data rate of the source code300in the array topology354may be determined. If the total data rate is below a processing specification310indicating a particular processing specification310, then the array topology354may be modified. For example a row of FPGA devices may be added or the FPGA devices306/308may be substituted for FPGA devices with higher I/O bandwidths.

Additionally, performance of the kernels305can be achieved by optimization of pipelining as well as utilizing local memory. Generally, having the kernels350operating in the FPGA devices306/308may reduce memory bottlenecks in proportion to an increase in available local memory of each of the FPGA devices306/308.

In some circumstances, a maximum speedup factor of a fastest kernel may be limited by the computation capacity FPGA devices306/308and a maximum data rate330as partitioned in the array topology354. When the maximum data rate330(not necessarily I/O data rate) exceeds maximum I/O pipe data rate, it is important not to expose the results of these computations to the external I/O and instead utilize the wide internal data width of FPGA fabric.

In the depicted embodiment, the first column FPGA device306executes the first kernel350A and the second kernel350B. Additionally, the second column FPGA device308executes the remaining kernels350C-350N. This partitioning is an example of straight forward spatial partitioning. Depending on the source code300, the straight forward spatial partitioning may not be optimum. Accordingly, the topology/partitioning module322may be configured to explore if an additional speedup factor can be achieved if one or more of the kernels350(e.g. the second kernel350B) can be segmented into additional kernels350, which may be executed by the FPGA devices306/308.

In some embodiments, the topology/partitioning module322may be configured to partition the source code300in larger array topologies. In these and other embodiments, partitioning the source code300may include the estimation of the data rates to derive optimum utilization of FPGA devices in the array per each application. Provided that partitioning is done effectively and interconnect bandwidth does not impose additional limits, the speedup factor of FPGA array can increase in proportion to the computation capacity of the entire FPGA array.

InFIG. 3, the computing device320may be controlled by a user380. Additionally or alternatively, the user380may input the source code300and/or the processing specifications310to the computing device320via a user device340. The array topology354and/or the partitioning based thereon may be presented to the user380. For example, the array topology354and/or the partitioning based thereon may be presented on a display or via a user interface. In response the user380may modify the processing specifications310on which the array topology354is based or accept modifications to the array topologies354suggested by the topology/partitioning module322to achieve the processing specifications310. In these embodiments, the topology/partitioning module322may operate as a tool that determines array topologies354specific for the source code300and the processing specifications310. In these and other embodiments, the user380may periodically be presented with updates and/or provided with opportunities to override the array topology354suggested by the topology/partitioning module322.

The user device340and/or the computing device320may include any computing device that includes a processor328, memory326, and network communication capabilities, which may include a communication unit324. The processor328, the memory326, the communication unit324are only depicted in the computing device320. In some embodiments, the processor328, the memory326, the communication unit324are included in the user device340.

Some examples of the user device340and/or the computing device320may include a laptop computer, a desktop computer, and a tablet computer. Additionally or alternatively, in some embodiments the user device340and/or the computing device320may include a hardware server or portion thereof. In the user device340and/or the computing device320the topology/partitioning module322, the processor328, the memory326, and the communication unit324may be communicatively coupled by a bus344.

The processor328may include an arithmetic logic unit (ALU), a microprocessor, a general-purpose controller, or some other processor array to perform partition of the source code300and/or determination of the array topology354. The processor328may be coupled to the bus344for communication with the other components (e.g.,322,326, and324). The processor328generally processes data signals and may include various computing architectures including a complex instruction set computer (CISC) architecture, a reduced instruction set computer (RISC) architecture, or an architecture implementing a combination of instruction sets. Multiple processors may be included in the computing device320and/or the user device340. Other processors, operating systems, and physical configurations may be possible.

The memory326may be configured to store instructions and/or data that may be executed by the processor328. The memory326may be coupled to the bus344for communication with the other components. The instructions and/or data may include code for performing the techniques or methods described herein. The memory326may include a DRAM device, an SRAM device, flash memory, or some other memory device. In some embodiments, the memory326also includes a non-volatile memory or similar permanent storage device and media including a hard disk drive, a floppy disk drive, a CD-ROM device, a DVD-ROM device, a DVD-RAM device, a DVD-RW device, a flash memory device, or some other mass storage device for storing information on a more permanent basis.

The communication unit324may be configured to transmit and receive data. The communication unit324may be coupled to the bus344. In some embodiments, the communication unit324includes a port for direct physical connection to a communication network (e.g., the Intranet, a WAN, a LAN, etc.) or to another communication channel. For example, the communication unit324may include a USB, SD, CAT-5, or similar port for wired communication. In some embodiments, the communication unit324includes a wireless transceiver for exchanging data via communication channels using one or more wireless communication methods, including IEEE 802.11, IEEE 802.16, BLUETOOTH®, or another suitable wireless communication method. In some embodiments, the communication unit324includes a wired port and a wireless transceiver.

In some embodiments, to determine the array topology354an iterative process may be performed by the topology/partitioning module322. For example, the topology/partitioning module322may determine a proposed topology (e.g., topology354). The proposed topology may be based on a processing specification, the source code300, an estimated dataflow rate, or some combination thereof.

The estimated dataflow rate may be based on a processing specification that may be input from a user. Additionally or alternatively, the estimated dataflow rate may be estimated by an input and output rate for a set of source code applications. The estimation of the dataflow rate (or maximum internal data rate) may continue through an entire chain of computations executed by FPGA devices.

For example, some source code applications such as computed tomography (CT) for medical imaging may include a specified data rate per second, which may not be deviated from. For instance, an examination of a patient in a doctor's office may involve processing of a real-time image pixels and a display of an image at twenty nine frames per second. This source code application may not back off from this dataflow rate for any reason. Accordingly, the proposed topology may be based on this dataflow rate.

Other source code applications may not include a strict dataflow rate. In these source code applications, a goal may be to complete the task or tasks as fast as possible, but there may not be a restriction as to how long the task may take. For example, such a source code application may include post processing of acquired or recorded CT images off-line with more detailed criteria than those processed during patient examination at the office. A goal may be to complete the thorough comparison and evaluation of the CT images to a reference disease database, but there is no restriction for how long the post processing and evaluation might take. For these applications a peak data rate may be optimized during the partitioning iterations to maximize usage of FPGA device computational resources, while having limits on the maximum input/output data rates determined by the specific FPGA devices, but not the user specification as in the case with real-time applications.

The topology/partitioning module322may then partition the source code300among the FPGA devices306/308. The topology/partitioning module322may determine whether each of the FPGA devices306/308is capable of achieving the processing specification310.

If not, the topology/partitioning module322may determine whether a neighboring FPGA device306or308has sufficient processing capability to accommodate a difference between the processing specification and a deficiency of the FPGA devices306or308. If so, the topology/partitioning module322may perform load balancing the kernels350assigned to the FPGA devices306/308and determine whether the proposed topology achieves the processing specification following the load balancing.

In response to a determination that the FPGA devices306/308are capable of achieving the processing specification310and in response to a determination that the proposed topology achieves the processing specification310, the topology/partitioning module322may present the proposed topology to the user380. In response to a determination that the neighboring FPGA devices306or308have insufficient processing capability and/or in response to a determination that the proposed topology does not achieve the processing specification310, the topology/partitioning module322may modify the proposed topology.

In some embodiments, after the array topology354is presented to the user380, the topology/partitioning module322may receive user input sufficient to modify the processing specification310. In response, the topology/partitioning module322may modify the array topology354based thereon and re-partition the source code300among FPGA devices306/308as arranged according to the modified array topology354.

In some embodiments, to determine the array topology354the topology/partitioning module322may determine whether to include additional code such as the pipes352, the synchronous kernels372, and multiplexers380between the FPGA devices306/308and/or the kernels350. If so, the topology/partitioning module322may generate additional code including the pipes352, the synchronous kernels372, and multiplexers380.

As mentioned in reference toFIG. 2, the array topology354may include FPGA devices306/308arranged in the dataflow direction250in which data is processed and in the parallel process direction252, which may be orthogonal to the dataflow direction250. In these embodiments, to partition the source code300, the topology/partitioning module322may read the source code300line-by-line and/or a processing specification. The topology/partitioning module322may define device logic applicable to the FPGA devices306/308. The device logic may include one or more of a (PCIe) endpoint, an optical transport network (OTN) framer, a traffic manager, a user datagram protocol (UDP) stack, a transmission control protocol (TCP) stack, a packet forwarding protocol, and a frame forwarding protocol.

The topology/partitioning module322may partition the source code300in accordance with the array topology354as analyzed in the parallel process direction252. The partitioning source code300as analyzed in the parallel process direction252may include parsing the source code300to identify iteration loops. Iteration loops may include “while” and “for” statements, for instance. The topology/partitioning module322may unroll the identified iteration loops. In response to there not being any iteration loops, a maximum number of parallel kernels (e.g., the third kernel350C through the Nth kernel350E) may be chosen based on a number of FPGA devices306/308in the parallel process direction252and a size of an address space of a memory expansion protocol implemented in the proposed topology354. The partitioning parallel source code in accordance as analyzed in the parallel process direction252may further include replicating kernel hardware. For example, if computing units of the third through the Nth kernels350C-350E have similar structures with different taps and coefficients at the same sampling rate, then the hardware reuse may be exploited via zero samples fill and coefficient overload techniques. Otherwise one or more of the third kernel350C to the Nth kernel350E may operate independently.

The topology/partitioning module322may vectorize one or more of the kernels350. By vectorizing the one or more kernels350an optimal FPGA arrangement of the array topology354in the dataflow direction252based on a utilization of the resources of the FPGA devices306/308. The vectorizing may include iterating a number of work items and iterating a number of compute units. In some embodiments, iterating the number of work items may include iterating a number “N” in a work item attribute: _attribute_((num_simd_work_itmes(N))), in which N represents a number that includes a value 1, 2, 4, 8, or 16. In some embodiments, iterating the number of compute units may include iterating a number M in a compute unit attribute: _attribute_((num_compute_units(M))), in which M represents an integer.

The topology/partitioning module322may determine whether resources of one or more of the FPGA devices306/308of the proposed topology354are utilized. The topology/partitioning module322may take into consideration already defined device logic in making such determination. If not, the topology/partitioning module322may reiterate (e.g., iterate again) the number of work items and/or the number of compute units. If so, the topology/partitioning module322may determine whether one or more of the kernels350are too large to be executed by one or more of the FPGA devices306/308.

In response to the one or more of the FPGA devices306/308having a capability to process the kernel350, the number of work items and/or the number of compute units for the kernels350may be included in the file370. In response to the kernel350being too large, the topology/partitioning module322may split the kernel350into two or more segmented kernels350.

The topology/partitioning module322may determine whether to include one or more storage elements to communicate data between the kernels350. In response to a determination to include the storage element, the topology/partitioning module322may add the storage element to the proposed topology354. In response to a determination not to include the storage element or a pipe, the topology/partitioning module322may reiterate the number of work items and/or the number of compute units.

The topology/partitioning module322may save or present the file370. The file370may include an optimized kernel and a proposed topology file. The file370may include device array address indexing information utilized for modifications of a host processor code.

The partitioning of the source code300is described with respect to embodiment in which the source code300is formatted according to an OpenCL. In some embodiments, the source code300may be formatted in C or C++ and translated to OpenCL by the topology/partitioning module322or a third party translator. Additionally or alternatively, the C or C++ source code may be segmented and passed down to the FPGA devices306/308for HLS C/C++ or OpenCL FPGA flow. Additionally, one or more embodiments may be configured for execution and use of another parallel software language such as CUDA.

As mentioned above, to enable computing elements or kernels of the array200to be programmed with uniform address space of a global memory, the array interconnect111may be implemented. The array interconnect111may be configured with low latency of load and store accesses among the member devices150and to support multiple priorities for atomic accesses, burst accesses, streaming access and single or ordinary accesses (collectively, accesses). For example, some load and store accesses such as atomic access cannot be sub-divided and interleaved with other type of accesses (e.g., burst accesses, streaming access, and single). Others types of access may have low tolerance to latency or delay such as burst accesses or data streaming. Accordingly, the array interconnect111may be configured to appropriately control the accesses low latency and multiple priorities. Additionally, the array interconnect111may maintain load and store order and data synchronization and may not allow access or data loss. The array interconnect111may be configured with adaptive address resolution and routing and graceful congestion handling.

In general, a kernel may include requests to write (store) and/or read (load) data to and from local or global memory. Write requests and read requests may be handled by load and store units (LSU). The LSU may include load units401and store units406. Each of the load units401and the store units406may include one or more access types. For example, inFIG. 4, the load units401and the store units406include atomic, burst, simple or single, and streaming.

Some implementations of LSUs, which may include implementations chosen by a device vendor, may rely on a commercial computer bus architecture. Some examples of the commercial computer bus architecture may include advanced microcontroller bus architecture (AMBA), AXI, or a proprietary Avalon architecture by Altera Corporation. The array interconnect111may interface with one or more of the commercial computer bus architectures. Additionally or alternatively, the commercial computer bus architectures may be isolated with a bus bridge, for instance.

The low latency may be controlled through selection of a granularity of the access. The granularity may be based directly on an amount of source data that an initiating LSU requires to send or receive across the array interconnect111to replicate the access by a remote LSU at a destination. The amount of source data is defined herein as a cell. By treating minimum load and store data as independent cells the array interconnect111may be scalable and efficient in terms of utilization of the FPGA resources.

The array interconnect111may support the following cell types: a store cell, a store burst, a store streaming cells, a load single initiator cell, a load single return data cell, a load burst, a load streaming cell initiator cell, a load return data cell, data cells, and an interconnect system cell. System cells may be utilized to exchange status and control information among the array interconnects as well as for access synchronization. The cells may bear payload. A non-payload bearing or idle cell may be transmitted during serial link idle times or between payload bearing cells. The non-payload bearing cells may be used to delineate cell boundaries, to maintain serial link integrity and to establish and to maintain alignment of the serial links. One or more cells may have port pair backpressure information such that local port congestion information may be distributed in the timeliest fashion globally among the member devices.

The cell size of load and store transactions may be different. A single load and store access may have a minimum cell size. The maximum cell size may be chosen to be the size of the largest single transaction. The maximum cell size may enable treatment of the burst access as just the burst of cells or streaming data as a stream of cells. The number of cells in the burst may be equal to a number of individual transactions of the burst. Additionally, the cell size may vary based on a particular implementation of the LSU and an associated bus architecture. The cell size may be selected for each implementation and the cell granularity may be maintained for each store and load access. Thus the cell size may be adjustable per each LSU implementation. Allowing adjustment of the size may reduce complexities and extra hardware and buffering in store and forward architectures and segmentation and reassembly functions that may lead to high latency.

The array interconnect111may be configured to prioritize atomicity of the accesses that cannot be interleaved with other accesses. Additionally, the array interconnect111may be configured to facilitate low latency for the accesses that have low latency tolerance. For example, the array interconnect111may include a fixed priority arbitration. The fixed priority arbitration may assign four priorities to LSU units401and406of based on type. Additionally, the array interconnect111may include a first arbitration level402and a second arbitration level404.

In the first arbitration level402, the load units401and the store units406of different access types may receive a priority assignment. The priority assignment may be based on the properties of the access type. For example, the priority assignment may be based on atomicity, divisibility, and tolerance to latency and delay. In the depicted embodiment, the LSUs including an atomic access (e.g., the LU atomic401and the SU atomic406inFIG. 4) receive a highest priority of 1, the LSUs including a burst access (e.g., the LU burst401and the SU burst406inFIG. 4) receive a priority of 2, the LSUs including a streaming access (e.g., the LU streaming401and the SU streaming406inFIG. 4) receive a priority of 3, and the LSUs including a simple access (e.g., the LU streaming401and the SU streaming406inFIG. 4) receive a lowest priority of 4.

The array interconnect111may include one or more arbiters403. The arbiters403may be configured to arbitrate the load units401and the store units406based at least partially on the priority assignments. The accesses may be arbitrated by the arbiters403in parallel. By arbitrating the accesses in parallel, access initiators may not be starved and access time dependencies may not be introduced. Additionally, arbitrating the accesses in parallel may allow initiating load unit401to include a burst access (LU burst401) and a store unit to include a burst access (SU burst406) on every clock cycle.

After the LSUs are arbitrated, the access data associated with the LSUs becomes a cell. The priority information may be carried in the cell. Each of the cells are substantially equivalent to any other of the cell of the array interconnect111. The cells may then enter the second arbitration level404.

The second arbitration level404may include a local load in port410(inFIG. 4, “LD in Port410”), a local store in port412(inFIG. 4, “ST in Port412”), and a global in port414. The local load in port410and the local store in port412may receive the cells from the arbiters403. The global in port414may receive cells from other member devices in an array implementing the array interconnect111.

Additionally, the second arbitration level404may include a second level arbiter416, a switch418, and an output port420. In the array each FPGA may have shared resources, which may include the switch418and the output port420. The output port420may pass cells to one or more other member devices of the array or another array interconnect that may be substantially similar to the array interconnect111. In some embodiments, one second level arbiter416may be included for each output port420. The number of input and output ports and arbiters may be dependent on a number of array dimensions. For example, a two-dimensional array may include an interconnect having four ports and a three-dimensional array may include an interconnect having six ports.

In a forward direction, one or more of the cells may arrive to one of the input ports410,412, or414. To pass traffic through to the member device of an array and/or the array interconnect, the shared resources are arbitrated by the second level arbiters416that have variable priority assignments per each arriving cell. The cells carry priority information in its header upon which the arbitration of the second level arbiters416is based. Moreover, the cells may be similarly arbitrated at the one or more other array interconnects in the array. Thus, a priority of the data path through the array interconnect111and any other array interconnect in the array may be maintained. Additionally, the array interconnect111may enable scalability of the arrays. In some embodiments, buffering resources by the input port414and the switch418may be distributed equally among member devices of the array, which may enable each array interconnect111to use a smallest possible size of the FPGA resources determined by the number of LSU units401and406, the input ports414, and the output ports420.

The array interconnect111may be expanded to arrays of larger topologies. For example, the array interconnect111may be expanded to support arrays of three dimensions and larger dimensions. Moreover, the interconnect topologies supported by the array interconnect111are not limited to the symmetrical arrays. The arrays can be clustered into a larger interconnect networks where each cluster can have larger dimensions array or dense mesh interconnect to facilitate local computations with fewer inter-cluster interconnect links. The inter-cluster interconnect links can encapsulate cells into higher level protocols such and OTN or Ethernet.

FIG. 5includes a detailed view of the array interconnect111. The array interconnect111inFIG. 5is depicted in a forward data path. Additionally, the array interconnect111ofFIG. 5is representative of an implementation in a [4×4] array.FIG. 5depicts an example of how decisions about destination of the cells may be performed to provide a uniform global memory address space.

The array interconnect111may include a bus adapter block550. The bus adapter block550may represent logic involved in isolation of specifics of a LSU bus protocol from the rest of the array interconnect111. The bus adaptor block550may include the store units450, the load units410, a load arbiter554B, a store arbiter554A, an address monitor and decode logic558, and a load list556.

The address monitor and decode logic558may be configured to determine whether the LSU access falls within the address range of the local FPGA global memory or a global memory of another member device of an array implementing the array interconnect111. In some embodiments, only the sizes of the cells are affected by a particular LSU address and data bus sizing.

In circumstances in which the address range is within a global memory of another member device, the load and store accesses may be captured into optional store cell and load cell storage stages. After arbitration by the load arbiter554B or the store arbiter554A, the load and store accesses may be directed to the store and load input switch ports (e.g., the load in port410ofFIG. 1or the store in port412). The load arbiter554B and the store arbiter554A may operate in parallel.

The store access may be a one-way transaction without a return data. The load access may be a bidirectional access split into a forward cell and a return cell. The forward load cells may be arbitrated similar to the store cell. However, to track the active and pending load accesses, the load list556may be maintained. One or more array interconnects111in one or more FPGA devices of the array may include a load list556to track active and pending load accesses. The load list556may be cleared upon arrival of the return of a load access cells.

The global memory address may be mapped into a path though the array interconnects111. For example, an adaptive router552may map the path through the array interconnect111. Additionally, the adaptive router552may direct an incoming cell (inFIG. 5, “In Cell”) to one of the output ports420.

The mapping may be accomplished via a lookup table560. In the lookup table560, numbers associated with the output ports420may be stored per range of the global address space. The lookup table560may be an efficient and a fast way to implement routing function with a minimum of FPGA hardware resources.

The adaptive router552may reduce local and global congested paths. For example, in a two-dimensional array with four adjacent nodes, there are 2 short and 2 long output paths, which may be chosen for each incoming cell. If one of the short paths is congested another short path may be chosen by the adaptive router552. If both short paths are congested, then adaptive router552may decide between one of the long paths or postpone transmission by some number of interconnect cycles.

The interconnect cycle may be determined by the fastest rate of a serial link and the maximum parallel data path bus. For example the link 12.5 Gigabits per second (Gbps)/64-bits parallel bus may include an interconnect cycle that is 195.3125 megahertz (MHz). The interconnect cycle may be one of the input/output port hardware constraints of the topology/partitioning module322ofFIG. 3.

The decision between one of the long paths and postponing the transmission may be based on the past history of the output port. For example, if the history for a particular number of past interconnect cycles indicate that there are no gaps or only a small number of gaps less than a configurable maximum congestion factor threshold (THR MAX), then the long path may be chosen. Additionally, a warning congestion counter may be incremented. However, if the past access history indicates that the congestion factor is less than minimum congestion factor threshold (THR MIN), then a decision may be to postpone transmission by one interconnect cycle. The shortest path choice may be made on a next interconnect cycle. The warning congestion counters as well as two congestion thresholds may be maintained per each of the output ports420.

Histories of the output ports420incorporate global congestion history into the decision making at the array interconnect111. In an array, the exchange patterns and global congestion patterns may stabilize over time, which may result in simpler computations. The THR MIN and THR MAX and the congestion counters may be provided for real-time control of the congestion patterns for more complex accelerated computations. The warning counters and congestions thresholds may be adapted to each accelerated application and unique cell exchange pattern therein. Therefore, the flexible and adaptive routing scheme enables maximum utilization of array interconnect111with minimum impact to computational performance of the entire array.

The adaptive router552will also determine if arriving cells are destined for the local FPGA device and it will direct these cells to the local LSU bus masters for replication of the accesses. Some additional details of this circumstance are provided with reference toFIG. 6.

The switch418may include n×2 buffers. The buffers may be configured to sustain accesses from all n input ports at every clock cycle. The buffers are not assigned per port. Instead, the buffers may be shared among n input ports and two store and load input ports.

In this architecture, there may be n+2 input ports and n output ports. Accordingly, congestions may be possible. A backpressure mechanism (not shown) may be included to throttle back load and store accesses. The backpressure mechanism may originate at each output port420and may propagate in the direction opposite to a direction of the cells. Together with backpressure and sequence numbers, input port storage and switch buffering (discussed elsewhere herein) may not allow data loss and may provide congestion handling. For example, because the input port accesses may have already incurred delay, the choice to throttle back store and load accesses may be driven by the goal of maintaining order and sequencing of the load and store accesses. Additionally, each cell may carry sequence numbers in data bits that are shared with burst count. The sequence numbers may be checked by local master, which replicates access. Additionally, missing cells may be fragged as errors.

The array interconnect111may include pipe objects hardware530. The pipe objects hardware530may be configured to generate data cells535. The data cells535may exchange information among the member devices and/or array interconnects included therein. The data cells535may be an input to the pipe objects hardware530that include a unidirectional transfer of the data cell535from a source FPGA device to a destination FPGA device. The data cells535may be communicated to the output ports420through the one or more multiplexers532or a data output port534, which may be dedicated to the data cells535. Whether the data cells535are communicated via the output ports420or the data output port534may be based on a data rate. For relatively low data rates, the output ports420may be used and for relatively high data rate the data output port534may be used.

FIG. 6includes another detailed view of the array interconnect111. The array interconnect111inFIG. 6is depicted in a return direction. One or more arriving cells602from the input ports414may be destined for an FPGA device implementing the array interconnect111, referred to as the local FPGA device. Accordingly, the adaptor router552may receive and route the arriving cells602to one or more load and store unit bus masters610A-610D (generally, LSU bus master610or LSU bus masters610). The LSU bus masters610may be configured to finalize accesses on a load unit global bus and a store unit global bus606A and606B respectively.

A number of LSU bus masters610may be equivalent to a number of the in ports414. The LSU bus masters610may be configured to operate in parallel such that the in cells602are not waiting for an available LSU bus master610. Additionally, a number of LSU global memory buses606may be equivalent to the number of the in ports414.

With combined reference toFIGS. 5 and 6, if one or more of the arriving cells602is a load cell with return data from remote load access, the arriving cell602is directed to the bus adapter bock550via arrow670. These arriving cells602may clear an active entry in the load list556. The LSU bus master610may also return load data to an initiating remote load unit. In this circumstance, the load data cell may be routed to the switch418and to one of the output ports420via the adaptive router552as shown by arrow570ofFIG. 5. In case of the store access cells, the LSU bus masters610may perform a write access on one or more of the global memory buses606. Additionally, in some embodiments, a first LSU global memory bus606A may be for load units and a second global memory bus606B may be for store units.

Referring back toFIG. 6, the data cells535may arrive from the in ports414(e.g., as an arriving cell602) as well as from a dedicated input data port607(generally, input data port607or input data ports607). The adaptive router552may direct the data cells535to a hardware implementing one or more receive data pipes609A-609E (generally, receive data pipes609). Additionally, the data cell in port607and/or a local storage608may direct the data cells535to one or more receive data pipes609. A number of receive data pipes609may be equivalent to a number of receive data pipes is equivalent to the number of the in ports414and a number of dedicated data cell in ports607.

Address bits of the data cell535may be used for a routing decision. A 64-bit address allows for 264=1.84e19 connections in an array implementing the array interconnect111. Accordingly, in data port607may include the local storage608for full rate serial to parallel conversion.

FIGS. 7-10illustrate example arrays700,800,900, and1000. Each of the arrays700,800,900, and1000may include one or more of the features and components described with reference toFIGS. 1-6. For example, each of the arrays700,800,900, and1000may be configured to execute parallel source code partitioned among the FPGA devices included therein. Additionally, each of the arrays700,800,900, and1000may include the array interconnect111. Each of the arrays700,800,900, and1000are briefly described below.

FIG. 7illustrates a block diagram of an example array700. The array700a two dimensional torus array. The torus array may include a torus interconnect701. The array700in some embodiments may include four global memory ports for each FPGA device150.FIG. 8illustrates a block diagram of another example array800. The array800is a three-dimensional array. InFIG. 8, the ellipses indicate that multiple FPGA devices150and cards may be added. Some embodiments of the array800may include six ports for each of the FPGA devices150. The array may be modified to a torus type through the addition of a torus interconnect as shown inFIG. 7. An array with higher dimensions may be built by adding ports.

FIG. 9illustrates a block diagram of another example array900. The array900includes a multiprocessing configuration with multiple host processors101configured as a cluster. In this configuration, multiple arrays902may execute accelerated computations according each host processor101. The code may be executed asynchronously in each host processor101in the cluster and per each array902. The array900may further include a host-to-host network908. Some examples of the host-to-host network may include 1 GE-10 GE Ethernet. The array900may also include a connection to a transport network910. For example, the connection may include an OTN at OTU2, OTU3 or OTU4 rates. The array900may also include a connection to a data network912. The data network912may include Ethernet at 1 GE, 10 GE or 100 GE rates. A number of additional FPGA data and transport network ports may be determined by a particular parallel task.

FIG. 10illustrates a block diagram of another example array1000. The array1000is arranged as a switched network interconnect. The array1000may include a single host processor1001and multiple host interfaces1003that may include a switch feature. For example, in the depicted embodiment the host interfaces1003include a PCIe switch, which may be configured to selectively interface with the host processor1001. In other embodiments, other types of host processor1001and interfaces1002may be implemented.

The array1000may also include multiple switches1002. The switched1002may interconnect a transport or any other type of switched network1005. The interconnected arrays1010may include one or more line cards each having one or more arrays of FPGA devices150. The FPGA devices150may be arranged according to a functionality of forwarding plane.

In addition to an array interconnect (e.g., the array interconnect111described herein), some of the FPGA devices150may include a switch interface1004, a framer1006, or a traffic manager logic. The switch interface1004, the framer1006, or the traffic manager logic may be configured to extract the payload from a frame such as an OTN wrapper. The switch interface1004, the framer1006, or the traffic manager logic may reside outside of the FPGA devices150or inside FPGA devices150. Thus, switching, framing and traffic management functions may be centralized or distributed.

In the example arrays700,800,900, and1000, the global memory access cells and data cells are transparently exchanged by entire array of the FPGA devices by encapsulating them in corresponding transport, data, and switched network protocols while maintaining a uniform global memory address space as well as facilitating the global data cell exchange via utilization of address bit fields as described above.

FIGS. 11A and 11Bare a flow chart of an example method1100of the parallel code partitioning among the member devices of an array. The method1100may be programmably performed in some embodiments by the topology/partitioning module322described with reference toFIG. 3. In some embodiments, the topology/partitioning module322or the computing device320may include or may be communicatively coupled to a non-transitory computer-readable medium (e.g., the memory326ofFIG. 3) having stored thereon programming code or instructions that are executable by a processor (such as the processor328ofFIG. 3) to cause a computing device320and/or the topology/partitioning module322to perform the method1100. Additionally or alternatively, the computing device320may include the processor328described above that is configured to execute computer instructions to cause the topology/partitioning module322or another computing device to perform the method1100. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation.

With reference toFIG. 11A, the method1100may begin at block1102. At block1102, a source code may be read. For example, the source code may be read line-by-line. Additionally, a processing specification may be read. At block1104, based on the read source code and/or the processing specification, a proposed topology may be defined. The proposed topology may include devices arranged in a dataflow direction in which data is processed in the array and one or more parallel process directions that may be orthogonal to the dataflow direction.

At block1106, based on the proposed topology a device logic applicable to the device may be defined that is applicable to the device included in the proposed topology. For example, in some embodiments, the device logic may include a PCIe endpoint, OTN framer, traffic manager, UDP stack, TCP stack, packet forwarding protocol, and frame forwarding protocol. One or more example of the device logic may occupy resources of one or more of the devices included in the proposed topology. The device logic that occupies resources of one or more of the devices may be taken into consideration during one or more other steps of the method1100.

With reference toFIG. 11B, at block1108, the source code may be partitioned in accordance with the proposed topology analyzed in a parallel process direction. The parallel process direction may be orthogonal to a dataflow direction. Additionally, in some arrays there may be multiple parallel process directions. For example, three-dimensional arrays may include two parallel process directions.

In some embodiments, partitioning the source code in the first direction may include one or more of blocks1110,1112,1114, and1116. At block1110, the source code may be parsed to identify iteration loops. In response to one or more iteration loops being present in the source code (“YES” at block1110), the method1100may proceed to block1112. At block1112, the identified iteration loops may be unrolled. In some embodiments, the loops may be partially or fully unrolled based on user input sufficient to indicate a degree to which the loops are to be unrolled.

In response to there not being any iteration loops (“No” at block1110), the method1100may proceed to block1114. At block1114, a maximum number of parallel kernels may be chosen. In some embodiments, the maximum number of parallel kernels may be based on a number of devices in the first direction of the proposed topology. Additionally, in these and other embodiments, the maximum number of parallel kernels may be increased by adding devices in the first direction to the proposed topology. The maximum number of parallel kernels may be limited by a size of address space of a memory expansion protocol implemented in the proposed topology.

At block1116, kernel hardware may be replicated. In some embodiments, user input may be received that is sufficient to select to replicate kernel hardware. A selection to replicate kernel hardware may be based on a specific task specification or processing specification. For example, a task in the source code may involve multiple data network ports to be processed by an identical parallel code. Accordingly, replicated kernel hardware may be implemented to process the task.

At block1118, one or more of the kernels may be vectorized. The kernels may be vectorized to optimize a device arrangement of the proposed topology in the dataflow direction. The device arrangement may be optimized based on a utilization of array member device resources of the proposed topology. In some embodiments, the vectorization of the kernels may include one or more of blocks1120,1122,1124,1126,1128,1130, and1132.

At block1120, a number of work items may be iterated. For instance, in embodiments implemented in the OpenCL, a number of the work items may be increased by iterating a number N in an example work item attribute:

In the work item attribute, N may be equal to integer values 1, 2, 4, 8, and 16. If N increases from 1 to 4, the amount of work executed by the FPGA device quadruples. In some circumstances, increasing the work items may be an economic way in terms of device resources to execute addition portions of the source code in parallel.

At block1122, a number of compute units may be iterated. For instance, in embodiments implemented in the OpenCL, a number of compute units may be increased by iterating a number M in an example compute unit attribute:

The number M may take an integer value. Increasing the number of compute units increases a number of load and store units and consequently increases required device resources in comparison to a similar increase of work items which may result in an increase in a number of busses multiplexed by the load and store units.

At1124, it may be determined whether resources of member devices of the proposed topology are utilized. For example, in embodiments in which the member devices are FPGA devices, it may be determined whether the FPGA logic fabric and dedicated resources such as registers, blocks of local memory, and DSP blocks are utilized. In some embodiments, the defined device logic may be taken into account in a determination made at block1124. In response to the device resources not being fully utilized (“No” at block1124), the method1100may proceed to block1120. The method1100may then proceed to one or more of blocks1120,1122,1124,1126,1128,1130,1132, and1134.

In response to the device resources being fully utilized (“YES” at block1124), the method1100may proceed to block1126. At block1126, it may be determined whether the kernel is too large to be executed by a member device. In response to member device being a sufficient size to process the kernel (“NO” at block1126), the method1100may proceed to block1134. At block1134, an optimized kernel file and a proposed topology file may be saved. The proposed topology file may contain the device array address indexing information that may be utilized, for example, for modifications of a host processor code.

In response to the kernel being too large (“YES” at block1126), the method1100may proceed to block1128. For example, if the kernel being analyzed is long and involves complex computations that cannot be performed by a single member device, the kernel may be too large. At block1128, the kernel may be split into segmented kernels. At block1130, it may be determined whether to add a storage element to communicate data between the segmented kernels. In some embodiments, the storage element may include an OpenCL pipe and/or a FIFO. In response to a determination to add a storage element, the method1100may proceed to block1132. At block1132, the storage element may be added to the proposed topology. The method1100may proceed from block1132to block1120. The method1100may then proceed to one or more of blocks1120,1122,1124,1126,1128,1130,1132, and1134. In response to a determination not to add the storage element, the method1100may proceed to block1120. The method1100may then proceed to one or more of blocks1120,1122,1124,1126,1128,1130,1132, and1134.

In some embodiments, using the method1100, each kernel and/or each segmented kernel may be optimized for maximum device utilization and consequently for a largest acceleration or speedup factor. A throughput factor and an acceleration factor of each kernel and/or each segmented kernel working together with the rest of kernels may be optimized for a same speed of real-time execution. Thus, the method1100may result in an optimum acceleration or speedup factor for a particular array topology and the number of devices in the array.

One skilled in the art will appreciate that, for this and other procedures and methods disclosed herein, the functions performed in the processes and methods may be implemented in differing order. Furthermore, the outlined steps and operations are only provided as examples, and some of the steps and operations may be optional, combined into fewer steps and operations, or expanded into additional steps and operations without detracting from the disclosed embodiments. For instance, when high level source code is not written in OpenCL, the method1100may include compiling another source code (e.g., C/C++ original code) into OpenCL code or kernels by an additional topology/partitioning module including third party topology/partitioning module. The OpenCL kernels may represent computationally intensive portions of the original source code. The remaining original source code may be executed on a host processor, for instance.

Additionally or alternatively, the method1100may include extracting computationally intensive portions of an original C/C++ code and create a hardware circuit by applying HLS design flow. A resulting hardware circuit may be replicated or instantiated multiple times along with an additional logic of load and store units. A number of replications may be equivalent to the number of compute units discussed above in the method1100. An amount of multiplexing of load and store data buses may be equivalent to the number of work items in the method1100.

Some portions of the method1100are described with reference embodiments in which the member devices of the arrays include FPGA devices. In some embodiments, the method1100may be applicable to any heterogeneous systems that may include GPUs, GPPs, DSPs, FPGA devices or any computation devices and their combinations including hybrid computing systems.

In some embodiments, if the source code includes computations without a dominant data direction as an alternative to the method1100, the array may be treated as a computational resource pool. Accordingly, an array of FPGA devices may include as many of the kernels as possible. The array may operate essentially as one large FPGA device. In these embodiments, bandwidth of the array interconnect may be a limiting factor.

FIGS. 12A and 12Bare a flow chart of an example method1200of array topology determination. The method1200may be programmably performed in some embodiments by the topology/partitioning module322described with reference toFIG. 3. In some embodiments, the topology/partitioning module322or the computing device320may include or may be communicatively coupled to a non-transitory computer-readable medium (e.g., the memory326ofFIG. 3) having stored thereon programming code or instructions that are executable by a processor (such as the processor328ofFIG. 3) to cause a computing device320and/or the topology/partitioning module322to perform the method1200. Additionally or alternatively, the computing device320may include the processor328described above that is configured to execute computer instructions to cause the topology/partitioning module322or another computing device to perform the method1200. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation.

The method1200may begin at block1202. At block1202, proposed topology for an array of devices may be determined. In some embodiments, the proposed topology may be based on an estimated dataflow rate of the array. The estimated dataflow rate may be based on a processing specification that may be input from a user. Additionally or alternatively, the estimated dataflow rate may be estimated by an inherent or operating input and output rate for a set of source code applications. For example, some source code applications such as medical CT image processing may include a specified data rate per second, which may not be deviated from. Other source code applications may not include a strict dataflow rate.

At block1204, parallel source code may be partitioned among member devices of the array. The member devices may include FPGA devices. In some embodiments, an initial partitioning of the parallel source code among the member devices of the array may be according to an initial set of segmented kernels. The initial set of segmented kernels may be a best guess as to a partition of the parallel source code to the member devices based on computational resources of the member devices and an estimate of an involved number and type of computations from initial read or parse of the parallel source code.

At block1206, it may be determined whether to include additional code. The additional code may be added to replicate or broadcast or to communicate input or intermediate data between the member devices and/or to multiplex or demultiplex the input or intermediate data. In response to a determination to include the additional code (“Yes” at block1206), the method1200may proceed to block1208. In response to a determination not to include the additional code (“No” at block1206), the method1200may proceed to block1210. At block1208, additional code may be generated. For example, the additional code may include repeaters, broadcast logic, FIFOs, pipes, multiplexers, demultiplexers, or some combination thereof.

At block1210, it may be determined whether to include additional code to synchronize local dataflow and global dataflow. In response to a determination to include the additional code to synchronize local dataflow and global dataflow (“Yes” at block1210), the method1200may proceed to block1212. In response to a determination not to include the additional code to synchronize local dataflow and global dataflow (“No” at block1210), the method1200may proceed to block1214.

At block1212, additional code to synchronize local dataflow and global dataflow may be generated. For example, the additional code may include a master synchronization kernel, a slave synchronization kernel, multiplexers, demultiplexers, code to communicate there between, or some combination thereof.

At block1214, it may be determined whether each of the member devices is capable of achieving a processing specification. In response to a determination that the member devices are capable of achieving the processing specification (“Yes” at block1214), the method may proceed to block1222. In response to a determination that one of the member devices is not capable of achieving the processing specification (“No” at block1214), the method may proceed to block1216.

At block1216, it may be determined whether neighboring member devices have sufficient processing capability to accommodate a difference between the processing specification and a deficiency of the member device. In response to a determination that the neighboring member devices do not have sufficient processing capability (“No” at block1216), the method1200may proceed to block1226. In response to a determination that the neighboring member devices have sufficient processing capability (“Yes” at block1216), the method1200may proceed to block1218.

At block1218, processing assigned to the member device and the neighboring member devices may be load balanced. At block1220, it may be determined whether the proposed topology achieves the processing specification. In response to a determination that the member devices are capable of achieving the processing specification (“Yes” at block1220), the method1200may proceed to block1222. In response to a determination that the member devices are not capable of achieving the processing specification (“No” at block1220), the method1200may proceed to block1226.

At block1224, user input sufficient to modify the processing specification may be received. For example, a user such as the user380may input a new processing specification, which may serve at least partially as grounds for a modification to the proposed topology or as a change to a partitioning of the parallel source code.

At block1226, the proposed topology of the array may be modified. For example, a row, a column, another array, etc. may be added to the proposed topology. From block1224, the method1200may proceed to block1204and one or more of blocks1206,1208,1210,1212,1214,1216,1218,1220, and1222may be performed.

The embodiments described herein may include the use of a special purpose or general-purpose computer including various computer hardware or software modules, as discussed in greater detail below.

Embodiments described herein may be implemented using computer-readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media may be any available media that may be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer-readable media may comprise tangible computer-readable storage media including RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other storage medium which may be used to carry or store desired program code in the form of computer-executable instructions or data structures and which may be accessed by a general purpose or special purpose computer. Combinations of the above may also be included within the scope of computer-readable media.