In this paper, we present a new methodology for structure optimization of block-based design. Instead of merging area and delay criteria, we segregate them into two independent steps. Solutions optimized for delay in the first step are optimized for area with a block-sizing algorithm in the second step. The fully optimized solutions eventually return to the first optimization step, if the user constraints are not met, using a structure-extraction module. A condition to this approach is that the area optimization phase does not alter the quality reached during delay optimization. We propose a framework for area optimization of delay-optimized structures based on structure similarities. We present a new model to represent block placements that share the same qualities for global routing. Using this model, we formally define the relation of similarity and exhibit several properties and theorems to validate our approach. The modules composing the area optimization phase are presented and experimental results confirm the validity of our methodology.

Floorplanning is an important step of IC design. Traditionally, floorplan representation has been segregated between slicing and non-slicing structures. We present a heuristic that translates any arbitrary structure into a slicing one, topologically equivalent to the initial one after a 1-D compaction.

This paper is devoted to a low-complexity algorithm for retiming circuits without cycles, i.e., those whose network graph is a direct acyclic graph (DAG). On one hand, DAGs have a great practical importance, as shown by the on-line arithmetic circuits used as a target application in this paper. On the other hand, retiming is a costly design optimization technique, in particular when applied to large circuits. Hence the need to design a specialized retiming algorithm to handle DAGs more efficiently than general-purpose retiming algorithms. Our algorithm dramatically improves on current solutions in the literature. We gain an order of magnitude in the worst case complexity, and we show convincing experimental results at the end of this paper.