My B.Sc Thesis

@ 2011-04-20 by João Paulo Pizani Flor

UPDATE (2011-08-01): I have already finished and presented my work. The text of the thesis itself is here for everybody to look at :)

It’s been a while since I started my last year as a Computer Science undergrad student of at the Federal University of Santa Catarina… And, as any other good student that wants to get their degree, I must write and present a B.Sc thesis - called “TCC” in Brazil…

I changed my mind a lot about the subject of the thesis during the last years, but, at last, I defined and formalized my subject proposal last September. My research involves Embedded System Design, and I am now a member of the Software/Hardware Integration Lab - UFSC. Let me try to explain, with a little more detail, what I am trying to achieve with my research

A question which captured my interest since my freshman year (when I found out all about FPGAs and HDLs) is the implementation of algorithms directly in hardware, without the usage of software running on a CPU. In fact, in our 4th semester (while studying Computability Theory) I got proof that the boolean circuit computation model has the same power of Turing machines. Which means, put simply, that any algorithm running in software can also be implemented as a network of fundamental logic gates.

AND there are several reasons for wanting to do that. Lots of algorithms have a high level of parallelism, and can benefit from a hardware implementation (which is inherently parallel). Examples of such massively parallel algorithms can be found in areas such as linear algebra (computer graphics), pattern recognition, sorting, and searching. So, one of the “possible” subjects for my thesis was always the description of these hardware blocks, or even more precisely: HOW to make this description simpler, easier to understand and more integrated to “conventional” programming.

Basically, the way in which we describe algorithms to run on hardware nowadays is still a lot primitive. The tools that synthesize HDL models to run on an FPGA work with an architectural circuit description as input. This means you must describe your algorithm in terms of building blocks and how they are interconnected. You must specify all interconnection details between these blocks (which “wires” connect to which others) and also the communication protocols between the blocks. In most cases, though, these boring and time-consuming tasks could be performed automatically by a tool, and WE PROGRAMMERS would take care of the only task that matters - defining the algorithm’s behavior.

Abstraction levels for hardware description
Abstraction levels for hardware description

In THIS exact point of the subject area I intend to intervene. There are already some (immature) tools that promise to automatize the boring interconnect and protocol description process, and I want to describe a complex circuit using them to compare the automatic implementation to the manual (low-level) one. The circuit I intend to describe and implement is a resource scheduler for the EPOS operating system. While most of the OS will run on a conventional CPU, the scheduler will run on hardware. Therefore, it’s also a goal of my research to establish and evaluate an interface for communication between components implemented in software and in hardware.

Well… without further ado, there it goes, a bird’s eye view of the whole system - as it should be when I’m finished :)

The EPOS System-on-Chip
The EPOS System-on-Chip

The “NoC” mentioned in the picture means Network-on-Chip, and is the common term used to refer to any interconnection network between components in a FPGA. Besides our humble scheduler :), other components will also be plugged onto this NoC: a serial interface, Ethernet adapter, etc. to allow our system to be tested.

That’s all for now, folks! Currently, I am working on the interface between the CPU we chose to use (Plasma softcore) and the main memory. This same bus interface (AMBA) will also be used to handle communication between the CPU and the scheduler. My next step will then be to describe the scheduler itself, using C++ and with the help of Catapult-C.

If at least half of all this works, it should already be sufficient to grant me a B.Sc \o/\o/\o/