sort [3,4,1,0,2] = [0,1,2,3,4]

Sorting makes for a good introduction to the library. Let’s start with the simplest kind of sorter possible: given a pair of 8-bit values, the function twoSort returns the sorted pair.

This definition makes use of three Blarney constructs: the Bit type for bit vectors (parametised by the size of the vector); the comparison operator .<.; and the ternary conditional operator ?. A quick test bench to check that it works:

We use Blarney’s always construct to perform the given action on every clock cycle. Blarney actions include statements for displaying values during simulation (display), terminating the simulator (finish), and mutating state (see below). All statements in an Action execute in parallel, within a single cycle of an implicit clock. We can generate Verilog for the test bench as follows.

Assuming the above code is in a file named Sorter.hs, it can be compiled at the command-line using

where blc stands for Blarney compiler. This is just a script (from Blarney’s Scripts directory) that invokes GHC with the appropriate compiler flags. Running the resulting executable ./Sorter will produce Verilog in the /tmp/twoSort directory, including a makefile to build a Verilator simulator. The simulator can be built and run as follows.

Sometimes it can be convenient to skip Verilog generation, and use the in-Haskell simulator.

Now after running ./Sorter we see the test bench output directly.

The in-Haskell simulator is much slower than Verilator, but can be more convenient for small designs. It is currently an experimental feature.

We can build a general N-element sorter by connecting together multiple two-sorters. One of the simplest ways to do this is the bubble sort network. The key component is a function bubble that takes a list of inputs and returns a new list in which the smallest element comes first.

If we repeatedly call bubble then we end up with a sorted list.

Running the test bench

in simulation yields:

To see that the sort function really is describing a circuit, let’s draw the circuit digram for a 5-element bubble sorter.

The input list is supplied on the left, and the sorted output list is produced at the bottom. Each + denotes a two-sorter that takes inputs from the top and the left, and produces the smaller value to the bottom and the larger value to the right. See The design and verification of a sorter core for a more in-depth exploration of sorting circuits in Haskell.

For simplicity, we’ve made our sorter specific to lists of 8-bit values. But if we look at the types of the primitive functions it uses, we can see that it actually has a more general type.

So .<. can be used on any type in the Cmp (comparator) class. Similarly, ? can be used on any type in the Bits class (which allows packing to a bit vector and back again). So a more generic definition of twoSort would be:

Indeed, this would be the type inferred by the Haskell compiler if no type signature was supplied. Using Haskell’s rebindable syntax, we can also use an if-then-else expression instead of the ternary conditional operator:

So far, we’ve only seen display and finish actions inside a Blarney module. Also supported are creation and assignment of registers. To illustrate, here is a module that creates a 4-bit cycleCount register, increments it on each cycle, stopping when it reaches 10.

This example introduces a number of new library functions: makeReg creates a register, initialised to the given value; the val field yeilds the current value of the register; and when allows conditional actions to be introduced. We can use if-then-else in an Action context. For example, the final three lines above could have been written as:

Running top in simulation gives

Queues (also known as FIFOs) are a commonly used abstraction in hardware design. Blarney provides a range of different queue implementations, all of which implement the following interface available when importing Blarney.Queue.

The type Queue a represents a queue holding elements of type a, and provides a range of standard functions on queues. The enq method should only be called when notFull is true and the deq method should only be called when canDeq is true. Similarly, the first element of the queue is only valid when canDeq is true. Below, we present the simplest possible implementation of a one-element queue.

The following simple test bench illustrates how to use a queue.

Wires are a feature of the Action monad that offer a way for separate action blocks to communicate within the same clock cycle. Whereas assignment to a register becomes visible on the clock cycle after the assigment occurs, assignment to a wire is visible on the same cycle as the assignment. If no assignment is made to a wire on a particular cycle, then the wire emits its default value on that cycle. When multiple assignments to the same wire occur on the same cycle, the wire emits the bitwise disjunction of all the assigned values.

To illustrate, let’s implement an n-bit counter module that supports increment and decrement operations.

We’d like the counter to support parallel calls to inc and dec. That is, if inc and dec are called on the same cycle then the counter’s output is unchanged. We’ll achieve this using wires.

State machines are a common way of defining the control-path of a circuit. They are typically expressed by doing case-analysis of the current state and manually setting the next state. Quite often however, they can be expressed more neatly in a Recipe — a simple imperative language with various control-flow constructs.

To illustrate, here is a small state machine that computes the factorial of 10.

Blarney provides a lightweight compiler for the Recipe language (under 100 lines of code), which we invoke above through the call to runRecipe.

A very common use of recipes is to define test sequences. For example, here is a simple test sequence for the Counter module defined earlier.

Here, we increment counter on the first cycle, and then again on the second. On the third cycle, we both increment and decrement it in parallel. On the fourth cycle, we display the value and terminate the simulator.

For convenience, recipes can also be constucted using do notation. The Stmt monad is simply a wrapper around Recipe, which defines monadic bind as sequential composition. It is entirely syntatic sugar, providing no new functionality.

To illustrate, here’s the factorial example from earlier, rewritten using the Stmt monad.

We have found that some users prefer Recipe syntax, while others prefer Stmt syntax, so we offer both.

Blarney provides a variety of block RAM modules commonly supported on FPGAs. They are all based around the following interface.

When a load is issued for a given address, the value at that address appears on out on the next clock cycle. When a store is issued, the value is written to the RAM on the current cycle, and a load of the new value can be requested on the subsequent cycle. A parallel load and store should only be issued on the same cycle if the RAM has been created as a dual-port RAM (as opposed to a single-port RAM). To illustrate, here is a test bench that creates a single-port block RAM and performs a store followed by a load.

Somewhat-related to block RAMs are register files. The difference is that a register file allows the value at an address to be determined within a clock cycle. It also allows any number of reads and writes to be performed within the same cycle. Register files have the following interface.