
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Circuit Partitioning Algorithm with Replication Capability for MultiFPGA Systems
Nozomu TOGAWA Masao SATO Tatsuo OHTSUKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.12
pp.17651776 Publication Date: 1995/12/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms) Category: Keyword: FPGA, circuit partitioning, logicblock replication, network flow,
Full Text: PDF(904.7KB)>>
Summary:
In circuit partitioning for FPGAs, partitioned signal nets are connected using I/O blocks, through which signals are coming from or going to external pins. However, the number of I/O blocks per chip is relatively small compared with the number of logicblocks, which realize logic functions, accommodated in the FPGA chip. Because of the I/O block limitation, the size of a circuit implemented on each FPGA chip is usually small, which leads to a serious decrease of logicblock utilization. It is required to utilize unused logicblocks in terms of reducing the number of I/O blocks and realize circuits on given FPGA chips. In this paper, we propose an algorithm which partitions an initial circuit into multiFPGA chips. The algorithm is based on recursive bipartitioning of a circuit. In each bipartitioning, it searches a partitioning position of a circuit such that each of partitioned subcircuits is accommodated in each FPGA chip with making the number of signal nets between chips as small as possible. Such bipartitioning is achieved by computing a minimum cut repeatedly applying a network flow technique, and replicating logicblocks appropriately. Since a set of logicblocks assigned to each chip is computed separately, logicblocks to be replicated are naturally determined. This means that the algorithm makes good use of unused logicblocks from the viewpoint of reducing the number of signal nets between chips, i.e. the number of required I/O blocks. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it decreases the maximum number of I/O blocks per chip by a maximum of 49% compared with conventional algorithms.

