|
In this thesis, we proposed a new technology mapping algorithmwhich maps an original combinational circuit to a network consistingof configurable logic blocks (CLBs). This algorithm tries tominimize the number of CLBs in the resulting network and keep thedepth of network as small as possible. First, we model this problemas a linear programming problem to find an optimal solution. Second,we transform this problem to a minimum covering problem and aneffective greedy algorithm is proposed to solve problems of largesize. The greedy algorithm is divided into five steps as follows. 1. Accept an LUT network as input. 2. For a set of LUTs, find all possible types of CLBs that contain these LUTs. 3. Generate all LUT sets that correspond to the types of the CLBs by heuristic method. 4. Find a minimum cover that corresponds to a mapping solution. 5. Merge some CLBs in the solution obtained in step 4. Currently, we have no effective ILP tool in hand to solve aproblem of large size. But on the other hand, the proposed heuristicalgorithm works quickly well. In fact, it gets the optimal solutionfor more than 48% of the tested examples. Compared with algorithmsin RASP, the proposed algorithm obtained 4.5% of improvement of theaverage area with only 2.78% of drawback of the average depth.
|