Abstract| W e propose an ecient performancedriven two-way partitioning algorithm to take i n to account clock cycle period and latency with retiming.W e model the problem with a Quadratic Programming formulation to minimize the crossing edge coun t with nonlinear timing constraints.By using Lagrangian Approach on Modular Partitioning (LAMP), w e merge nonlinear constraints to the objective function.The problem is then decomposed into primal and dual two subprograms.The primal and dual problems are solv ed by a Quadratic Boolean Programming approac h and by a subgradient method using cycle mean method, respectively.Experimental results show our algorithm achieves an average of 23.25% clock cycle period and 19.54% latency reductions compared to the Fiduccia-Mattheyses algorithm.In terms of the a verage number of the crossing edges, our results are only 1.85% more.1 Problem F orm ulation A synchronous digital system can be represented by a directed graph, G(V = R [ C; E); where R is the set of register nodes and C is the set of combinational block nodes.Each n o d e i has an associated size s i and delay d i .E is the set of directed edges which correspond to signal ow in the system.Each edge (i; j) is associated with an attribute c i;j , which denotes the number of the interconnections from nodes i to j.A t w o-way partition P. The capacity limits of these modules are denoted by S 1 and S 2 , respectively.An edge (i; j) i s a crossing edge of P if node i and node j are in dierent subsets V 1 and V 2 .W e assume register nodes and non-crossing edges are of zero delay.The crossing edges have a n i n termodule delay determined by technologies. Assum ptionsW e make the following assumptions in this paper: 1.The intermodule delay is less than the desired clock period, T. 2. Data ow are ne-grained in nature.Although we assume the combinational blocks are negrained, some structures, e.g. the delays on crossing edges, are inherently coarse-grained and cannot be split.

Rediscoveredand mathematically proved that a partitioning problem under timing and capacity constraints can be formulated exuctly as a Quadratic Boolean Programming Problem.'fMs new formulation allows arbitrary component sizes, arbitrary capacities of partitions, arbitrary interconnection costs and delay models between partitions.We then found a generalizatior@nhancementof Burkard's heuristic to efficiently solve the problem.Seven industrial circuits were used to compare our method against two other heuristics based on the traditional approach of component interchanges.Test results showed the superiority of our new method in terms of both solution quality and CPU usage,for problems under very tight Tirnhg and Capacity Constraints.

We propose a novel paradigm for two-way circuit partitioning which minimizes the clock cycle. The replication technique is suggested for feedback loops to minimize the impacts of intermodule delays and the crossing edges when necessary. A flow timing cut is devised to produce partitions which can be guaranteed to achieve clock cycles equal to their lower bound with respect to the partitions using retiming. When the clock cycle optimization is the major objective and feedback loop sizes are not large, we propose an efficient, easy to implement algorithm which still guarantees achieving the lower bound clock cycle with respect to its partition. Experimental results have shown that our algorithms can achieve an average of 15% clock cycle time reduction compared to the best retimed results produced by 20 runs on each test case using a Fiduccia-Mattheyses algorithm.