On-site programmable device FPGA logic unit model and general bin packing algorithm thereof

Abstract

The invention relates to an on-site programmable device FPGA logic unit model and a general bin packing algorithm thereof. The module is analyzed and modeled according to realizable subscriber circuit logic function type in logic unit, and can be divided into three stages according to mutual driving case, the first stage is a searching table, the second stage is a special device, and the third stage is a sequential device, and the model can widely describe present commercial FPGA chip logic unit structure. Based on the module, the invention provides a general logic unit bin packing algorithm from bottom to top, which respectively establish user-defined logic devices for a device using the special device as core, a device using the sequential device as core and a device using the searching table as core in subscriber circuit, and carries out bin packing for the self- established devices by employing gain function calculation. The algorithm is a universal algorithm for treating bin packing problem of various logic units, has wide representation, versatility, practicality and excellent time spending performance, and is suitable for large-scale subscriber circuit.

Description

technical field [0001] The invention belongs to the electronic design automation (Electronic Design Automation, EDA) technical field of Field Programmable Gate Array (FPGA), be specifically related to a kind of model of FPGA logic unit and a kind of logic unit of Field Programmable Gate Array based on lookup table Generic bin packing algorithm. technical background [0002] Literature [1] points out that a logic block (Configurable Logic Block) is a component used to implement user circuit logic in a field programmable gate array (Field Programmable Logic Array, FPGA). Block (Configurable I / O Block) is the three important components of FPGA, such as figure 1 shown. [0003] With the development of the FPGA structure, the logic block gradually develops into a hierarchical logic block and becomes the mainstream. Hierarchical logic block (also known as cluster structure logic block, which contains multiple logic units) puts the line network that originally needs to use inter...

AI Technical Summary

Problems solved by technology

[0004] A logic cluster is the simplest structural model of a hierarchical logic block. Its internal logic unit BLE and internal interconnection switch matrix adopt the most simplified method. Its shortcomings are: first, the logic unit BLE structure It is the simplest structure that can realize combinational or sequential logic, does not contain any special devices, and the described function is too simple, which is not applicable in the actual application field of commercial FPGA; second, the internal interconnection switch matrix is ​​fully connected, Causes a waste of chip area

Third, the connection between the internal logic unit BLE and the connection relationship with the logic cluster is too simple, which is not applicable to the actual application field of commercial FPGA

Although [9] also proposed a functional model of FPGA logic units and a general logic unit packing algorithm, this algorithm has a lot of time overhead in the function matching process, so it is not suitable for large-scale user circuit netlists

At present, there is no model and related algorithms of logical units that are both universal and practical

Images