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.

Temporary Suspension

I have not been posting anything in my blog recently as many of you noticed and some of you mailed. The fact is that I am busy in two completely independent work. 1. Designing and implementing a completely new heuristic of logic minimization and 2. Physical layout design for a CMOS charge pump.

Both these are interesting and consume most of my time. As a result, I cannot find time to post my views on my blogpage. So until mid-December, there will be sporadic updates in the blog. Nothing more than that. Starting mid-December, I will be back on track.

Returning 80s

Fashion is cyclic. What goes out of fashion today would be fashion tomorrow. Now whatever was the fashion is coming back slowly. I am not talking about the pure fashion news. I am talking about a silicon PCB and a 3D chip with buses through bare silicon between layers. Some start ups are trying to build PCB-like system on a bare silicon. One does it in 3D and the other in 2D. With a high ASIC price and the need for compact logic, this may come as an alternative for many struggling IC makers.

ARM-wrestling with Intel

ARM Cortex A8 is finally going to run in GHz speed, delivering more than 2000 Mips. So your Netbooks and iPhones may just be faster. If your response is Intel's Atom is already beyond GHz mark, here is the best part of the news: ARM Cortex A8 does all these while consuming just 640 mW power and can run at a minimum supply of 1 volt. Currently iPhone 3G runs at 600 MHz powered by ARM Cortex A8 processor. Both Intel and ARM knows that netbooks and smartphones are the computers of tomorrow, as PC was back in eighties.

So both the companies are gearing up from opposite directions to capture the market. Intel's x86-based Atom runs at 2 GHz, but the problem is that it's like the gas-guzzlers of GM. People would not go for a PDA or netbook that consumes battery at fast rate. Intel has speed but the problem is with the power consumption which it is working towards. It has already announced the release of Metfield, a 32 nm Atom that hits market in 2010. Smaller size chip with low power consumption. The best fit to compete with ARM. Intel's Atom codenamed Metfield is already reported by CNET as the smartphone chip of the 2011. The figure (Courtesy: Intel/CNET) shows the strategy of Intel.

As with ARM is concerned, market presence is its huge advantage. Almost all the latest handheld gadgets have ARM inside. ARM developers have more experience in embedded systems and so poised to develop low power processors. Currently they are up to the task of speeding up the processor to meet the x86 standard. Both ARM and x86 are superscalar architecture. I think both of them use AMBA interconnects. Starting from ARMv5TE (introduced in 1999), they have a DSP instruction set extension, which Atom also has. But the similarities end here. Cortex architecture is strikingly different from the x86 architecture. This fall, Texas Instruments is going to sample on OMAP4 with two parallel Cortex A9 cores in place of a single Atom core. There are already plans to introduce a quad-core Cortex A9 (see figure, Courtesy ARM/CNET), which would certainly pose a stiffer competition to Metfield.

Atmel's battery authentication IC - a reality check

Atmel introduces a cryptographic battery authentication IC - AT88SA100S in a attempt to curb the market of counterfeit batteries that has all sorts of problems that would tarnish the brand value of original equipment manufacturer (OEM). I think the idea is more like digitally signing the battery. OEM would have a signature that the quacks cannot forge.

The AT88SA100S CrytpoAuthentication™ IC is the only battery authentication IC that uses a SHA-256 cryptographic engine...

SHA-256! Excellent hashing algorithm. Developed and recommended by NSA itself. I don't think there are many commercial hardware implementation of SHA-256. SHA-2 style hashing like SHA-256 requires many registers and gates compared to SHA-1 implentations. As a result, the die size, the critical path, and the operational frequency all increase. Frequency specifications are not given in this press release. But here comes the most important claim:

...a SHA-256 cryptographic engine and a 256-bit key that cannot be cracked using brute force methods.

Now that's interesting. I am not a professional cryptanalyst or a professor of mathematics. But what I know is that any N-bit hash function can be cracked through brute force with atmost 2^N trials - in this case 2²⁵⁶ trials. A collision attack can be done in a 2^N/2 trials - in this case 2¹²⁸ trials. In a 256-bit key hash function, a 50% probability of random collision can be obtained through birthday attack with 4 x 10³⁸ attempts. Well, these are quite large number of trials that may take years of computational time. Still you cannot categorically deny that brute force is impossible. May be in their implementation, brute force would not be allowed. Something like wait for 3 unsuccessful attempts and then self-destruct. Such a scheme would not pass. I don't want my iPhone to be broken, just because I tried putting in a phony battery. I need more detail.

The 256-bit key is stored in the on-chip SRAM at the battery manufacturer’s site and is powered by the battery pack itself. Physical attacks to retrieve the key are very difficult to effect because removing the CryptoAuthentication chip from the battery erases the SRAM memory, rendering the chip useless.

Challenge/response Authentication. Battery authentication is based on a "challenge/response" protocol between the microcontroller in the portable end-product (host) and the CrytpoAuthentication IC in the battery (client).

The first point makes a lot of sense. The key is the SRAM powered by the battery itself. You pull the SRAM, the CMOS SRAM cells would loose power and thus memory. Second point is that it uses challenge/response authentication. It is more like the UNIX password authentication - user supplies password, it is hashed and the hash is compared with the stored hash in the UNIX server. In this case, I think battery would supply its hash to the device. The device must have a table of possible battery manufacturer ids and their hashes. How secure is this table?

Security of a system lies in its overall implementation rather than the strength of the cryptographic algorithm it uses for communication. The algorithm itself is just a part of it and not all of it.

Overall, Atmel has done a good job. Soon we can expect electronic devices to support only the authentic batteries that do not leak and spoil your device itself. Soon we can say Auf Wiedersehen to counterfeit batteries and their makers.

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.

Ride on the STBus - a brief look at the different protocols

System on Chip (SoC) communication architecture is a vital component in SoC that interconnects heterogeneous components and IP blocks and supplies a mechanism for data and control transfer. This is a significant parameter in the performance and power utilization of the chip, especially when the feature size is in nanometers. As a result, a given architecture must ensure to deliver an agreed QoS through arbitration mechanisms. Recently I took some interest in going through the VSIA (Virtual Socket Interface Alliance) standards for intra-chip communication and the closely aligned bus architecture of STMicroelectronics (STBus) to see how it fits in an automobile collision avoidance system (Blogger sucks. I cannot upload a PDF! Ridiculous!!).

The STBus IP connects an initiator and a target. The initiator (master) initiates the communication by sending a service request to the target and waits for a response. The target obtains the service requests, validates it, processes it and sends back the response. There are configuration registers to change the behavior of request and response handling. These configuration registers allow changing of bus behavior and adjusting the traffic depending on priority, bandwidth, etc.

STBus Block Diagram

There are three protocols in which STBus can operate: Type 1, Type 2, and Type 3 protocols. Type 1 is for a simple, low performance access to peripherals. Type 2 is a little more complex with support to pipelined architecture. Type 3 extends supports to asynchronous interactions and complex instructions with varied sizes. All these are implemented used a shared multiplexer or a crossbar multiplexer based architecture. After going through the characteristics of these protocols, it was easy for me to decide that Type 1 and Type 2 interface are suffice for my collision avoidance system.

Type 1 protocol is the best candidate for general purpose I/O with very minimal operations. It has a very simple handshake with each packet containing the type of transaction (request or response), position of the last cell, address of the operation and the related data. All peripherals are required to instantiate these mandatory signals.

Type 2 protocol has everything within the Type 1 added with pipelining ability, source labeling, prioritization, etc. Another important feature of Type 2 is that a transaction can be split into two parts: the request and the response. So once the initiator sends the request part it can do whatever other activities without waiting for the response, since response is like a separate transaction. This property certainly adds to the performance of the system. Pipelined transactions arise as a result of this transaction splitting. The Type 2 initiator can send consecutive transaction as in a pipeline. The most important point to note here is that the order of transaction has to be maintained with care. The response is expected in the same sequence in which the request is sent. As a result, the initiator-target pairing has to be maintained until all responses are received. Establishing contact with a new target is forbidden if the existing target has not responded for all service requests.

Type 3 protocol is a more advanced protocol that is prescribed only if both the interacting systems are intelligent enough to cope with the complex handshakes between initiator and target. Two main features of Type 3 protocol are shaped packets and out of order transaction management. Shaped packet allows a varied size of request and response packet to be transferred. This feature is certainly an improvement in bandwidth usage. The out of order transaction management feature allows transactions to be processed in any order. This is because in Type 3 protocol, each transaction is earmarked with a four byte transaction id.

In the collision avoidance system, I was talking about all the peripherals and external registers can be connected through Type 1 protocol. Type 2 is well positioned between my baseband demodulator and signal processor or FPGA. My baseband demodulation gives me complex baseband signal values for a 64 element array. For this array, I have to perform power spectrum estimation. My transaction size is going to be fixed and the initiator (baseband modem) is coupled with the target (DSP/FPGA). The spectral estimation is usually a complex process and may take more time than baseband demodulation. So Type 2 allows me to split the request and response and pipeline the flow to the processor. I may need to add a buffer at the target end and latency at initiator end so as to balance the difference in speed. In Type 2, since I cannot resend a message that is already delivered, I have to piggyback the acknowledgement to decide whether the initiator can send another asynchronous packet or go to a wait state.

A Quick Tour of the FORst

In an earlier post about VLSI routing, I promised a little wonkish post on Obstacle Avoiding Rectilinear Steiner Minimum Tree (OARSMT). This may be it, but still not so wonkish. In this post, I would try to explain FORst - one of the earlier methods (2004) to solve OARSMT problem.

OARSMT is a NP-Complete problem and so it cannot be solved in polynomial time. So VLSI designers use different heuristics to derive the solution for OARSMT or simply RSMT. The simplest of all the solutions is to derive a rectilinear minimum spanning tree and taking that as the approximation for RSMT. Theoretically, it is nearly a 50% approximation, i.e. wire length would be up to 50% more if we assume rectilinear minimum spanning tree to be RSMT, although in practice, it would be lot better.

In this paper, the authors have derived a 3-step heuristic algorithm as an optimal solution for OARSMT. The first step is to split the entire graph into several subgraphs depending on the location of the terminals. For this we have to construct a full steiner tree. Full steiner tree is the one in which all nodes in the graph are leaves. Hwang's theorem is used to construct such a tree. Once done, we just need to wipe out all edges that pass over one or more obstacles. Now the nodes in the subtrees that we get, constitutes the subgraph.

The second step is RSMT construction. It is apparent that the subgraphs that we constructed are free of obstacles. We can use any heuristic to construct the RSMTs. The original paper uses a combination of ant colony optimization (ACO) and greedy approximation methods to construct the RSMTs. To be more specific, ACO is used for smaller terminals for accuracy and for connecting them together in a larger terminal greedy method is used as it produces faster result.

The third step is to combine all the RSMTs. The nearest nodes of every RSMT is joined together with all adjacent subgraphs. The paper gives experimental evidence that even a large graph with several obstacles can be routed in a small time. A typical nanometer integrated circuit fabric would have thousands of nodes and hundreds of obstacles like power lines, IPs, etc. All those cases can be treated as large scale OARSMT problem and FORst is the right candidate if you are looking for a solution.

FORst is now nearly five years old and there have been several improvements and several improved heuristics resulting in more and more efficient implementations. However we just could not miss our FORst. It's like the 8088 processor, however outdated you would always learn before proceeding to the architecture of P4.

VLSI Routing - the most interesting puzzle of the last decade

One of the most important task in physical design of VLSI circuits is routing. The speed and power conservation of the chip depends upon how the different components are routed using the shortest possible wiring. The speed at which an optimal or semi-optimal route is derived, is crucial for the rate of chip production in scale. To solve this problem, we have to divulge into Graph theory.


Now lets start with Minimum Spanning Tree. In a connected, undirected, weighted graph with several nodes, a spanning tree is defined as subgraph that connects all the vertices together. A graph can have many spanning trees. One of those spanning tree becomes a minimum spanning tree, if the sum of weights of all edges in that spanning tree is the least compared to the other spanning trees. So in a simple VLSI layout in which we need to connect all nodes, you can very well assert that the minimum spanning tree is the best way to route the different nodes. Minimum spanning tree problem is easy to solve using any of these algorithms.

But in practise, the layout routing is not always that easy. The complication comes when the total number of nodes in the graph is V and there are N nodes, such that N is a subset of V. In such a situation, we have an option to use the nodes that are in V, but not in N, provided it yields a better solution. The minimum spanning tree among the N used nodes is not necessarily the most optimal solution, because using the nodes that are not in N, we could actually create shorter routes. So we have to go for a steiner tree. A Steiner tree is a tree that connects the N nodes in a graph using extra nodes, in an attempt to reduce the total Euclidean length. Solving a Steiner tree problem is not so simple because the Steiner Tree problem is a NP-complete problem. Under certain circumstances the problem can be solved in polynomial time, but in general heuristics-based algorithm has to be used. To get more details about Steiner Tree problem, please refer to this book. A typical VLSI layout will have V nodes in which only N needs to be connected, although you can use all the V nodes to ensure shortest routing. So Steiner Tree Problem is more similar to VLSI routing than the spanning tree problem.

There is another practical factor that we overlooked in the previous paragraph. In VLSI routing, we cannot simply take any arbitrary route to connect two nodes. In other words, the shortest route between two nodes is not necessarily the line connecting them. This is because once the placement is over, the routing is allowed only through the rectilinear grid in between the cells. So the problem to solve is not really Steiner Tree, but a rectilinear Steiner Tree. So in a VLSI layout, given a set of terminal, the rectilinear Steiner minimum tree interconnects all the terminals through some additional nodes.

But as the size of the chip reduces, as we move from micrometer scale design to nanometer scale design, new problems crop up. The VLSI routing in a nanometer design has to consider various obstacles like power lines, pre-routed nets, jumpers, etc. As a result, an obstacle avoiding rectilinear steiner minimal tree (OARSMT) has become an important problem in recent years. The first practical approach of OARSMT was present in the name of FORst approach in 2004. Since then there has been a lot of interesting heuristics and approximations to solve this problem. In another wonkish post, I would explain FORst and recent developments to optimize OARSMT solution in another wonkish post.