‹header›

‹date/time›

Click to edit Master text styles

Second level

Third level

Fourth level

Fifth level

‹footer›

‹#›

First of all, thank you for attending my thesis defense.

My thesis title is “EVE: A CAD Tool Providing Placement and Pipelining Assistance for High-Speed FPGA Circuit Designs”

The Push-button solution has improved a lot over the years. Nowadays, it can achieve speed in excess of 100 MHz. However, if we want to push FPGA circuit designs towards the physical limit of the silicon, which will be in the range of 300-400+ MHz, the push-button approach does not work. Also, the push-button flow involves iteratively floorplan and place and route over and over again until the timing goal is achieved, so it is rather time consuming, and if a change is applied to the floorplan, the whole design will have to be placed and routed again. By the time the result is available, it might look decoupled from the change. We were motivated by a paper published by Brian Von Herzen, with title “Signal Processing at 250MHz using high-performance FPGA’s”. He talked about the “Event Horizon concept” which is very useful in high-speed designs. Therefore, we decided to build a manual editor which makes use of this concept. It is called EVE, which stands for “Event horizon Editor”.

This diagram describes the Xilinx Virtex-E CLB architecture.

Each CLB has two slices.

Each slice contain 2 4-input LUTs, a carry chain, and 2 FFs

Now I’ll define the term “Event Horizon” which is introduced by Brian Von Herzen in his paper. I’ll use the example described in my thesis.

First, let’ set the target speed to 250MHz, resulting in a timing budget of 4ns.

Then, we’ll collect timing characteristics of the chip, such as maximum clock skew, clock-to-output delay, LUT delay, and FF setup time. We then calculate the “Event Horizon”. We find that maximum routing delay is 1.1ns, so the target CLB can reach places that allow a routing delay of at most 1.1ns.

This green area represents the “Event Horizon”.

It’s defined as the physical locations relative to the src CLB where a target CLB can be located while still satisfying the timing budget.

This diagram describes the difference between the push-button CAD flow and what we called the Event Horizon methodology. As we can see the push-button flow has a loop for doing floorplanning, placement & routing, and timing analysis.

The Event Horizon methodology however works like this:

Instead of making a change in the floorplan, and feed through the backend tools, as in the push-button flow, Placement and packing of a small portion of the circuit is changed, and the modified circuit is incremetnally placed, routed and timing analyzed.

The effect of the small change is immediately available to the user.

EVE has two modes of operations: the Timing Exact Microscopic Placement (TEMP) mode, and the pipelining mode.

…

This diagram demonstrates the “Timing Horizon”. It is similar to the concept of “Event Horizon” I described a while ago. Throughout my thesis, I just call it the “Horizon”. It will display the effect of the overall circuit speed when a circuit element moved to the indicated target positions. The gradient of blue colours show the “goodness” of the positions, with lighter colours indicating better positions. Also, a number is displayed indicating the difference in overall circuit timing. A negative number means the speed improves.

This diagram shows the Timing Exact Microscopic Placement Mode, or what we called the TEMP mode.

It displays the circuit as a grid of CLBs.

Each CLB has two slices.

And each slice has six components: 2 LUTs, 2 carry elements, and 2 FFs.

At the bottom, there is a status bar showing the current speed of the circuit. It is updated after each user move.

Here is the currently selected FF component.

This shows a 3D plot of the pin-to-pin routing delay values for a particular group of delay values.

Von Herzen also showed that in such high-speed designs, circuit elements sometimes could not be placed within the Event Horizon. In such cases, a pipelining FF is inserted within the original Event Horizon, to form a new extended Event Horizon that can reach further away from the src CLB. This guides us to look into pipelining as an important element of the Event Horizon approach.

This diagram illustrates the pipelining mode.

It displays the circuit in a directed acyclic graph (DAG) format.

Each node is an input/output pin of a logic slice, or input/output ports of sequential elements such as flip-flops and shift registers. Each edge represents an electrical connection in the circuit, it has an assocaited logic or routing delay. Two nodes labeled “START” and “END” connect to the primary inputs and outputs. When a flip-flop is inserted on an edge, a box appears. If the edge is flip-flop insertable, the box is solid, otherwise, it’s hollow. Edges are coloured red if they’re critical, and green if they’re flip-flop insertable. The status bar will display at all times the estimated new circuit timing after pipeline synthesis. When flip-flop tracing is enabled, a series of concentric circles are displayed to help the user locate a flip-flop which can be moved to a particular edge.

This diagram describes the Xilinx Virtex-E routing architecture.

Each CLB has local feedback connections between its 2 slices.

Each CLB has two carry chains running vertically upwards.

It can connect to a switch box which connects to general routing including singles, hexes, and longs. There are also direct connects (or what we call nearest neighbour connects) going horizontally to the CLB’s left and right neighbours.

There are 2 wires going in each direction.

These nearest neighbour connections are very important in high-speed designs, because it’s the fastest routing resource available across CLB, and we have to carefully control the placement of connecting circuit elements to make good use of them.

This diagram shows the Xilinx hardware description language (HDL) design flow. The boxes in white are CAD tools and boxes in green are files.

It begins with design entry using an HDL or Verilog.

Then a logic synthesizer like Synplify Pro synthesizes the design into a EDIF netlist of logic gates.

Then in another stage, MAP, which is a technology mapper packs the logic gates into CLBs.

The NCD file generated after the MAP stage can then be placed and routed using the PAR tool, or it can also be floorplanned using the Xilinx Floorplanner, or it can be manually edited using the Xilinx FPGA Editor.

We can also timing analyze the NCD file using TRACE and generate a timing report.

Another tool, the XDL utility can convert between the Xilinx binary NCD format to a text based XDL circuit description file.

Synplify Pro is an advanced synthesis tool that can do resource sharing, automatic pipelining and register balancing.

Now we’ll look at the various concepts involved in pipelining.

Extracting routing delays is much more difficult because of the large number of pin-to-pin delay values present in the Virtex-E chip.

This chart summarizes the distribution of net distances for the Vision circuit.

It has 88% of the nets with Manhattan distance <= 10.