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 contains a description of how the k–way.x [1] partitioning algorithm was interfaced to the Xilinx tool, XACT. Other partitioning algorithms may be interfaced with the Xilinx Design Development System in a similar manner. This document is intended to provide users of the Partitioning benchmark suite with guidelines about interfacing their partitioning algorithms to the Xilinx Design Development System.

2 Software Implementation of the k–way Partitioning Algorithm

We implemented the proposed k–way partitioning algorithm in the C language and designed interfaces to the Xilinx tool XACT [2]. In Figure 1 we illustrate the process of using our partitioning tool, k–way.x, as an extension of the XACT Design Development System.

2.1 Interface to the XACT Xilinx Development System

Figure 1: Interfacing k − way.x to XACT

The input data to k–way.x is a design description given in the XNF format as a netlist of gate primitives. Using the XACT software, this description can be readily mapped into a netlist of CLBs and IOBs represented in the MAP format. The need for partitioning arises when the mapped netlist does not fit into any FPGA package available in the device library. Furthermore, partitioning can be used to minimize the design cost, even if it is possible to implement the design as a single, large FPGA IC. For example, it is possible that the smallest FPGA chip with a sufficient number of CLBs is unroutable, forcing the designer to use a larger device, capable of not only containing all CLBs but also yielding a 100% routing completion. This larger device may be significantly oversized compared to the design size; in other words, its CLB utilization may be very poor. If the design is partitioned, it is possible that a number of smaller devices with higher CLB utilization could be used, thus reducing the design cost.

Currently, the designer has to perform the partitioning manually. In certain cases this task may be manageable, e.g., if the circuit was designed by a designer using schematic capture tools. However, the partitioning task may be exceedingly difficult when its subject is a large netlist, e.g., generated automatically by a high–level synthesis tool. An automatic partitioning tool is the only practical alternative in the latter case.

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] User Guide and Tutorials. Xilinx, Inc., 2100 Logic Drive, San Jose, California, 1991.