
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 Path Delay Constraints for MultiFPGA Systems
Nozomu TOGAWA Masao SATO Tatsuo OHTSUKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E80A
No.3
pp.494505 Publication Date: 1997/03/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems) Category: Keyword: FPGA, multiFPGA system, circuit partitioning, path delay, logicblock replication,
Full Text: PDF(893.6KB)>>
Summary:
In this paper, we extend the circuit partitioning algorithm which we have proposed for multiFPGA systems and present a new algorithm in which the delay of each critical signal path is within a specified upper bound imposed on it. The core of the presented algorithm is recursive bipartitioning of a circuit. The bipartitioning procedure consists of three stages: 0) detection of critical paths; 1) bipartitioning of a set of primary inputs and outputs; and 2) bipartitioning of a set of logicblocks. In 0), the algorithm computes the lower bounds of delays for paths with path delay constraints and detects the critical paths based on the difference between the lower and upper bound dynamically in every bipartitioning procedure. The delays of the critical paths are reduced with higher priority. In 1), the algorithm attempts to assign the primary inputs and outputs on each critical path to one chip so that the critical path does not cross between chips. Finally in 2), the algorithm not only decreases the number of crossings between chips but also assigns the logicblocks on each critical path to one chip by exploiting a network flow technique. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it resolves almost all path delay constraints with maintaining the maximum number of required I/O blocks per chip small compared with conventional alogorithms.

