The general idea
To
convert software programs written in C++
into
synthesisable Verilog
HDL
(a
register
transfer level
hardware
description language) such that existing EDA
tools can generate integrated circuit layouts and FPGA
configurations.
The conversion will proceed in a number of
transformations,
each
of which modifies the program slightly to convert some aspect of the
program to a more hardware-like or lower level dialect
(hence
Inferno, from Dante's
epic
poem) whilst leaving the functionality of the program unchanged.
In inferno, we implement lowering transformations as elimination and
substitution of language constructs
thereby
progressively restricting the dialect.
Inferno
will map C++ classes and objects bijectively to Verilog modules and
module instances respectively, thereby preserving program
architecture. Each module instance will contain its own sequential
execution infrastructure and will communicate with other instances
over protocols comparable to standard bus protocols such as ARM's
AXI.
Some of the intermediate dialects will correspond to valid and
simulatable SystemC
models
(including SystemC Transaction
Level Models), for the purposes of validation and clarification
of intent when neither pure C++ nor Verilog are suitable source-forms
for the program.
Inferno transformations are applied to an internal representation called the inferno tree which is a polymorphic, topology-oriented acyclic digraph – this means that it uses nodes' type, inheritance ancestry and link topology to capture the maximum possible proportion of information about the program (as opposed to enums, bools, custom classes etc). The inferno tree represents programs with source-like semantics and will support an approximate closure of C++, SystemC and Verilog. We specify the tree in a minimal style plus utilities, and use Boost's shared_ptr for the links between nodes to simplify memory management.
The sequence of transformations will be controlled by an automatic tool based on the properties of individual transformations expressed in terms of disallowed, introduced and removed constructs. Inferno interfaces with the clang front-end (part of the LLVM compiler project) to parse C++ programs into the inferno tree. We can render legal C++ output programs directly from the tree and generate input files for Graphviz. A graph for an example program that sums the numbers from 1 to 10 follows.
Most of the transformations will be implemented using a generic in-tree search and replace tool which implements topological wildcarding based on the tree's existing class hierarchy. The algorithm has many extensions to increase its expressivity, and it takes advantage of the topology-oriented style of inferno trees in order to be language-indepenedent.
An example search and replace pattern follows: this one searches for do-while loops and replaces them with a network of gotos, and it handles continue correctly (break is handled by another transformation).
The result of applying the above transformation to the above example program is shown below.
More graphs of inferno transformations can be found here. Doxygen documentation is here
Development
The project is written in C++ with STL and Boost libraries. It brings in specific snapshot revisions of llvm and clang. It presently builds in GCC3.x and 4.x on Linux and Cygwin. This page, and the project's subversion repository, docs and forums are all hosted at
See the SourceForge project page for more information.
Releases
Version |
Subversion revision |
Date |
Notes |
|
0.1 |
707 |
Feb 2011 |
Includes a beta-level Search and Replace algorithm, with documentation, and 16 transformation steps implemented. |
|
0.2 |
786 |
Mar 2012 |
Release level search and replace algorithm, partial SystemC integration, suite of SystemC test cases, beta-level sequential phase implementation, better documentation including Doxygen. |
Background reading
Program Theory
Some background on academic program theory can be found in the Wikipedia pages on programming language theory, lambda calculus, process calculus and pi calculus. The latter two deal with parallel programs and introduce the concept of the channel which will be important in our intermediate representations.
A higher level language for Hardware Synthesis defines an academic hardware language which extends the concept of channels slightly in the direction of pointers. Trampolined style presents a generic way of stating-out (converting to a state machine) within the lambda calculus. Lambda calculus's obsession with recursion makes the examples harder to read than the underlying ideas require. Software Optimisation Using Hardware Synthesis Techniques makes interesting comparisons between software compilation and hardware synthesis. It should be noted that in our project, synthesis is performed on our output by existing tools, and we don't need to duplicate their optimisations.
Software to hardware conversion
The Challenges of Hardware Synthesis from C-like Languages provides a thorough overview of existing technologies in the area of the present project and should be considered essential reading in spite of its downbeat tone. Hardware synthesis from C/C++ from 1999 illustrates the state of the art before the emergence of SystemC and TLM and therefore serves as background and motivation for later ideas (Let me know if you can find a legitimate free link to this article).
Automatic Hardware Synthesis for a Hybrid Reconfigurable CPU featuring Philips CPLDs describes a conversion from assembly language into hardware that can work alongside a conventional processor. For our project, assembly language is rejected as an input format because it does not represent the structure of a program's data, and instead requires the presence of flat, RAM-like storage. Memory Representation and Hardware Synthesis of C Code with Pointers and Complex Data Structures gives ideas for pointer representation but appears to group data based on dynamic (usage) analysis, whereas I intend to use static (structural) information for grouping/locality. Optimisation of Hardware Compilation using Programmable Transformations is interesting for its discussion of program transformations in hardware synthesis (most work on program transformations applies to software compilers). Note that the emphasis of this paper is on optimisations, whereas we will focus on translation from software to hardware.
SystemC and Transaction Level Modelling
The SystemC Library Overview and SystemC Version 2.0 User s Guide describe what SystemC can do and how to use it. The best way to understand SystemC internals is via the code, which may be downloaded from the SystemC web site. No-one ever talks about SystemC version 1; it must have sucked.
The power-point presentation Transaction Level Modeling: An Overview gives an intro to the subject. Note in particular the 2-axis graph that enumerates different TLM styles by algorithmic and timing precision. Transaction Level Modeling in System Level Design has excellent diagrams that illustrate TLM styles and the difference between them. Early Hardware/Software Integration Using SystemC 2.0 and Transaction level modeling of SoC with SystemC 2.0 give examples of a few different TLM styles. Advancing Transaction Level Modeling -- Linking the OSCI and OCP-IP Worlds at Transaction Level is interesting but OCP-IP (chip-level networking) is out of the scope of this project (our converter might translate implementations of OCP-IP protocols but it doesn't have to understand them) .
Other
The ANSI C++ spec from 1997. Icarus Verilog is a handy package for simulating and synthesising Verilog. The IEEE Verilog 1364-2001 Standard What's New, and Why You Need It discusses the Verilog-2001 standard which is the one we will use.
Parallelism is not an initial priority for this project. However, when the time comes, OpenMP is a candidate for the necessary extensions to the input language (however it seems rather complex).
DRC's Reconfigurable Processor Unit seems like an interesting target platform. FPGA+CPU systems are not an initial target, but to make this particular configuration work well, we would need to integrate efficiently with HyperTransport.
License
This is an open source project, and all the code, documents and
web pages are subject to the BSD
license.
This page copyright © John Graley 2009-2012. Licensing conditions as per the BSD license.