CN101888240A - A General Interconnect Box Structure and Modeling Method for Field Programmable Logic Array - Google Patents

Abstract

The invention belongs to the technical field of programmable device structures, and in particular relates to a general interconnection box (GRB) structure of a field programmable logic array (FPGA). The GRB structure of the present invention not only provides connections between horizontal interconnect resources and vertical interconnect resources, but also provides connections between CLB/IOB and interconnect resources and direct connections between CLB/IOB pins. Compared with the CB/SB wiring structure and the CS-box structure described by the VPR tool commonly used in the prior art, the general switch box can better improve the FPGA performance. The experimental results show that compared with the CB/SB structure FPGA, the FPGA with the GRB structure can get 17.5% performance optimization in the case of an increase of 10.9% switch usage.

Description

A General Interconnect Box Structure and Modeling Method for Field Programmable Logic Array

technical field

The invention belongs to the technical field of programmable device structures, and in particular relates to a general interconnection box (GRB) structure of a field programmable logic array (FPGA).

Background technique

With the rapid development of semiconductor process technology, the cost of transmission tubes has become "minimal", and the one-time engineering expenses (non-recurring engineering, NRE) are becoming more and more expensive for ASIC (Application Specific Integrated Circuits) products. Compared with traditional ASIC products, FPGA (Field Programmable Gate Array) has the following characteristics: flexibility, low NRE and verification costs, short development cycle and long life cycle. Even for customer end products, FPGAs have become an important implementation medium.

FPGA is composed of programmable input and output (Input and Output, IO), programmable logic block (ConfigurableLogic Block, CLB) and programmable interconnection (Routing Interconnect). Programmable logic blocks are generally connected to programmable interconnects through connection blocks (Connection Block, CB). Traditional programmable interconnection resources are generally composed of horizontal interconnection resources and vertical interconnection resources, which are connected to each other through a switch box (SwitchBlock, SB). With the increasing scale of FPGA, the speed and performance requirements of FPGA are getting higher and higher, and the traditional interconnection resources have become the bottleneck of speed improvement. This is because the traditional interconnection structure divides interconnection resources into horizontal interconnection resources and vertical interconnection resources, and the two logic units that need to be interconnected in applications are often not on the same horizontal or vertical line, so regardless of the two logic How close the unit is, at least one programmable switch is required to connect the two logic units, which has a great impact on the speed of the FPGA.

In order to solve the above problems, the American XLINX company proposed the concept of direct interconnection (directconnection). The main idea is to add an interconnection resource called direct interconnection, which can directly connect 8 logic units next to a logic unit without Through the programmable switch, this can speed up the connection speed of some close distances.

The prior art (document [2]) discloses a connection-switch box (CSB) structure. However, it uses the same connection mode for internal logic pins and IO pins, and it cannot be determined whether this mode is optimal.

References relevant to the present invention are:

[1] Xilinx corporation, "Virtex-II Pro and Virtex-II Pro X Platform FPGAs: CompleteData Sheet", 2005

[2] Zhou, C.L., Cheung, R., and Wu, Y.-L. What if Merging Connection and SwitchBoxes--an Experimental Revisit on FPGA Architectures, IEEE International Conference on Communications, Circuits and Systems, 2004, 1295-1299

[3] Betz, V., Rose J., and Marquardt, A. Architecture and CAD for Deep-SubmicronFPGAs. Boston, Kluwer Academic Publishers, 1999, 51-103. Chinese version: Wang Lingli, Yang Meng, Zhou Xuegong, "Deep Submicron FPGA Structure and CAD Design", Electronics Industry Press, November 2008

[4] Y.M.Chang, D.F.Wong, and C.K.Wong, Universal Switch Modules for FPGADesign. ACM Trans.On Design Automation of Electronic Systems, 1996, 80-101

[5] M.Shyu, G.M.Wu, Y.D.Chang et al, Generic Universal Switch Blocks, IEEE Trans. On Computers, 2000, 348-359

[6] H.Fan, J.Liu, Y.L.WU et al, General Models and a Reduction Design Technique for FPGA Switch Box Designs.IEEE Trans.On Computers, 2003, 21-30

Contents of the invention

The object of the present invention is to propose a general interconnection box (GRB) structure of a Field Programmable Logic Array (FPGA) which improves circuit performance.

The GRB structure of the present invention provides connections between horizontal interconnect resources and vertical interconnect resources, connections between CLB/IOB and interconnect resources, and direct connections between CLB/IOB pins.

The present invention proposes a generic interconnection box structure as shown below:

_{Fc_input} = (0.25, 0.25, 0.25, 0.25);

F _{c_output} = (0.25, 0.25, 0.25, 0.25);

F _{c_pad} = (0.5, 0, 0, 0);

F _{c_output_with_lb_input} = 0.5;

F _{c_output_with_pad_input} = 0.

In conjunction with accompanying drawing, the present invention is described in detail:

"Classic symmetric" FPGA interconnect resources include Switching Box (Switching Box, SB), Connection Box (Connecting Box, CB) and interconnection segments. As shown in Figure 1(a), CB connects the pins of programmable logic unit (LogicBlock, LB) or input/output unit (Input\Output Block, IOB, for the sake of brevity, IOB is not shown in the figure) to the interconnection segment, SB Then connect the different interconnecting line segments. The present invention introduces a "fast line" structure, so that the pins of different LB\IOBs are directly connected through a general routing block (GRB). As shown in Figure 1(b), GRB is an array of a series of programming switches, through which the metal line segments at different positions or the pins of LB\IOB can be connected.

The wiring structure of GRB is defined as a directed graph G=(V, E), where V represents a node set, and E represents a set of edges. Similar to the concept of the routing resource map [3] in VPR, all logic pins and routing tracks are members of V, and all routing switches form a set E. Assuming that LB contains n logical pins and W routing tracks, then each logical pin is represented as a node Vpi, Vtj, k represents the kth track in the jth direction of GRB, where 1≤i≤n, 1≤j ≤4, 1≤k≤W. Assume that the GRB has 4 sides, only one wiring track type, and all wiring switches are transfer tubes. In the present invention, for simplicity and correctness, (b) does not display the direction of the side. The numbering of the GRB takes a routing node as the reference object, and the routing node where the node is located is marked as direction 1. In contrast, the right and left are directions 2, 3, and 4, respectively. When considering nodes "A" and "B" in (b), their numbers are shown in the figure.

(a) shows the result of using the GRB method for the CB\SB structure in the VPR, and the logic pins can only be connected to the tracks on the same side. Since the connections between nets are already well defined, such as Disioint, Universal[4][5], HUSB[6] and Wilton structures, they are not shown in the figure. In the CSB structure proposed in [2], such as (b), logic pins can be connected in other directions except that they cannot be connected to the track on the same side. In (c), assuming that Vp2 is an output pin, it can be directly connected to Vp1, Vp3 and Vp4. At the same time, there is no restriction as in (b) that the tracks in the same direction cannot be connected. It can be seen that the structure of CB\SB in VPR and the structure of CS-box in literature [2] are two special cases of the GRB structure.

The GRB structure can be determined by the following parameters:

(1).F _{c_input} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an input pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4.

(2).F _{c_output} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an output pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4.

(3).F _{c_pad} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an IO pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4.

(4).F _{c_output_with_lb_input} , this parameter describes the flexibility of the "fast line" connection, which means that the output pin of a logic block can drive the ratio of the input pins of all its adjacent modules. For example,

F _{c_output_with_lb_input} = 1" indicates that any output pin of a logic block can drive all input pins of its adjacent logic block.

(5). F _{c_output_with_pad_input} , similar to F _{c_output_with_lb_input} , this parameter indicates the proportion of a logic block output pin that can drive all adjacent IO pins.

For example, suppose V _p2 is a logic output pin and V _p1 , V _p3 and V _p4 are input pins. (a), because all logic pins can only be connected to the track on the same side, both F _{c_input} and F _{c_output} are (1, 0, 0, 0). And because there is no "fast line", F _{c_output_with_lb_input} is 0. In (b), both _{Fc_input} and _{Fc_output} are (0, 0.25, 0.25, 0.25), and _{Fc_output_with_lb_input} is 0. Similarly, in (c), _{Fc_input} is (0, 0.25, 0.25, 0.25) and _{Fc_output} is (0.25, 0.25, 0.25, 0.25). And since the output pin V _p2 can be connected to the input pins V _p3 , V _p1 and V _p4 of all adjacent modules, the value of F _{c_output_with_lb_input} is 1.

In order to obtain an effective GRB structure, the above parameters are determined by the following steps:

(1). Run VPR, compare the difference in circuit performance under different parameters and compare it with the circuit performance under the CB/SB structure in VPR, and determine F _{c_input} and F _{c_output} .

(2). On the basis of (1), determine the proportion of "fast line", that is, the value of F _{c_output_with_lb_input} .

(3). Based on the above results, set the optimal number of IO pins, that is, the values of F _{c_pad} and F _{c_output_with_pad_input} .

The GRB structure of the present invention not only provides connections between horizontal interconnect resources and vertical interconnect resources, but also provides connections between CLB/IOB and interconnect resources and direct connections between CLB/IOB pins. Compared with the CB/SB wiring structure and the CS-box structure described by the VPR tool commonly used in the prior art, the general switch box can better improve the FPGA performance. The experimental results show that compared with the CB/SB structure FPGA, the FPGA with GRB structure can get 17.5% performance optimization in the case of 10.9% increase in switch usage.

For ease of understanding, the present invention will be described in detail below through specific drawings and embodiments. It should be pointed out that the specific examples and accompanying drawings are only for illustration. Obviously, those skilled in the art can make various amendments and changes within the scope of the present invention according to the description herein. These amendments and Modifications are also included within the scope of the present invention.

Description of drawings

Figure 1 (a) Basic interconnection structure of classic FPGA (b) GRB structure.

Figure 2 (a) CB\SB structure (b) CS-box structure (c) GRB structure.

Detailed ways

Example 1

Added the setting of the GRB structure in the VPR tool. In the experiment, all channels only contain double lines, the switch box adopts the Wilton structure, and the others adopt the default settings of VPR. The analysis of the results mainly examines the channel width occupied by the circuit, the delay of the critical path and the number of wiring switches used. "CW" represents the number of channels required to make the circuit open, "CP" represents the delay of the critical path, and "SN" represents the number of switches used to make the circuit open. Small "CW" and "CP" values indicate optimized circuit performance.

The steps to determine each parameter are as follows:

(1). Run VPR, compare the difference in circuit performance under different parameters and compare it with the circuit performance under the CB/SB structure in VPR, and select the optimal F _{c_input} and F _{c_output} . Experiments show that when the four elements are distributed evenly, that is, the values of F _{c_input} and F _{c_output} (0.25, 0.25, 0.25, 0.25) can achieve a better effect.

(2). On the basis of determining F _{c_input} and F _{c_output} , set the parameter F _{c_output_with_lb_input} in the same principle. Experiments show that when the value of F _{c_output_with_lb_input} is set to 0.5, compared with the circuit performance under the CB/SB structure, there is at least 7% improvement.

(3). Set F _{c_pad} and F _{c_output_with_pad_input} according to the requirement of performance optimization. Experiments show that the performance of "F _{c_pad} = (1, 0, 0, 0)" is only 0.2% higher than that of F _{c_pad} = (0.5, 0, 0, 0)". Similarly, F _{c_output_with_pad_input} from 0 In the process of increasing to 1, there is no significant change in performance impact.

Therefore, the present invention proposes a generic interconnection box structure as shown below:

_{Fc_input} = (0.25, 0.25, 0.25, 0.25);

F _{c_output} = (0.25, 0.25, 0.25, 0.25);

F _{c_pad} = (0.5, 0, 0, 0);

F _{c_output_with_lb_input} = 0.5;

F _{c_output_with_pad_input} = 0.

Claims (3)

1. a general interconnection box structure of a field programmable logic array, is characterized in that its structure is determined by the following parameters: (1).F _{c_input} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an input pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4; (2).F _{c_output} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an output pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4; (3).F _{c_pad} , a tuple with four elements, (f _c1 , f _c2 , f _c3 , f _c4 ), f _ci represents the proportion of an IO pin that can be connected to the line segment on the i-th side of the GRB, where 0≤ f _ci ≤ 1, 1 ≤ i ≤ 4; (4).F _{c_output_with_lb_input} , this parameter describes the flexibility of the "fast line" connection, which means that the output pin of a logic block can drive the ratio of the input pins of all its adjacent modules; (5). F _{c_output_with_pad_input} , similar to F _{c_output_with_lb_input} , this parameter indicates the proportion of a logic block output pin that can drive all adjacent IO pins. 2. A kind of field can become the general interconnection box structure of logic array, it is characterized in that its parameter is determined by the following steps: (1). Add the setting of GRB structure in the VPR tool and then run, compare the difference of circuit performance under different conditions of parameters and compare with the circuit performance under the CB/SB structure in VPR, determine _{Fc_input} , _{Fc_output} ; (2). On the basis of (1), determine the proportion of "fast line", that is, the value of _{Fc_output_with_lb_input} ; (3). Based on the above results, set the optimal number of IO pins, that is, the values of F _{c_pad} and F _{c_output_with_pad_input} . 3. the general interconnection box structure of field programmable logic array according to claim 1, it is characterized in that in described (4), F _{c_output_with_lb_input} =1 represents that any output pin of a logic block can drive its adjoining All input pins of the logic block.

Images