A New Fpga Packing Algorithm

Compared with the product of ASIC and full customed design, the design of FPGA has many wonderful features such as flexible, easy to implement and so on. But under the same process condition, the speed, power consumption and chip size of FPGA is a serious problem and make it less competitive. This thesis is trying to describe a new method for clustering which is called re-generation clustering. In this way we will use re-generation clustering to shrink the level of cluster to improve the performance of FPGA.There will be a simple introduction about the clustering algorithm of FPGA at the beginning of thesis, and focus on the T-VPack. T-VPack is the clustering algorithm which is designed for improving timing score. But its feature is not to update the timing score simultaneously which make it not find the critical path correctly and get the error result when it's clustering. This thesis is based on this point and develops a new clustering algorithm which can update the timing score simultaneously. There will show three new clustering algorithms in this thesis and the third one is the most powerful.This new method will shrink the cluster length by copying the logic. Compared with the T-VPack it can find the critical path correctly and update the timing score simultaneously. At the same time, it can compress the input of logic inputs and increase the new blocks as few as possible. Finally the copying-logic algorithm is tested for a large amount of designs. It can shrink the critical path by 14% and control the increasing block under 5% at most case. It has reached the design goals.