BINET: an algorithm for solving the binding problem

Abstract

In this paper we present BINET (BInding using NETwork flows), a heuristic for solving the binding problem which occurs in high-level synthesis of digital systems. BINET is derived from an ILP formulation by mapping the binding problem for each time step onto a network optimization problem which can be optimally solved in polynomial time. Solving a sequence of these network flow problems gives a heuristic solution to the binding problem. BINET considers floorplanning during the design process and uses this information to reduce interconnect area. By using a rip-up and re-bind approach, considerable improvements can be achieved in the quality of the RTL design. BINET produces very good solutions in the order of seconds for several benchmarks. Among several current heuristics, BINET produces designs repairing minimum wiring requirement.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>