3D-FPGA Reinvented

The concept of 3D chip has been coming and going. I have not seen many commercial chip that is 3D. But that may be the norms in future, as we find it difficult to integrate more transistors into a given area.

If the area is small, stack it up. That's what was done in New York in the mid nineties. In future, at least in a distant future, that's what they would do in Atlanta and Phoenix. What applies to geography, applies to chip design - I find them both extremely similar.

This time, the famous and well respected innovator Zvi Or-Bach has reinvented 3D FPGA. FPGA has a big advantage of ASIC in terms of rapid development cycle and less initial investment. But in practice, FPGA is much slower and are not dense enough. FPGA architecture and the synthesis technology has undergone several changes taking it closer and closer to ASIC in terms of performance. 3D FPGA may be yet another step, as Or-Bach claims.

Nu-PGA tries to increase the interconnect density of the FPGA by taking the antifuse to a separate layer from the configurable logic blocks. What does the increasing interconnect density mean? A lot, actually. With a rich interconnect availability, the bounding box of the chip is reduced a lot. So the placement and routing algorithm need not have to bother much about where to lay the track, number of tracks in each direction and what the channel width is. Also it increases the speed of placement and routing process. All these clearly mean getting closer to ASIC.

But the 3D FPGA described above is more like a building with two levels. Not so fancy, but we have never done anything more than one-level building earlier. I would however expect the building to go up fast, like putting CLBs on top of each other in different layers, or having a layer of CLB and a layer of IO blocks. I seriously think there is a good scope for growing tall as there is more space available there. Let's see how the market reacts to these innovative ideas and where it takes us to.

Hardware / Software Partitioning Decision

Most important part of Hardware / Software partitioning scheme is to determine which part of software needs to be moved to FPGA. This problem becomes complex in a system with multiple applications running at a time. Kalavade et al has given a set of thumb rules to decide whether a given node can be moved to hardware or not. Here they are:

• Repetition of a node: How many times a given type of node occurs across all applications? More this number, better to implement this in hardware.
• Performance-area ratio of a node: What is the performance gain, if a given node is implemented in hardware, in terms of area penalty in the implementation? Higher the ratio, better to move to hardware.
• Urgency of the node: How many times goes the given node appear in the critical path of applications? More this number, better would be the overall performance if this is moved to the hardware
• Concurrency of the node: How many concurrent instances of the given node can potentially run at a time (on an average)? Hardware is always good at doing things in parallel.

By considering these four factors, we can decide the multiple nodes that would qualify for hardware implementation.

Numeric definite integral in FPGA

Today when I looked at the comp.arch.fpga USENET feed, I saw an interesting question: how to perform integration in FPGA? Well, most of the time the answer would be, since FPGA is not handling continuous function, summation would be the approximation for integration. From the first glance, this may look like a right answer. But when we look at the purpose of integration, we find that it is too bad an approximation.

The purpose of integration is usually to find the area under a curve. If that is the case, to evaluate it numerically we have to go for adaptive quadrature algorithms, like Simpson's quadrature, Lobatto's quadrature, Gauss-Konrad quadrature, etc. If you are using MATLAB, you should be familier with the quad functions which has implemented these adaptive quadrature algorithms.

In an FPGA however, we never get input as functions, rather they are outputs of functions. For example, you would never get something like f(x) = (sin(x) + 20) for all 0<=x<=pi. Instead it would be the values of f(x) for each discrete value of x. In that case, the integration can be approximated as sum of area of triangle formed between the adjacent different values and the rectable formed by the lowest of the adjacent values with x-axis (y=0). And this has to be done for each value of x (usually comes with each CLK) and summed up. Once we get the result, we can multiply the result with the difference in x-axis between samples. Usually in an FPGA, the x-axis is CLK and so we have to use CLK period as the scale.

So at each CLK (somebody please tell me how to use LaTeX with blogger):

int(n) = int(n-1) + diff(f(n), f(n-1)) >> 1 + min(f(n), f(n-1))

The function is not as difficult to implement as it looks. The diff(f(n), f(n-1)) >> 1 gives the area of the triangle and min(f(n), f(n-1)) gives the area of the rectangle. "int" is the integration or the area under the curve at that limit. The function works if the CLK frequency is 1 Hz. For the other frequencies, the final integration function just needs to be multiplied by the CLK period.

For an ever-increasing function [f(n) >= f(n-1) for 0<=n<=N], the formula would reduce down to:

int(n) = int(n-1) + (f(n) - f(n-1)) >> 1 + f(n-1)

This works neat, but it is up to the person who implements, to determine whether they need summation or finding area.

A Verilog HDL library for fixed point-floating point conversion

Generally when people ask for my advice to learn Verilog HDL, I prescribe them this book, this book, this book or this book. But then, learning of a programming language does not complete without practise. So I would suggest that they write a synthesisable, vendor-neutral Verilog code for a simple, fixed point RISC microprocessor and test it by writing a testbench. Later on they can expand then processor to include pipelined processing.

But in recent days, the floating point processors are slowly creeping into the scene, displacing their fixed point counterpart, although the choice between them are extremely application specific.
So I ask the Verilog newbies to try out a floating point RISC processor, additionally. But why do they need to write a testbench separately for the floating point processor, if it is functionally similar to its fixed point counterpart, they wrote at the beginning? I tried searching around and found an extremely useful library (AFFHL).

Frankly the name of this library is not so cool, but its design and its working are impressive. I managed to convert the comprehensive testbench that I wrote for the fixed point processor to a testbench for floating point processor. This hardware library can also convert floating to fixed point, although I have not yet tried it. Simulink has toolbox for floating-to-fixed point conversion. But now a HDL library for that is simply wonderful.

Unfortunately I don't think VHDL has such a library (please correct me if I am wrong). In future you would see such a VHDL library based on AFFHL design in this page, provided the designers permit.