Logic Partitioning


Logic partitioning is a critical area of VLSI CAD. In order to build complex digital logic circuits it is often essential to subdivide multi-million transistor designs into manageable pieces. In some cases this is necessary in order to fit into the limited die sizes and packaging hierarchies of current technologies. In other situations existing CAD algorithms cannot efficiently handle complete systems, and designs must be broken into smaller chunks for both CAD performance and quality reasons. To meet these needs, we have been researching methods for partitioning large circuits into smaller pieces. This has involved work on logic bipartition, logic replication, and recursive bipartitioning onto restricted topologies (particularly multi-FPGA system topologies).

There are a huge number of techniques that have been considered for partitioning. We performed a survey of many of them, primarily those that build from the Kernighan-Lin, Fiduccia-Mattheyses bipartitioning algorithm. The results of this survey is in "An Evaluation of Bipartitioning Techniques". By combining most of the current bipartitioning literature, along with some novel new techniques, we have developed what we believe is the highest quality logic bipartitioning algorithm in the literature today.

Achieving the highest quality bipartitioning requires not just breaking the logic nodes into two groups, but may in fact benefit from duplicating some of the logic nodes. Specifically, if there is one node whose output is needed in both partitions, that node can be duplicated, generating the same signal locally in both partitions. Thus, this signal no longer needs to be communicated between the partitions, improving the quality of the partitioning. We investigated numerous logic replication techniques from the literature, as well as some new approaches, to develop a high-quality replication algorithm. As a result we were able to improve our bipartitioning results by about 39%, yielding significantly better results than have been reported previously. The results of this work are contained in "Replication for Logic Bipartitioning".

We also considered the problem of how to apply bipartitioning iteratively to multi-FPGA systems. Specifically, it is important to figure out what order of cuts in the logic correspond to what locations in the multi-FPGA system, so we both know how many I/O resources are available, as well as picking the best order to optimize for locality, thus minimizing the length and amount of inter-FPGA routing. This work can be found in "Logic Partition Orderings for Multi-FPGA Systems".

Researchers

Faculty

o Scott Hauck
o Majid Sarrafzadeh

Graduate Students

o Morgan Enos
o Jie Xue

Undergraduate Researchers

o Stephen Knol

Related Work

o Multi-FPGA Systems & Rapid-Prototyping
Development of the Springbok Rapid-Prototyping System for Board-Level Designs, as well as partitioning, pin assignment, and routing topology work for general multi-FPGA systems.

Journal Articles

S. Hauck, G. Borriello, "An Evaluation of Bipartitioning Techniques" (PDF), IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 8, pp. 849-866, August 1997.

M. Enos, S. Hauck, M. Sarrafzadeh, "Evaluation and Optimization of Replication Algorithms for Logic Bipartitioning" (PDF), IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 9, pp. 1237-1248, September, 1999.

Patents, Theses, and Book Chapters

S. Hauck, Multi-FPGA Systems, Ph.D. Thesis, University of Washington, Dept. of C.S.&E., September, 1995.

M. Enos, Replication for Logic Partitioning (PDF), M.S. Thesis, Northwestern University, Dept. of E.C.E., September, 1996.

Conference and Symposium Papers

S. Hauck, G. Borriello, "Logic Partition Orderings for Multi-FPGA Systems" (PDF), ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pp. 32-38, February, 1995.

S. Hauck, G. Borriello, "An Evaluation of Bipartitioning Techniques" (PDF), Chapel Hill Conference on Advanced Research in VLSI, pp. 383-402, March, 1995.

M. Enos, S. Hauck, M. Sarrafzadeh, "Replication for Logic Bipartitioning" (PDF), International Conference on Computer-Aided Design, pp. 342-349, 1997.

Technical Reports

S. Hauck, A. Agarwal, "Software Technologies for Reconfigurable Systems" (PDF), 1996.


For access to the rest of my information please see my homepage.