JP5701054B2 - Reconfigurable logic block, programmable logic circuit device using the same, and technology mapping method - Google Patents

Description

  The present invention relates to a reconfigurable logic block (hereinafter referred to as RLB [Reconfigurable Logic Block]), a programmable logic circuit device using the same, and a technology mapping method.

  In recent years, a programmable logic circuit device (PLD [Programmable]) capable of freely reconstructing an internal logic circuit integrated in a semiconductor device in the field by programming using a hardware description language (HDL [Hardware Description Language]). Logic Device], FPGA [Field Programmable Gate Array], DAP / DNA [Digital Application Processor / Distributed Network Architecture], DRP [Dynamically Reconfigurable Processor], etc.) have been put into practical use.

  In addition, as an example of the prior art relevant to the above, patent document 1-patent document 7, and nonpatent literature 1 can be mentioned.

US Pat. No. 4,706,216 US Pat. No. 4,870,302 US Pat. No. 6,998,872 US Patent Application Publication No. 2007/0222477 JP 2003-18000 A JP 2004-248293 A JP 2007-166579 A

(Vaughn Betz, Jonathan Rose, and Alexander Marquardt), `` Architecture and CAD for Deep-Submicron FPGAs (The Springer International Series in Engineering and Computer Science) '', published by Springer

  In a programmable logic circuit device such as an FPGA, a lookup table (hereinafter referred to as LUT [Look-Up Table]) is used as a basic element for realizing a desired logic circuit. The LUT holds the output values of the truth table in the configuration memory on a one-to-one basis, and a desired logic circuit can be realized by decoding them with a plurality of multiplexers. If a K-input LUT (hereinafter referred to as a K-LUT) is used, all logic circuits having K inputs or less can be implemented. However, in the conventional LUT, the delay performance increases as the number of inputs increases (the delay decreases), but the number of unused memories increases and the mounting area (LUT size) increases. In other words, the memory used by the LUT There is a problem that the number (LUT size) and the delay performance are in a trade-off relationship (see, for example, Patent Document 1 and Patent Document 2).

  Conventionally, an adaptive LUT as shown in FIG. 27 has been proposed as a device for reducing the number of memories used in the LUT (see, for example, Patent Document 3 and Patent Document 4). This is a technique for reducing the number of memories by dividing a LUT having a large number of inputs so that a plurality of LUTs having a small number of inputs can be used. Certainly, if the logic circuit is mounted using an adaptive LUT with a large number of inputs, the delay performance can be improved as compared with the case where a logic circuit is mounted using a large number of LUTs with a small number of inputs. However, the conventional adaptive LUT has a problem that the number of used memories (power consumption) of the LUT increases when an LUT having a large number of inputs is used without being divided.

  Conventionally, a cluster-based logical block configuration method as shown in FIG. 28 has been proposed (see, for example, Non-Patent Document 1). This is a technique for improving the performance without lowering the LUT memory usage rate by clustering a large number of LUTs with a small number of inputs. However, the conventional cluster-based logical block has a problem in that a large number of multiplexers and memories are required to connect the LUTs in the logical block, so that hardware resources necessary for wiring increase.

  FIG. 29 is a list summarizing the above-described features of the prior art. Conventional LUTs (for example, 4-LUT) have a small logical block size, so the number of constituent memories is small. However, the delay performance is low, and the number of logical blocks used when the same circuit is mounted is large. Become. On the other hand, conventional adaptive LUTs (for example, adaptive 6-LUT) and cluster-based logical blocks (for example, 4-LUT × 8) have high delay performance, and the logical block when the same circuit is mounted. Although the number of uses is small, the size of the logical block is large, so the number of constituent memories is large.

  In addition, as another conventional technique, in Patent Document 5, an M-input N-output look-up table includes a plurality of LUT units and an internal configuration control unit that controls an internal configuration of the plurality of LUT units. A lookup table is disclosed. According to this prior art, for example, in the case of 6 inputs and 3 outputs, the area efficiency is improved by switching the mode such as 3 2-LUTs, 2 3 LUTs, or 6 6-LUTs. It is possible to make it. However, in this prior art, a 64-bit memory is required to implement a 6-input logic circuit. Therefore, when a large number of 6-input logic circuits appear in technology mapping, the number of memories used is large. It was. In addition, since there are more output lines than the conventional LUT, there is a concern that the wiring area increases.

  Further, Patent Document 6 is composed of six 2-LUTs, and an incomplete look that can implement a complete 4-LUT and a commonly used 6-input logic function at a relatively high rate. An uptable has been proposed. According to this prior art, the configurable logic circuit can execute only a subset of all six input logic functions, so that the silicon area occupied by the configurable logic circuit in the FPGA can be greatly reduced. However, in this prior art, since there are two output lines from the logic cell, the wiring area increases when used as a 6-input subset. In addition, there is room for further reduction in the number of configuration memories in the cell.

  Further, in Patent Document 7, a reconfigurable logic block including a first circuit that constitutes an arithmetic circuit and a second circuit that constitutes a circuit outside the arithmetic circuit, the first and second A reconfigurable logic block has been proposed in which different circuits are configured by changing the setting of a predetermined signal in a circuit. According to this prior art, arithmetic operations and logic operations can be efficiently implemented, and in logic operations, some logic circuits can be implemented with a small number of BLE [Basic Logic Elements]. However, in this prior art, some of the logic circuits that can be mounted do not consider the appearance probability, and there is room for further improvement in the efficient logic circuit mounting.

  In view of the above-mentioned problems found by the inventors of the present application, the present invention provides a reconfigurable logic block capable of realizing a reduction in device area and power consumption, and a programmable using the same. An object is to provide a logic circuit device and a technology mapping method.

  In order to achieve the above object, a reconfigurable logic block according to the present invention is a reconfigurable logic block having a maximum of K inputs (x [0] to x [K-1]), and has m inputs (y [ 0] to y [m−1], where m is smaller than K and y belongs to x, and n inputs (z [0] to z [n−1], where n is K A second look-up table smaller than z belonging to x) and a combinational circuit of p inputs (c [0] to c [p−1], where p is smaller than K and c belongs to x), A configuration (first configuration) is provided that includes a selector that selects one of the first lookup table and the second lookup table in accordance with the output of the combinational circuit.

  The reconfigurable logic block having the above first configuration compares a truth table representing each of a plurality of logic circuits, and implements a portion in which the same pattern is continuous using the second lookup table. The remaining portion may be configured to be implemented with the first lookup table (second configuration).

  In the reconfigurable logic block having the second configuration, the plurality of logic circuits include a logic circuit mapped with a K-input look-up table having a high appearance probability (third Configuration).

  In addition, the programmable logic circuit device according to the present invention has a configuration (fourth configuration) having a reconfigurable logic block having the third configuration.

  The technology mapping method according to the present invention is intended for the programmable logic circuit device having the fourth configuration described above, and sets the maximum input number K of the reconfigurable logic block as the input number j. A first step that advances the flow to the second step; a second step that searches for a node that is not covered and advances the flow to the third step; determines whether there is a cut of j inputs; If the flow advances to the fourth step, and if there is no cut, the third step advances the flow to the tenth step; the fourth step advances the flow to the fifth step by cutting into a j-input partial circuit; j is greater than m If it is greater, the flow proceeds to the sixth step; otherwise, the flow proceeds to the eighth step; Calculating a P representative element of the partial circuit and proceeding the flow to the seventh step; determining whether or not the partial circuit can be implemented by the reconfigurable logic block based on the P representative element; If implementation is possible, the flow proceeds to the eighth step, and if implementation is impossible, the seventh step proceeds to the third step; covering the node with the reconfigurable logic block, and the flow to the ninth step An eighth step to proceed; a determination as to whether or not all nodes have been covered; a ninth flow to end the series of flows if they have been covered; and a flow to the second step if not already covered; A tenth step of decrementing the input number j by one and advancing the flow to the second step (fifth configuration); It has been.

  According to the present invention, it is possible to provide a reconfigurable logic block capable of realizing a reduction in area and power consumption of a device, a programmable logic circuit device using the same, and a technology mapping method. It becomes possible.

The block diagram which shows the example of whole structure of the programmable logic circuit apparatus which concerns on this invention Diagram showing an implementation example of a 3-input logic circuit The figure which shows the notional structure of the reconfigurable logic block which concerns on this invention Truth table showing an example of memory usage The figure which shows the 1st structural example of a reconfigurable logic block The figure which shows the relationship between the input conditions and memory in a 1st structural example. The figure which shows the memory pattern (P equivalence class) of the circuit mapped by 6-LUT Flow chart showing a 6-input technology mapping method The flowchart which shows the general view of the technology mapping method which concerns on this invention The figure which shows the 2nd structural example of a reconfigurable logic block The figure which shows the 3rd structural example of a reconfigurable logic block. The figure which shows the 4th structural example of a reconfigurable logic block. The figure which shows the 5th structural example of a reconfigurable logic block. The figure which shows the 6th structural example of a reconfigurable logic block. The figure which shows the 7th structural example of a reconfigurable logic block. The figure which shows the 8th structural example of a reconfigurable logic block. The figure which shows the 9th structural example of a reconfigurable logic block. The figure which shows the 10th structural example of a reconfigurable logic block. The figure which shows the 11th structural example of a reconfigurable logic block. The figure which shows the 12th structural example of a reconfigurable logic block The figure which shows the 13th structural example of a reconfigurable logic block The figure which shows the 14th structural example of a reconfigurable logic block The figure which shows the 15th structural example of a reconfigurable logic block. The figure which shows the 16th structural example of a reconfigurable logic block The figure which shows the formation method of LUT and the aggregation state of a memory in each structural example The figure which shows the coverage of the logic circuit in each configuration example Block diagram showing a conventional example of an adaptive LUT Block diagram showing a conventional example of a cluster-based logical block List of features of conventional technologies

<Programmable logic circuit device>
FIG. 1 is a block diagram showing an example of the overall configuration of a programmable logic circuit device according to the present invention. The programmable logic circuit device 100 of this configuration example includes an I / O block 101, a reconfigurable logic block 102 (hereinafter abbreviated as RLB [Reconfigurable Logic Block] 102), a connection block 103 (hereinafter referred to as CB [Connection Block]). ], A switch block 104 (hereinafter abbreviated as SW [Switch Block] 104), and a wiring 105.

  The I / O block 101 exchanges signals with the outside. A plurality of RLBs 102 are arranged in a matrix and are used as arithmetic elements for realizing a logic circuit. The CB 103 couples the RLB 102 and the wiring 105. The SB 104 is a cross point of the wiring 105.

  In order to improve the performance of the programmable logic circuit device 100, a new RLB 102 is required, and the present invention mainly relates to a new configuration of the RLB 102.

<Background to the Present Invention>
When a logic circuit is represented by a conventional LUT, there are many cases in which the same logic function is realized with different LUT memory patterns (configuration information). In addition, there are many repeated portions of the same data in the LUT memory pattern. That is, the conventional LUT-based circuit representation is a truth table directly expressed as configuration data, and there are a plurality of implementations even in the same logic circuit. Therefore, if the logic circuits obtained by switching the input signals are regarded as the same, it can be said that the circuit representation by the LUT is essentially redundant. Hereinafter, the redundancy of the LUT will be described by exemplifying a 3-input logic circuit.

  FIG. 2 is a diagram illustrating an implementation example of a three-input logic circuit. As shown in FIG. 2, the truth table of the function f and the function g is different in some patterns, but if the input b and the input c are interchanged, the function f and the function g can be regarded as the same. At this time, the logic circuit for realizing the function f and the logic circuit for realizing the function g belong to the same P [Permutation] equivalence class. That is, if the function f is obtained by changing the input order of the function g, it can be said that the function f and the function g belong to the same P equivalence class.

  The inventors of the present application realize a logic cell capable of mounting a logic circuit equivalent to the conventional one even with a smaller number of configuration memories than the conventional LUT by removing the redundancy of the circuit expression by the LUT from the above consideration. The present invention has been obtained with the idea of being able to.

<Reconfigurable logic block>
FIG. 3 is a diagram showing a conceptual configuration of a reconfigurable logic block according to the present invention. The reconfigurable logic block (K-A ² LUT) with the maximum K inputs (x [0] to x [K-1]) according to the present invention includes m inputs (y [0] to y [m-1], Where m is smaller than K and y belongs to x) and n inputs (z [0] to z [n-1], where n is smaller than K and z becomes x Of the second lookup table 2 of p. (P [1] to c [p−1], where p is smaller than K and c belongs to x), And a selector 4 for selecting one of the first lookup table 1 and the second lookup table 2 in accordance with the output.

In addition, the reconfigurable logic block (KA ² LUT) according to the present invention is a portion in which the same pattern is continuous when comparing truth tables each representing a plurality of logic circuits necessary for mounting an application. (For example, refer to the portion surrounded by a broken line in FIG. 4) is implemented by the second look-up table 2, and for the remaining portion (for example, refer to the portion surrounded by a solid line in FIG. 4), the first look It is implemented by the uptable 1.

Further, in the reconfigurable logic block (KA ² LUT) according to the present invention, the plurality of logic circuits include a logic circuit mapped with the K-LUT having a high appearance probability. . In the above mapping, it is desirable to replace the input variables so that many identical patterns appear (so that the same output values are arranged as much as possible).

By adopting the above configuration, it is possible to realize a logic circuit necessary for mounting an application with a smaller number of configuration memories than a conventional K-LUT. More specifically, when implementing the logic of K input, whereas it is necessary to conventional K-LUT in 2 ^K number of memory number, reconfigurable logic block according to the present invention (K- If (A ² LUT), the number of (2 ^m +2 ⁿ ) memories is sufficient.

As described above, the reconfigurable logic block (KA ² LUT) according to the present invention can maintain the same function as that of the conventional K-LUT with a smaller number of memories. It is possible to reduce the area of the device and reduce power consumption. Further, in the case of the reconfigurable logic block (KA ² LUT) according to the present invention, since the number of input / output lines is not different from that of the conventional K-LUT, it is possible to prevent an increase in wiring area.

The reconfigurable logic block (KA ² LUT) according to the present invention collects a plurality of output values in a small memory, and can deal with logic circuits having various numbers of inputs (maximum K inputs). In this specification, it is named KA ² LUT [Abridged Adaptive LUT].

<Points of the present invention>
The points of the reconfigurable logic block (KA ² LUT) according to the present invention will be described together. First, the first point is that a part of a logic circuit (maximum K inputs) whose number of inputs is larger than m can be mounted, and all of the logic circuits whose number of inputs is m or less can be mounted. This is a possible structure. The second point is that, among the logic circuits whose number of inputs is larger than m, some of the logic circuits that can be implemented preferentially include those that have a high appearance probability, in other words, can be implemented. The number of configuration memories is reduced by efficiently limiting the number of some logic circuits. The third point is that logic circuits that can be replaced with each other by replacing inputs are regarded as the same (P equivalence class).

<First configuration example>
FIG. 5 is a diagram showing a first configuration example of the reconfigurable logic block according to the present invention, and shows a circuit configuration when the maximum number of inputs K = 6.

The reconfigurable logic block (6-A ² LUT) of the first configuration example includes a first block A (3-LUT (A) using memories [0] to [7]) and a second block B (memory 3-LUT (B) using [10] to [17]), 2-bit memories [8] and [9], selectors SEL0 to SEL2, and a combinational circuit CMB.

  The first block A outputs any one of data stored in the memories [0] to [7] according to the input signals in1 to in3. The second block B outputs any one of the data stored in the memories [10] to [17] according to the input signals in1 to in3. The selector SEL0 selects one of the output data of the selector SEL1 and the output data of the selector SEL2 as the output signal out according to the input signal in0. The selector SEL1 selects one of the output data of the first block A and the storage data of the memory [8] according to the output of the combinational circuit CMB. The selector SEL2 selects one of the output data of the second block B and the stored data of the memory [9] according to the output of the combinational circuit CMB.

  The combinational circuit CMB generates switching signals for the selectors SEL1 and SEL2 according to the input signals in3 to in5. In the first configuration example, the combinational circuit CMB includes a NOR gate G1 that performs a NOR operation of the input signals in3 to in5, an AND gate G2 that performs an AND operation of the input signals in3 to in5, and an output of the NOR gate G1. An OR gate G3 that performs an OR operation with the output of the AND gate G2.

  The first block A, the second block B, and the selector SEL0 form a four-input (in0 to in3) lookup table, which is the first lookup table 1 (m = 4) in FIG. It corresponds to. The 2-bit memories [8] and [9] and the selector SEL0 form a one-input (in0) lookup table, which corresponds to the second lookup table 2 (n = 1) in FIG. To do. The combinational circuit CMB corresponds to the combinational circuit 3 in FIG. The selectors SEL1 and SEL2 correspond to the selector 4 in FIG.

The conventional 6-LUT requires 2 ⁶ = 64 bits of memory, whereas the reconfigurable logic block (6-A ² LUT) of the first configuration example has 2 ⁴ +2 ¹ = 18 bits. Consists of memory.

  FIG. 6 is a diagram showing the relationship between the input condition and the memory in the first configuration example, and FIG. 7 shows the first memory pattern (P equivalence class) mapped in 6-LUT in descending order of appearance probability. It is the figure shown to the 7th place. The memory pattern in FIG. 7 represents 6-LUT output data O0 to O63 as 64-bit binary values.

  As can be seen from FIG. 7, in all the first to seventh memory patterns, the 5th to 28th bits (O4 to O27) and the 37th to 60th bits (O36 to O59). Are all 0 or 1 sequences. Therefore, in the first configuration example, among the above-described portions where the same value is continuous, the former is concentrated in the 1-bit memory [8], and the latter is concentrated in the 1-bit memory [9]. Among the remaining portions, the first bit to the fourth bit (O0 to O3) and the 29th bit to the 32nd bit (O28 to O31) are realized in the first block A, and the 33rd bit. Bit 2 to bit 36 (O32 to O35) and bit 61 to bit 64 (O60 to O63) are realized in the second block B.

  Specifically, in the first configuration example, {in0, in1, in2, in3, in4, in5} = {0,-,-, 0, 0, 0} and {0,-,-, 1, 1 , 1} (where “−” is 0 or 1), the output data O0 to O3 and O28 to O31 are held in the memories [0] to [7] of the first block A, and {in0, in1, in2, in3, in4, in5} = {1, −, −, 0,0,0} and output data O32 to O35 and O60 to O63 corresponding to {1, −, −, 1,1,1} It is held in memories [10] to [17] of two blocks B. Further, output data O4 to O27 and O36 to O59 other than the above are collected in the memories [8] and [9].

  Then, as shown in FIG. 6, {in0, in1, in2, in3, in4, in5} = {0,-,-, 0, 0, 0} and {0,-,-, 1, 1, 1} In this case, the output data of the first block A is used as the output signal out, {in0, in1, in2, in3, in4, in5} = {1,-,-, 0, 0, 0} and {1,-, When-, 1, 1, 1}, the output data of the second block B is used as the output signal out. When the combination of input signals is other than the above, the data stored in the memory [8] or [9] is used as the output signal out.

If the netlist is implemented with a 6-A ² LUT (18 bits), the number of memories per cell can be reduced by 46 bits compared to the conventional 6-LUT (64 bits) implementation. . Further, the 6-A ² LUT of the first configuration example can realize about 52% of the memory pattern used in the 6-LUT and about 47% of the memory pattern used in the 5-LUT. Therefore, it is possible to mount a logic circuit with a smaller number of memories than in the past. In addition, it is possible to mount a logic circuit with a smaller number of cells than in the case of mounting with a conventional 4-LUT.

<Technology mapping method>
FIG. 8 is a flowchart showing a 6-input technology mapping method.

  In step S101, a search is made for a node that is not covered in the input netlist, and the flow proceeds to step S102.

  In step S102, it is determined whether there is a 6-input cut. Here, if a yes determination is made, the flow proceeds to step S102, and if a no determination is made, the flow proceeds to step S108.

  In step S103, the 6-input cut is cut out as a partial circuit, and the flow proceeds to step S104.

  In step S104, the P representative element of the partial circuit cut in step S103 is calculated, and the flow proceeds to step S105. Note that the P representative element is the smallest when the function in the P equivalence class is regarded as a binary value.

In step S105, based on the P representative element calculated in step S104, it is determined whether or not the partial circuit cut in step S103 can be mounted with the 6-A ² LUT. If the determination is yes, the flow proceeds to step S106. If the determination is no, the flow returns to step S102 to search for another cut.

In step S106, the node is covered by the 6-A ² LUT, and the flow proceeds to step S107.

  In step S107, it is determined whether or not all nodes have been covered. Here, when a yes determination is made, the above-described series of flows is terminated, and when a no determination is made, the flow returns to step S101.

In step S108, even if all the 6-input partial circuits that can be implemented by the 6-A ² LUT are covered, all the nodes are not yet covered. Mapping is done. For 5-input technology mapping, it is sufficient to replace the number of inputs described above from “6” to “5”.

After that, even if all the 5-input partial circuits that can be implemented with the 6-A ² LUT are covered, but not all the nodes are still covered, all the remaining nodes are cut into partial circuits with 4 inputs or less. Then, the node is covered. Since the 6-A ² LUT can mount all the logic circuits having four inputs or less, the step S104 for calculating the P representative element and the step for verifying the mounting possibility by the 6-A ² LUT S105 is no longer necessary.

FIG. 9 is a flowchart showing an overview of the technology mapping method according to the present invention, which is a more generalized version of the flowchart described in FIG. This flowchart is based on the premise that all logic circuits with m inputs or less can be implemented in the KA ² LUT, and that a gate-level Boolean network decomposed to K inputs or less is input. And

In step S201, the maximum input number K of the KA ² LUT is set as the input number j, and the flow proceeds to step S202.

  In step S202, a search is made for a node that is not covered with respect to the input netlist, and the flow proceeds to step S203.

  In step S203, it is determined whether or not there is a j-input cut. Here, if a yes determination is made, the flow proceeds to step S204, and if a no determination is made, the flow proceeds to step S210.

  In step S204, the cut of j input is cut out as a partial circuit, and the flow proceeds to step S205.

  In step S205, it is determined whether j is larger than m. Here, if a yes determination is made, the flow proceeds to step S206, and if a no determination is made, the flow proceeds to step S208.

  In step S206, the P representative element of the partial circuit cut in step S204 is calculated, and the flow proceeds to step S207.

In step S207, based on the P representative element calculated in step S206, it is determined whether or not the partial circuit cut in step S204 can be mounted with the 6-A ² LUT. If the determination is yes, the flow proceeds to step S208. If the determination is no, the flow returns to step S203 to search for another cut.

In step S208, the 6-A ² LUT covers the node, and the flow proceeds to step S209.

  In step S209, it is determined whether or not all nodes have been covered. Here, when a yes determination is made, the above-described series of flows is terminated, and when a no determination is made, the flow returns to step S202.

In step S108, even if all the j-input partial circuits that can be implemented by the 6-A ² LUT are covered, not all the nodes have been covered yet, so the input number j is decremented by one, and the flow proceeds to step S108. It returns to S202.

As described above, node covering is repeated while decrementing the number of inputs j one by one, and even if all of the (m + 1) input subcircuits that can be implemented with the 6-A ² LUT are covered, all the nodes are still covered. If not, the remaining nodes are all cut into partial circuits of m inputs or less, and the nodes are covered. Since the 6-A ² LUT can mount all the logic circuits of m inputs or less, the step S206 for calculating the P representative element and the step for verifying the mounting possibility by the 6-A ² LUT S207 is no longer necessary. Therefore, if j = m and no determination is made in step S205, the flow jumps to step S208.

As shown in FIG. 3, the reconfigurable logic block (KA ² LUT) according to the present invention includes a first lookup table 1 having m inputs and a second lookup table 2 having n inputs. When m> n, all logic circuits with m inputs or less can be mounted. Therefore, if the reconfigurable logic block (KA ² LUT) according to the present invention is used, it is possible to technology map a given Boolean network with a smaller number of memories than the K-LUT.

<Second Configuration Example to Sixteenth Configuration Example>
For a P representative with a high probability of appearance, the input is different from that in the first configuration example (see FIG. 5) and converted to P equivalence classes. In the following second configuration example to sixteenth configuration example in which the two-bit memories [8] and [9] are aggregated and the remaining part is realized by the first block A and the second block B, the combinational circuit CMB has the first combination circuit CMB. The circuit structure is different from the configuration example.

  FIG. 10 is a diagram illustrating a second configuration example of the reconfigurable logic block. In the second configuration example, O4 to O15 and O20 to O31 are aggregated in the memory [8], and O36 to O47 and O52 to O63 are aggregated in the memory [9]. Further, O0 to O3 and O16 to O19 are realized by the first block A, and O32 to O35 and O48 to O51 are realized by the second block B. In the second configuration example, the combinational circuit CMB has only a NOR gate G4 that performs a NOR operation on the input signals in4 and in5.

  FIG. 11 is a diagram illustrating a third configuration example of the reconfigurable logic block. In the third configuration example, O4 to O23 and O28 to O31 are aggregated in the memory [8], and O36 to O55 and O60 to O63 are aggregated in the memory [9]. Further, O0 to O3 and O24 to O27 are realized by the first block A, and O32 to O35 and O56 to O59 are realized by the second block B. In the third configuration example, the combinational circuit CMB includes a NOR gate G5 that performs a negative OR operation of the input signals in3 to in5 (however, the input signals in3 and in4 are inverted inputs), and the negative of the input signals in3 to in5. There is a NOR gate G6 that performs a logical sum operation, and an OR gate G7 that performs a logical sum operation on the output of the NOR gate G5 and the output of the NOR gate G6.

  FIG. 12 is a diagram illustrating a fourth configuration example of the reconfigurable logic block. In the fourth configuration example, O4 to O19 and O24 to O31 are collected in the memory [8], and O36 to O51 and O56 to O63 are collected in the memory [9]. Further, O0 to O3 and O20 to O23 are realized by the first block A, and O32 to O35 and O52 to O55 are realized by the second block B. In the fourth configuration example, the combinational circuit CMB includes an AND gate G8 that performs an AND operation of input signals in3 to in5 (inverted input for the input signal in3), and a negative OR operation of the input signals in3 to in5. And an OR gate G10 that performs an OR operation on the output of the AND gate G8 and the output of the NOR gate G9.

  FIG. 13 is a diagram illustrating a fifth configuration example of the reconfigurable logic block. In the fifth configuration example, O0 to O7, O12 to O15, and O20 to O31 are aggregated in the memory [8], and O32 to O39, O44 to O47, and O52 to O63 are aggregated in the memory [9]. Yes. Further, O8 to O11 and O16 to O19 are realized in the first block A, and O40 to O43 and O48 to O51 are realized in the second block B. In the fifth configuration example, the combinational circuit CMB includes a NOR gate G11 that performs a NOR operation of input signals in3 to in5 (inverted input for the input signal in4), and input signals in3 to in5 (however, input A NOR gate G12 that performs a negative OR operation on the signal in3) and an OR gate G13 that performs an OR operation on the output of the NOR gate G11 and the output of the NOR gate G12.

  FIG. 14 is a diagram illustrating a sixth configuration example of the reconfigurable logic block. In the sixth configuration example, O0 to O3, O8 to O15, and O20 to O31 are aggregated in the memory [8], and O32 to O35, O40 to O47, and O52 to O63 are aggregated in the memory [9]. Yes. Further, O4 to O7 and O16 to O19 are realized by the first block A, and O36 to O39 and O48 to O51 are realized by the second block B. In the sixth configuration example, the combinational circuit CMB includes a NOR gate G14 that performs a NOR operation of the input signals in3 to in5 (inverted input for the input signal in5), and the input signals in3 to in5 (however, the input signal in5). A NOR gate G15 that performs a negative OR operation on the signal in3) and an OR gate G16 that performs a logical OR operation between the output of the NOR gate G14 and the output of the NOR gate G15.

  FIG. 15 is a diagram illustrating a seventh configuration example of the reconfigurable logic block. In the seventh configuration example, O0 to O11 and O20 to O31 are aggregated in the memory [8], and O32 to O43 and O52 to O63 are aggregated in the memory [9]. O12 to O19 are realized by the first block A, and O44 to O51 are realized by the second block B. In the seventh configuration example, the combinational circuit CMB includes a NOR gate G17 that performs a negative OR operation on the input signals in3 to in5 (however, the input signals in4 and in5 are inverted inputs), and the input signals in3 to in5 (however, NOR gate G18 that performs a negative OR operation on the input signal in3), and an OR gate G19 that performs a logical OR operation between the output of the NOR gate G17 and the output of the NOR gate G18.

  FIG. 16 is a diagram illustrating an eighth configuration example of the reconfigurable logic block. In the eighth configuration example, O0 to O7, O12 to O23, and O28 to O31 are aggregated in the memory [8], and O32 to O39, O44 to O55, and O60 to O63 are aggregated in the memory [9]. Yes. Further, O8 to O11 and O24 to O27 are realized in the first block A, and O40 to O43 and O56 to O59 are realized in the second block B. In the eighth configuration example, the combinational circuit CMB has only an AND gate G20 that performs a logical product operation of the input signals in4 and in5 (however, the input signal in5 is an inverting input).

  FIG. 17 is a diagram illustrating a ninth configuration example of the reconfigurable logic block. In the ninth configuration example, O0 to O7, O12 to O19, and O24 to O31 are aggregated in the memory [8], and O32 to O39, O44 to O51, and O56 to O63 are aggregated in the memory [9]. Yes. Further, O8 to O11 and O20 to O23 are realized by the first block A, and O40 to O43 and O52 to O55 are realized by the second block B. In the ninth configuration example, the combinational circuit CMB includes a NOR gate G21 that performs a NOR operation of input signals in3 to in5 (inverted inputs for the input signals in3 and in5), and input signals in3 to in5 (however, NOR gate G22 that performs a negative OR operation on the input signal in4), and an OR gate G23 that performs a logical OR operation between the output of the NOR gate G21 and the output of the NOR gate G22.

  FIG. 18 is a diagram illustrating a tenth configuration example of the reconfigurable logic block. In the tenth configuration example, O0 to O7 and O12 to O27 are aggregated in the memory [8], and O32 to O39 and O44 to O59 are aggregated in the memory [9]. Further, O8 to O11 and O28 to O31 are realized in the first block A, and O40 to O43 and O60 to O63 are realized in the second block B. In the tenth configuration example, the combinational circuit CMB includes a negative OR operation of the AND gate G24 that performs a logical product operation of the input signals in3 to in5, and the input signals in3 to in5 (inverted input for the input signal in4). And an OR gate G26 that performs a logical OR operation between the output of the AND gate G24 and the output of the NOR gate G25.

  FIG. 19 is a diagram illustrating an eleventh configuration example of the reconfigurable logic block. In the eleventh configuration example, O0 to O3, O8 to O23, and O28 to O31 are aggregated in the memory [8], and O32 to O35, O40 to O55, and O60 to O63 are aggregated in the memory [9]. Yes. In addition, O4 to O7 and O24 to O27 are realized in the first block A, and O36 to O39 and O56 to O59 are realized in the second block B. In the eleventh configuration example, the combinational circuit CMB includes a NOR gate G27 that performs a NOR operation of the input signals in3 to in5 (inverted input for the input signal in5), and the input signals in3 to in5 (however, the input signal in5). An AND gate G28 that performs an AND operation on the signal in5), and an OR gate G29 that performs an OR operation on the output of the NOR gate G27 and the output of the AND gate G28.

  FIG. 20 is a diagram illustrating a twelfth configuration example of the reconfigurable logic block. In the twelfth configuration example, O0 to O11, O16 to O23, and O28 to O31 are aggregated in the memory [8], and O32 to O43, O48 to O55, and O60 to O63 are aggregated in the memory [9]. Yes. In addition, O12 to O15 and O24 to O27 are realized by the first block A, and O44 to O47 and O56 to O59 are realized by the second block B. In the twelfth configuration example, the combinational circuit CMB includes a NOR gate G30 that performs a NOR operation of the input signals in3 to in5 (however, the inverting input for the input signals in4 and in5), and the input signals in3 to in5 (however, The NOR gate G31 performs a negative OR operation on the input signals in3 and in4), and the OR gate G32 performs a logical OR operation between the output of the NOR gate G30 and the output of the NOR gate G31.

  FIG. 21 is a diagram illustrating a thirteenth configuration example of the reconfigurable logic block. In the thirteenth configuration example, O0 to O3, O8 to O19, and O24 to O31 are aggregated in the memory [8], and O32 to O35, O40 to O51, and O56 to O63 are aggregated in the memory [9]. Yes. Further, O4 to O7 and O20 to O23 are realized by the first block A, and O36 to O39 and O52 to O55 are realized by the second block B. In the thirteenth configuration example, the combinational circuit CMB has only an AND gate G33 that performs a logical product operation of the input signals in4 and in5 (however, the input signal in4 is an inverting input).

  FIG. 22 is a diagram illustrating a fourteenth configuration example of the reconfigurable logic block. In the fourteenth configuration example, O0 to O3 and O8 to O27 are aggregated in the memory [8], and O32 to O35 and O40 to O59 are aggregated in the memory [9]. Further, O4 to O7 and O28 to O31 are realized by the first block A, and O36 to O39 and O60 to O63 are realized by the second block B. In the fourteenth configuration example, the combinational circuit CMB includes an AND gate G34 that performs a logical product operation of the input signals in3 to in5 and a negative logical sum operation of the input signals in3 to in5 (however, the input signal in5 is an inverted input). And an OR gate G36 that performs a logical OR operation on the output of the AND gate G34 and the output of the NOR gate G35.

  FIG. 23 is a diagram illustrating a fifteenth configuration example of the reconfigurable logic block. In the fifteenth configuration example, O0 to O11, O16 to O19, and O24 to O31 are aggregated in the memory [8], and O32 to O43, O48 to O51, and O56 to O63 are aggregated in the memory [9]. Yes. In addition, O12 to O15 and O20 to O23 are realized in the first block A, and O44 to O47 and O52 to O55 are realized in the second block B. In the fifteenth configuration example, the combinational circuit CMB includes a NOR gate G37 that performs a NOR operation of input signals in3 to in5 (inverted inputs for the input signals in4 and in5), and input signals in3 to in5 (however, NOR gate G38 that performs a negative OR operation on the input signals in3 and in5), and an OR gate G39 that performs a logical OR operation between the output of the NOR gate G37 and the output of the NOR gate G38.

  FIG. 24 is a diagram illustrating a sixteenth configuration example of the reconfigurable logic block. In the sixteenth configuration example, O0 to O11 and O16 to O27 are aggregated in the memory [8], and O32 to O43 and O48 to O59 are aggregated in the memory [9]. In addition, O12 to O15 and O28 to O31 are realized in the first block A, and O44 to O47 and O60 to O63 are realized in the second block B. In the sixteenth configuration example, the combinational circuit CMB has only an AND gate G40 that performs a logical product operation of the input signals in4 and in5.

  FIG. 25 is a diagram illustrating LUT formation methods and memory aggregation states in the first to sixteenth configuration examples. Symbol “A” indicates that output data is held in the first block A (memory [0] to [7]), and symbol “B” indicates that output data is in the second block B (memory). [10] to [17]) indicate that they are held. Reference numeral “8” indicates that output data is collected in the memory [8], and reference numeral “9” indicates that output data is concentrated in the memory [9].

  For example, in the case of the second configuration example, {in0, in1, in2, in3, in4, in5} = {0,-,-, 0, 0, 0} and {0,-,-, 1, 0, 0} In this case, the output data of the first block A is used as the output signal out, {in0, in1, in2, in3, in4, in5} = {1,-,-, 0, 0, 0} and {1,-, When-, 1, 0, 0}, the output data of the second block B is used as the output signal out. When the combination of input signals is other than the above, the data stored in the memory [8] or [9] is used as the output signal out.

FIG. 26 shows the coverage ratio of the logic circuit in the first to sixteenth configuration examples (the coverage ratio of the 6-input logic circuit, the coverage ratio of the 5-input logic circuit, and the coverage ratio of all the logic circuits including 4 inputs or less). FIG. This table shows the reconfigurable logic block (6-A) according to the present invention among the logic circuits used when MCNC [Microelectronics Center of North Carolina] benchmark circuit (117 types) is subjected to technology mapping by EMAP. ² LUT) indicates the ratio of those that can be mounted. EMap is a technology mapping tool for power optimization developed by UBC [University of British Columbia].

If the reconfigurable logic block (6-A ² LUT) according to the present invention is used, the coverage shown in FIG. 26 can be realized with about one-third the number of memories compared to the conventional 6-LUT. Is possible.

<Other variations>
The configuration of the present invention can be variously modified in addition to the above-described embodiment without departing from the gist of the invention. That is, the above-described embodiment is an example in all respects and should not be considered as limiting, and the technical scope of the present invention is not the description of the above-described embodiment, but the claims. It should be understood that all modifications that come within the meaning and range of equivalents of the claims are included.

  The present invention, for example, is a technique that can be used effectively for realizing a reduction in area and power consumption of an FPGA.

100 Programmable logic circuit (FPGA)
101 I / O block 102 Reconfigurable logic block (RLB)
103 Connection block (CB)
104 Switch block (SB)
105 Wiring 1 First Look-up Table (m-LUT)
2 Second lookup table (n-LUT)
3 Combinational circuit 4 Selector A 1st block (3-LUT)
B 2nd block (3-LUT)
SEL0, SEL1, SEL2 selector CMB combination circuit G (1, 4, 5, 6, 9, 11, 12, 14, 15, 17, 18, 21, 22, 25, 27, 30, 31, 35, 37, 38 ) NOR gate G (2, 8, 20, 24, 28, 33, 34, 40) AND gate G (3, 7, 10, 13, 16, 19, 23, 26, 29, 32, 36, 39) OR Gate

Claims (9)

A reconfigurable logic block with a maximum of K inputs (x [0] to x [K-1]),
a first lookup table with m inputs (y [0] to y [m-1], where m is smaller than K and y belongs to x);
a second lookup table with n inputs (z [0] to z [n−1], where n is smaller than K and z belongs to x);
a combinational circuit of p inputs (c [0] to c [p-1], where p is smaller than K and 2 or larger , and c belongs to x);
A selector that selects one of the first lookup table and the second lookup table according to the output of the combinational circuit;
A reconfigurable logic block comprising:   Comparing truth tables each representing a plurality of logic circuits, mounting a portion where the same pattern is continuous in the second look-up table, and mounting the remaining portion in the first look-up table The reconfigurable logic block according to claim 1, wherein:   3. The reconfigurable logic block according to claim 2, wherein the plurality of logic circuits include logic circuits mapped with a K-input look-up table having a high appearance probability. 4.   A programmable logic circuit device comprising the reconfigurable logic block according to claim 3. A technology mapping method for the programmable logic circuit device according to claim 4,
A first step in which the maximum number of inputs K of the reconfigurable logic block is set as the number of inputs j and the flow proceeds to the second step;
A second step that searches for uncovered nodes and advances the flow to a third step;
It is determined whether or not there is a j-input cut, and if there is a cut, the flow proceeds to the fourth step, and if there is no cut, the flow proceeds to the tenth step;
a fourth step of cutting into j input partial circuits and advancing the flow to the fifth step;
a determination is made as to whether j is greater than m; if it is greater, the flow proceeds to the sixth step; otherwise, the flow proceeds to the eighth step;
A sixth step of calculating a P representative element of the partial circuit and advancing the flow to the seventh step;
Based on the P representative element, it is determined whether or not the partial circuit can be mounted by the reconfigurable logic block. If the partial circuit can be mounted, the flow proceeds to the eighth step. A seventh step to advance to the step;
An eighth step of covering the node with the reconfigurable logic block and advancing the flow to the ninth step;
Determining whether or not all nodes have been covered; if covering has been completed, end the series of flows; otherwise, proceed to the second step;
A tenth step in which the input number j is decremented by one and the flow proceeds to the second step;
A technology mapping method characterized by comprising:   A reconfigurable logic block with a maximum of K inputs (x [0] to x [K-1]),
  a first lookup table with m inputs (y [0] to y [m-1], where m is smaller than K and y belongs to x);
  a second lookup table with n inputs (z [0] to z [n−1], where n is smaller than K and z belongs to x);
  a combinational circuit of p inputs (c [0] to c [p−1], where p is smaller than K and c belongs to x);
  A selector that selects one of the first lookup table and the second lookup table according to the output of the combinational circuit;
  Have
  Comparing truth tables each representing a plurality of logic circuits, mounting a portion where the same pattern is continuous in the second look-up table, and mounting the remaining portion in the first look-up table Features a reconfigurable logic block.   The reconfigurable logic block according to claim 6, wherein the plurality of logic circuits include logic circuits mapped with a K-input look-up table having a high appearance probability.   A programmable logic circuit device comprising the reconfigurable logic block according to claim 7.   A technology mapping method for the programmable logic circuit device according to claim 8,
  A first step in which the maximum number of inputs K of the reconfigurable logic block is set as the number of inputs j and the flow proceeds to the second step;
  A second step that searches for uncovered nodes and advances the flow to a third step;
  It is determined whether or not there is a j-input cut, and if there is a cut, the flow proceeds to the fourth step, and if there is no cut, the flow proceeds to the tenth step;
  a fourth step of cutting into j input partial circuits and advancing the flow to the fifth step;
  a determination is made as to whether j is greater than m; if it is greater, the flow proceeds to the sixth step; otherwise, the flow proceeds to the eighth step;
  A sixth step of calculating a P representative element of the partial circuit and advancing the flow to the seventh step;
  Based on the P representative element, it is determined whether or not the partial circuit can be mounted by the reconfigurable logic block. If the partial circuit can be mounted, the flow proceeds to the eighth step. A seventh step to advance to the step;
  An eighth step of covering the node with the reconfigurable logic block and advancing the flow to the ninth step;
  Determining whether or not all nodes have been covered; if covering has been completed, end the series of flows; otherwise, proceed to the second step;
  A tenth step in which the input number j is decremented by one and the flow proceeds to the second step;
  A technology mapping method characterized by comprising:

Images