`(19) Japan Patent Office
`(JP)
`
`(12) Public patent bulletin (B2) (11) Patent number
`
`JP 3580785 B22004.10.27
`
`(45) Issued date October 27, 2004 (10.27.2004)
`
`(24) Publication date
`
` July 30, 2004 (7.30.2004)
`
`Patent No. 3580785
`
`(P3580785)
`
`
`
`(51) Int. Cl.7
`HO3K
`HO1L
`
`19/177
`21/82
`
`F1
`HO3K
`HO1L
`
`19/177
`21/82
`
`
`
`
`
`
`
`
`A
`
`
`
`Number of claims 6
`
` (16 pages
`in total)
`
`
`
`
`
`
`(21) Application
`Number
`(22) Application
`Filing Date
`(65)
`Japanese
`Unexamined Patent
`Application
`Publication No.
`(43)
`Publication
`date
`
`Request
`examination
`
`
`
`
`
`
`
`
`
`Japanese Patent Application 2001-
`199644 (P2001-199644)
`
`(73) Applicant
`
`396023993
`
`June 29, 2001 (6.29.2001)
`
`Patent
`Unexamined
`Japanese
`Application Publication No. 2003-
`18000 (P2003-18000A)
`
`January 17, 2003 (1.17.2003.)
`
`
`
`
`
`
`
`Semiconductor Technology Academic
`Research Center
`6th floor, Yusen Shin-Yokohama Building,
`
`3-17-2 Shin-Yokohama, Kohoku-
`ku, Yokohama City, Kanagawa Prefecture
`
`for
`
`June 29, 2001 (6.29.2001)
`
`(74) Agent
`
`100077517
`
`
`
`
`
`
`
`
`
`
`
`(74) Agent
`
`(74) Agent
`
`(74) Agent
`
`
`
`Patent Attorney
`
`Patent
`
`Takashi Ishida,
`100092624
`Junichi Tsuruta, Patent Attorney
`100100871
`Shigeru Tsuchiya, Patent Attorney
`100082898
`Masaya Nishiyama,
`Attorney
`100081330
`Sotoji Higuchi,
`
`
`(74) Agent
`
`
`
`
`
`
`
`
`Continued on the last page
`
`
`
`(54) (Title of the Invention) LOOK UP TABLE, PROGRAMMABLE LOGIC CIRCUIT DEVICE HAVING LOOK
`
`Patent Attorney
`
`UP TABLE, AND THE LOOK UP TABLE CONFIGURATOIN METHOD
`
`
`
`(57) (Scope of Patent Claims)
`
`(Claim 1)
`
`A lookup table with M inputs and N outputs, characterized in that the table is equipped with a plurality of LUT
`
`units, and an internal configuration control means for controlling the internal configuration of the plurality of
`
`LUT units; the internal configuration control means comprises a plurality of selectors for selecting input/output
`
`signals of the plurality of LUT units and a selector control means for controlling each selector to define a
`
`configuration of the plurality of LUT units; the selector control means comprises a memory, and controls the
`
`plurality of selectors according to data stored in the memory; the selector is equipped with an input signal
`
`selection selector provided at the input of at least one LUT unit for selecting an input signal, and an output signal
`
`selection selector that is provided at the output of the LUT unit for selecting an output signal, wherein the input
`
`signal selection selector and the output signal selection selector are controlled according to the data stored in the
`
`memory and the input signal.
`
`(Claim 2)
`
`The lookup table according to claim 1, characterized in that the M-input N-output lookup table is a 6-input 3-
`
`output lookup table.
`
`
`
`
`
`
`
`10
`
`20
`
`Intel Exhibit 1040
`Intel v. Iida
`
`

`

`(Claim 3)
`
`The lookup table of claim 2, characterized in that the 6-input 3-output lookup table comprises eight 3-input 1-
`
`(2)
`
`JP 3580785 B22004.10.27
`
`output LUT units.
`
`(Claim 4)
`
`The lookup table of claim 2, characterized in that the 6-input 3-output lookup table comprises four 3-input 2-
`
`output LUT units.
`
`(Claim 5)
`
`A programmable logic circuit device, comprising a plurality of logic blocks; a plurality of wirings connected to
`
`each logic block; a plurality of switch means provided at intersections of the wirings; a connection block provided
`
`10
`
`between the input/output line of each logic block and each wiring; and I/O block for external input/output,
`
`characterized in that: the logic block comprises the lookup table according to any one of claims 1-4.
`
`(Claim 6)
`
`A method of constructing a look-up table, an M-input N-output lookup table, characterized in that, multiple LUT
`
`units are prepared, the input/output signals of the plurality of LUT units are selectively controlled to set a
`
`predetermined internal configuration mode, and the signal input to at least one of the LUT units and the signal
`
`output by the LUT unit are each selectively controlled by a predetermined function of the data stored in the
`
`lookup table and the input signal.
`
`(Detailed Description of the Invention)
`
`(0001)
`
`(Technical field to which the invention belongs)
`
`The present invention relates to a technology for configuring a lookup table with which the mounting area can
`
`be reduced.
`
`In recent years, programmable logic circuit devices have attracted attention as devices capable of realizing logic
`
`circuits that meet various user needs by electrically programming internal circuits. This programmable logic
`
`circuit device, known as a Programmable Logic Device (PLD ) or Field Programmable Gate Array Hardware
`
`(FPGA ), beyond its use for hardware prototyping, has recently come to be used for constructing large-scale
`
`circuits (e.g., microprocessors, etc.) that themselves have various functions. Such a programmable logic circuit
`
`device has a lookup table (LUT) as a main component, and there is a strong demand for a reduction in the circuit
`
`area of this LUT.
`
`(0002)
`
`(Conventional technology)
`
`20
`
`30
`
`A look-up table (LUT), which is a major element of programmable logic circuit devices (PLDs and FPGAs),
`
`consists of memory and can implement any logic circuit. A basic configuration of such an FPGA has been
`
`proposed in the past, for example, in US Patent Nos. 4,706,216 and 4,870,302. In addition, multi-context and
`
`clustering of multiple LUTs in FPGA have been proposed, for example, in US Pat. Nos. 5,778,439 and 5,905,385.
`
`Furthermore, the research results regarding the evaluation of the LUT used for FPGA (for example, evaluation
`
`and performance evaluation regarding functionality and area, evaluation of clustering, etc.) are presented in, for
`
`example, J. Rose et al., “Architecture of Field-Programmable Gate Arrays: The Effect of Logic Block
`Functionality on Area Efficiency”, IEEE J. Solid-State Circuits, vol. 25, no. 5, pp. 1217-1225，Oct． 1990, J.
`Rose et al., “The Effect of Logic Block Architecture on FPGA Performance”， IEEE J. Solid-State Circuits, vol.
`27，no. 3，pp． 281-287, Mar． 1992, and E． Ahmed et al． ，”The Effect of Logic LUT and Cluster Size on
`
`40
`
`Deep-Submicron FPGA Performance and Density”, FPGA 2000, Monterey, CA USA, 2000.
`
`
`
`
`50
`
`

`

`(3)
`
`JP 3580785 B22004.10.27
`
`(0003)
`
`In a programmable logic circuit device, the number of bits M of the input signal of the logic circuit that can be
`
`implemented corresponds to the number of bits of the address of the memory forming the LUT, and the number
`
`of bits N of the output signal corresponds to the number of output bits of the memory. Therefore, a logic circuit
`
`that can be implemented in one LUT is an arbitrary M-input N-output logic circuit. Such a LUT is referred to
`
`herein as an M-input N-output LUT.
`
`(0004)
`
`(Problem to Be Solved by the Invention)
`
`10
`
`Conventionally, for example, in an FPGA, both the number of inputs M and the number of outputs N of LUTs
`
`are fixed values, and an arbitrary logic circuit is divided into M input N output circuit units and implemented
`
`using multiple LUTs.
`
`Therefore, in conventional FPGAs, if a circuit with less than M bits of inputs is created by dividing the circuit,
`
`one LUT must be assigned to the circuit with less than M bits of inputs, causing an increase in the mounting area.
`
`(0005)
`
`In view of the above-described problems of the conventional programmable logic circuit device, the main object
`
`of the present invention is to reduce the circuit area of a lookup table (LUT), that is, a programmable logic circuit
`
`20
`
`device. Another object of the present invention is to reduce the power consumption of the programmable logic
`
`circuit device.
`
`(0006)
`
`(Means for Solving the Problem)
`
`The first aspect of the present invention is to provide a lookup table with M inputs and N outputs, characterized
`
`in that the table is equipped with a plurality of LUT units, and an internal configuration control means for
`
`controlling the internal configuration of the plurality of LUT units; the internal configuration control means
`
`comprises a plurality of selectors for selecting input/output signals of the plurality of LUT units and a selector
`
`control means for controlling each selector to define a configuration of the plurality of LUT units; the selector
`
`control means comprises a memory, and controls the plurality of selectors according to data stored in the memory;
`
`30
`
`the selector is equipped with an input signal selection selector provided at the input of at least one LUT unit for
`
`selecting an input signal, and an output signal selection selector that is provided at the output of the LUT unit
`
`and selects an output signal, wherein the input signal selection selector and the output signal selection selector
`
`are controlled according to the data stored in the memory and the input signal.
`
`(0007)
`
`The second aspect of the present invention is to provide a programmable logic circuit device, comprising a
`
`plurality of logic blocks; a plurality of wirings connected to each logic block; a plurality of switch means provided
`
`at intersections of the wirings; a connection block provided between the input/output line of each logic block and
`
`40
`
`each wiring; and I/O block for external input/output, where the lookup table comprises M inputs and N outputs,
`
`characterized in that the table is equipped with a plurality of LUT units, and an internal configuration control
`
`means for controlling the internal configuration of the plurality of LUT units; the internal configuration control
`
`means comprises a plurality of selectors for selecting input/output signals of the plurality of LUT units and a
`
`selector control means for controlling each selector to define a configuration of the plurality of LUT units; the
`
`selector control means comprises a memory, and controls the plurality of selectors according to data stored in the
`
`memory; the selector is equipped with an input signal selection selector provided at the input of at least one LUT
`
`unit for selecting an input signal, and an output signal selection selector that is provided at the output of the LUT
`
`50
`
`

`

`(4)
`
`JP 3580785 B22004.10.27
`
`unit for selecting an output signal, wherein the input signal selection selector and the output signal selection
`
`selector are controlled according to the data stored in the memory and the input signal.
`
`(0008)
`
`The third aspect of the present invention provides a method for configuring an M-input N-output lookup table,
`
`comprising: preparing a plurality of LUT units; selectively controlling the input/output signals of the plurality of
`
`LUT units to set a predetermined internal configuration mode, and selectively controlling each of the signal input
`
`to at least one of the LUT units and the signal output by the LUT unit by a predetermined function of the data
`
`stored in the lookup table and the input signal.
`
`According to the present invention, by providing a mode change memory in the LUT, unlike the LUT used in
`
`conventional FPGAs, it is possible to realize an LUT having a plurality of inputs and outputs. As a result, it is
`
`possible to configure LUTs suitable for the number of input signals required by the divided circuits, thereby
`
`preventing an increase in mounting area. In addition, by stacking circuits that do not operate at the same time in
`
`the same LUT and operating them while switching between them, it is possible to greatly reduce not only the
`
`mounting area but also the power consumption.
`
`(0009)
`
`(Embodiments of the invention)
`
`A lookup table, a programmable logic circuit device having the lookup table, and a method of configuring the
`
`lookup table according to the present invention will be described in detail below with reference to the
`
`accompanying drawings.
`
`FIG. 1 is a block diagram showing an example of FPGA to which the present invention is applied. In FIG. 1,
`
`reference numeral 100 is an FPGA as an example of a programmable logic circuit device, 101 is an I/O block,
`
`102 is a logic block (CLB: Configurable Logic Block), 103 is a connection block (C), and 104 is a switch matrix
`
`(S), and 105 indicates wiring.
`
`(0010)
`
`As shown in FIG. 1, an FPGA 100 is configured with logic blocks (CLBs) 102 arranged in an array, wiring
`
`(circuit area) 105 surrounding these CLBs 102, and I/O blocks 101 for inputting/outputting with the outside. A
`
`switch matrix (S) 104 is arranged at the intersection of each wiring 105 for connecting them, and a connection
`
`block (C) 103 is arranged between each input/output line of each CLB 102 and the wiring 105. Each CLB 102 is
`
`configured with a lookup table (LUT) 121, a latch 122, and a selector 123. The present invention is primarily
`
`related to the configuration of the LUT 121.
`
`(0011)
`
`FIG. 2 is a block diagram showing a 6-input 3-output LUT as an example of the LUT in FPGA, and shows an
`
`example of the LUT 121 in FIG. 1. That is, the LUT shown in FIG. 2 corresponds to a configuration in which
`
`M=6 and N=3 in the M-input N-output LUT. Regarding the values of M and N, M=6 and N=3 are merely
`
`examples, and there are other various values, and there are also cases where M=N or M<N.
`
`(0012)
`
`FIG. 3 is a block diagram showing the internal configuration modes of the 6-input 3-output LUT shown in FIG.
`
`2. By changing the values (X, Y, Z) of the mode change memory (71), as described later in detail, 6-input 3-
`
`output LUT can be set to internal configurations as shown in FIGS. 3(a) to 3(f).
`
`Specifically, FIG. 3(a) shows a case where a 6-input, 3-output LUT is mode-set as three 2-input, 1-output LUTs.
`
`For example, in a conventional FPGA (conventionally, a 4-input 1-output LUT is used as a unit), 3 LUTs (4-
`
`input 1-output LUT) are required to assign three 2-input 1-output circuits to the LUT. However, in the
`
`configuration shown in FIG. 3(a), only one 6-input 3-output LUT is sufficient.
`
`
`
`
`10
`
`20
`
`30
`
`40
`
`50
`
`

`

`(5)
`
`JP 3580785 B22004.10.27
`
`(0013)
`
`By the way, the area ratio of the 4-input 1-output LUT and the 6-input 3-output LUT, including the wiring area,
`
`is about 1:1.5. Therefore, in the configuration shown in FIG. 3(a), for example, compared to the conventional
`
`example using three 4-input 1-output LUTs, the circuit mounting area ratio is (1 x 3): 1.5, that is, about 1:0.5.
`
`can be reduced, decreasing the area by up to about 50%.
`
`(0014)
`
`Also, FIG. 3(b) shows a case where the mode was set as two 3-input 1-output LUTs. In this case, for example,
`
`compared to the conventional example using two 4-input 1-output LUTs, the circuit mounting area ratio is (1 x
`
`2): 1.5, that is, about 1:0.75 can be reduced, decreasing the area by up to about 25%.
`
`10
`
`Furthermore, FIG. 3(c) shows a case where the mode was set as a 6-input 1-output LUT instead of a 6-input 3-
`
`output LUT.
`
`(0015)
`
`FIG. 3(d) shows the mode setting as 3-input 1-output LUT x 8 planes. FIG. 3(e) shows the case where the mode
`
`was set as 4-input 1-output LUT×4 planes, and FIG. 3(f) shows the case where the mode was set as 5-input 1-
`
`output LUT×2 planes. FIG. 4 is a diagram for explaining an example of the circuit mapping method in the lookup
`
`table, and shows the reason why the mode settings of FIGS. 3(d) to 3(f) are possible.
`
`(0016)
`
`As shown in FIG. 4, for example, in mapping methods using control structures such as if~, else, and case in
`
`20
`
`Register Transfer Level (RTL) description in Hardware Description Language (HDL), since conditional branches
`
`are explicitly guaranteed not to operate concurrently, the processing within each condition is mapped to each
`
`context. Switching between contexts is performed, for example, by a signal from a control circuit implemented
`
`in another LUT (lookup table).
`
`(0017)
`
`In such a case, as shown in FIGS. 3(d) to 3(f), a plurality of LUTs can be composed of one LUT. Specifically, in
`
`the case of FIG. 3(d), eight 3-input 1-output LUTs can be configured with one LUT (one 6-input 3-output LUT
`
`in the case of FIG. 3(d)). In addition, in the case of FIG. 3(e), four 4-input 1-output LUTs can be configured with
`
`one LUT, and in the case of FIG. 3(f), two 5-input 1-output LUTs can be configured with one LUT.
`
`(0018)
`
`Specifically, the configuration shown in FIG. 3(e) can realize a maximum area reduction of up to about 62%, for
`
`example, by making the circuit mounting area ratio of (1 x 4): 1.5, that is, it can be reduced to about 1:0.375,
`
`with respect to the conventional 40 examples using four 4-input 1-output LUTs. In other words, the LUT of the
`
`embodiment shown in FIG. 3(e) (LUT composed of one 6-input 3-output LUT) can be configured with a
`
`conventional LUT having about 32% of the mounting area (LUT configured with four 4-input 1-output LUTs),
`
`further significantly reducing power consumption.
`
`(0019)
`
`Further, for example, the circuit mounting area of the ALU circuit of 8 operations can be reduced to about 75%,
`
`improving the mounting efficiency, comparing of mounting with a conventional 4-input 1-output LUT, and using
`
`a 6-input 3-output LUT as shown in Fig. 3(e) as a 4-input 1-output LUT x 4 planes.
`
`FIG. 5 is a block diagram showing a 6-input 3-output LUT 7 as an example of LUT in an FPGA according to the
`
`present invention together with input and output signals, equivalent to that in which six input signals A, B, C, D,
`
`E, F and three output signals Q, V, W are added to the 6-input, 3-output LUT121 shown in FIG. 2.
`
`
`
`
`30
`
`40
`
`50
`
`

`

`(6)
`
`JP 3580785 B22004.10.27
`
`(0020)
`
`FIG. 6 is a block diagram showing an example of the internal configuration of the 6-input 3-output LUT shown
`
`in FIG. 5.
`
`As shown in FIG. 6, the 6-input 3-output LUT 7 (121) includes a mode change memory 71, selectors 721-726,
`
`and 3-input 1-output LUT units (memory arrays) 731-738. The mode change memory 71 stores 3-bit data X, Y,
`
`Z designated by the user. The relationship between the 6-bit inputs A to F and the 3-bit outputs Q, V, and W is
`
`set according to user’s requests.
`
`(0021)
`
`Each selector (selector for input signal selection) 721 to 725 selects the input signals according to the data X, Y,
`
`and Z stored in the mode change memory 71, respectively, after inputting a predetermined signal in the 6-bit
`
`input signal. That is, the signals A and C are input to the selector 721, signals B and D are input to the selector
`
`722, and one signal selected from selection signal F0 (X, Y, Z) defined by data X, Y, Z, respectively, is output.
`
`The signals A and D are similarly input to the selector 723, signals B and E are input to the selector 724, signals
`
`C and F are further input to the selector 725, and one signal selected from selection signal F1 (X, Y, Z) defined
`
`by data X, Y, Z, respectively, is output.
`
`(0022)
`
`Each of the 3-input 1-output LUT units 731-738 includes an address decoder, a memory, and a selector, and
`
`outputs a 1-bit signal in response to a 3-bit input signal, as will be described later. That is, signals A, B, and C
`
`are input to the LUT units 731, 732, 734 to 736, and 738, respectively, also, either signal A or C and either signal
`
`B or D selected by the selection signal F0, and the signal C are input to the LUT unit 733. Further, either signal
`
`A or D, either signal B or E, and either signal C or F selected by selection signal F1 are input to LUT unit 737.
`
`The output signals of the LUT units 731 to 738 are input to a selector (selector for output signal selection) 726,
`
`and one signal from a selection signal F2 (D, E, F, X, Y, Z) defined by signals D, E, F and data X, Y, Z is selected
`
`and output as signal V. Signal Q is output from LUT unit 731, and signal W is output from LUT unit 737.
`
`(0023)
`
`10
`
`20
`
`FIG. 7 is a block diagram showing an example of a 3-input 1-output LUT unit 731 in the 6-input 3-output LUT
`
`7 of FIG. 6. The 3-input 1-output LUT units 731 to 738 all have the same configuration.
`
`The LUT unit 731 shown in FIG. 7 includes an address decoder 7311, a selector 7312, and memory unit groups
`
`30
`
`M11 to M14 and M21 to M24 each composed of two sets of 4 bits. The address decoder 7311 decodes the 2-bit
`
`input signals A and B, to designate one each of the memory unit groups M11 to M14 and M21 to M24, and
`
`furthermore, according to the input signal C, choose one set of either memory unit groups M11-M14 or M21-
`
`M24 to output data.
`
`(0024)
`
`FIG. 8 is a block diagram showing another example of a 3-input 1-output LUT unit 731 in the 6-input 3-output
`
`LUT 7 of FIG. 6.
`
`The LUT unit 731 shown in FIG. 8 includes an address decoder 7313 and an 8-bit memory unit group M31-M38.
`
`The address decoder 7313 decodes the 3-bit input signals A, B, and C, and designates one of the memory unit
`
`40
`
`groups M31 to M38 to output its data (Q).
`
`
`
`
`50
`
`

`

`(7)
`
`JP 3580785 B22004.10.27
`
`(0025)
`
`The relationship between 3-bit data X, Y, Z specified in the mode change memory 71 in the 6-input 3-output
`
`LUT shown in FIG.6 and the corresponding internal configuration (setting mode) will be described with reference
`
`to FIGS. 3(a) to 3(f).
`
`First, as shown in FIG. 3(a), when the 6-input, 3-output LUT 7 (121) is set to the mode of three 2-input, 1-output
`
`LUTs, the selection signals F0 and F1 select input “1” in selectors 721, 722 and 723-725, and selection signal F2
`
`selects input “2” in selector 726.
`
`(0026)
`
`That is, the user designates the 3-bit data X, Y, Z to be stored in the mode change memory 71, so that the selection
`
`signals F0 (X, Y, Z) and F1 (X, Y, Z) select input “1” in each selector 721, 722 and 723-725, and so that the
`
`selection signal F2 (D, E, F, X, Y, Z) selects the input “2” in the selector 726.
`
`(0027)
`
`Then, it is possible to configure as three 2-input 1-output LUTs shown in Fig. 3(a), by using LUT unit 731 that
`
`outputs signal Q after signals A, B, and C are input; LUT unit 733 input with signals C, D via selectors 721 and
`
`722 and direct signal C and that outputs signal V via selector 726; and LUT unit 737 input with the signals D, E,
`
`and F via the selectors 723 to 725 and outputs the signal W. Note that either input signal C in the LUT unit 731
`
`or input signal C in LUT unit 733, and input signal D via the selector 723 in the LUT unit 737 are extra input
`
`signals in each LUT unit, but these do not pose a problem.
`
`(0028)
`
`Then, as shown in FIG. 3(b), when mode setting a 6-input 3-output LUT 7 as two 3-input 1-output LUTs, the
`
`selection signal F1 designates 3-bit data X, Y, Z to be stored in the mode change memory 71 so as to select input
`
`“1” in the selectors 723-725. Then, it is possible to configure as two 3-input 1-output LUTs shown in Fig. 3(b),
`
`by using LUT unit 731 that outputs signal Q after signals A, B, and C are input; and LUT unit 737 input with the
`
`signals D, E, and F via the selectors 723 to 725 and outputs the signal W.
`
`(0029)
`
`As shown in Fig. 3(c), when setting the mode of a 6-input 3-output LUT as a 6-input 1-output LUT, the selection
`
`signals F0 and F1 select the input “0” in each selector, and the selection signal F2 determines the value of selector
`
`726 by input signals D, E, and F and outputs signal V. That is, a 1-bit signal V is output from 6-bit inputs of
`
`signals A, B, and C and signals D, E, and F.
`
`(0030)
`
`As shown in Fig. 3(d), when setting the mode of a 6-input 3-output LUT as a 3-input 1-output LUT x 8 planes,
`
`the selection signals F0 and F1 select the input “0” in each selector, and the selection signal F2 determines the
`
`value of selector 726 by signals D, E, and F and outputs signal V. In this case, signals D, E, and F use plane
`
`switching signals.
`
`(0031)
`
`As shown in Fig. 3(e), when setting the mode of a 6-input 3-output LUT as a 4-input 1-output LUT x 4 planes,
`
`too, the selection signals F0 and F1 select the input “0” in each selector, and the selection signal F2 determines
`
`the value of selector 726 by signals D, E, and F and outputs signal V. In this case, signal D is one of the 4-bit
`
`input signals along with signals A, B, and C, and signals E and F use plane switching signals.
`
`(0032)
`
`As shown in Fig. 3(f), when setting the mode of a 6-input 3-output LUT as a 5-input 1-output LUT x 2 planes,
`
`the selection signals F0 and F1 select the input “0” in each selector, and the selection signal F2 determines the
`
`value of selector 726 by signals D, E, and F and outputs signal V. In this case, signals D and E are two of the 5-
`
`bit input signals along with signals A, B, and C, and signal F uses a plane switching signal.
`
`
`
`
`10
`
`20
`
`30
`
`40
`
`50
`
`

`

`(8)
`
`JP 3580785 B22004.10.27
`
`(0033)
`
`As described above, according to this embodiment, for example, a 6-input 3-output LUT can be used as various
`
`internal configuration modes by changing the values X, Y, and Z of the mode change memory 71.
`
`FIG. 9 is a block diagram showing another example of the internal configuration of the 6-input 3-output LUT
`
`shown in FIG. 5, and shows an example of the internal configuration of the 6-input 3-output LUT different from
`
`that shown in FIG. 6.
`
`(0034)
`
`As shown in FIG. 9, the 6-input 3-output LUT 8 (121) has a mode change memory 81, selectors 821-826, and 3-
`
`input 2-output LUT units 831-834. The mode change memory 81 stores 3-bit data X, Y, Z designated by the user.
`
`The relationship between the 6-bit inputs A to F and the 3-bit outputs Q, V, W is set according to the user’s
`
`request.
`
`(0035)
`
`That is, while the 6-input 3-output LUT 7 shown in FIG. 6 described above has eight 3-input 1-output LUT units
`
`731 to 738, the present 6-input 3-output LUT 8 shown in FIG. 9, except for being equipped with four 3-input 2-
`
`output LUT units 831-834, has substantially the same configuration.
`
`3-bit data X, Y, Z designated to the mode change memory 81 in the LUT 8 shown in FIG. 9, selection signals F0
`
`(X,Y,Z), F1 (X,Y,Z) and F2 (D, E, F, X, Y, Z) accordingly, and the operations of the selectors 821 to 826
`
`(corresponding to the selectors 721 to 726) controlled by these selection signals F0, F1 and F2 are similar to that
`
`described with reference to FIGS. 6 and 3(a)-3(f), so the description thereof is omitted here.
`
`(0036)
`
`FIG. 10 is a block diagram showing an example of a 3-input 2-output LUT unit in the 6-input 3-output LUT of
`
`FIG. 9. All of the 3-input 2-output LUT units 831 to 834 have the same configuration.
`
`The LUT unit 831 shown in FIG. 10 includes an address decoder 8311, selectors 8312 and 8313, and memory
`
`unit groups M41-M44, M51-M54, M61-M64, and M71-M74, each of which consists of four sets of 4 bits. The
`
`address decoder 8311 decodes the 2-bit input signals A and B to designate each one of four memory unit groups
`
`M41-M44, M51-M54, M61-M64 and M71-M74, and further selects and outputs, according to the input signal C,
`
`one set of data of the memory unit groups M41 to M44 or M51 to M54 (output signal Q: signal supplied to the
`
`input “0” of the selector 826), and one set of data of memory unit groups M61-M64 or M71-M74 (signal supplied
`
`to input “1” of selector 826).
`
`(0037)
`
`FIG. 11 is a block diagram showing another example of a 3-input 2-output LUT unit in the 6-input 3-output LUT
`
`of FIG. 9.
`
`The LUT unit 831 shown in FIG. 11 comprises an address decoder 8314 and two sets of 8-bit memory unit groups
`
`M81-M88 and M91-M98. The address decoder 8314 decodes the 3-bit input signals A, B, C to designate one of
`
`the two groups of memory units M81-M88 and M91-M98, and outputs data (output signal Q: the signal supplied
`
`to the input “0” of the selector 826 and the signal supplied to the input “1” of the selector 826).
`
`(0038)
`
`
`
`
`10
`
`20
`
`30
`
`40
`
`50
`
`

`

`(9)
`
`JP 3580785 B22004.10.27
`
`FIG. 12 is a block diagram showing still another example of a 3-input 2-output LUT unit in the 6-input 3-output
`
`LUT of FIG. 9.
`
`The LUT unit 831 shown in FIG. 12 includes an address decoder 8315, selectors 8316 and 8317, and eight sets
`
`of 2-bit memory unit groups M111, M121; M112, M122, …M118, M128. The address decoder 8315 decodes
`
`the 1-bit input signal A to designate each one of the eight memory unit groups M111, M121 to M118, M128, and
`
`with 2-bit input signals B and C, further selects and outputs one set of data in the memory unit groups M111,
`
`M121 to M114 and M124 (output signal Q: signal supplied to input “0” of selector 826) and one set of data in
`
`the memory unit groups M115, M125 to M118 and M128 (signal supplied to input “1” of selector 826).
`
`(0039)
`
`FIG. 13 is a block diagram showing a configuration example of an 8-operation ALU circuit (ALU16) 90. In FIG.
`
`13, reference characters G and H denote 16-bit data, I denotes a command signal that determines the operation,
`
`and J denotes an output signal. As shown in FIG. 13, the ALU circuit 90 includes eight arithmetic circuits of an
`
`OR circuit 91 to which 16-bit data G and H are input, respectively; an AND circuit 92; an XOR circuit 93; a not
`
`circuit 94; + (addition) circuit 95; NE (Not Equal) circuit 96; GT (Greater Than) circuit 97; and SHIFT (shift)
`
`circuit 98, as well as a selector 99 that selects the outputs of these eight arithmetic circuits 91 to 98 by a command
`
`signal I; where output signal J corresponding to the command signal I is output.
`
`(0040)
`
`10
`
`FIG. 14 and FIG. 15 below showed a comparison between the case of implementing from a 3-input 1-output
`
`LUT used in conventional FPGAs to a 7-input 1-output LUT (horizontal axis: 3 LUT to 7 LUT) for the ALU
`
`20
`
`circuit (ALU 16) 90 shown in FIG. 13 and the case of implementing 6-input 3-output LUT as shown in FIG. 6 (a
`
`configuration comprising eight 3-input 1-output LUTs 731 to 738, mode change memory 71 and selectors 721 to
`
`726: 3 LUT*8), and a 6-input 3-output LUT as shown in FIG. 9 (a configuration comprising four 3-input 2-output
`
`LUTs 831 to 834, mode change memory 81 and selectors 821 to 826: 4 LUT*4) used in the FPGA according to
`
`the present invention. The ALU 16 includes, for example, a data selector (a circuit that does not need to use an
`
`LUT) for switching wiring, a random logic (a circuit configured with an LUT), and a flip-flop (a circuit that is a
`
`fixed portion of a logic block). It goes without saying that the comparison between FIGS. 14 and 15 is made
`
`under substantially the same conditions other than the configuration of the LUT.
`
`(0041)
`
`FIG. 14 shows the difference in area ratio when the ALU 16 shown in FIG. 13 is mounted on the LUTs (3 LUT
`
`to 7 LUT and 6-input 3-output LUT (3 LUT*8 and 4 LUT*4)) used in the conventional and inventive FPGAs,
`
`and FIG. 15 is a diagram showing the difference in the number of configuration data bits when the ALU 16
`
`shown in FIG. 13 is implemented in LUTs used in the conventional and the inventive FPGAs. The vertical axis
`
`in FIG. 14 shows the area ratio when configured using various LUTs, assuming that the area is 1 when configured
`
`using a commonly used 4-input 1-output LUT (4 LUTs), and the vertical axis in FIG. 15 indicates the number of
`
`bits of configuration data when configured using various LUTs.
`
`(0042)
`
`As is clear from FIG. 14, for example, the area ratio when the ALU 16 as shown in FIG. 13 is mounted on the
`
`6-input 3-output LUT (3 LUT*8 and 4 LUT*4) used in the FPGA according to the present invention is
`
`significantly smaller than when the same ALU 16 is mounted on the LUTs (3 LUTs to 7 LUTs) used in the
`
`conventional FPGA. Specifically, for example, 3 LUT*8, where a 6-input 3-output LUT is implemented as a 3-
`
`input 1-output × 8 planes gives an area about 75% when implemented using a 4-input 1-output LUT (4 LUTs),
`
`which has the smallest area among conventional LUTs.
`
`
`
`
`30
`
`40
`
`50
`
`

`

`(10)
`
`JP 3580785 B22004.10.27
`
`(0043)
`
`Furthermore, as is clear from FIG. 15, the number of configuration data bits, when the ALU 16 is implemented
`
`with the 6-input 3-output LUT (3 LUT*8 and 4 LUT*4) used in the FPGA according to the present invention is
`
`equivalent to that of 4 LUTs, which is the smallest among conventional LUTs. That is, the reason the 6-input 3-
`
`output LUT of the present invention can have a comparable number of configuration data bits, despite requiring
`
`four times as many configuration data for 4-input 1- output, for example, is that while the conventional LUT
`
`constructs the selectors in output stage with LUTs, in the present invention, the number of LUTs used can be
`
`reduced by switching the wiring.
`
`(0044)
`
`In the above description, the 6-input 3-output LUT used in the FPGA according to the present invention is merely
`
`an example, and the present invention can be applied to an M-input N-output (for example, 8-input 4-output)
`
`LUT