Fpga Software Packing Algorithm Research

Compared with ASIC, the programmability of FPGAs makes circuit designed in a shorter developing period, at lower cost and has the advantage of reconfigurable functions. With the advancement of semiconductor technology and market driven power, modern FPGAs' programmable architecture is becoming more and more complex with increasing reconfigurable ability which makes FPGA users more reliable on computer aided design. Therefore, it is significant to enhance FPGA CAD tools. The thesis focuses on packing algorithm which strongly relates to the physical implementation of FPGA chips, researching on the typical packing algorithm, summarizing the pros and cons of each algorithm and proposing effective improved algorithm targeting current challenges in the arena of modern packing algorithm.Modern FPGA's architecture is updating quickly and varies diversely. The question lies in how to develop packing algorithm adapting to the variety and complexity of programmable structure as well as the optimization of user design based on the favorable features of the structure itself. The thesis presents the novel packing algorithm called CSPack based on CSP graph matching. It first identifies sub-circuits satisfying constraints using graph matching and maps the sub-circuits by instructions with the idea of routability and timing driven. The experiment result shows that CSPack is able to pack targeting complex FPGA architectures with flexibility and could optimize with designated rules. CSPack achieves 7.8% increase in timing performance and the number of configurable logic blocks has deceased by 5.7%.With the enrichment of FPGA logic capacity and interconnect resources, high performance circuit designers has increasing requirement of routability and timing. Traditional packing algorithm attempts to reach 100% logic utilization. However, for some applications this may cause unroutability due to local congestion. Hence, the problem lies in how to develop packing aiming at routability and timing performance enhan cement. The thesis suggests RePack which tries to balance logic and interconnect requirement, using CLB depopulation method in the highly interconnected regions and spreading the congested BLE in the uncongested areas. Through iteratively CAD flow which gradually reduces the channel width and improved seed & candidate BLE selection process, RePack could realize 8.3% increase in timing performance,37% deduction in channel width and logic utilization improvement at 36%.Application oriented multi-core structure study is the hot researching area. Therefore, it has a positive effect in developing corresponding compute aided design tools. The thesis applies the existing core idea of CSPack and RePack in the multi-core software assisting design and proposes the whole design CAD flow which generates control data flow graph based on high-level synthesis tool GAUT. Then it identifies the data path and control logic through the algorithm of graph pattern matching. The experiment result shows that the raised CAD flows could implement typical DSP application like FFT and assist hardware designers to evaluate the proposed multi-core architecture.