Algorithm Development for FPGAs

Hardware Design

As mentioned in the previous section, accelerating algorithms on FPGAs requires that a circuit is designed to perform the algorithm on the FPGA. Since FPGAs originated as versatile components for implementing electronic hardware, numerous hardware design tools are available to hardware designers specialized in creating circuits for FPGAs. They can choose to develop their design in VHDL, Verilog or using an ESL design tool.

Regardless of the tools chosen, hardware design requires a solid knowledge of electrical engineering and the understanding of subjects of FPGA circuit design such as:

Gates, wires, CLBs, multipliers, etc.
 Signal timing and clocking.
 FPGA microarchitecture.
 Interfacing to vendor board adaptation layer.

From the perspective of software development, there is a huge semantic gap between the software source code (an instruction stream for a processor), and the gates and wires of the FPGA, making it a challenge to map software algorithms to the FPGA.

The Mitrion Virtual Processor

The Mitrion Software Acceleration Platform has been developed for the sole purpose of allowing software developers to benefit from FPGA-based software acceleration, without having to deal with the complexities of hardware design.

What makes the Mitrion Platform unique is that it introduces a processor as an abstraction layer between the FPGA hardware and the software that is to be run. While other programming solutions for FPGAs attempt to produce circuit designs directly from a high level language, the Mitrion Platform adds the Mitrion Virtual Processor, which executes software on the FPGA. The benefit is that the processor gives a complete separation of software from hardware, and the software developer is isolated from all aspects of FPGA hardware design. With the Mitrion Virtual Processor, all the circuit design is already taken care of and is delivered as part of the Mitrion Platform.

A New Processor Architecture

A processor that is to run software efficiently on an FPGA has to overcome the challenges imposed by the FPGA’s low clock frequency. This means that the processor must allow massive parallel execution and take advantage of the configurability to maximize the utilization of FPGA resources.

Processors using the ubiquitous von Neumann architecture are already available for FPGAs, both in the form of PowerPC or MIPS processor blocks on the FPGA, as well as circuit designs (known as IP-blocks) for implementation using the FPGAs configurable logic. A von Neumann processor is essentially a state machine that operates sequentially on instructions fetched from RAM memory.
 

The von Neumann Processor

The advantage of a von Neumann processor is that the programming aspects are well supported and understood after more than 60 years of use. It is also capable of executing programs of arbitrary size. However, it has serious drawbacks for use on FPGAs:

 The single instruction stream gives exposes no parallelism.
 The utilization of the hardware is low, with large parts of the logic being idle during the execution of an instruction.
 The key factor affecting the performance is clock frequency. Since FPGAs run at much lower clock frequencies than CPUs, the performance will be low.

The Mitrion Virtual Processor fulfils the requirements for efficient execution through a non-von Neumann architecture that delivers:

 Instruction level parallelism – allowing all instructions to execute concurrently.
 Loop level parallelism – allowing many loop iterations executing concurrently.
 Maximum utilization of the FPGA resources by allowing the processor to be adapted to the software it is running.

In the Mitrion Virtual Processor architecture, there is no instruction stream. Instead, the data streams through fixed program instructions on the FPGA. The Mitrion Virtual Processor logic that performs the program instructions are called processing elements.

The process of adapting a Mitrion Virtual Processor to a program is performed by the processor configuration unit of the Mitrion SDK. The process consists of picking the required processing elements and creating the appropriate point-to-point or switched network connections between them. The result is a processor that is parallel at the level of single instructions and fully adapted to the program. The circuit design for the processor is output by the Mitrion SDK as VHDL code, ready to be run through synthesis and place & route process and installed on a hybrid computer system.

Programming the Mitrion Virtual Processor

The Mitrion SDK includes a compiler for Mitrion-C, a C family programming language used to program the Mitrion Virtual Processor. The reason for introducing a new programming language for the Mitrion Virtual Processor is based on the conviction that parallel programming is easier with a parallel programming language. The design goals of Mitrion-C are to:

 Give access to the instruction- and loop-level parallelism available from the Mitrion Virtual Processor.
 Ease the learning curve by using a C-like syntax.
 Hide all aspects of FPGA circuit design from the programmer.

Mitrion-C Compared to Circuit Design

Mitrion-C is a high level programming language that is designed to let programmers take advantage of ultra-fine grained parallelism and synchronization together with tightly coupled microprocessor/FPGA co-processing. It cannot be used to design a circuit. The Mitrion Platform does not provide the possibility to integrate Mitrion Virtual Processors into circuit designs, other than the automatic integration with board adaptation layer logic on supported hybrid computing systems.

The performance of a Mitrion Virtual Processor programmed in Mitrion-C is comparable to hand designed circuits at the same clock speed. The hand designed circuits may have a small performance advantage, but this comes at the cost of a significantly longer development process. This is analogous to the performance trade-off in using a high level language versus assembler for microprocessors.

FPGAs Expose Machine Organization

Current hybrid computer systems expose the programmer to the details of machine organization. This must be taken into account when developing the algorithms that are going to run on the FPGA.

The FPGA may be connected to the host system many different ways:

 In an CPU socket, connected via HyperTransport or Front Side Bus, where software, not hardware, determines machine organization.
 On a slave card or device connected via PCI, PCI Express or NUMAlink.

Local memory may be configured different ways:

 Smaller but faster SDRAM, or larger but slower DRAM.
 Small number of large address spaces, or larger number of small memories.

Software Development Cycle and Portability

A major advantage of the Mitrion Platform is that the development of accelerated applications follows a software life cycle. When porting to other FPGA-based hybrid computer systems, the programmer will only need to change the details pertaining to the specifics of the machine organization. This lets users immediately exploit FPGA evolution with regard to sizes, speeds, and on-chip memory.

Mitrion-C development cycle

Previous: Hybrid Computers