Compiling the extra dimension

Three dimensional FPGA and three dimensional chips are creating a lot of buzz and may be the direction that VLSI design and reconfigurable computation are headed in. Why is it just a "may be"? There are a few start up companies that have come up with the 3D fabric and the interesting part is that the third dimension is not the same for everyone. In some architecture, the third dimension is the z-axis. So the 3D FPGA is just multiple fabrics of FPGAs stacked up. So the chip that looked like Manhatten structure earlier would start looking like Tokyo flyovers with roads running between different layers. In some other FPGA architecture, the third dimension is the time axis. What all these essentially mean is that, a mash-up multi-dimensional FPGA is certainly a possibility. So what's the problem with this?

Starting up a company with a new FPGA architecture and be successful with that is extremely difficult. The reason is not because of the quality of your architecture; rather it is because you may have to make the entire array of computer-aided design tools available to make your architecture programmable. Every company that might potentially use the newly introduced architecture would have a tried and tested development process that is strictly defined on the basis of the existing technology. They would want to fit the exact process with the new technology and this is where several newbies fail. Unless you can convince your customers that the benefit that your new technology brings to the table can overwhelm the temporary loss of productivity due to the process change, you cannot sell your product.

So the three dimensional FPGA should have a HDL parser and optimizer, logic minimization, technology mapping, placement and routing tooling support to the same extent that Xilinx or Altera provides. Now the first two are pretty established and architecture independent. You can use one of the different implementations of Espresso for logic minimization. Technology mapping can be very much similar to how it is done in the existing 2D FPGA, using force directed scheduling or any other established scheme.

The problem starts with the last two: placement and routing. Most of the placer and router used in industry are proprietary. I am pretty much confident that Altera's placement algorithm is deterministic and may be Xilinx also has a deterministic placement, I am not sure. When it comes to routing, most of these tools use negotiated routing with the negotiation scheme being proprietary. Placement is a NP-hard problem and routing is NP complete. So to achieve a critical path, if your placement and routing takes twenty times more CPU cycles than what the existing tools take, then your potential customers are going to take a step back immediately. Well, they want a "rapid" prototyping, you see.

If the 3D FPGA happens to be entirely made up of similar CLBs and IO blocks, the placement and routing is a little easier. Versatile Place and Route (VPR) is the standard, open source academic tool for placement and routing. It performs a simulated annealing based placement and Pathfinder-based negotiated routing on array-based FPGAs. How easy is it to modify VPR to support the third dimension? A block is defined in VPR through the following structure:

struct s_block
{
char *name;
t_type_ptr type;
int *nets;
int x;
int y;
int z;
};

In this structure, you can give the name of the block, type of the block, typically CLB or IO-block and the cartesian coordinate of the block's location, during placement. Here the x and y indicate the coordinates in x-y plane. What is z? No, it's not the third dimension you are looking for. Rather z is the number that specifies which sub-block the net refers to. So a single block can have multiple sub-block - each sub-block is a logic element. In this structure, you may have to add another variable to specify the coordinate in the third dimension (you may have to use a different name, since z is taken). And then it involves changing all the loops in VPR. You may also need to change the placement file's structure to introduce the extra dimension and make Pathfinder understand that. It is difficult; but with some effort, it is possible to make VPR support the 3D FPGA placement and routing. But can its quality compete with the existing 2D FPGAs? Can it be done on click of a button at a reasonable speed?

So on summary, introducing the third dimension in FPGA is certainly impressive. But if you want to make money out of it, you have to provide an array of necessary tooling support so that your potential customers can realize the fruits of extra dimension, without taking much risk and paying much price. On the other hand, 3D FPGA may evolve from some already established company that is not struck in a marketing myopia. Lets wait and see.