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!

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…)

Exams are coming up and I’ve been going over some analogue electronics in preparation, just to make sure I actually do understand it. Whilst going over some notes I found some instructions in the lecturers notes that proved to be especially useful: how to use SPICE.

SPICE is a circuit simulator and it’s fairly good. Like all good systems it makes mistakes every now and then but we can overlook that in most cases. So I tried to test my understanding of how a Zener diode works by designing a really simple shunt regulator. It’s not much use in the real world but it can supply 100mA at 5V (well, 4.7V because Zener ratings are strange) to some load.

Theory says that the Zener will stop acting like a regulator when no current flows through it, and this happens when the voltage across it fails to exceed its breakdown voltage. As shown in the above circuit diagram, R1 and R2 form a potential divider, hence the voltage across R2 is V1*R2/(R1+R2). The breakdown voltage is roughly 5V as mentioned earlier, therefore the device will stop conducting when R2/(R1+R2) <= 5/12.

Personally, I think this graph is pretty awesome, even if it is completely unlabelled. Up the left hand side is the output voltage (i.e. the voltage across R2) and along the bottom is the resistance of R2. The curve bends quite sharply at about 50 Ohms which works out to be exactly what we predicted earlier: 50/(70+50)=5/12.

I’m impressed with LTspice. This took like 5 minutes to do. Most of the tools we use are fairly complicated, but this is pretty easy. It draws graphs well and it’s easy to get the plots you actually want rather than plotting everything against time. The only downside is that it doesn’t support parametric sweeps in the GUI so you have to type it in manually, but overall it seems pretty cool.