Bisection of Partitioned Logic
Original Publication Date: 1986-Apr-01
Included in the Prior Art Database: 2005-Mar-08
This publication discusses the problem of partitioning of VLSI networks into two parts-bisection problem. The importance of the problem is well understood and numerous heuristic solutions were proposed [1,2,3, 4] wherein most of the research in the area addresses the problem in its original form: given a network (collection of nodes and nets), partition the set of nodes into two parts of approximately equal size, minimizing the number of dissected nets (nets connecting nodes from different parts). However, one of the most important applications of bisection theory, namely, placement technique based on partitioning, requires more than just a bisection. It is more often required to partition the logic into more than two parts, or bisect already clustered logic in such a way that every cluster also gets bisected [5,6,7].