language: en

An Improved Algorithm for Performance Optimal Technology Mapping with Retiming in LUT-Based FPGA Design

Jason Cong and Chang Wu
Department of Computer Science University of California,
Los Angeles, CA 90024

Abstract A novel algorithm, named SeqMapII, of technology mapping with retiming for optimal clock period for K-LUT based FPGAs was recently proposed by Pan and Liu [13]. The time complexity of their algorithm, however, is O(K 3 n 4 log(Kn 2 ) log n) for sequential circuits with n gates, which is too high for medium and large size designs in practice. In this paper, we present three strategies to improve the performance of the approach in [13]: 1) efficient label update with single K-cut computation based on the monotone property of labels that we showed for sequential circuits, 2) a novel approach for the K-cut computation on partial flow networks, which are much smaller in practice, 3) SCC (strongly connected component) partition to further speedup the algorithm. In practice, our algorithm works in O(K 2 n 3 log n) time and O(Kn) space according to our experimental results. It is 2fi10 4 times faster than SeqMapII-opt for computing optimal solutions and 2 times faster than SeqMapII-heu which uses very small expanded circuits as a heuristic.

1. Introduction