SME: A High Productivity FPGA Tool for Software Programmers

In this paper, we will give an overview of our programming model, Synchronous Message Exchange (SME), which we believe is a useful tool for FPGA development. SME is a CSP-derived programming model, that is used to describe hardware and can be translated into VHDL. Because SME is built on CSP, we can avoid deadlocks and race conditions, which are normally associated with concurrent programming.

We will start by introducing the concepts of SME, in Section 2, followed by the updates SME has received to the back-end in the past few years, in Section 3. Finally, we’ll present some examples of the capabilities of SME, in Section 4.

In this section, we will give a short introduction to a number of existing solutions seeking to simplify the programming of FPGAs.

A process in SME is a sequential block of code, with each process being isolated from the other processes. Like in CSP, processes in SME share nothing except for buses and constants. There are two types of processes that exists in SME: simple processes and simulation processes.

Buses are the means of communication between processes. They contain a collection of fields, which are bundled together by a user, based on context. For example, it makes sense to bundle all of the signals that go into a port of a RAM, as they relate to each other.

Buses are directly comparable to wires, registers, and latches in hardware, which are limited to static constructs, and therefore the allowed data type of the fields in buses are also limited to static constructs.

Buses are broadcast between the connected processes. There can be multiple reading and writing processes to a bus, but only one writing process for each field in a bus. This is as there cannot be double drivers to wires in hardware, at least not without some form of conflict resolution. If no process writes to a field in a bus during a clock cycle, the last written value will be latched for the following clock cycle. Buses can, like processes, be clocked or unclocked. Clocked buses won’t propagate their value until the following clock cycle. Unclocked buses will propagate their value to the subsequent processes within a clock cycle. All buses, that a clocked process reads from, must have an initial value or be guarded by some field which have an initial value. If a clocked process attempts to read a field that does not have a value, it will receive an indeterminate value. SME handles this by throwing an exception, indicating that the developer has to explicitly handle this. This is controlled with the InitialValue attribute on fields, or the InitialisedBus attribute on buses, which set all of the fields to have the default datatype value as initial value.

As mentioned before, an SME simulation consists of processes and buses, which is collectively known as a network. A network describes how the processes and buses are instantiated and connected. As the simulation has not been started when a network is being created, a user can use both static and dynamic constructs. As such, dynamic collections and strategies can be used for instantiation. For example, to define a pipeline of a single type of process, one can utilize lists and loops. It is during the instantiation that every process, bus and how they are connected, is registered by SME.

There are multiple strategies for instantiating a network. We propose that every process instantiates its own output buses, given that there can only be one writing process per field in a bus and this way, all buses needed in the network will be instantiated correctly. This might not always work, such as the case where multiple processes write to individual fields of a bus, in which there should not be multiple instances of that bus. Therefore, this strategy should not be considered a catch-all solution for all problems, but is generally sufficient. On a related note, zombie instances of buses are allowed, as they won’t be translated into hardware, but these are not recommended.

Once the network has been set up, SME creates a dependency graph, where processes are nodes and buses are edges. This dependency graph indicates how the processes are connected and the order that they should be triggered in. In this dependency graph, there cannot be cycles of unclocked processes and buses, as it would result in a short circuit on the board, when the network is translated into hardware.

Processes are triggered based on two strategies: through the hidden clock, which controls the clocked processes, or through whether or not all of the input buses have been written to, which controls the unclocked processes. Processes are independent either if they are clocked processes or if they do not share opposite ends of a bus instance. Note: chains of processes connected by bus instances are not considered independent.

Since each process is sequential, the parallelism in SME is explicit. In order for something to run in parallel, a user needs to solve the problem by using multiple clocked processes. Every independent process is triggered concurrently. If two unclocked processes depend on each other through a bus instance, the process with the bus instance as input wont be triggered until the other process has been triggered and completed executing.

After the dependency graph has been created and verified, the simulation can begin. A simulation is a run of multiple clock cycles. The algorithm for driving the simulation is as follows:

1. 1.

   Propagate all of the clocked buses.

2. 2.

   Collect all of the clocked processes into an active set.

3. 3.

   Trigger all of the processes in the active set.

4. 4.

   Propagate all of the unclocked buses, which are edges out of the nodes corresponding to the processes in the active set.

5. 5.

   All of the processes, whose input edges in the dependency graph have been propagated, become the new active set.

6. 6.

   Repeat steps 3 - 5 until there are no more processes, which have not been triggered.

7. 7.

   Check if the simulation stop condition has been met

   • •

     If the stopping condition has been met, the simulation terminates.

   • •

     If the stopping condition has not been met, the simulation repeats from step 1.

To verify whether a network is correct, the programmer has to write tests. This is done through simulation processes, which will either drive the network with input, verify the output or both. As mentioned in Section 2.1.2, a simulation process is not limited to the synthesizable part of SME, but the developer can use the entirety of the front-end language, which is one of the great strengths of SME.

For example, to produce an implementation that computes an image, it is not necessary to write a function to read the image. The image can simply be loaded through an external library and during each clock cycle, the pixel values of the image can be fed into the network on the buses.

During simulation, every value on every bus is recorded for every clock cycle. These values are then saved in a trace file, which is used to test the resulting VHDL.

SME creates a VHDL test bench, loads this trace file and drives all of the input buses with values from the trace file. It then verifies that all of the values on all of the output buses matches the values from the trace file. This helps in verifying that the resulting VHDL is clock cycle accurate, compared to the SME simulation.

This means that it is not necessary for the developer to create a test bench manually in VHDL, which can be very tedious. This ensures that testing the network can be done faster, compared to what would otherwise be possible, and it also makes the development simpler when using SME.

It is often useful to have optimized implementations of common constructs. In the software world this is handled by libraries, and in the hardware world it is handled by IP Cores. SME uses a mix of these two approaches called components. Components provide a high-level C# library during simulation, which are then translated into IP Cores in VHDL. By using the components, the user does not have to write to the exact specification a vendor requires.

As described in Section 2.3, an SME network is described by instantiating processes and buses. As this is done before running the simulation, there are no constraints on the constructs used for this, giving the option to dynamically build the network.

This wasn’t always the case. Previous versions of SME relied on the type definitions, rather than the instances. For building the network, SME would gather all definitions of processes and buses and instantiate exactly one of each. Connections were generated based on the types, as there could only exist one instance in a network. The idea was that connections would then be created automatically instead of explicitly.

This became a problem for bigger designs featuring either multiple instances of the same process, such as registers in a pipeline, or design utilizing compositionality, where processes and buses are grouped together. In these cases, the user had to define the same process multiple times. This was partly solved by using templates for generating code, but it proved hard to debug from the template level.

Our new approach is to have the user construct the network explicitly, by manually instantiating and connecting everything. It might seem tedious, but it opens up the possibility of using dynamic structures and constructs, such as lists or loops, for describing the network. This is possible as it is not crucial how the entities are instantiated, as long as it is done before the simulation is started, at which point all structures has to be static. This new way of instantiation translates well to VHDL.

Different programming languages have different strengths which could prove useful in different situations. To better support multiple implementation languages, an intermediate representation for SME networks was developed [28]. With an IL representation it would be possible to develop libraries in one language and invoke them from another. It also simplifies the generation of the resulting HDL as only a well defined set of constructs need to be supported. Due to resource constraints, the SMEIL approach is not fully developed.

To verify that the created hardware model behaves as expected, test benches are usually the main method of testing. These test benches are often sufficient, but in some cases it is not enough to find critical errors in the hardware design. With formal verification it might be possible to locate some of these errors that have not been detected with the standard test bench. While formal verification is the desired approach, it is also difficult and is not possible in all formats and languages. Therefore, it is not typically a standard tool for testing.

CSP [3] is a process algebra that provides a method to express interaction between processes of concurrent systems. Some properties can be formally verified in systems described in CSP. This means that if hardware can be described in CSP, it will be possible to formally verify certain properties within the hardware that cannot, or is difficult to, be tested through the test bench. As previously mentioned in Section 1, SME is derived from CSP and therefore for each SME model there will be an equivalent CSP model. This means that the SME model can be formally verified using the equivalent CSP model as it is directly translatable.

The system TAPS (Towards Automatic Program Specification) [18, 29] provides translation from SMEIL, see Section  3.3, to the machine-readable version of the CSP process algebra, $CSP_{M}$ [30]. The generated $CSP_{M}$ code will not only be equivalent to the SMEIL code from which it originates, but it will also include assertion statements to formally verify properties within the defined hardware model. These properties can be verified with the $CSP_{M}$ refinement checker tool, FDR4 (Failures-Divergences Refinement) [31]. Instead of having to create advanced test benches, TAPS provides a simple way to verify the hardware model via FDR4s assertion functionalities. FDR4 can, using TAPS, assert that the observed values of a channel, in a simulated SMEIL program, are in fact the only possible values communicated on that specific channel within a specified amount of clock cycles. The amount of clock cycles are defined, by the user, when simulating the system.

For example, a hardware design can have a 4 bit connection from one process to another, which can represent the number 0 through 15. But the system might not have been designed for numbers above 10 to be communicated between the processes. It would, of course, be possible to test the network for numbers above 10, but for more elaborate designs it might be too complex for the developer to grasp. A formal verification with TAPS would be able to verify if it is possible for a number above 10 to be communicated between these processes with the current design.

The SME simulation observes the values throughout the simulation, then adds the values to the code and outputs it. It also defines the size of the range of the observed values, for example 4 bits for the range 0 - 15. These ranges are used by TAPS to create assertion statements for the verification.

Utilising the formal verification properties of the FDR4 refinement tool, the assertion statements of the translated $CSP_{M}$ code can be verified.

The SME model is simulated for a specified amount of clock cycles. It is necessary to simulate the system in order to get data to verify, but this also means that if the simulation has not been running long enough, the verification might not be adequate. This challenge has been discussed in [29].

In order to be able to simulate the internal state between clock cycles, it is necessary for TAPS to simulate recursive processes and a possibility to retain the state between the cycles. When creating recursive processes in $CSP_{M}$ for formal verification, it is necessary to have the recursion stop eventually, since it is not possible to formally verify endless loops. Because CSP is not inherently synchronous, it is necessary to have the functionality to translate the clock that drives the SME circuit to the $CSP_{M}$ translation. Therefore TAPS provides the possibility of modeling a globally synchronous clock in $CSP_{M}$ that drives the network and terminates after a specific number of clock cycles.

Throughout the last couple of years, several different projects have been created with SME as a main structure. Each of the mentioned projects, in this section, have been performed by masters students at the University of Copenhagen with no prior knowledge of SME or FPGAs. These projects showcase the capabilities of SME, in that SME can be used for implementing hardware without having any prior knowledge or understanding of hardware programming. Some of them also show that the granularity of SME proves a challenge.

This example, as shown in Figure 1, describes a hardware counter, that increments a counter every $n$ clock cycles. This is usually used as a toy example, since it can be implemented very easily on an FPGA. It can also provide a very visual result, if the inputs are mapped to something like a physical switch and the outputs are mapped to LED lights.

It has one input, Control containing the field active, which controls whether it should increment. It has one output, LEDs containing the field value, which is a 4 bit binary value holding the current count.

The performance of this example is not really important, as the main requirement is that it meets the given timing. In this case, we implemented it at 50 MHz, incrementing every second, so $n$ is set to 50 million. The numbers describing resource utilization can be seen in Table I.

This example, as shown in Figure 2, shows how regular C# code can be used to create hardware. It is implemented using a single process, which contains an AES implementation, taken from the Mono project [42]. For verification, the output has been compared to a call to the standard C# library implementation in System.Security.Cryptography.Aes.

It has two inputs, Key and DataIn. One for loading the encryption key and the other for the data to encrypt. It has one output, DataOut, for the encrypted data. The Key bus has five fields: one LoadKey, indicating whether the process should store the given key, and four Key[n] fields holding the encryption key. The two Data buses has three fields: two Data[n], holding the data encrypted/to be encrypted data, and one DataReady indicating whether the data on the two other fields are valid.

While it does map to hardware, it is not a very efficient implementation, as can be seen in Table I. This is mainly due to everything happening within one clock cycle, where everything could be pipelined. However, it still shows how higher level code can be implemented in hardware using SME. Given the design consumes two 64-bit words per clock cycle, the throughput is $2*64*f_{max}=1.92$ Gbit per second.

This example, as shown in Figure 3, shows matrix multiplication, a common High Performance Compute (HPC) problem. It was developed as part of the masters student project described in Section 3.5.6.

It exposes the A port of three Block RAM holding the matrices, $A$, $B$ and $C$, used for the computation $C=A*B$. These ports are named AportA, BportA and CportA respectively. It has two MatrixMeta input buses and one MatrixMeta output, specifying the sizes and validity of the respective matrices. Each MatrixMeta bus is associated with the BRAM of the same post-fix. The bus has five fields: a valid indicating whether the data is valid, a base holding the base address, a stride indicating the access stride, a height and width specifying the size of the matrix.

It is implemented in a pipelined fashion, where each sub computation is performed in a single clock cycle, as is shown by the two processes Multiplier and Accumulator. On each clock cycle, one value is read from the $A$ and $B$ matrix, which are streamed to the Multiplier. The Accumulator keeps adding its input, until the address for matrix $C$ changes, where it will write the value to $C$.

The performance of the implementation can be seen in Table I. Each entry in $C$ takes in the order of $M*N*K$ clock cycles to compute. The main bottleneck of the implementation is the multiplication, which is performed within a single clock cycle. By pipelining it, performance should increase, with only some additional registers for transmitting the address.

This example, as shown in Figure 4, shows a bigger and more complex control system in the form of the classical CPU architecture used for education: The MIPS processor. It was implemented as a masters student project, which followed the steps of a machine architecture class taught at the University of Copenhagen [37]. The resulting design features a pipelined processor, along with logic handling the data hazards introduced by pipelining. It is not implemented using BRAM, as components weren’t available at the time of writing. This example shows that controller systems, where tight control is a requirement, is a great fit for SME.

It exposes two memory ports for instruction and main memory respectively. It also features a Control bus for starting/stopping the processor.

It has been verified by taking programs generated by a MIPS compiler, injecting them into the instruction memory, running the programs and verifying that the memory in the main memory is as expected. The performance of the implementation can be seen in Table I. The main bottleneck of the system lies within the ALU, as it can perform a multiplication and a division, both of which are done within a single clock cycle.

This example, as shown in Figure 5, stems from a simple problem encountered at the MAX IV synchrotron in Lund, Sweden. At MAX IV, the detectors generate a massive amount of data in the orders of 100s of Gbit per second [44], when running the experiments. In many cases, they are unable to get a real-time feedback from the system while running. Even though a simple representation, in the form of a histogram, is usually sufficient. This is not feasible to do in CPU or GPU, due to the memory hierarchy of machines introducing too much overhead, but can be easily expressed as a streaming problem, as shown in this example.

The implementation has two input buses, Index and Value, indicating the index into the histogram and the value to add to that index. It also features a BRAM port, Mem, for resetting the internal state and reading out the result.

There exists a data hazard, when two consecutive sets of index/value have the same index. In this case, a write will be in-flight to the memory, while a read is issued, both to the same address. If this isn’t handled, the value read will be the old value, not the new, resulting in incorrect results. This has been handled by the Forwarder process, which detects this clash and forwards the in-flight value instead of the value read from BRAM.

The performance of the implementation can be seen in Table I. Given the design consumes one Index and one Value per clock cycle, the system has a throughput of $2*32*f_{max}=12.8$ Gbit per second.

We would like to leverage the asynchronous programming language construct, which have become popular in most high-level languages. In C#, this is done by supporting Task and the async keyword. These are already utilized when simulating an SME network, but are currently unavailable inside common processes. We think these constructs can be used to express the concurrent nature of hardware models much better.

In most high clocked designs, streaming data is the go-to strategy. To ensure a constant flow of data, there must not be any back-pressure from a network. A usual fix for this problem is the use of FIFO queues. We would like to implement multi-cycle buses, which would reflect the behaviour of these queues in a more elegant matter in the C# simulation.

As has been very popular with many high-level languages, we would like to implement more library functions in the form of SME components, described in 2.6. Examples of these are a Math library containing many common implementations of Math operations, a floating point library for introducing floating point support, and an AXI library for easy-to-use implementations of the popular AXI protocol [45].

We would like to have a tighter integration into the high-level frameworks of the major vendors, as these provide a lot of helpful functionality, such as communication with other systems and hardware controllers. Both of the major vendors, Xilinx and Intel, support using Register Transfer Level (RTL) kernels as part of their respective high-level frameworks. Since SME targets VHDL, which is an RTL language, it should be possible to conform to the standard of the two vendors.

As stated in Section 3.1.1, there is a false dependency when running the SME model. We believe this is due to .NET locking the buses. However, given that the SME model does not allow for multi-drivers, the dependency of multiple writers should not be present. A better approach would be locking the individual fields, rather than the entire bus. The dependency of two clocked processes reading and writing to the same bus is also false, since each process will only have one end of the bus. This should be circumvented by splitting the object into a reading and a writing end, thus locking individual ends.