An Excerpt From:

‘Partitioning Digital Circuits

for Implementation in Multiple FPGA ICs’

Roman Kužnar^{1,2}, Franc Brglez^{1}, Krzysztof Kozminski^{1}

The following pages contain an excerpt from the MCNC Technical Report named above. This information is provided in order to facilitate the use of the Partitioning (Xilinx) benchmarks developed as part of the project described in this MCNC Technical Report.

Memoranda in this series are issued for early dissemination to MCNC, its six Participating Institutions, and MCNC Industrial Affiliates. They are not considered to be published merely by virtue of appearing in this series. This copy is for private circulation only and may not be further copied or distributed.

MCNC Technical Reports are routinely submitted for publication elsewhere. Their distribution outside the MCNC Community prior to publication is limited to peer communications and specific requests. References to this work should be made either to the published version, if any, or in the form “private communication.”

For information about the ideas expressed herein, contact the author(s) directly. For information about the MCNC Technical Report Series, or Industrial Affiliates Program, contact Corporate Communications, MCNC, P.O. Box 12889, Research Triangle Park, NC 27709; 919-248-1842.

February 25, 1994 Technical Report TR93-03

\begin{matrix}c \\ ◯ \end{matrix}1993 MCNC All Rights Reserved

1MCNC Center for Microelectronic Systems Technologies, P.O. Box 12889, Research Triangle Park, NC 27709

2 Department of Electrical and Computer Engineering, University of Ljubljana, Tržaška 25, 61000 Ljubljana, Slovenia

Partitioning Digital Circuits

for Implementation in Multiple FPGA ICs

Roman Kužnar, Franc Brglez, Krzysztof Kozminski

ABSTRACT

This report considers the problem of obtaining a minimum–cost partitioning of a large logic circuit into a collection of subcircuits such that each subcircuit will fit into some device selected from a given library. Each device in the library may have a different price, size, and terminal capacity associated with it. This work has been motivated by a need to provide digital system designers with a capability to implement large circuits that do not fit in any one of the commercially available FPGA devices. Automatic partitioning software is needed to relieve the designers from the tedious task of partitioning the design manually in such situations.

The main result of the performed research is a partitioning algorithm based on a recursive application of the Fiduccia-Mattheyses bipartitioning heuristic. This heuristic has been amended with appropriate extensions to handle (a) the overall goal of the cost minimization and (b) the constraints reflecting the limitations on the capacity of FPGA chips. While the formulation and the implementation are general, we demonstrate the application of our method using circuits generated with a commercial tool and partitioned for implementation with a specific library of Xilinx’s FPGA devices.

The experimental partitioning software, k-way.x, developed in the course of the reported work, has exhibited a very encouraging performance, being able to produce solutions with cost quite near to the theoretical minimum calculated for many of the benchmark circuits.

1 Comments

The following section describes the results obtained while using the k–way.x partioning algorithm [1] to partition circuits from the Partitioning benchmark suite. This document is intended to provide users of the Partitioning benchmark suite with guidelines about reporting results obtained using their partitioning algorithms on benchmark circuits, and also some sample results.

2 Experimental Results

Since we wanted to exercise our algorithm on a wide spectrum of different circuit sizes, and the commonly used layout synthesis benchmarks include only a few netlists with known functionality, we selected for our experiments a subset of the well–known test generation benchmarks [2, 3]. As these circuits include full functional descriptions of all elements, we were able to map them into the XC2000 and XC3000 device families. The characteristics of the benchmark circuits after mapping them into their respective families are shown in Table 2. A number of the benchmarks we used are clearly too large to be mapped into a single Xilinx’s FPGA device, and even if better mappings could be found with somewhat lower CLB counts, the designer still would be faced with a partitioning problem to solve. In any case, in the context of this report it is not important whether the mappings performed by the XACT tool are the best possible. In this section, we discuss our experiences gained from using the k–way.x tool on the chosen benchmarks, and demonstrate this program’s effectiveness in minimizing the overall partitioning cost.

2.1 Partitioning Experiments

We used k–way.x in two partitioning experiments. The benchmarks mapped into the XC2000 FPGA family were partitioned with the objective of obtaining an implementation using identical FPGA devices. In this case, the problem is effectively simplified into partitioning into a smallest number of subsets, with constraints on the size and terminal count of each subset. The benchmarks mapped into the XC3000 FPGA family were partitioned with the objective of obtaining a least–cost implementation using any variety of FPGA devices listed in Table 1.

For the circuits mapped into the XC2000 family, the numbers of CLBs range from 74 to 833 while the numbers of IOBs range from 64 to 313. Considering the XC2064 device with 64 CLBs and 58 IOBs, the task is to partition the netlist into minimum number of devices, while meeting CLB and IOB constraints of the device. As mentioned earlier, we also need to measure routability of the devices after partitioning. The results of partitioning shown in Table 3 are encouraging in several ways. For 5 out of 8 circuits, we achieved the minimum cost possible, indicating that our implementation of the bisection algorithm is relatively stable and generates results which are consistent over a wide range of circuits. For the remaining 3 circuits, we had to increase the number of subcircuits mostly due to the unusually large ratio of IOBs to CLBs in the original circuit, which had to be distributed between the individual subcircuits. While not shown explicitly, only one subcircuit in one of the benchmarks was found initially unroutable and required backtracking with lower utilization bound to achieve 100% routability. The fact that none of these circuits had global clock or similar signals accounts for relatively high CLB utilization without a major impact on routability. Finally, the CPU cost of partitioning is negligible compared to all other tasks, such as mapping, placement and routing performed by the XACT tool.

For the circuits mapped into the XC3000 family, CLBs range from 283 to 2904 while IOBs range from 64 to 313. Considering the XC3000 device library in Table 1 with CLBs ranging from 64 to 320, IOB ranging from 64 to 144 and the relative price range from N$1.00 to N$4.83, the task of partitioning is not necessarily defined as finding a partition with the minimal number of devices but rather it is to minimize the overall cost of the partition. Again, the results shown in Table 4 are encouraging. We report results using the integer programming tool lp–solve to generate a lower bound for the lowest cost solution, followed by actual solutions generated with k–way.x in a static as well as a dynamic mode. Partitions generated during the static mode of k–way.x basically attempt to match the device distribution provided by the lp–solve for the initial circuit. In contrast, subcircuits generated during the dynamic mode of k–way.x always match a partition to the largest device returned by lp–solve for the remainder subcircuit before the bisection. The details of the dynamic version of the k–way algorithm have been given earlier.

While it may be unrealistic to expect that we can meet the lower bound solutions for general circuits, both static and dynamic solutions in Table 4 appear reasonable, compared to the lower bound solutions which have no constraints on the terminals or the number of cut nets allowed in the partition. In both modes, the CPU costs are comparable.

Device  Type No.  c_{i}  t_{i}  d_{i}  l_{i} u_{i} CLB cost
(i)  (CLB) (IOB) (N$)  d_{i}/c_{i}
XC3020xx-xx  1  64  64  1.00 0.8 0.9 0.0156
XC3030xx-xx  2  100  80  1.36 0.8 0.9 0.0136
XC3042xx-xx  3  144  96  1.84 0.8 0.9 0.0128
XC3064xx-xx  4  224  110 3.15 0.8 0.9 0.0141
XC3090xx-xx  5  320  144 4.83 0.8 0.9 0.0151

Table 1: A subset of the Xilinx XC3000 device library

Circuit #CLBs #IOBs #DFF #NETs #PINs
c499  74  73  -  123  409
c1355  74  73  -  123  408
c1908  147  58  -  238  780  Mapped
c2670  210  221  -  450  1255  into
c3540  373  72  -  569  1933 XC2000
c5315  535  301  -  936  3004
c6288  833  64  -  1472  3438
c7552  611  313  -  1057  3318
c3540  283  72  -  489  1645
c5315  377  301  -  699  2409
c6288  833  64  -  1472  3438
c7552  489  313  -  921  2924 Mapped
s5378  381  86  179  628  2332  into
s9234  454  43  288  716  2671 XC3000
s13207  915  154  661  1377  5309
s15850  842  102  597  1265  4977
s38584 2904  292  1452  3884  17483

Table 2: Benchmark circuit characteristics

Circuit  Cost  Cost  CPU  CLB  IOB
(Lower bound) (achieved) Cost  utilization  utilization
(N$)  (N$)  (sec.) min. avg. max. min. avg. max.
c499  2.00  2.00  4.2 0.47 0.56 0.69 0.95 0.96 0.97
c1355  2.00  2.00  4.4 0.58 0.58 0.58 0.95 0.95 0.95
c1908  3.00  3.00  15.9 0.64 0.77 0.89 0.64 0.79 0.98
c2670  4.00  6.00  51.6 0.28 0.55 0.92 0.74 0.91 1.00
c3540  6.00  6.00  59.4 0.94 0.97 1.00 0.74 0.93 1.00
c5315  9.00  11.00  176.8 0.55 0.77 0.89 0.78 0.91 1.00
c6288  14.00  14.00  306.2 0.84 0.94 1.00 0.43 0.57 0.69
c7552  10.00  11.00  239.1 0.48 0.88 1.00 0.72 0.90 1.00

Table 3: Partitioning using XC2000 devices of a single type ($1.00/device)

References

[1] R. Kuznar, F. Brglez, and K. Kozminski. Partitioning Digital Circuits for Implementations in Multiple FPGA ICs. Technical report, MCNC, Research Triangle Park, NC, February 1993.

[2] F. Brglez and H. Fujiwara. A Neutral Netlist of 10 Combinational Benchmark Circuits and A Target Translator in FORTRAN. In IEEE 1985 International Symposium On Circuits and Systems, pages 663–698, June 1985.

[3] F. Brglez, D. Bryan, and K. Kozminski. Combinational Profiles of Sequential Benchmark Circuits. In IEEE 1989 International Symposium on Circuits and Systems Proceedings, May 1989.

Circuit  Device  Total Cost CPU Cost
Distribution  (N$)  (sec.)
c3540 {0,1,0,1,0}  4.51  0.1
c5315 {0,3,1,0,0}  5.92  0.1
c6288 {0,5,3,0,0}  12.33  0.1  Lower bound
c7552 {0,0,4,0,0}  7.36  0.1  solutions
s5378 {0,0,3,0,0}  5.52  0.1  using
s9234 {0,0,2,1,0}  6.83  0.1  lp-solve
s13207 {1,1,6,0,0}  13.40  0.1
s15850 {0,0,5,1,0}  12.35  0.1
s38548 {0,1,0,14,0}  45.50  0.1
Circuit  Device  Total Cost CPU Cost  CLB  IOB
Distribution  (N$)  (sec.)  Utilization Utilization
c3540 {1,1,0,1,0}  5.51  26.2  0.74  0.82
c5315 {0,0,5,0,0}  9.19  77.8  0.52  0.95
c6288 {0,6,3,0,0}  13.68  88.6  0.80  0.50  Static
c7552 {0,0,4,0,0}  7.36  71.1  0.85  0.93  solutions
s5378 {0,1,4,0,0}  8.72  69.7  0.56  0.92  using
s9234 {0,0,3,1,0}  8.68  87.8  0.69  0.74  k-way.x
s13207 {9,1,6,0,0}  21.39  227.5  0.59  0.92
s15850 {0,1,6,1,0}  15.59  206.5  0.71  0.79
s38584 {3,6,0,13,0}  52.15  493.4  0.78  0.43
Circuit  Device  Total Cost CPU Cost  CLB  IOB
Distribution  (N$)  (sec.)  Utilization Utilization
c3540 {0,0,3,0,0}  5.52  26.2  0.86  0.73
c5315 {2,1,2,0,0}  7.03  79.4  0.73  0.89
c6288 {0,0,4,2,0}  13.66  78.6  0.96  0.50  Dynamic
c7552 {0,0,4,0,0}  7.36  73.4  0.85  0.93  solutions
s5378 {0,0,1,0,1}  6.67  68.4  0.82  0.82  using
s9234 {0,0,0,1,1}  7.98  63.3  0.77  0.76  k-way.x
s13207 {3,5,4,0,0}  17.16  239.8  0.72  0.88
s15850 {0,0,2,2,1}  14.80  171.8  0.83  0.78
s38584 {0,5,15,4,1}  51.83  466.5  0.75  0.67

Table 4: Partitioning using XC3000 device library in Table 1