Floorplanning
Customer
Our customers are IBM Systems and Technology Group (STG) and IBM Electronic Design Automation (EDA). STG develops IBM's hardware and systems. EDA provides the tools to do so.
Challenge
Floorplanning is part of the development flow of integrated circuits. It is the process of deciding where to place subunits of a hardware design within a larger unit, together with port placement and wire routing. The problem has various flavors, depending on the design methodology used and the point in the development flow in which it must be solved. Typically some combination of the following constraints must be satisfied: blocks of logic may not overlap, ports may not overlap, certain areas may not be populated, wire lengths must be below corresponding thresholds, ports and wires may not be too close to each other, different ports and wires must/may go in different metal layers, etc. There may also be an optimization aspect added, e.g., conserve as much space as possible or minimize the number of wire crossings.
In today's densely packed designs such problems are quite difficult to solve and optimize. The number of logic blocks can range from dozens to millions, blocks may not necessarily be rectangular, ports may be constrained to block edges, etc. Finally, some of these problems must be solved in minutes, some in hours, and some might allow days, provided that the solution is of very high quality.
Solution
Specific problem instances are modeled as constraint satisfaction problems and solved using our CSP technology. We use both GEC and Stocs in order to solve this problem. In addition, we apply other satisfaction/optimization methodologies such as Mixed Integer Programming where appropriate. To date we have been tackling three problems.
- Large Blocks Placement Place a large number of blocks without overlap such that the estimated wiring cost will be minimized.
- Pin Assignment Place a large number of ports within (already placed blocks) such that the estimated wiring cost will be minimized.
- Custom Design Floorplanning Place both blocks and ports without overlap such that the estimated wire lengths will all satisfy their timing constraints.
Achievements
This work is in progress. In the Large Blocks problems we were able to improve the solution for an academic benchmark problem instance by around 30% with respect to the solution found by the current tools. In Pin Assignment we have preliminary results indicating improvements in the range of 20% - 30% over the existing tool.
Contact: Wesam Ibraheem (wesam@il.ibm.com)