Network Flow Based Datapath Bit Slicing

摘要

In deep sub-micro designs, more functions are integrated into one chip, and datapath has become a critical part of the design. Typical datapath consists an array of bit slices. The inherent high degree regularity of datapaths is especially attractive to the placement and routing to achieve regular layout with high density and high performance. However, the current design methodology may generate inferior datapath designs because the datapath regularity cannot be well understood by the traditional design tools. In previous works, several techniques are proposed to preserve/re-identify datapath structures. However, they either restrict the datapath optimization or have little tolerance on bit slice difference. In this work, we present a novel approach to re-identify datapath bit slices. Contrary to the previous template-based approach, we convert the bit slicing problem to the bit matching problem. Then a min-cost max-flow based algorithm is proposed to identify the main-frame of bit slices so that the datapath bit matching is achieved. An efficient two way search approach is developed to derive the full bit slices based on the bit matching results. We further improve the bit slicing solution with an iterative method. The experimental results demonstrate the effectiveness and efficiency of our approach.