Kier's Blog

SimpleHLST needs to read in some code, written by humans, to begin generating data structures that we can actually work with. This can take up to three stages:

• Lexical Analysis – convert the input text into a list of tokens that distinguishes language features from whitespace, comments, pre-processor commands, etc. (“Unknown character on line 2″ errors are produced by this stage).
• Syntax Analysis – convert the list of tokens into a syntax tree which shows the entire file hierarchically as perfectly valid expressions (this is where “Missing semicolon on line 4″ type errors come from).
• Semantic Analysis – process the syntax tree to make sure that it makes sense according to the rules of the language. Type checking falls under this category for instance, so this is where “warning, assigning ‘int’ to ’short’ – possible loss of data” type errors come from.

SimpleHLST only needs a very basic language and I’m not planning to have it support complex data, so I don’t think we’ll need a semantic analysis stage at the moment.

An example

Suppose we have the following mathematical expression, f(t) = 2t + k, and we want to implement it in some program; we could write something like

f(t) = 2*t + k.

Before any more advanced stages can take place, the compiler must extract the information from this expression. This is exactly the same principle as we humans extracting information from text. We have languages that each have a vocabulary of words with specific definitions which we can use to convey detailed information. Each word only represents a small piece of information; the context and sentence structure contains the rest.

Programming languages are exactly the same and this is where Lexical Analysis (or, colloquially, Tokenisation) gets its name from. Programming languages tend to use symbols, or tokens, instead of words for brevity. The output of this stage would be an array that looks somewhat like the following table.

Now the parser can operate on this set of tokens instead of having to wade through the text itself. This example is, obviously, very simplistic and having a separate tokenising and parsing stages may even complicate things, but it is incredibly useful for handling more complex languages such as C and Verilog. (continue reading…)

I’m taking a module called Digital Systems Synthesis this semester which covers some of the algorithms used by modern high level synthesis tools to generate RTL code. Our lecturer told us about a coursework he used to set where we were expected to write a very basic high level synthesis tool; he stopped setting it a few years back because he thought it was too programming oriented. It sounds like a pretty awesome side-project so I’ve decided to give it a go!

I’m not sure how long it’ll take me to complete so I’ve decided to split my progress over multiple blog posts. I’ll start by briefly describing what high level synthesis actually is and what elements I’m expecting my simple program to have.

Digital Design Flow

Chip design is immensely difficult because we can fit so many transistors in them (around 30 million on a pin head!) so we can’t think of it as a single design. It is broken up into many smaller modules that are designed under various “levels of abstraction” which basically means a set of interdependent tasks.

The figure above shows the process used for digital chip design and it may be surprising just how far removed the physical transistors are. There are so many in modern designs that it just becomes impractical to consider each one. Hardware Description Languages (like Verilog, VHDL and SystemC) are used for every level apart from the physical layout and look very similar to programming languages but there is a difference that will become apparent later.

You may be wondering if this means that modern chips are actually designed by programs. Well they certainly play a very large part in a lot of widespread designs. Hardware description language (HDL) code is fed into compilers in exactly the same way that programming language code is, but there is a specialist compiler for each dashed line in the figure. High level synthesis tools produce RTL, RTL compilers produce netlists, and layout tools produce silicon layouts. It does take care and skill to drive these tools effectively and often some hand tweaking may be required to make the most of the design, but ultimately this is how it all works.

I’m going to focus on the thing at the very top. I’m planning to make a very basic HDL that is capable of describing equations and algorithms, and then feed that into SimpleHLST which will generate Verilog code. In an ideal situation I would synthesise the output of this onto an FPGA but that is a long way off just yet.

The Plan

There is a lot to consider for this project, and I think the tasks will break down as follows.

• Read in language and generate data flow graph (DFG)
• Run ASAP/ALAP algorithms on the DFG to work out what functional units are required
• Use constrained algorithms on the DFG to get an optimal design for our purpose
• Join the functional units together using data-path synthesis techniques
• Finally, synthesise a controller to drive the data-path

After this lengthy process SimpleHLST should produce some Verilog code that we can simulate to make sure it works.

Onwards!

In the next part we’ll design a very basic HDL that will fit our needs and, hopefully, start a program that may even understand it!

I’ve been meaning to update this for a fair while now as an uncharacteristically large amount of stuff has happened. Since exams finished I’ve managed to get a job at ECS working for two of my lecturers on two separate projects, which is pretty good because it means my work is varied. Both are IC design projects though, so there is a similar vein running through them.

One of my minor duties on this dual-job is to assemble slides from about twelve people into a large presentation, with cover slides for each speaker, every Friday for a progress meeting we all have. Naturally the first Friday I just did it by hand by importing each one in turn into PowerPoint. However it is a fairly tedious job, and to paraphrase a certain member of staff: why do something by hand when I have a powerful computer under the desk?

So I began to investigate automating the process.

Turns out that Python has an IMAP module in its standard library, which isn’t too surprising I suppose as the Python standard library is enormous. After some playing I managed to write a program that logged into my university email account and downloaded the appropriate PowerPoint attachments.

(continue reading…)

Wow, I’ve really been neglecting my website for a while. I had an amazing 1902 bullshit comments from spam bots or wankers or something. Luckily Wordpress identified all but a hundred or so as completely lacking of any worth and flagged them for manual verification. Fuck that. All 1902 pointless comments deleted by a single click of a button; thank you SQL.

An unfortunate side effect of this atrocity is that you must now register to post comments. Every cloud has a silver lining however: now you shameless, friendless people with an increased sense of self-worth can’t post plugs to your boring blog that would bring a sloth to tears.

End rant, moving on…

Finally, D4 (our big project of the year) is done and dusted! It was a pretty interesting couple of weeks, despite being filled with stress, aggrovation and late nights. We had to design a fire detection system that could accurately measure temperature, detect smoke and the presence of people from up to four sensors and display that information on a web interface. (continue reading…)