Mapping Algorithm For Hierarchical FPGA

With the continuous upgrading in function, density, velocity and cost reduction , the application of FPGA(field programmabe logic gate array) was more and more widely. In the meantime, its structure has become increasingly complex and volatile, which requires the EDA (Electronic Design Automation) system function need to expand, performance need to be upgraded. It is imperative to in-depth study the use of algorithms in EDA tools.The thesis of this work is in the FPGA EDA systems responsible for mapping the logical design of the module.According to the logic block structure of Xinlinx Virtex device,a hierarchical structure model of FPGA logic block which name is XVCLB was established in this paper.The circuit structure of input and output, local interconnect switch matrix and logic unit were described respectively as quantifiable parameters, mathematical matrix and digraphIn this paper, a new LUT (Look-Up-Table) mapping algorithm -xvcmap was obtained based on Flowmap and cutmap, its mapping speed was improved and the share of resources was reduced.Based on the concept to use logical unit function circuit to describe the idea of logic function, the logical unit mapping algorith, Xvmap, was obtained,which used in XVCLB model.After abstract circuit into digraph mathematical model, the realization of circuits match was used in subgraph isomorphism algorithm.In addition, the switch matrix model in Cluster structure model was improved in this paper, and the logical unit packing algorithm Xvpack was achived which was applied to XVCLB model. In considering various types of constraints, the core of algorithm is to packed logical unit to the level of logic block which adopted greedy algorithm.The experiments indicate that this paper presents the structure model and the algorithm is more applicable to a commercial FPGA.