Hierarchical design methodology supports complex FPGAs

Hierarchical design methodology supports complex FPGAs
By Salil Raje,
July 18, 2003 (9:56 p.m. EST)
URL: http://www.eetimes.com/story/OEG20030717S0047

FPGA devices have grown to ASIC size and complexity, but traditional EDA tools and methodologies have failed to keep pace. Engineers designing high-end FPGAs are beginning to face the types of problems that are all too familiar to most ASIC designers, delaying or even obstructing them from completing their designs. These include such problems as long and unpredictable route times, too many design iterations, and difficulty achieving timing closure.

Fortunately, there is an alternative for today's FPGA designers — adopting ASIC-style hierarchical design methodologies made possible by recent advancements in EDA software. Hierarchical design methodologies coupled with advanced analysis capabilities applied early in the design cycle enable designers to catch potential physical implementation problems prior to place and route.

Designers can then make the necessary adjustments to their designs before the lengthy place and route process begin s, thereby reducing the duration and number of design iterations. These block-based, hierarchical methodologies also increase the predictability of routing, as well as provide the ideal platform for teamwork and leveraging the reuse of intellectual property (IP).

Lengthy place and route

Complex FPGA designs can now require twenty or more hours of place and route time, especially when designers have specified a number of timing constraints. These designs can also require as many as fifty or more physical iterations, which is a serious bottleneck. Complicating matters, route times are unpredictable and unreliable. Repeated route iterations produce varying results from run to run, even when the design itself has not changed.

Using hierarchical, block-based, incremental methodologies, it is no longer necessary to run place and route on the entire flattened design each time the designer makes a small change. With this methodology an FPGA designer can run place and route only on the blo cks that have changed, leaving the rest of the physical design intact. Designers may also place and route blocks individually, enabling them to sequentially implement and assemble the design starting with the most critical blocks, or with the first blocks that become available (Figure 1).

Figure 1 — Start floorplaning a design by placing the timing critical blocks first, leaving the rest of the floorplan unpopulated.

With flat methodologies, it is common to kick off multiple routing runs, with random seed values, and hope that one will produce acceptable timing results. In a hierarchical methodology you can define area groups to effectively guide place and route towards successful results, which is a far more deterministic process.

When a designer defines area groups in the design, the problem of placing and routing a flattened design is broken into smaller, more manageable, block-level problems. C onsequently the overall place and route runtime is reduced.

Using a hierarchical methodology, designers also have the option of locking in the placement and routing results for blocks that meet timing requirements so that subsequent design changes do not affect them. This makes the overall place and route process far more predictable and stable.

Too many design iterations

Like ASIC designers, FPGA designers are iterating many times during physical implementation. This is because they are juggling too many parameters that must simultaneously meet requirements. These parameters may include the following:

Timing
Utilization
Connectivity
Power
I/O placement
Clock regions

The designer frequently does not know if all the parameters are met until after place and route. Since some of the parameters can be interrelated, the designer often fixes one problem and causes many more problems by doing so. This process is inherently unstable, involving too many lengthy place and route iterations in order to attain design closure.

Hierarchical methodologies attack these problems early, prior to lengthy place and route, through analysis and planning. With early floorplanning and analysis, the designer substantially reduces the number of back-end iterations.

Suppose that a designer runs a quick connectivity analysis and finds a potential routing congestion problem between several heavily connected blocks of the design (Figure 2). At that point the designer has the option to change the floorplan and fix the problem immediately, without waiting for a lengthy place and route that may not complete.

Once the designer adjusts the floorplan (Figure 3), the design has the necessary partitioning, block arrangement, and constraints to guide the place and route process to produce successful results. The resulting efficient floorplan should dramatically decrease place and route runtime and may also potentially improve design performance.

Figure 2 — Connectivity analysis shows potential routing congestion problem.

Figure 3 — Adjusted floorplan that produces successful place and route results.

With increased FPGA design complexity, designers are finding that timing closure is becoming more elusive. Some of the common hurdles they must overcome include timing knots, long critical paths that span hierarchy, complex clocking schemes and high fan-out.

Early analysis

The only way to reliably conquer these kinds of tough design problems is through integrated floorplanning and analysis — an EDA methodology that ASIC designers have been successfully using for many years. By using this methodology they can restrict logic migration and shorten connectivity lengths, thus boosting design performance. The analysis stage finds the timing problems ear ly, before lengthy place and route. The floorplanning stage then enables designers to make the necessary adjustments to avoid timing problems.

The latest FPGA methodologies also provide physical optimization capability, so that designers can analyze and address any implementation problems that might occur after place and route. At this point designers might try to attain performance targets by further manipulating the design. They can make adjustments to placement, either at the leaf level or block level, and then run incremental timing analysis to see if these changes positively affect design performance. With this methodology, designers see timing analysis results in minutes, instead of waiting hours for place and route to complete.

Methodology results example

Table 1 shows the results of integrated floorplanning and analysis combined with a hierarchical methodology. The results shown are from using the PlanAhead software from Hier Design. By enabling block-based, incremental d esign, this methodology improved the place and route runtime and, as an extra benefit, boosted design performance while maintaining utilization.

Table 1 — Increased performance and decreased routing time due to incremental methodology.

The designer implemented this particular design using a Xilinx xc2v6000 part. The part was 98 percent utilized and had four global clocks.

The designer floorplanned only four modules of the total design. The first row of the table shows place and route results prior to floorplanning. The second row shows the results after floorplanning. The third row shows the combined effect of using floorplanning with an incremental design methodology. The Clock column shows the longest path delay and the Runtime column shows the total CPU time used by the Xilinx place and route tools.

Using this improved ASIC-style design methodology, the designer was able to improve per formance by 31 percent. With incremental design techniques, the runtime was improved 4-7X for each subsequent incremental design change.

Controlling utilization

Controlling utilization is frequently an important aspect of FPGA design. Some designers try to crowd as much logic as they can into a part so that they can use a particular device that meets their needs in terms of volume production. Others want to leave a little spare space to ease the implementation of engineering change orders (ECOs) that may happen naturally throughout the design cycle.

Designers of products with long serviceable life cycles, such as medical or military equipment, may want to leave lots of space in their designs, or in particular blocks of their designs, for future field fixes and product upgrades.

Controlling utilization is much easier through the block-level techniques of a hierarchical design methodology. Designers that want to maximize utilization can set the utilization to a given level, and then run block-level place and route. If the route is successful, the designer can shrink the block and run block-level place and route again. The designer can continue this process to reach maximum utilization. Designers can also dramatically increase utilization by using Xilinx's area group compression constraints on blocks that are non-timing critical.

Designers who wish to leave some spare space in their designs can use hierarchical floorplanning to individually control the utilization level for each logic block. They may choose to leave more space in blocks that are relatively unverified, in anticipation that these blocks may require multiple design changes. They may leave less spare space in blocks that are well field-tested, since design changes in those blocks would be less likely.

Intellectual Property (IP) flow

Designing a complex FPGA requires a divide and conquer approach, such as the IP reuse and teamwork methodologies in widespread use by the ASIC design community. Hierarchical design enables teamwork and IP reuse. Designers can split their work into smaller, more manageable, block-based pieces, assigning responsibility of a given block, or set of blocks, to a given designer. Design managers can decide to reuse IP blocks from previous designs, or even purchase them from a third party, to shorten design and verification time.

Through hierarchical design, designers can fully characterize each block. They can freeze the placement within these blocks so that timing, power, and other physical characteristics are fixed and known to meet their requirements. Designers can then quickly connect these blocks to form larger, more complex designs that meet their physical requirements. In the ASIC world this is often referred to as a system-on-a-chip (SOC) methodology, and offers great benefits to designers developing very complex FPGAs.

This methodology is also particularly valuable for ASIC designers using FPGAs for prototyping. ASIC designers often want to run thei r FPGA prototype at the maximum possible speed, so it is important that each component logic block of the FPGA design meets their timing requirements.

The new FPGA design paradigm

FPGA designers are now encountering many of the same problems as ASIC designers. ASIC designers overcame them using hierarchical design with integrated planning and analysis tools. This methodology is now available to FPGA designers through recent advancements in EDA tools.

Diagram 1 — ASIC design style reduces FPGA iteration times

Designers who use this methodology can reduce the number of design iterations, as well as the length of these iterations. Designers can tightly control utilization, cramming more and more logic into a given part or leaving adequate space for future ECOs, field fixes, or upgrades for long life-cycle products. Designers can also more effectively work as a team by dividing a desig n into smaller, more manageable blocks, as well as hastening design and verification through IP reuse.

Salil Raje is chief technology officer (CTO) and co-founder of Hier Design. Previously, he was director of research and development at Monterey Design Systems where he was responsible for the development of physical prototype and analysis software.