Method of, and apparatus for, stream scheduling in a parallel pipelined stream processor

0001The present invention relates a method of, and apparatus for, stream scheduling in pipelined hardware. More particularly, the present invention relates to a method of, and apparatus for, generating a hardware design for a pipelined parallel stream processor.

0002Computer systems are often used to implement computational models of a particular physical system, region or event. Commonly, such computational models require iterative numerical calculations to be solved for a large number of data areas or data points. This requires an extremely large number of calculations to be performed; consuming large amounts of computational resources and requiring a significant time period to perform complete the necessary calculations.

0003Often, a processor such as a central processing unit (CPU) is found in most computing systems. However, whilst a CPU is able to process such calculations, the time period required may be prohibitive unless powerful computing systems are used.

0004Traditionally, the performance of a computing system has been increased by increasing the operating frequency of the CPU (i.e. by increasing the number of operations the CPU can carry out per second) and by reducing the size of the individual transistors on the CPU so that more transistors can be accommodated per unit area. However, due to power constraints, in the future increasing the CPU frequency may only deliver modest performance improvements. Further, it is becoming increasingly difficult to reduce the size of transistors due to the limitations of lithographic processes and material capabilities.

0005An alternative approach to increase the speed of a computer system for specialist computing applications is to use additional or specialist hardware accelerators. These hardware accelerators increase the computing power available and concomitantly reduce the time required to perform the calculations. In certain cases, a specialist hardware accelerator may increase the performance of highly parallel applications by over an order of magnitude or more.

0006One such example of a suitable system is a stream processing accelerator having a dedicated local memory. The accelerator may be located on an add-in card which is connected to the computer via a bus such as Peripheral Component Interconnect Express (PCI-E). The bulk of the numerical calculations can then be handled by the specialised accelerator.

0007A useful type of stream processor accelerator can be implemented using Field-Programmable Gate Arrays (FPGAs). FPGAs are reprogrammable hardware chips which can implement digital logic. FPGAs comprise no intrinsic functionality and, instead, include a plurality of gates, flip-flops and memory elements which are configurable through use of appropriate software elements.

0008A schematic example of an FPGA device is shown in <figref idref="f0001">Figure 1</figref>. Different types of FPGA chips may be used; however the larger and more arithmetic function-rich FPGAs are more desirable.

0009The FPGA 10 comprises a programmable semiconductor device which comprises a matrix of configurable logic blocks (CLBs) 12 connected via programmable reconfigurable interconnects 14 (shown here as the shaded area in <figref idref="f0001">Figure 1</figref>). In order to get data into and out of the FPGA 10, a plurality of input pads 16 and output pads 18 are provided.

0010The CLBs 12 are the basic logic unit of the FPGA 10. A schematic diagram of a typical CLB 12 is shown in <figref idref="f0001">Figure 2</figref>. The CLB 12 comprises a configurable switch matrix comprising typically a 4 or 6 input look up table (LUT) 20, which in some cases may also be configurable as a small buffer of up to about 32 bits, some specialist circuitry (such as, for example, a multiplexer), one or more flip-flop units 22 which act as temporary memory storage and an output 24. Additionally, an FPGA 10 comprises a plurality of block memory units 26. The block memory units 26 comprise addressable memory units which can be used as storage buffers in the FPGA 10. A fixed amount of buffer space is available per FPGA 10. Therefore, it must be carefully allocated.

0011The LUTs 20 of each CLB 12 can be configured to perform a variety of functions; for example, logic gates such as NAND and XOR, or more complex functions. A typical FPGA may comprise up to 10⁵ LUTs 20. The CLBs 12 are able to operate in parallel, providing a powerful resource for numerically-intense calculations.

0012FPGA-based stream processors comprise calculation functions mapped into one or more hardware units along the path from input to output. The FPGA then performs the computation by streaming the data items through the hardware units. Each hardware unit will require a particular time period within which to complete the necessary computation. This is known as the latency of the hardware unit and is commonly defined in terms of the number of clock cycles the hardware unit requires to complete the computation. Once the computation is complete, the data then moves "downstream" to further hardware units or to an output. The streaming architecture makes efficient utilization of the computation device, as every part of the circuit is performing an operation on one corresponding data item in the data stream at any point during the calculation.

0013<figref idref="f0002">Figure 3</figref> shows an example of such a streaming architecture created using the CLBs 12 of the FPGA to implement a stream processor thereon. <figref idref="f0002">Figure 3</figref> shows a 4 input 16-i, 4 output 18-i stream computing engine which can be implemented on the FPGA stream processor 10.

0014Between the inputs 16-i and the outputs 18-i is provided a computational data path 30. The computational data path 30 is a graphical representation of an algorithm as it is expressed in hardware. The computational data path 30 is also referred to as a kernel. A typical FPGA 10 may comprise a multiplicity of parallel kernels.

0015The computational data path 30 is implemented using the CLBs 12 and other logic and comprises arithmetic operations 32 (performed in one or more LUTs 20) and buffer memories 26. In other words, each arithmetic unit 32 is implemented in hardware as a hardware element (which may comprise one or more hardware units) on the FPGA. The buffer memories 26 may comprise either block RAM (as provided by the block memory units 26) or distributed RAM (comprising the memory made available through use of the LUTs 20 or flip flops 22). As shown, the computational data path 30 is arranged to process data in parallel.

0016In operation, the data is streamed through the CLBs 12 of the FPGA stream processor 10 and the arithmetic operations 32 are carried out on the data as it is streamed.

0017Often, FPGA circuits are designed using circuit schematics or a hardware description language (HDL) such as, for example, Verilog. HDLs are used to write synthesisable specifications for FPGA hardware. A simulation program is run which enables simulation of the desired spatial and temporal configuration of the FPGA so that the operation of the FPGA can be modelled accurately before being physically created. HDLs include syntax for expressing parallelism (also known as concurrency) and may include an explicit notion of time.

0018As an example, <figref idref="f0003">Figures 4a) and 4b</figref>) illustrate graphs defining a simple streaming data path. A graph is a representation of a desired processing operation (e.g. mathematical calculations such as convolutions) to be implemented in hardware as part of a stream processor. The graph represents the processing operation as a parallel structure in the time domain as a function of clock cycles, with data "flowing" along a data path from the input(s) to the output(s) with increasing clock cycle. The data path comprises discrete objects (or nodes) which perform processing operations on the streamed data. The discrete objects correspond directly to hardware elements to be implemented as part of a stream processor on the FPGA. Hardware elements may comprise one or more hardware units (such as CLBs) on the physical FPGA.

0019<figref idref="f0003">Figure 4a</figref>) shows a three input (A, B and C) data path 40 having a single output 42. The data path 40 comprises a pair of nodes 44, 46. In this example, the nodes 44, 46 comprise adders. The nodes 44, 46 are connected between the inputs and output by means of "edges" 48 (or interconnects) between the inputs A, B, C, nodes 44, 46 and output 42.

0020As shown in <figref idref="f0003">Figure 4a</figref>) (and subsequent figures), the nodes 44, 46 and edges 48 define a plurality of branches within the data path 40. In general, a data path represents a particular process operation or function and is implemented as a pipelined circuit through which the data flows. A kernel may also comprise a plurality of branches (also called control paths) which do not compute directly on the data but may configure the data path at different points in time to change its function. These branches may be dependent upon other branches, or may be independent or semi-independent depending upon the nature of the bulk computation performed by a particular data path.

0021However, whilst for clarity the term data path corresponds to a kernel, it is within the scope of the invention for a data path to be split across more than one kernel. The scope of the terms defined herein will be readily apparent to one skilled in the art.

0022Expressed as an equation, the desired calculation is: <maths id="math0001" num="1)"><math display="block"><mfenced><mi mathvariant="italic">A</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">B</mi></mfenced><mo>+</mo><mi>C</mi><mo>=</mo><mi mathvariant="italic">Output</mi></math><img file="EP2490141A2_D0001.tif" /></maths>

0023Therefore, it is desired to add inputs A and B at node 44 before adding the result to input C at node 46. However, this data path 40 will generate incorrect calculations. This is because each node 44, 46 has a particular latency associated therewith, i.e. the processor time it takes the adder 44, 46 to complete the calculation before the result is released to the next stage of the data path 40. In other words, the data propagates through the data path 40 in a lock step manner - each node 44, 46 has a latency associated therewith. In the common case a global clock is distributed to all nodes (running for example at 100MHz), and the latency of each node is measured in number of clock cycles.

0024Consequently, once data is inputted simultaneously at inputs A, B and C, data input A and data input B will arrive at adder 44 at the same time as input data C arrives at adder 46. Consequently, adder 46 will attempt to add input data C to no value at all (because the value from adder 44 has yet to arrive), generating an incorrect result. For later clock cycles where adder 46 is able to add two actual data values, then the wrong numbers will still be added because data reaching adder 46 from adder 44 will be one cycle behind the data reaching adder 46 directly from input C.

0025<figref idref="f0003">Figure 4b</figref>) shows the hardware solution to this problem. The solution is to add buffering 50 to the edge 48 between input C and adder 46. This adds a delay of one cycle to the data inputted from input C so that the data from adder 44 (i.e. the product of inputs A and B) arrives at adder 46 at the same time as data from input C.

0026Therefore, insertion of buffering to create a data path or data stream which functions in a correct temporal manner is a required feature of suitable HDLs. In many cases, the user of the HDL is required to specify appropriate buffering. However, whilst HDLs are able to generate data paths which can then be implemented into hardware on actual FPGAs, less consideration has been paid to the optimisation of the data pathways on FPGAs.

0027Two known methods for building up a circuit taking latencies into account are As Soon As Possible (ASAP) and As Late As Possible (ALAP). In ASAP, all of the inputs are cycle aligned, i.e. all of the inputs are aligned to the same arbitrary cycle (which may be cycle 0 at the start of a calculation). However, this requirement, together with differing input latencies along different branches of the data path, can lead to a mismatch of the input latencies. Therefore, in such cases, buffering is required as shown in <figref idref="f0003">Figure 4b</figref>). Since the memory available for buffering is limited on an FPGA 10, it is often desirable to reduce the amount of buffering required.

0028In contrast, the ALAP scheme develops the data path starting with the output. Performing the analysis on the above example using ALAP gives the data path 52 shown in <figref idref="f0004">Figure 4c</figref>). As shown in <figref idref="f0004">Figure 4c</figref>), the input C has now been shifted forward by a latency unit of 1. Therefore, there is no longer a need for a buffer in the edge between Input C and adder 46. Consequently, valuable chip resources such as block memory 26 can be saved by this approach.

0029However, this approach is only suitable for certain situations. <figref idref="f0004">Figure 4d</figref>) shows a data path 54. The data path 54 corresponds to the data path 52 of <figref idref="f0004">Figure 4c</figref>); however, in this instance, an additional output 56 is added. As shown, the output 56 is offset by a latency of -1 from the original output, i.e. the result desired at the second output 56 is only that from A+B (i.e. the result from the adder 44) and so there is no need to wait for the adder 46 to perform the calculation (A+B)+C.

0030However, this data path arrangement cannot be created using ALAP because ALAP requires all outputs to have the same offset. This is because the data paths are created starting with the outputs and so the point where outputs are scheduled must be predetermined. Therefore, to implement the data path 54 shown in <figref idref="f0004">Figure 4d</figref>), the circuit shown in <figref idref="f0005">Figure 4e</figref>) is required. As shown, an additional buffer 58 is required to ensure that the outputs are all at the same offset. The additional buffer is unnecessary and results in a sub-optimal configuration and excessive and non-beneficial usage of resources.

0031For the data path 54 shown in <figref idref="f0004">Figure 4d</figref>), neither ASAP nor ALAP can schedule this design optimally with minimum use of resources. Therefore, there is a need for an optimised manner of generating optimised data paths for massively pipelined hardware such as can be implemented using FPGAs. The more optimised each data path is within an FPGA, the more data paths can be accommodated for a given FPGA with a fixed amount of block RAM 26. Consequently, the processing power of an FPGA can effectively be boosted by efficient architecture of the data paths formed thereon.

0032Attempts have been made to address these issues in related systems. <i>"</i><nplcit id="ncit0001" npl-type="b"><text>Synthesis and Optimization of Digital Circuits ", G. De Micheli, McGraw-Hill, 1994</text></nplcit> describes scheduling operations in the context of multi cycle architecture. This reference addresses minimising overall latency while spreading operations over a number of cycles.

0033<i>"</i><nplcit id="ncit0002" npl-type="s"><text>ASC: A Stream Compiler for Computing With FPGAs" O. Mencer, IEEE Transactions On Computer Aided Design Of Integrated Circuits And Systems 2006, Vol 25; No. 9, pages 1603-161</text></nplcit> describes an HDL which uses scheduling in a pipelined architecture. However, no provision is made to optimise the configuration of the FPGA data path layout.

0034Optimisation of algorithmic descriptions is known in the field of high-level synthesis. High-level synthesis is an automated design process that interprets an algorithmic description of a desired behaviour and creates hardware that implements that behaviour. The starting point is a high-level description in a language such as ANSI C, this is then translated into a control data flow graph (CDFG). Operations in the CDFG are mapped to multiple control steps, and then resources are allocated to execute the operations with the intention of using the same hardware resource to implement different algorithmic operations at different control steps.

0035Examples of the high-level synthesis approach can be found in: "<nplcit id="ncit0003" npl-type="s"><text>A Formal Approach to the Scheduling Problem in High Level Synthesis". C.T. Hwand et al, IEEE Transactions on Computer-Aided Design; Vol 10; No 4; 1991</text></nplcit>; <patcit id="pcit0001" dnum="US7000213A"><text>US-A-7,000,213</text></patcit>; <patcit id="pcit0002" dnum="US6941541A"><text>US-A-6,941,541</text></patcit>; "<nplcit id="ncit0004" npl-type="s"><text>Minimizing Buffer Requirements under Rate-Optimal Schedule in Regular Dataflow Networks", R. Govindarajan et al. ACAPS Technical Memo 69, Feb 1994, MCGill University</text></nplcit>; "<nplcit id="ncit0005" npl-type="s"><text>ILP-Based Scheduling with Time and Resource Constraints in High Level Synthesis", S. Chaudhuri and R. Walker, Proc. VLSI Design '94, pp.17-25</text></nplcit>; "<nplcit id="ncit0006" npl-type="s"><text>Rate Optimal VLSI design from data flow graph", Oh et al, submissions for 35th Design Automation Conference, DAC 98</text></nplcit>; and "<nplcit id="ncit0007" npl-type="s"><text>Scheduling algorithms for high-level synthesis" Govindarajan, Term Paper, Dept ECECS, University of Cincinnati, March 17th 1995</text></nplcit>. However, none of the above examples relates to the scheduling of optimised parallel pipelined stream processor hardware designs or their implementation on FPGAs.

0036As described above, compute units or nodes have a latency which can lead to the data becoming misaligned and mangled unless it is corrected with carefully placed buffering. Although it is straightforward to add buffering to a circuit to balance latencies this is often suboptimal and results in excessive usage of the finite amount of buffering memory provided on a typical FPGA.

0037Therefore, to date, known schemes and hardware for optimising the data path structure of parallel pipelined hardware such as can be implemented on an FPGA have suffered from the technical problem that they are not able to optimise and fully utilise the available resources of an FPGA by efficient stream scheduling.

0038According to a first aspect of the present invention, there is provided a method of generating a hardware design for a pipelined parallel stream processor, the method comprising: defining, on a computing device, a processing operation designating processes to be implemented in hardware as part of said pipelined parallel stream processor; defining, on a computing device, a graph representing said processing operation as a parallel structure in the time domain as a function of clock cycles, said graph comprising at least one data path to be implemented as a hardware design for said pipelined parallel stream processor and comprising a plurality of parallel branches configured to enable data values to be streamed therethrough, the or each data path being represented as comprising at least one input, at least one output, at least one discrete object corresponding directly to a hardware element to be implemented in hardware as part of said pipelined parallel stream processor, the or each discrete object being operable to execute a function for one or more clock cycles and having a predefined latency associated therewith, said predefined latency representing the time required for said hardware element to execute said function, said data values propagating through said data path from the at least one input to the at least one output as a function of increasing clock cycle; defining, on a computing device, the at least one data path and associated latencies of said graph as a set of algebraic linear inequalities; solving, on a computing device, said set of linear inequalities; optimising, on a computing device, the at least one data path in said graph using said solved linear inequalities to produce an optimised graph; and utilising, on a computing device, said optimised graph to define an optimised hardware design for implementation in hardware as said pipelined parallel stream processor.

0039By providing such a method, the optimisation of a hardware design for a stream processor can be considered as a global optimisation problem in which integer linear programming can be used to produce an optimal solution. This enables the hardware design, when implemented in hardware as a pipelined parallel stream processor, to utilise fully the available resources of the hardware platform. In an embodiment, the latency of each discrete object is known and predefined. This is because the hardware element (comprising one or more hardware units) represented by the discrete object has a known latency. Consequently, in an embodiment, the predefined latency is a fixed latency having a constant value.

0040In one embodiment, said processing operation comprises a mathematical function or calculation to be implemented in hardware as said pipelined parallel stream processor.

0041In one embodiment, the or each hardware element comprises one or more hardware units on said pipelined parallel stream processor.

0042In one embodiment, the or each hardware element is configured to carry out a predetermined mathematical function.

0043In one embodiment, the or each hardware element comprises one or more hardware units on said pipelined parallel stream processor and/or is configured to carry out a predetermined mathematical function.

0044In one embodiment, said step of optimising comprises minimising the amount of buffering required to schedule said data path and/or inserting, if required, buffering into at least some of the branches of said data path.

0045In one embodiment, said step of optimising comprises minimising the amount of buffering required to schedule said data path.

0046In one embodiment, said step of optimising the data path further comprises: if required, inserting buffering into at least some of the branches of said data path.

0047In one embodiment, said buffering represents memory units on said pipelined parallel stream processor.

0048In one embodiment, said buffering is minimised for the entire graph.

0049In one embodiment, said step of optimising further comprises merging two or more buffers into a single buffer. In one embodiment, said step of optimising further comprises allocating a single buffer to two or more branches of said at least one data path.

0050In one embodiment, said step of optimising further comprises merging two or more buffers into a single buffer and/or allocating a single buffer to two or more branches of said at least one data path.

0051In one embodiment, said graph comprises multiple inputs and multiple outputs, each input and each output being connected to at least one branch of said at least one data path.

0052In one embodiment, said inputs are not cycle aligned. In one embodiment, said outputs are not cycle aligned.

0053In one embodiment, said graph comprises multiple inputs and multiple outputs, each input and each output being connected to at least one branch of said at least one data path. In one embodiment, said inputs and/or outputs are not cycle aligned.

0054In one embodiment, said graph comprises multiple parallel data paths to be implemented in hardware as said pipelined parallel stream processor, and said steps of solving and optimising are carried out for each of said multiple parallel data paths.

0055In one embodiment, the method further comprises providing, on a computing device, at least one stream offset object located at a particular point in the data path, said stream offset object being operable to access, for a particular clock cycle and for said particular point in the data path, data values from a clock cycle different from said particular clock cycle.

0056In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle before said particular clock cycle.

0057In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle after said particular clock cycle.

0058In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle offset from said particular clock cycle by a preselected number of clock cycles.

0059In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle offset from said particular clock cycle by a number of clock cycles dependent upon a variable.

0060In one embodiment, the value of said variable is specified after said optimised hardware design has been implemented in hardware as said pipelined parallel stream processor.

0061In one embodiment, the value of said variable is specified before said processing operation is run on said pipelined parallel stream processor.

0062According to a second aspect of the present invention, there is provided a method of generating a hardware design for a stream processor, the method comprising: defining, on a computing device, a processing operation designating processes to be implemented in hardware as part of said stream processor; defining, on a computing device, a graph representing said processing operation in the time domain as a function of clock cycles, said graph comprising at least one data path to be implemented in hardware as part of said stream processor and configured to enable data to be streamed therethrough, the or each data path comprising at least one input, at least one output and at least one discrete object, said data propagating through said data path from the at least one input to the at least one output as a function of increasing clock cycle; providing, on a computing device, at least one stream offset object located at a particular point in the data path, said stream offset object being operable to access, for a particular clock cycle and for said particular point in the data path, data values from a clock cycle different from said particular clock cycle; optimising, on a computing device, the at least one data path in said graph to produce an optimised graph; and utilising, on a computing device, said optimised graph to define an optimised hardware design for implementation in hardware as said stream processor.

0063In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle before said particular clock cycle.

0064In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle after said particular clock cycle.

0065In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle offset from said particular clock cycle by a preselected number of clock cycles.

0066In one embodiment, said at least one stream offset object is operable to access data values from: a clock cycle before said particular clock cycle; a clock cycle after said particular clock cycle; or a clock cycle offset from said particular clock cycle by a preselected number of clock cycles.

0067In one embodiment, said at least one stream offset object is operable to access data values from a clock cycle offset from said particular clock cycle by a number of clock cycles dependent upon a variable.

0068In one embodiment, said variable is specified after said optimised hardware design has been implemented in hardware as said stream processor.

0069In one embodiment, the value of said variable is specified before said processing operation is run on said stream processor.

0070In one embodiment, the step of optimising further comprises: defining, on a computing device, said at least one data path of said graph as a set of algebraic linear inequalities; solving, on a computing device, said set of linear inequalities; optimising, on a computing device, the at least one data path in said graph using said solved linear inequalities to produce an optimised graph.

0071In one embodiment, said stream processor is implemented on a Field Programmable Gate Array or an Application Specific Integrated Circuit.

0072In one embodiment, the method further comprises the step of forming said optimised hardware design on said stream processor such that said stream processor is operable to perform said processing operation.

0073According to a third aspect of the present invention, there is provided a Field Programmable Gate Array, an Application Specific Integrated Circuit or programmable logic device, having a design generated using method of the first or second aspects.

0074According to a fourth aspect of the present invention, there is provided a system for generating a hardware stream processor design, the system comprising: a processor arranged to execute the method of one of the first or second aspects and to generate a list of instructions for the programming of a programmable logic device having the generated design.

0075According to a fifth aspect of the present invention, there is provided a method of making a programmable logic device, comprising: generating a design using the first or second aspects of the method; and programming the logic device to embody the generated design.

0076According to a sixth aspect of the present invention, there is provided a computer program arranged, when run on a computer, to execute the steps of the first or second aspects.

0077According to a seventh aspect of the present invention, there is provided a computer program according to the sixth aspect stored on a computer-readable medium.

0078According to an eighth aspect of the present invention, there is provided a Field Programmable Gate Array, other programmable logic device, or Application Specific Integrated Circuit having a design generated using method of the first or second aspects.

0079According to a ninth aspect of the present invention, there is provided a system for generating a hardware stream processor design, the system comprising: a processor arranged to execute the method of the first or second aspects and to generate a list of instructions for the programming of a programmable logic device having the generated design.

0080According to a tenth aspect of the present invention, there is provided an accelerator card comprising a Field Programmable Gate Array, an Application Specific Integrated Circuit or programmable logic device according to the third aspect.

0081According to an eleventh aspect of the present invention, there is provided a computing device comprising: a central processing unit; a memory; and at least one accelerator card according to the tenth aspect.

0082According to a twelfth aspect of the present invention, there is provided a computer program product executable by a programmable processing apparatus, comprising one or more software portions for performing the steps of the first or second aspects.

0083According to a thirteenth aspect of the present invention, there is provided a computer usable storage medium having a computer program product according to the twelfth aspect stored thereon.

0084Embodiments of the present invention will now be described in detail with reference to the accompanying drawings, in which: <ul id="ul0001" list-style="none"><li><figref idref="f0001">Figure 1</figref> is a schematic diagram of an FPGA device;</li><li><figref idref="f0001">Figure 2</figref> is a schematic diagram showing a programmable logic block forming part of the FPGA based stream processor of <figref idref="f0001">Figure 1</figref>;</li><li><figref idref="f0002">Figure 3</figref> is a schematic diagram of an example of a possible computation structure for an FPGA-based stream accelerator;</li><li><figref idref="f0003">Figure 4a</figref>) shows an example of a graph illustrating a simple data path which will result in generation of errors;</li><li><figref idref="f0003">Figure 4b</figref>) shows an example of a simple data path scheduled using ASAP in which buffering is added to ensure correct calculation;</li><li><figref idref="f0004">Figure 4c</figref>) shows an example of a simple data path scheduled using ALAP techniques;</li><li><figref idref="f0004">Figure 4d</figref>) shows an example of a desired simple data path comprising two outputs;</li><li><figref idref="f0005">Figure 4e</figref>) shows an example of the data path of <figref idref="f0004">Figure 4d</figref>) produced using ALAP techniques;</li><li><figref idref="f0005">Figure 5</figref> shows an example of two nodes and associated latencies;</li><li><figref idref="f0006">Figure 6</figref> shows the example of <figref idref="f0003">Figure 4a</figref>) with additional notation;</li><li><figref idref="f0006">Figure 7a</figref>) shows an example of the use of prevs;</li><li><figref idref="f0007">Figure 7b</figref>) shows a further example of the use of prevs;</li><li><figref idref="f0007 f0008">Figures 8a) to 8c</figref>) show the use of stream offsets;</li><li><figref idref="f0009">Figure 8d</figref>) shows the use of tapping and folding buffers;</li><li><figref idref="f0009">Figure 9</figref> shows the use of a loop;</li><li><figref idref="f0010">Figures 10a) to 10c</figref>) show the use of variable offsets and their implementation;</li><li><figref idref="f0011">Figure 11</figref> shows a schematic of a computing apparatus for carrying out the method of the present invention;</li><li><figref idref="f0011">Figure 12</figref> shows a flow chart of the method of the present invention; and</li><li><figref idref="f0012">Figure 13</figref> shows a schematic diagram of a computer apparatus suitable for use with stream processing hardware produced using the method of the present invention.</li></ul>

0085As set out above, stream computing is an efficient way to process large amounts of data with arithmetic hardware. However, the performance of stream computing devices is often limited by chip resources such as block memory 26.

0086Due to latency of hardware elements such as compute or arithmetic, and the need to hold previous values of a calculation for future calculations, buffering must be inserted. Inefficient usage of buffering will result in excessive consumption of memory on an FPGA 10. This will limit the number of data paths or kernels which can be implemented in an FPGA 10.

0087However, there are many options for the placement of this buffering. Placing the buffering optimally can be considered to be a global optimisation problem. In this regard, integer linear programming can be used to produce an optimal solution.

0088As set out above, a graph is a way of describing an algorithm as a parallel structure in the time domain using a data path to represent the desired algorithm. A data path can be represented graphically as a mathematical structure consisting of a group of nodes connected by edges. Nodes represent discrete objects such as arithmetic units or compute units. Edges represent connections between two nodes. In other words, nodes represent operations and edges show where the output of each operation feeds into the input of another.

0089Both nodes and edges may have attributes; for example nodes may have particular properties such as an associated latency. Additionally, edges may have an associated direction.

0090A typical FPGA 10 will comprise a number of discrete data paths. The number of data paths on a typical FPGA is typically around 10 or less. However, each data path may comprise a multiplicity of parallel branches which comprise, in total typically 10² to 10⁵ computation elements. This enables massively parallel calculations to be performed. Considering each of these data paths, an optimal solution to the global minimisation of a multiplicity of data paths including data branches on an FPGA is sought.

0091<figref idref="f0005">Figure 5</figref> shows the underlying principle of the present invention. <figref idref="f0005">Figure 5</figref> shows two nodes 102, 104. The node 102 has an input 106 and an output 108. The node 104 has an input 110 and an output 112. The two nodes 102, 104 are connected together by an edge 114. The edge 114 extends between the output 106 of node 102 and the input 110 of node 104.

0092Node 102 is the "parent" node <i>m</i> and node 104 is the "child" node <i>n.</i> Data arrives at the parent node <i>m</i> 102 at time T(<i>m</i>). Since the node 102 comprises a compute unit, a finite amount of time is required for the computation on received data to be performed. Such a computation may involve LUTs, shift registers or other elements. The time required to perform the calculation is known as the latency of the parent node <i>m</i> 102 and is defined as λ(<i>m</i>). The nodes 102, 104 are representative of, and correspond to, one or more hardware units (i.e. CLBs 12) on the FPGA 10 and the latencies thereof correspond to those of the actual hardware.

0093Therefore, the data will arrive at the input 110 of the child node <i>n</i> 104 at time T (<i>n</i>). T (<i>n</i>) must, therefore, be greater than or equal to the time T(<i>m</i>) that the data arrives at the input 106 of the parent <i>m,</i> plus the latency λ(<i>m</i>) of the parent node <i>m</i> 102. The time T (<i>n</i>) will only be equal to T(<i>m</i>) plus λ(<i>m</i>) if the edge 114 has zero latency. In the common case, edges do not have a latency since they do not contain any flip-flops and only represent connections between nodes. In the following examples, nodes are described as having latency. However, alternative formulations may be utilised whereby edges are defined as having a latency, or both nodes and edges may have associated latencies.

0094Additionally, input latencies can also be taken into account by being added to the output latencies, although in these examples all input latencies will be assumed to be zero.

0095Therefore, where there are N nodes, the arrangement of <figref idref="f0005">Figure 5</figref> can be expressed algebraically as set out in expression 1): <maths id="math0002" num="1)"><math display="block"><mo>∀</mo><mfenced><mi>n</mi><mo>⁢</mo><mi>m</mi></mfenced><mo>⋅</mo><mo>∈</mo><mi mathvariant="italic">NxN</mi><mn>.</mn><mrow><mi mathvariant="italic">child</mi><mfenced><mi>n</mi><mo>⁢</mo><mi>m</mi></mfenced><mo>)</mo></mrow><mo>→</mo><mi>T</mi><mfenced><mi>n</mi></mfenced><mo>≥</mo><mi>T</mi><mfenced><mi>m</mi></mfenced><mo>+</mo><mi>λ</mi><mfenced><mi>m</mi></mfenced></math><img file="EP2490141A2_D0002.tif" /></maths>

0096Now, taking the example of <figref idref="f0003">Figure 4a</figref>), a set of linear inequalities can be produced. <figref idref="f0006">Figure 6</figref> shows the data path of <figref idref="f0003">Figure 4a</figref>) but with additional notation allocating each node a reference between <i>n1</i> to <i>n5.</i>

0097Now, as shown in <figref idref="f0006">Figure 6</figref>, the data path 40 of <figref idref="f0003">Figure 4a</figref>) and <figref idref="f0006">Figure 6</figref> can be expressed as a series of linear constraints, assuming that the addition operations have a latency of 1 cycle, as set out in expression 2): <maths id="math0003" num="2)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">3</mn></mfenced><mo mathvariant="italic">≥</mo><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">0</mn></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">3</mn></mfenced><mo mathvariant="italic">≥</mo><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">4</mn></mfenced><mo mathvariant="italic">≥</mo><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">3</mn></mfenced><mo>+</mo><mn mathvariant="italic">1</mn></mtd></mtr><mtr><mtd><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">4</mn></mfenced><mo mathvariant="italic">≥</mo><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">5</mn></mfenced><mo mathvariant="italic">≥</mo><mi mathvariant="italic">T</mi><mfenced><mi mathvariant="italic">n</mi><mo>⁢</mo><mn mathvariant="italic">4</mn></mfenced><mo mathvariant="italic">+</mo><mn mathvariant="italic">1</mn></mtd></mtr></mtable></math><img file="EP2490141A2_D0003.tif" /></maths>

0098In addition to these linear constraints, we can also formulate a linear expression of the total amount of buffering needed to meet these constraints as set out in expression 3): <maths id="math0004" num="3)"><math display="block"><mtable columnalign="left"><mtr><mtd><mo>∀</mo><mi>e</mi><mo>∈</mo><mi mathvariant="italic">edges</mi><mo>→</mo><mi>B</mi><mfenced><mi>e</mi></mfenced><mo>=</mo><mi>T</mi><mfenced><mi>e</mi><mn>.</mn><mi mathvariant="italic">destnode</mi></mfenced><mo>-</mo><mi>T</mi><mfenced><mi>e</mi><mn>.</mn><mi mathvariant="italic">sourcenode</mi></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="italic">totalbuffering</mi><mo>=</mo><mfenced><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>e</mi><mo>∈</mo><mi mathvariant="italic">dges</mi></mrow></munder></mstyle><mi>B</mi><mfenced><mi>e</mi></mfenced></mstyle><mo>×</mo><mi mathvariant="italic">bitwidth</mi><mfenced><mi>e</mi></mfenced></mfenced></mtd></mtr></mtable></math><img file="EP2490141A2_D0004.tif" /></maths>

0099This expression for the total amount of buffering in 3) can be optimally minimised in the presence of the constraints in 2) using an Integer Linear Programming solver, for example, the GNU Linear Programming Kit (GLPK). The result of this minimisation will be a "schedule" of fixed values for <i>T(n)</i> for all nodes in the graph such that total buffering is minimal. As buffering is minimised block memory usage in the FPGA 10 is also minimised. As discussed, block memory usage can often be a limiting factor in FPGA design.

0100One other important feature of data paths which can be optimised by the present invention is what is known as "prevs" or previous values. Prevs enable previous values to be used in a calculation e.g. to look 10 cycles back in the stream use a prev of size 10. For example, take the calculation in equation 4): <maths id="math0005" num="4)"><math display="block"><mi mathvariant="italic">a</mi><mfenced open="[" close="]"><mi mathvariant="italic">i</mi></mfenced><mo mathvariant="italic">=</mo><mi mathvariant="italic">a</mi><mfenced open="[" close="]"><mi mathvariant="italic">i</mi></mfenced><mo mathvariant="italic">+</mo><mfenced><mi mathvariant="italic">a</mi><mo>⁢</mo><mfenced open="[" close="]"><mi mathvariant="italic">i</mi><mo mathvariant="italic">-</mo><mn mathvariant="italic">1</mn></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">b</mi><mo>⁢</mo><mfenced open="[" close="]"><mi mathvariant="italic">i</mi><mo mathvariant="italic">-</mo><mn mathvariant="italic">1</mn></mfenced></mfenced></math><img file="EP2490141A2_D0005.tif" /></maths>

0101This can be described as: <maths id="math0006" num="5)"><math display="block"><mi mathvariant="italic">a</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">a</mi><mo mathvariant="italic">+</mo><mfenced><mi mathvariant="italic">prev</mi><mfenced><mi mathvariant="italic">a</mi></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">prev</mi><mfenced><mi mathvariant="italic">b</mi></mfenced></mfenced></math><img file="EP2490141A2_D0006.tif" /></maths>

0102Commonly, prevs are implemented as a buffer with zero latency. The buffer size is the delay that will be introduced on the data, causing a previous value to be presented on the output. This is illustrated in <figref idref="f0006">Figure 7a</figref>), implementing equation 5). Therefore, to achieve the above, it is necessary to provide two buffers (labelled prev (1) in <figref idref="f0006">Figure 7a</figref>)) with zero latency and, in order to schedule the data path correctly given the latency of the adder nodes, a single buffer of latency 1 - making the total buffer count 3.

0103In contrast, prevs in the present invention can be defined as stream offsets looking backwards in the stream and are, thus, equivalent to identity nodes with negative latency. Therefore, in the present invention, the scheduling can be optimised globally and the data path of <figref idref="f0006">Figure 7a</figref>) could be replaced by the arrangement of <figref idref="f0007">Figure 7b</figref>). As shown, through the use of stream offsets, shown as diamond shaped nodes, this circuit is scheduled and requires zero buffering. This is because the latency of the first adder node has been used to provide the necessary delay for the second adder node and no additional buffering is required as a result.

0104So, in other words, the use of stream offset nodes produces no hardware directly, but after scheduling the data will be offset by the correct amount in the right places. This is highly efficient because some of the individual latencies can be cancelled out and implementation latencies can be utilised.

0105A further common type of function is a discard. In the example of the following algebraic expression: <maths id="math0007" num="6)"><math display="block"><mi mathvariant="italic">Output</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">discard</mi><mo>⁢</mo><mfenced><mi mathvariant="italic">prev</mi><mfenced><mi mathvariant="italic">a</mi></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">a</mi></mfenced></math><img file="EP2490141A2_D0007.tif" /></maths>

0106A circuit implementing the sub-equation <i>prev(a)</i>+<i>a</i> would generate an invalid result on the first cycle because, since the prev function will delay one output by a cycle, on the first cycle only <i>a</i> reaches the adder and not <i>prev(a).</i> Therefore, the first cycle will comprise invalid data. This can be addressed by the use of the discard which simply discards the first (invalid) result and passes the next result to the output. If a prev is a request for a previous value of a data stream, a discard can be thought of as requesting a "future" value.

0107Thus prevs and discards can both be generalised as stream offsets. Therefore, for a variable a with desired offset <i>n</i>, a prev or discard can be represented as: <maths id="math0008" num="7)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">Prev</mi><mfenced><mi mathvariant="italic">a</mi><mo>⁢</mo><mi mathvariant="italic">n</mi></mfenced><mo mathvariant="italic">=</mo><mi mathvariant="italic">streamOffset</mi><mo>⁢</mo><mfenced><mi mathvariant="italic">a</mi><mo mathvariant="italic">,</mo><mo>-</mo><mi mathvariant="italic">n</mi></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="italic">Discard</mi><mfenced><mi mathvariant="italic">a</mi><mo>⁢</mo><mi mathvariant="italic">n</mi></mfenced><mo mathvariant="italic">=</mo><mi mathvariant="italic">streamOffset</mi><mfenced><mi mathvariant="italic">a</mi><mo>⁢</mo><mi mathvariant="italic">n</mi></mfenced></mtd></mtr></mtable></math><img file="EP2490141A2_D0008.tif" /></maths>

0108So, as an example, take equation 8): <maths id="math0009" num="8)"><math display="block"><mi mathvariant="italic">a</mi><mfenced open="[" close="]"><mi mathvariant="italic">i</mi></mfenced><mo mathvariant="italic">=</mo><mi mathvariant="italic">a</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">a</mi><mo>⁢</mo><mfenced open="[" close="]"><mi mathvariant="italic">i</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">1</mn></mfenced></math><img file="EP2490141A2_D0009.tif" /></maths>

0109Equation 8) can be written under the new formulation as: <maths id="math0010" num="9)"><math display="block"><mi mathvariant="italic">a</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">a</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">streamOffset</mi><mo>⁢</mo><mfenced><mi mathvariant="italic">a</mi><mo mathvariant="italic">,</mo><mo mathvariant="italic">+</mo><mn mathvariant="italic">1</mn></mfenced></math><img file="EP2490141A2_D0010.tif" /></maths>

0110As a practical example of the optimisation process, take equation 10): <maths id="math0011" num="10)"><math display="block"><mi mathvariant="italic">a</mi><mfenced open="[" close="]"><mi mathvariant="italic">i</mi></mfenced><mo mathvariant="italic">=</mo><mi mathvariant="italic">a</mi><mo>⁢</mo><mfenced open="[" close="]"><mi mathvariant="italic">i</mi><mo mathvariant="italic">-</mo><mn mathvariant="italic">10</mn></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">a</mi><mfenced open="[" close="]"><mi mathvariant="italic">i</mi></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">a</mi><mo>⁢</mo><mfenced open="[" close="]"><mi mathvariant="italic">i</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">10</mn></mfenced></math><img file="EP2490141A2_D0011.tif" /></maths>

0111This is a common case and can be represented in the present invention as: <maths id="math0012" num="11)"><math display="block"><mi mathvariant="italic">a</mi><mo mathvariant="italic">=</mo><mi mathvariant="italic">streamOffset</mi><mo>⁢</mo><mfenced><mi mathvariant="italic">a</mi><mo mathvariant="italic">,</mo><mo>-</mo><mn mathvariant="italic">10</mn></mfenced><mo>+</mo><mi>a</mi><mo>+</mo><mi mathvariant="italic">streamOffset</mi><mfenced><mi mathvariant="italic">a</mi><mo>⁢</mo><mn mathvariant="italic">10</mn></mfenced></math><img file="EP2490141A2_D0012.tif" /></maths>

0112The data path for this is shown in <figref idref="f0007">Figure 8a</figref>), and the scheduled data path configuration in <figref idref="f0008">Figure 8b</figref>). As shown, a buffering total of 28 is required in this arrangement. Notice that the buffers allocated are of size 19 and 9 rather than 20 and 10, since the 1 cycle latency of the adder has been taken into account.

0113This buffering can be reduced further through a further process known as tap and fold.

0114<figref idref="f0008">Figure 8c</figref>) shows an example of "tapping". In this example, the separate buffers of 19 and 9 have been replaced by a common buffer of 9 and a further buffer of 10, saving a buffer of 9.

0115Additionally, <figref idref="f0009">Figure 8 d)</figref> shows an example of "folding" where two buffers can be combined into one. This is important since separate buffer allocations may be allocated different memory resources. To explain, block memory is often allocated in units of 18Kbit or 36Kbit. When a buffer is allocated, whether the whole of the buffer or only a part thereof is utilised is irrelevant. For a smaller buffer, the access addresses to the buffer change and only a part of the buffer is used. However, the remainder of the buffer is not usable by other data paths. Therefore, being able to "fold" or condense the buffers is important in resource management.

0116The method of the present invention is also operable to handle loops. If feedback is included in a data path pipeline of this type, then a dependency loop is introduced. This presents a problem in a particular pipeline if the data can not complete an entire circuit of the loop in one cycle.

0117Traditionally, these issues are solved by the insertion of a buffer. This is usually done manually to balance the size of the buffer against the latency of the circuit and schedule the data.

0118However, considering this problem with the present approach, in order to satisfy the scheduling linear equations, the latency of the whole loop must be zero. This is possible by the insertion of a negative stream offset. If the negative stream offset is large enough, the circuit will give the result expected from the source code. Otherwise, the compilation will fail. However, the failure provides valuable feedback to the user. For example, if the compilation fails, this indicates that the loop is not possible. The manual insertion of a buffer that is required in other methods is eliminated, and the amount of buffer memory required is optimised since the latency of the full loop is considered. An example of a loop formed using the present invention is shown in <figref idref="f0009">Figure 9</figref>.

0119In some situations, it is not appropriate to use fixed latencies. Such a situation may arise, for example, in a case where it is desired to access points in a multidimensional data set offset by one or more rows, but where the actual size of the data set is not initially known. This is when variable latencies are useful - when using offsets to access points in a two or three dimensional data block with a size unknown when compiling the data paths.

0120Consider, as an example, a two dimensional block of 100 x 100 data points. In this case, to access a point on the previous row an offset of -100 is required. However, if the dimensions of the block are not known when compiling the data path, it is not possible to provide an offset which will select data on different rows.

0121However, even if the size it not known when compiling, it is possible to describe the block dimensions algebraically as <i>nx</i> x <i>ny.</i> Therefore, to access different rows, an offset of -<i>nx</i> is required. Further, algebraic latencies can be optimised by breaking them down into separate coefficients. These systems can then be solved independently. For example suppose we have algebraic inequalities as set out in expression 12) below: <maths id="math0013" num="12)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">0</mn><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo mathvariant="italic">+</mo><mi mathvariant="italic">nx</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">2</mn><mo>⁢</mo><mi mathvariant="italic">nxy</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">10</mn></mtd></mtr><mtr><mtd><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">3</mn><mo>⁢</mo><mi mathvariant="italic">nx</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">4</mn><mo>⁢</mo><mi mathvariant="italic">nxy</mi><mo mathvariant="italic">+</mo><mn mathvariant="italic">20</mn></mtd></mtr><mtr><mtd><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mn mathvariant="italic">30</mn></mtd></mtr></mtable></math><img file="EP2490141A2_D0013.tif" /></maths>

0122These expressions cannot be solved directly using a linear solver as the values for <i>nx</i> and <i>nxy</i> are not known. To deal with this, we can break them down into a set of separate inequalities in terms only of <i>nx</i>, <i>nxy</i> and the constant part of the expression, respectively, which can be solved. For expression 12) this is done as follows: <maths id="math0014" num="13)"><math display="block"><mtable columnalign="left"><mtr><mtd><mfenced><mi mathvariant="italic">for nx</mi></mfenced></mtd><mtd><msub><mrow><mi>t</mi><mo>⁢</mo><mn mathvariant="italic">0</mn></mrow><mi mathvariant="italic">nx</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">1</mn></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow><mi mathvariant="italic">nx</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">3</mn></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow><mi mathvariant="italic">nx</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mn>0</mn></mtd></mtr></mtable></math><img file="EP2490141A2_D0014.tif" /></maths><maths id="math0015" num="14)"><math display="block"><mtable columnalign="left"><mtr><mtd><mfenced><mi mathvariant="italic">for nxy</mi></mfenced></mtd><mtd><msub><mrow><mi>t</mi><mo>⁢</mo><mn mathvariant="italic">0</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">2</mn></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">4</mn></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mn>0</mn></mtd></mtr></mtable></math><img file="EP2490141A2_D0015.tif" /></maths> and <maths id="math0016" num="15)"><math display="block"><mtable columnalign="left"><mtr><mtd><mfenced><mi mathvariant="italic">for the constant part</mi></mfenced></mtd></mtr><mtr><mtd><mspace width="2em" /><msub><mrow><mi>t</mi><mo>⁢</mo><mn mathvariant="italic">0</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">2</mn></mtd></mtr><mtr><mtd><mspace width="2em" /><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo mathvariant="italic">+</mo><mn mathvariant="italic">4</mn></mtd></mtr><mtr><mtd><mspace width="2em" /><msub><mrow><mi mathvariant="italic">t</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow><mi mathvariant="italic">nxy</mi></msub><mo mathvariant="italic">></mo><mo mathvariant="italic">=</mo><mn>0</mn></mtd></mtr></mtable></math><img file="EP2490141A2_D0016.tif" /></maths>

0123Once the inequalities for <i>nx</i>, <i>nxy,</i> and the constant parts have been solved, they can be combined using addition to generate the final "schedule" for the graph as follows: <maths id="math0017" num="16)"><math display="block"><mi>T</mi><mfenced><mi>n</mi></mfenced><mo>=</mo><msub><mi>T</mi><mi mathvariant="italic">nx</mi></msub><mfenced><mi>n</mi></mfenced><mo>+</mo><msub><mi>T</mi><mi mathvariant="italic">nxy</mi></msub><mfenced><mi>n</mi></mfenced><mo>+</mo><msub><mi>T</mi><mi>c</mi></msub><mfenced><mi>n</mi></mfenced></math><img file="EP2490141A2_D0017.tif" /></maths>

0124In the case where the variable offset is <i>nx</i>, a schedule for the constants is produced (<figref idref="f0010">Figure 10a</figref>), together with the schedule for nx (shown in <figref idref="f0010">Figure 10b</figref>) and then combined to give the resultant schedule which is shown in <figref idref="f0010">Figure 10c</figref>). Such offsets can be easily implemented in the method of the present invention, to afford greater flexibility to production of FPGA designs where the actual size of the data blocks are unknown when compiling the FPGA (i.e. when implementing the hardware design for the stream processor in the FPGA).

0125The physical buffer memories on chip can be allocated for the maximum allowable size of <i>nx</i> and if smaller values of <i>nx</i> are required at runtime then only part of the buffer will be utilized. However the generated circuit contains optimally minimal amount of buffering given the specified minimum and maximum values of <i>nx.</i>

0126An implementation of the present invention will now be described with reference to <figref idref="f0011">Figures 11 and 12</figref>.

Step 300: Initialise library

0127The method of the present invention can be run on a standard computing apparatus 400 or other programmed or programmable apparatus running an operating system such as Windows or Linux.

0128In this embodiment, the method is implemented as application 402 which utilises a Java library 404. However, other languages may be used and these will be apparent to the skilled person. For example, the application could be run in C, C++ or any other suitable programming language.

0129The application 402 has a graphical user interface (GUI) 406 which enables a use of the computing apparatus 400 to enter commands and access the application.

0130At step 300, the application and Java library is initialised. The method then proceeds to step 302.

Step 302: Specify data expressions

0131Through the GUI 406, the user specifies the desired data flow as expressions. These may comprise commands such as <i>add (add(a, b), c).</i> As an example, the user may wish to process a typical 2D cross convolution as defined in expression 18) below. Expression 18) uses, for conciseness, shorthand terminology where: <ul id="ul0002" list-style="none"><li><i>a * b</i> means <i>mul(a, b)</i> creating a multiply node with two inputs;</li><li><i>a + b</i> means <i>add(a, b)</i> creating an add node with two inputs; and</li><li><i>a[b]</i> means <i>streamOffset(a, b)</i> creating a stream offset node with one input and offset of <i>b</i>.</li></ul><maths id="math0018" num="18)"><math display="block"><mi>o</mi><mo>=</mo><mi>c</mi><mo>*</mo><mfenced><mi mathvariant="italic">i</mi><mfenced open="[" close="]"><mo mathvariant="italic">-</mo><mi mathvariant="italic">nx</mi></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">i</mi><mfenced open="[" close="]"><mo mathvariant="italic">-</mo><mn mathvariant="italic">1</mn></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">i</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">i</mi><mfenced open="[" close="]"><mn mathvariant="italic">1</mn></mfenced><mo mathvariant="italic">+</mo><mi mathvariant="italic">i</mi><mfenced open="[" close="]"><mi mathvariant="italic">nx</mi></mfenced></mfenced></math><img file="EP2490141A2_D0018.tif" /></maths> where <i>o</i> is the output, <i>i</i> is the input and <i>nx</i> is the variable size of the fast dimension in the dataset.

0132Once these commands and expressions have been entered, the method proceeds to step 304.

Step 304: Produce graph

0133Once the commands have been entered at step 302, the application 402 utilises the Java library 404 to produce a graph represented by Java objects. Using the example outlined above in expression 18), this will generate a graph such as: <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="17mm" /><colspec colnum="2" colname="col2" colwidth="30mm" /><colspec colnum="3" colname="col3" colwidth="15mm" /><thead><row><entry valign="top"><b><i>Node ID</i></b></entry><entry valign="top"><b><i>Type</i></b></entry><entry valign="top"><b><i>Inputs</i></b></entry></row></thead><tbody><row><entry>0</entry><entry>Input (<i>i</i>)</entry><entry>-</entry></row><row><entry>1</entry><entry>Stream offset (-<i>nx</i>)</entry><entry>0</entry></row><row><entry>2</entry><entry>Stream offset (-1)</entry><entry>0</entry></row><row><entry>3</entry><entry>Stream offset (1)</entry><entry>0</entry></row><row><entry>4</entry><entry>Stream offset (<i>nx</i>)</entry><entry>0</entry></row><row><entry>5</entry><entry>Add</entry><entry>1 2</entry></row><row><entry>6</entry><entry>Add</entry><entry>5 0</entry></row><row><entry>7</entry><entry>Add</entry><entry>6 3</entry></row><row><entry>8</entry><entry>Add</entry><entry>7 4</entry></row><row><entry>9</entry><entry>Constant (<i>c</i>)</entry><entry>-</entry></row><row><entry>10</entry><entry>Multiply</entry><entry>98</entry></row><row><entry>11</entry><entry>Output (<i>o</i>)</entry><entry>10</entry></row></tbody></tgroup></table></tables>

0134The method then proceeds to step 306.

Step 306: Extract and process latency information

0135In step 306, the latency information in the graph produced in step 304 is extracted. To take the example illustrated in expression 18), this produces latencies as follows: <tables id="tabl0002" num="0002"><table frame="all"><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="29mm" /><colspec colnum="2" colname="col2" colwidth="18mm" /><thead><row><entry valign="top"><b><i>Type</i></b></entry><entry valign="top"><b><i>Latency</i></b></entry></row></thead><tbody><row><entry>Input</entry><entry>1</entry></row><row><entry>Stream offset (<i>x</i>)</entry><entry><i>x</i></entry></row><row><entry>Add</entry><entry>1</entry></row><row><entry>Constant</entry><entry>0</entry></row><row><entry>Multiply</entry><entry>10</entry></row></tbody></tgroup></table></tables>

0136The method then proceeds to step 308.

Step 308: Define linear inequalities and buffering expressions

0137From the above definition of the graph as set out in step 302 and associated latencies defined or assumed in step 306, the method then generates a set of linear inequalities defining each of the data paths. Using the example of expression 18) this provides the following combination of constraints and buffering expressions for the constant parts of the latencies for nodes in the graph: <tables id="tabl0003" num="0003"><table frame="all"><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="29mm" /><colspec colnum="2" colname="col2" colwidth="31mm" /><tbody><row><entry><i>T1</i> > = <i>T0</i> + <i>1</i></entry><entry><i>B0</i> = <i>T1</i> - <i>T0</i> - <i>1</i></entry></row><row><entry><i>T2</i> > = <i>T0</i> + <i>1</i></entry><entry><i>B0</i> = <i>T2</i> - <i>T0</i> - <i>1</i></entry></row><row><entry><i>T3</i> > = <i>T0</i> + <i>1</i></entry><entry><i>B0</i> = <i>T3</i> - <i>T0</i> - <i>1</i></entry></row><row><entry><i>T4</i> > = <i>T0</i> + <i>1</i></entry><entry><i>B0</i> = <i>T4</i> - <i>T0</i> + <i>1</i></entry></row><row><entry><i>T5</i> > = <i>T1</i></entry><entry><i>B0</i> = <i>T6 - T0</i> - <i>1</i></entry></row><row><entry><i>T5</i> > = <i>T2</i> - <i>1</i></entry><entry><i>B1</i> = <i>T5 - T1</i></entry></row><row><entry><i>T6</i> > = <i>T5</i> + <i>1</i></entry><entry>B<i>2</i> = <i>T5</i> - <i>T2</i> + <i>1</i></entry></row><row><entry><i>T6</i> > = <i>T0</i> + <i>1</i></entry><entry><i>B3</i> = <i>T7</i> - <i>T3</i> - <i>1</i></entry></row><row><entry><i>T7</i> > = <i>T6</i> + <i>1</i></entry><entry><i>B4</i> = <i>T8</i> - <i>T4</i></entry></row><row><entry><i>T7</i> > = <i>T3</i> + <i>1</i></entry><entry><i>B5</i> = <i>T6 - T5</i> - <i>1</i></entry></row><row><entry><i>T8</i> > = <i>T7</i> + <i>1</i></entry><entry><i>B6</i> = <i>T7</i> - <i>T6</i> - <i>1</i></entry></row><row><entry><i>T8</i> > = <i>T4</i></entry><entry><i>B7</i> = <i>T8</i> - <i>T7</i> - <i>1</i></entry></row><row><entry><i>T10</i> > = <i>T9</i></entry><entry><i>B8</i> = <i>T10</i> - <i>T8</i> - <i>1</i></entry></row><row><entry><i>T10</i> > = <i>T8</i> + <i>1</i></entry><entry><i>B9</i> = <i>T10</i> - <i>T9</i></entry></row><row><entry><i>T11 > = T10 + 10</i></entry><entry><i>B10 = T11 T10 - 10</i></entry></row></tbody></tgroup></table></tables>

0138And the following constraints and buffering expressions for nx: <tables id="tabl0004" num="0004"><table frame="all"><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="23mm" /><colspec colnum="2" colname="col2" colwidth="27mm" /><tbody><row><entry><i>T</i>1 > = <i>T0</i></entry><entry><i>B0</i> = <i>T1</i> - <i>T0</i></entry></row><row><entry><i>T2</i> > = <i>T0</i></entry><entry><i>B0</i> = <i>T2</i> - <i>T0</i></entry></row><row><entry><i>T3</i> > = <i>T0</i></entry><entry><i>B0</i> = <i>T3</i> - <i>T0</i></entry></row><row><entry><i>T4</i> > = <i>T0</i></entry><entry><i>B0</i> = <i>T4</i> - <i>T0</i></entry></row><row><entry><i>T5</i> > = <i>T1</i> - <i>1</i></entry><entry><i>B0</i> = <i>T6</i> - <i>T0</i></entry></row><row><entry><i>T5</i> > = <i>T2</i></entry><entry><i>B1</i> = <i>T5</i> - <i>T1 + 1</i></entry></row><row><entry><i>T6</i> > = <i>T5</i></entry><entry><i>B2</i> = <i>T5 - T2</i></entry></row><row><entry><i>T6</i> > = <i>T0</i></entry><entry><i>B3</i> = <i>T7</i> - <i>T3</i></entry></row><row><entry><i>T7</i> > = <i>T6</i></entry><entry><i>B4</i> = <i>T8</i> - <i>T4</i> -<i>1</i></entry></row><row><entry><i>T7</i> > = <i>T3</i></entry><entry><i>B5</i> = <i>T6</i> - <i>T5</i></entry></row><row><entry><i>T8</i> > = <i>T7</i></entry><entry><i>B6</i> = <i>T7</i> - <i>T6</i></entry></row><row><entry><i>T8</i> > = <i>T4 + 1</i></entry><entry><i>B7</i> = <i>T8</i> - <i>T7</i></entry></row><row><entry><i>T10</i> > = <i>T9</i></entry><entry><i>B8</i> = <i>T10</i> - <i>T8</i></entry></row><row><entry><i>T10</i> > = <i>T8</i></entry><entry><i>B9</i> = <i>T10</i> - <i>T9</i></entry></row><row><entry><i>T11</i> > = <i>T10</i></entry><entry><i>B10</i> = <i>T11</i> - <i>T10</i></entry></row></tbody></tgroup></table></tables>

0139Once the constraints have been set as a group of linear inequalities, the method proceeds to step 310.

Step 310: Solve linear inequalities

0140At step 310, the linear inequalities generated in step 310 are solved. The linear inequalities may be solved by running them through an integer linear programming (ILP) solver. Such a linear system can be solved using, for example, the GNU Linear Programming Kit (GLPK). Thus, taking the example used here, expression 19) below is minimised for both the constants and for <i>nx:</i><maths id="math0019" num="19)"><math display="block"><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">0</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">1</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">2</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">3</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">4</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">5</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">6</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">7</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">8</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">9</mn><mo>+</mo><mi mathvariant="italic">B</mi><mo>⁢</mo><mn mathvariant="italic">10</mn></math><img file="EP2490141A2_D0019.tif" /></maths>

0141The result of the minimisation produces a pipeline schedule as set out below: <tables id="tabl0005" num="0005"><table frame="all"><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="18mm" /><colspec colnum="2" colname="col2" colwidth="19mm" /><colspec colnum="3" colname="col3" colwidth="10mm" /><colspec colnum="4" colname="col4" colwidth="22mm" /><thead><row><entry valign="top"><b><i>Variable</i></b></entry><entry valign="top"><b><i>Constant</i></b></entry><entry valign="top"><b>nx</b></entry><entry valign="top"><b><i>Actual time</i></b></entry></row></thead><tbody><row><entry><i>T0</i></entry><entry><i>0</i></entry><entry><i>0</i></entry><entry><i>0</i></entry></row><row><entry><i>T1</i></entry><entry><i>1</i></entry><entry><i>1</i></entry><entry><i>nx + 1</i></entry></row><row><entry><i>T2</i></entry><entry><i>2</i></entry><entry><i>0</i></entry><entry><i>2</i></entry></row><row><entry><i>T3</i></entry><entry><i>2</i></entry><entry><i>0</i></entry><entry><i>2</i></entry></row><row><entry><i>T4</i></entry><entry><i>4</i></entry><entry><i>0</i></entry><entry><i>4</i></entry></row><row><entry><i>T5</i></entry><entry><i>1</i></entry><entry><i>0</i></entry><entry><i>1</i></entry></row><row><entry><i>T6</i></entry><entry><i>2</i></entry><entry><i>0</i></entry><entry><i>2</i></entry></row><row><entry><i>T7</i></entry><entry><i>3</i></entry><entry><i>0</i></entry><entry><i>3</i></entry></row><row><entry><i>T8</i></entry><entry><i>4</i></entry><entry><i>1</i></entry><entry><i>nx</i> + <i>4</i></entry></row><row><entry><i>T9</i></entry><entry><i>5</i></entry><entry><i>1</i></entry><entry><i>nx</i> + <i>5</i></entry></row><row><entry><i>T10</i></entry><entry><i>5</i></entry><entry><i>1</i></entry><entry><i>nx</i> + <i>5</i></entry></row><row><entry><i>T11</i></entry><entry><i>15</i></entry><entry><i>1</i></entry><entry><i>nx</i> + <i>15</i></entry></row></tbody></tgroup></table></tables>

0142The method then proceeds to step 312.

Step 312: Insert buffering to graph

0143Once the minimised schedule computed in step 310 has been determined, the schedule is applied to the graph through the insertion of buffer nodes to meet the schedule. To use the example defined above, this produces buffering as follows: <tables id="tabl0006" num="0006"><table frame="all"><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="12mm" /><colspec colnum="2" colname="col2" colwidth="10mm" /><tbody><row><entry><i>0</i> -> <i>2</i></entry><entry><i>1</i></entry></row><row><entry><i>0</i> -> <i>3</i></entry><entry><i>1</i></entry></row><row><entry><i>0</i> -> <i>4</i></entry><entry><i>3</i></entry></row><row><entry><i>1</i> -> <i>5</i></entry><entry><i>nx</i></entry></row><row><entry><i>7</i> -> <i>8</i></entry><entry><i>nx</i></entry></row></tbody></tgroup></table></tables>

0144The method then proceeds to step 314.

Step 314: Optimise buffering

0145Various optimisation passes can run on the data paths. This may include tap and fold operations as described previously. A fold operation is where two buffers appear end to end and can be merged into one longer buffer.

0146As described above, tapping is where two buffers are present coming from the same node output going to different node inputs. In this case, the buffers can be converted to two chained buffers. For example, two buffers length <i>M</i> and <i>N</i> where <i>M</i> > <i>N</i> can be converted into a buffer of length N followed by one of length (<i>M - N</i>). This can save a lot of on chip memory through use of space which would otherwise be wasted.

0147In the example described above, the 3 buffers coming out of node 0 (total length 5) can be tapped into one buffer of length 1 followed by one buffer of length 2 (total length 3). This value 3 corresponds to the final value of B0.

0148Once the schedule has been defined, the method proceeds to step 316.

Step 316: Compile graph

0149Once the optimised schedule has been determined, the graph can be compiled into a format such that the physical FPGA can then be formed. Compilers and compilation methods are well known in the art and the skilled person would be readily aware of software, hardware and implementations that could be used with the present invention. The method then proceeds to step 318.

Step 318: Produce FPGA design

0150Once the graph has been compiled into the correct format in step 316, the FPGA design for the stream processor is formed. The FPGA design can then, optionally, be used to implement the optimised data paths (or kernels) and data flow in hardware. Once the FPGA design has been formed in hardware on an FPGA chip or device, it can be used as required by the end user to perform the stream calculations defined in step 302.

0151<figref idref="f0012">Figure 13</figref> shows a schematic view of a computing device 500 with which an FPGA design 502 formed using the method of the present invention may be used. The computing device 500 comprises a Central Processing Unit (CPU) 504, a main memory 506 and a data bus 508.

0152The CPU 504 may take any suitable form and comprises a processor for carrying out the instructions of a computer program run on the computing device 500. The CPU 504 is the primary element carrying out the functions of the computing device 500 as is well known in the art. The CPU 504 is commonly located on a motherboard (not shown) which comprises the necessary contacts to supply the CPU 504 with power and to connect the CPU 504 to other components in the computing device 500.

0153The main memory 506 is associated with the CPU 504 and comprises an area of RAM. The RAM may take the form of SRAM, Dynamic RAM (DRAM) in which bits of data are stored as a charge in a capacitor or transistor gate, or any other suitable memory type. As is common for many computing applications, the main memory 506 may be provided as a plurality of SRAM or DRAM modules. These modules can quickly be replaced should they become damaged or when greater storage capacity is required. The main memory 506 is able to communicate with the CPU 504 via the motherboard forming part of the computing device 500.

0154The data bus 508 enables additional devices to be connected to the computing device 500 and to communicate with components of the computing device 500. The data bus 508 may take any suitable form, for example a Peripheral Component Interconnect Express (PCI-E) data bus. The data bus 508 acts as a motherboard-level interconnect to link motherboard-mounted peripherals and as an expansion card interface for add-in cards.

0155The FPGA 502 is located on, in this example, an accelerator card 510. The accelerator card 510 is configured to connect to the data bus 508 and may be, for example, a PCI-E format expansion board comprising interconnects suitable for connecting to a PCI-E data bus.

0156Whilst, for clarity, only a single accelerator card 510 is included in the following example, it would be readily apparent to the skilled person that additional accelerator cards comprising FPGAs 502 formed according to the method of the present invention may be included to provide additional computational power. For example, four accelerator cards 510 may be included in parallel within one system, with each card communicating to the CPU 504 and to each other. Alternatively, multiple FPGA devices 502 may be provided on a single accelerator card 510.

0157Variations will be apparent to the skilled person. For example, whilst the herein-described examples relate to the generation of hardware designs for FPGA-based stream processors, the present invention is also applicable to the design of other programmable logic devices or Application Specific Integrated Circuits (ASICs). The skilled person would readily be aware of alternative devices which fall within the scope of the present embodiments.

0158Embodiments of the present invention have been described with particular reference to the examples illustrated. While specific examples are shown in the drawings and are herein described in detail, it should be understood, however, that the drawings and detailed description are not intended to limit the invention to the particular form disclosed. It will be appreciated that variations and modifications may be made to the examples described within the scope of the present invention.