Claims
The invention claimed is:
1. A device to reconfigure multilevel logic networks, wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by the functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, due to a logic modification that modifies an output vector F(b) of said objective logic function F(X) for an input vector b to an “invalid value”, comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a nearest place to an output terminal, among unmodified said plurality of pq elements;
means to check correspondence that checks whether the input vector corresponding to an output vector c exists other than said input vector b, wherein c denotes the output vector for said input vector b among output vectors of LUTs of said pq element E G ;
and means to modify by deleting a vector that changes the state of said pq element E G onebyone as modified, and to rewrite the output vector c for said input vector b to the “invalid value”, when said input vector b is the only vector that produces said output vector c in LUTs of the pq element E G .
2. A device to reconfigure multilevel networks, wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, due to a logic modification such that an output vector a for an input vector b is appended to a set of the output vectors of said objective logic function F(X), comprising:
means to select element that selects pq elements onebyone from a pq element E G that is in a furthest place from an output terminal, among unmodified said plurality of pq elements;
means for association that changes a state of the pq element E G as modified, when the pq element E G is not in a nearest place to the output terminal, and that changes an output vector c to a vector value not used as an output vector of the pq element, when the output vector c for said input vector b is an “invalid value” among output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for said input vector b of LUTs of the pq element E 0 into the output vector a, and that changes the state of the pq element E G as modified, when said pq element E G is in the nearest place to the output terminal.
3. A device to modify logic networks, wherein an output vector Q(b i ) of a main logic network for a specific object input vector b i is modified to a modification output vector Q′(b i ), where b i is an input vector among input vectors b applied to input variables X, and said main logic network implements an objective logic function Q(X) of an input variable X, comprising:
an auxiliary memory that stores a vector for modification P i in a prescribed address A i , to modify said output vector Q(b i ) into said modification output vector Q′(b i ) for said specific object input vector b i ,
means to modify that produces said modification output vector Q′(b i ), according to the vector for modification P i and the output vector Q(b i ) produced by said main logic network, when said auxiliary memory produces the vector for modification P i ;
and an address generation circuit that realizes an address generation function F(X), wherein F(X) produces the prescribed address A i for said auxiliary memory that stores said vector for modification P i , when a value of the input variable X equals an object input vector b i ;
and wherein said address generation circuit is composed of multilevel logic networks, where a plurality of pq elements that store lookup tables (LUTs) of subfunctions obtained by a functional decomposition of said address generation function F(X), are connected to form a network according to a connection relation among inputs and outputs of subfunctions;
an exclusive OR of said vector for modification P i and said output vector Q(b i ) of the main logic network for said object input vector b i , is equal to said modification output vector Q′(b i );
said auxiliary memory produces said vector for modification P i to a means to modify, when the address A i produced by said address generation circuit is applied, and produces zero for other cases;
and said means to modify is an EXOR gates performing the exclusive OR operations between outputs of said auxiliary memory and outputs of said main logic network.
4. A device to modify logic networks, wherein an output vector Q(b i ) of a main logic network for a specific object input vector b i is modified to a modification output vector Q′(b i ), where b i is an input vector among input vectors b applied to input variables X, and said main logic network implements an objective logic function Q(X) of an input variable X, comprising:
an auxiliary memory that stores a vector for modification P i in a prescribed address A i , to modify said output vector Q(b i ) into said modification output vector Q′(b i ) for said specific object input vector b i ;
means to modify that produces said modification output vector Q′(b i ), according to the vector for modification P i and the output vector Q(b i ) produced by said main logic network, when said auxiliary memory produces the vector for modification P i ;
and an address generation circuit that realizes an address generation function F(X), wherein F(X) produces the address A i for said auxiliary memory that stores said vector for modification P i , when a value of the input variable X equals said specific object input vector b i ;
and wherein said address generation circuit is composed of multilevel logic networks, where a plurality of pq elements that store lookup tables (LUTs) of subfunctions obtained by a functional decomposition of said address generation function F(X), are connected to form a network according to a connection relation among inputs and outputs of subfunctions;
said auxiliary memory produces said vector for modification P i to a means to modify, when the address A i produced by said address generation circuit is applied;
said means to modify is a tristate buffer connected in an output stage of said main logic network and said auxiliary memory;
said tristate buffer in the output stage of said main logic network is in a high impedance state when an output value of said address generation circuit is not an “invalid value”, and otherwise in a low impedance state;
and said tristate buffer in an output stage of said auxiliary memory is in the high impedance state when the output value of said address generation circuit is the “invalid value”, and otherwise in the low impedance state.
5. A device to modify logic networks as claimed in claim 3 , wherein said auxiliary memory is a pq element in a final stage of said address generation circuit.
6. A device to modify logic networks as claimed in claim 3 , further comprising:
a reconfiguration device to reconfigure said address generation circuit, due to a logic modification that modifies an output vector F(b) of said address generation function F(X) for an input vector b into an “invalid value” in said address generation circuit; wherein said reconfiguration device comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a nearest place to an output terminal, among unmodified said pq elements;
means to check correspondence that checks whether an input vector corresponding to an output vector c exists other than said input vector b, wherein the output vector c denotes an output vector for said input vector b, among output vectors of LUTs of said pq element E G ;
and means to modify by deleting a vector that changes a state of said pq element E G as modified, and that rewrites the output vector c for said input vector b to the “invalid value”, when said input vector b is the only vector that produces said output vector c in the LUTs of the pq element E G .
7. A device to modify logic networks as claimed in claim 3 , further comprising:
a reconfiguration device to reconfigure said address generation circuit, due to a logic modification such that an output vector a for an input vector b is appended to a set of the output vectors of an objective logic function F(X) in the address generation circuit;
wherein said reconfiguration device comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a furthest place from a output terminal, among unmodified pq elements;
means for association that changes a state of the pq element E G as modified, when the pq element E G is not in a nearest place to the output terminal, and that changes an output vector c to a vector value not used as an output vector for the pq element, when the output vector c for an input vector b is an “invalid value” among output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for said input vector b of LUTs of the pq element E G into an output vector a, and that changes the state of the pq element E G as modified, when said pq element E G is in the nearest place to the output terminal.
8. A method to reconfigure multilevel logic networks, wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by a functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, due to a logic modification that modifies an output vector F(b) of said objective logic function F(X) for an input vector b into an “invalid value”, comprising the steps of:
a selecting element step that selects pq elements onebyone from a pq element E G that is in a nearest place to an output terminal, among unmodified said pq elements;
a checking correspondence step that checks whether an input vector corresponding to an output vector c exists other than said input vector b, wherein the output vector c denotes an output vector for said input vector b, among output vectors of LUTs of said pq element E G ;
and a modifying by deleting a vector step that changes a state of said pq element E G as modified, and that rewrites the output vector c for said input vector b to the “invalid value”, when said input vector b is the only vector that produces said output vector c in the LUTs of the pq element E G ;
wherein, above the method to reconfigure multilevel logic networks is executed repeatedly.
9. A method to reconfigure multilevel logic networks, wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by a functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, due to a logic modification such that an output vector a for an input vector b is appended to a set of the output vectors of said objective logic function F(X), comprising the steps of:
a selecting element step that selects pq elements onebyone from a pq element E G that is in a furthest place from an output terminal, among unmodified pq elements;
an associating step that changes a state of the pq element E G as modified, when the pq element E G is not in a nearest place to the output terminal, and that changes an output vector c to a vector value not used as an output vector of a pq element, when the output vector c for said input vector b is an “invalid value” among output vectors LUTs of the pq element E G ;
and a modifying by adding a vector step that rewrites the output vector c for said input vector b of LUTs of the pq element E G into an output vector a, and that changes the state of the pq element E G , as modified, when said pq element E G is in the nearest place to the output terminal;
wherein, above the method to reconfigure multilevel logic networks is executed repeatedly.
10. A reconfigurable multilevel logic network wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by a functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, comprising:
a reconfiguration circuit that modifies said multilevel logic networks, due to a logic modification that modifies an output vector F(b) of said objective logic function F(X) for an input vector b into an “invalid value”;
wherein said reconfiguration circuit comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a nearest place to an output terminal, among unmodified pq elements;
means to check correspondence that checks whether an input vector corresponding to an output vector c exists other than said input vector b, wherein input vector c denotes an output vector for said input vector b, among output vectors of LUTs of said pq element E G ;
and means to modify by deleting a vector that changes a state of said pq element E G as modified, and to rewrite the output vector c for said input vector b to the “invalid value”, when said input vector b is in the only vector that produces said output vector c in LUTs of the pq element E G .
11. A reconfigurable multilevel logic network wherein a plurality of pq elements storing lookup tables (LUTs) of subfunctions obtained by a functional decomposition of an objective logic function F(X) with input variables X, are connected to form a network according to a connection relation among inputs and outputs of said subfunctions, comprising:
a reconfiguration circuit that performs reconfiguration of said multilevel logic networks, due to a logic modification such that an output vector a for an input vector b is appended to a set of the output vectors of said objective logic function F(X);
wherein said reconfiguration circuit comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a furthest place from an output terminal, among unmodified pq elements;
means for association that changes a state of the pq element E G as modified, when the pq element E G is not in a nearest place to the output terminal, and that changes an output vector c to a vector value not used as an output vector of a pq element, when the output vector c for said input vector b is an “invalid value” among output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for said input vector b of LUTs of the pq element E G into the output vector a, and that changes the state of the pq element E G as modified, when said pq element E G is in the nearest place to the output terminal.
12. A device to modify logic network as claimed in claim 4 , wherein said the auxiliary memory is a pq element in a final stage of said address generation circuit.
13. A device to modify logic networks as claimed in claim 4 , further comprising:
a reconfiguration device to reconfigure said address generation circuit, due to a logic modification that modifies an output vector F(b) of said address generation function F(X) for an input vector b into the “invalid value” in said address generation circuit;
wherein said reconfiguration device comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a nearest place to an output terminal, among unmodified pq elements;
means to check correspondence that checks whether an input vector corresponding to an output vector c exists other than said input vector b, where wherein output vector c denotes the output vector for said input vector b, among output vectors of LUTs of said pq element E G ;
and means to modify by deleting a vector that changes a state of said pq element E G as modified, and that rewrites the output vector c for said input vector b to the “invalid value”, when said input vector b is the only vector that produces said output vector c in LUTs of the pq element E G .
14. A device to modify logic networks as claimed in claim 4 , further comprising:
a reconfiguration device to reconfigure said address generation circuit, due to a logic modification such that an output vector a for an input vector b is appended to a set of the output vectors of said objective logic function F(X) in the address generation circuit;
wherein said reconfiguration device comprising:
means to select an element that selects pq elements onebyone from a pq element E G that is in a furthest place from an output terminal, among unmodified pq elements;
means for association that changes a state of the pq element E G as modified, when the pq element E G is not in a nearest place to the output terminal, and that changes an output vector c to a vector value not used as an output vector of a pq element, when the output vector c for said input vector b is the “invalid value” among output vectors LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for said input vector b of LUTs of the pq element E G into an output vector a, and that changes the state of the pq element E G as modified, when said pq element E G is in the nearest place to the output terminal.
TECHNICAL FIELD
The present invention relates to a device to reconfigure multilevel logic networks that is logically designed through repetitive functional decomposition of any logic function, and a device to modify logic networks using the same.
BACKGROUND ART
A general logic circuit is configured using a special LSI (ASIC: Application Specific Integrated Circuit). However, a development cost for the ASIC is high, and its modification requires a lot of time and money. On the other hand, an FPGA (Field Programmable Gate Array) having simple logic configuration has been developed but is unsatisfactory in terms of power reduction and performance under present circumstances.
To that end, in general, the ASIC is designed with any extra logic circuit being previously incorporated thereinto to enable modification. This design can deal with a minor functional change flexibly to some extent.
A device disclosed in, for example, Patent Document 1 is wellknown as a device to modify logic networks that undergoes a minor functional change. The device to modify logic networks discussed in Patent Document 1 is intended to modify an output value of a ROM storing a program to be executed with a CPU and is configured using the FPGA.
FIG. 20 show the configuration of a device to modify logic networks 103 described in Patent Document 1. A ROM 101 stores a program to be executed with a CPU 102 . The CPU 102 sends an address to the ROM 101 through an address bus 104 . The ROM 101 produces data to the address through a first data bus 106 .
The device to modify logic networks 103 receives an address applied from the address bus 104 and receives corresponding data from the first data bus 106 . A modification address storage unit 111 in the device to modify logic networks 103 registers an address of the ROM 101 where data to be modified is stored. A comparison circuit 113 determines whether the modification address storage unit 111 stores an address value that matches an address value applied from the address bus 104 . If any address is matched, a match signal is produced; if no address is matched, a mismatch signal is produced. The match signal or mismatch signal is produced to a data selection circuit 114 .
On the other hand, the modification data storage unit 112 registers data to be modified in association with each address value registered in the modification address storage unit 111 . If a match signal is applied from the comparison circuit 113 , the data selection circuit 114 produces data read from the modification data storage unit 112 to the second data bus 105 . If a mismatch signal is applied, the data selection circuit 114 produces data applied from the first data bus 106 to the second data bus 105 . The data produced to the second data bus 105 is applied to the CPU 102 as read data.
In this way, an address to be modified of the ROM 101 is registered in the modification address storage unit 111 and in addition, data to be modified is registered in the modification data storage unit 112 to thereby moderately change data in the ROM 101 .
Patent Document 1: Japanese Unexamined Patent Application Publication No. 2002297408 Patent Document 2: Japanese Unexamined Patent Application Publication No. 2004258799 NonPatent Document 1: T. Sasao and M. Matsuura, “BDD representation for incompletely specified multipleoutput logic functions and its applications to functional decomposition”, Design Automation Conference, Anaheim, Calif., Jun. 1317, 2005, pp. 373378.
DISCLOSURE OF INVENTION
Problems to be Solved by the Invention
In a design phase, it is uncertain which part of the original logic circuit needs to be modified. Accordingly, the device to modify logic networks needs to be able to modify an arbitrary output of the original logic circuit. For that purpose, the logic configuration of the circuit should be freely changeable.
On the other hand, the device to modify logic networks is an extra circuit not engaged in operations of the original logic circuit unless the logic circuit is modified. Thus, it is preferred to minimize the footprint and power reduction of the device to modify logic networks as much as possible.
The above conventional device to modify logic networks is configured using the FPGA with a view to expanding the versatility of the circuit. This leads to a problem that a wide wiring area is required and in addition, a relatively large chip area is required to implement the device to modify logic networks.
Further, in the case of reconfiguring the FPGA, in general, the wiring structure is changed. Accordingly, the reconfiguration should be carried out in consideration of an influence of a wiring delay etc. Moreover, in case of an erroneous change, the circuit might be broken at the worst, so the circuit change should be carefully performed. In addition, the circuit change needs to be executed while the logic circuit operation is suspended, considering the wiring change involved in the circuit change. Therefore, the FPGA is not appropriate for such an application as requires realtime dynamic change during operations of the logic circuit (for example, a change of the logic circuit configuration involved in learning with a dictionary, a neutral network, etc.).
Here, an LUT cascade logic circuit has been known as a logic circuit having reconfigurable logic configuration see Patent Document 2 and NonPatent Document 1). In the LUT cascade logic circuit, objective logic function is decomposed into plural subfunctions that involve a serial input/output relationship through functional decomposition based on a binary decision diagram (BDD), and each subfunction is implemented as an LUT using a memory. Since the LUT cascade logic circuit is mostly configured by memories, high integration thereof is easily achieved and its footprint can be reduced.
However, reconfiguration of the LUT cascade logic circuit requires a lot of computations under conventional conditions. Upon the reconfiguration, first, a BDD of objective logic function is prepared and repeatedly subjected to partition and reconfiguration to thereby find the optimum functional decomposition method. Then, resultant subfunctions are each turned into an LUT and stored in memory. If the objective logic function involves many input variables, it is necessary to take considerable time processing the variables on a computer equipped with a largecapacity memory. Thus, the LUT cascade logic circuit has not hitherto been applied to a device to modify logic networks intended for a simple rewriting operation.
However, considering that any means enables simplified reconfiguration of the logic configuration of the LUT cascade logic circuit and minor modification of the logic configuration, if the device to modify logic networks is applied to the LUT cascade logic circuit, this application will be a promising approach to the realization of small circuit area and lowpower dissipation.
In view of the above circumstances, it is an object of the present invention to provide a device to modify logic networks that can realize small circuit area and lowpower dissipation compared with a conventional one by using a reconfigurable LUT logic circuit similar to the above LUT cascade logic circuit, while retaining flexibility in change of the circuit logic configuration. It is another object of the present invention to provide a device to modify logic networks that enables realtime dynamic modification during operations of a logic circuit.
It is still another object of the present invention to provide a device to reconfigure multilevel logic networks, which can reconfigure a multilevel logic network used in the above device to modify logic networks with small footprint and low power reduction in a simple manner.
It is yet still another object of the present invention to provide a reconfigurable multilevel logic network capable of minor reconfiguration of logic function and realtime dynamic reconfiguration during operations of the logic circuit.
Means for Solving the Problems
[1] Explanation of Terms and Background Principle of the Invention
To begin with, main terms used in this specification are defined, and several theoretical backgrounds of the present invention are described.
[Definition 1] (Address Generation Function and Address Generation Logic Function)
Function F ( X ): B n →{0,1, . . . , k } ( X is n ary vector, B={ 0,1})
Under this condition, if F(a i )=i (i=1, 2, . . . , k) with respect to k different registered vectors a i εB n (i=1, 2, . . . , k) and F=0 with respect to the other (2 n −k) input vectors, F(X) is an address generation function with a weight k. The address generation function generates 1 to k unique addresses with respect to k different binary vectors. A multioutput logic function that expresses an output value of the address generation function as a binary value is called address generation logic function”.
(End of Definition)
In this specification, it is assumed that a value of k is much smaller than the total number of inputvector combinations 2 n (k<<2 n ).
[Definition 2] (Address Detection Function)
Function f ( X ): B n →{0,1 , . . . , k } ( X is n ary vector)
Under this condition, if f(a i )=1 (i=1, 2, . . . , k) with respect to k different registered vectors a i εB n (i=1, 2, . . . , k), and f=0 with respect to the other (2 n −k) input vectors, f(X) is an address detection function with a weight k.
(End of Definition)
[Definition 3] (Address Table and Address Generation Circuit)
A table showing output vectors F(a i )(εB m ) corresponding to k registered vectors {a i i=1, 2, . . . , k; a i εB n } of address generation logic function F(X): B n →{0, 1, . . . , k} is an address table. A circuit that realizes the address table is an address generation circuit.
(End of Definition)
[Definition 4] (Partition)
An input vector is represented by X=(x 1 , x 2 , . . . , x n ). A set of variables of X is represented by {X}. Provided that {X 1 }∪{X 2 }={X} and {X 1 }∩{X 2 }=φ, X=(X 1 , X 2 ) is partition of X where φ represents an empty set.
(End of Definition)
[Definition 5] (Decomposition Chart, Standard Decomposition Chart, and Column Multiplicity)
Assuming that completely specified function f(X): B n →B q (B={0, 1}, X=(x 1 , x 2 , . . . , x n ), n, qεnatural number), (X L , X H ) is partition of X, and the dimension of X (the number of variables) is represented by d(X). A table that satisfies the following conditions (1) to (3) with respect to function f(X) and partition of X: X=(X L , X H ) is a decomposition chart of f.
(1) A table includes 2 nL columns×2 nH rows.
(2) Each row and each column include a label in binary code, and the set of labels in each row and column include every conceivable pattern of n L bits and n H bits as elements.
(3) Each element in a table is a truth value f: f(X L , X H ) with respect to a combination (X L , X H ) of labels in column and row corresponding to each element.
X L is referred to as bound variables (bound variables), and X H is referred to as free variables (free variables). The number of different column patterns in a decomposition chart is referred to as column multiplicity in a decomposition chart, and represented by μ. A chart where X L =X and X H =φ is also described as a special decomposition chart.
Further, a decomposition chart of function f, in which X L =(x 1 , x 2 , . . . , X nL ) and X H =(x nL+1 , x nL+2 , x n ) is referred to as a standard decomposition chart.
(End of Definition)
Example 1
In a decomposition chart of Table 1, n L =3 and n H =2. Further, the number of column patterns of the decomposition chart is 2, (0110) T and (1101) T . Thus, μ=2.
(End of Example)
TABLE 1 EXAMPLE OF DECOMPOSITION CHART
[Lemma 1]
The column multiplicity of a decomposition chart for an address generation (detection) function with a weight k is k+1 at most.
(End of Lemma)
[Lemma 2]
Provided that F is an address generation function, two address generation functions G and H satisfy the following expression (1), and a weight of the function F is equal to a weight of the function G.
F ( X 1 ,X 2 )= G ( H ( X 1 ), X 2 ) (1)
(End of Lemma)
(Proof)
Consider a decomposition chart where X 1 is bound variables, and X 2 is free variables. Also consider an address generation function H where an ordinal level of the maximum value in each column in a decomposition chart is represented by H(X i ) (if the maximum value is 0, an ordinal level is set to 0). In this case, only a column including output values of 0 is contracted. Therefore, the number of output values of the function G, which are not 0 is the same as that of the function F. Further, G is also an address generation function.
(End of Proof)
Example 2
Consider a decomposition chart for a 5variable address generation function F(X) shown in Table 2 (see FIG. 1 ). Assuming that the function F(X) is decomposed such that F(X 1 , X 2 )=G(H(X 1 ), X 2 ) where X 1 =(x 1 , x 2 , x 3 , x 4 ), X 2 =(x 5 ), the column multiplicity in Table 2 is 7. In this example, H is a 4input/3output function as shown in Table 3, more specifically, an address generation logic function with a weight 6 . Table 4 shows a decomposition chart for a function G. As understood therefrom, the function G obtained by decomposing the address generation function F with a weight 7 is also an address generation function with a weight 7 .
(End of Example)
TABLE 2
DECOMPOSITION CHART FOR FUNCTION F
TABLE 3
TRUTH TABLE FOR FUNCTION H
x 1
x 2
x 3
x 4
y 1
y 2
y 3
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
0
TABLE 4 DECOMPOSITION CHART FOR FUNCTION G
[Lemma 3]
Provided that f is an address detection function, an address detection function g and an address generation function H satisfy the following expression (2), and a weight of the function g is lower than a weight of the function f.
ƒ( X 1 ,X 2 )= g ( H ( X 1 ), X 2 ) (2)
(End of Lemma)
This can be proved similar to Lemma 2. Since an output of an address detection function is a single output, a circuit using the address detection function is simpler than a corresponding address generation circuit.
[Definition 6] (pq Element)
A pq element refers to a memory realizing an arbitrary pinput/qoutput logic function, and its memory size is 2 p q.
(End of Definition)
[Theorem 1]
An address generation logic function with a weight k can be composed using pq elements in a number corresponding to the number derived from the following expression (3).
⌈
n

q
p

q
⌉
.
(
WHERE
,
p
>
q
,
q
=
⌈
log
2
(
k
+
1
)
⌉
)
(
3
)
(End of Theorem)
(Proof)
An address generation logic function F with a weight k can be subjected to functional decomposition as expressed by the following expression (4).
F ( X 1 ,X 2 )= G ( H ( X 1 ), X 2 ) (4)
In this example, G(X 1 ••, X 2 ) is also an address generation function with a weight k as will be understood from Lemma 1, and the number of inputs is reduced to n−(p−q). This operation is repeated plural times corresponding to the number calculated as follows:
⌈ n  q p  q ⌉ TIMES ( 5 )
As a result, the number of inputs can be reduced down to q. Accordingly, an address generation circuit can be configured only using pq elements.
(End of Proof)
Example 3
The number of nonzero output values of the 5variable address generation function F(X) in Table 2 is 7 (k=7). Thus, the following expression (6) is established, and as shown in FIG. 1 , the circuit can be realized using 4input/3output elements.
q =┌ log 2 ( k+ 1)┐=┌ log 2 (7+1)┐=3 (6)
(End of Example)
Upon circuit synthesis with pq elements, if p is set large, the number of pq elements necessary to realize the circuit is reduced but the total memory size is increased. On the other hand, if p is set small, the total memory size is reduced but the number of pq elements increases.
Consider that an address generation circuit is synthesized using pq elements. In this case, a method of determining p, which can minimize the number of elements without increasing the total memory size, is given by the following theorem.
[Theorem 2]
In the case of implementing an address generation logic function as a multilevel logic network using pq elements, an upper limit for the total memory size is lowest if p−q=1 or p−q=2.
(End of Theorem)
(Proof)
Upon the functional decomposition of an address generation circuit using pq elements, the number of input lines of the circuit can be reduced by r=p−q at each decomposition. To reduce n input lines down to q lines, functional decomposition should be repeated plural times corresponding to the number calculated as follows:
s
=
⌈
n

q
r
⌉
TIMES
(
7
)
Further, s pq elements are necessary to realize the circuit. Thus, the requisite total memory size is as follows:
MEM=s· 2 p q (8)
If n is large enough, the memory size can be approximated as follows:
MEM ≃ ( 2 r r ) · ( n  q ) · 2 q q ( 9 )
Since n and p are fixed under the above provision, only r is variable. If r=1 or r=2, 2 r /r takes the maximum value. Thus, the above theorem is proved.
(End of Proof)
In general, the number of levels of the circuit is desirably small, the circuit is configured under the condition of r=p−q=2. Theorem 1 indicates that an address generation circuit can be synthesized as a multilevel logic network using pq elements by repeating functional decomposition. The following Example 3 shows that various multilevel logic networks including an LUT cascade logic circuit can be synthesized according to functional decomposition.
Example 4
An address generation circuit with the number of inputs n=48 and a weight k=255 is configured.
q =┌ log 2 (255+1)┐=8 (10)
The above relationship is established. Thus, a value of p, which can minimize the memory size and reduce the number of circuit levels, is 10 (p=10). Since the number of input lines is decremented by 2 per pq element, if 20 pq elements are used, the number of inputs can be reduced down to 8. An address generation circuit as shown in FIG. 2 can be achieved using 20 pq elements, for example. In this case, the number of circuit levels is 10, and the memory size is 160 kbit.
Further, if an element having a large number of inputs is used, the number of elements and delay time can be reduced. In an illustrated example of FIG. 3 , p=11 and q=8. In this case, the number of elements is (48−8)/(11−8)=14, the number of circuit levels is 8, and the memory size is 212 kbit. In an illustrated example of FIG. 4 , p=12 and q=8. In this case, the number of elements is (48−8)/(12−8)=10, the number of circuit levels is 5, and the memory size is 320 kbit.
(End of Example)
Theorem 2 indicates a condition for setting an upper limit for the total memory size to the lowest value upon the implementation of a general address generation function. The total memory size is minimized with a particular address generation function even if a relationship of p−q=2 is not satisfied.
Next, described is a method of multilevel logic reconfiguration for reconfiguring a multilevel logic network using pq elements with varying address tables for an address generation function. The modification of the multilevel logic network can be divided into two basic operations:
(1) deletion of registered vector
(2) addition of registered vector
Thus, the above operations (1) and (2) are considered below.
Further, as described above, the multilevel logic network using pq elements is configuring through repeated functional decomposition of an objective logic function F. Thus, it is only necessary to describe how to modify a function H and a function G under the condition that functionaldecomposed function F(X 1 , X 2 )=G(H(X 1 ), X 2 ) in the case where an address table for the objective logic function F is changed.
In the following description, “input variable” and “output variable” refer to undetermined values, and “input vector” and “output vector” refer to a specific value of an input variable and a specific value of an output variable.
(1) Deletion of Registered Vector
Assume that partition of an input variable X (εB n ) is expressed by X=(X 1 , X 2 ), functional decomposition of an address generation function F(X) is expressed by F(X 1 , X 2 )=G(H(X 1 ), X 2 ), a vector a (εB n ) is a registered vector of an address generation function F(X), and partition of the vector a corresponding to the partition of the input variable: X=(X 1 , X 2 ) is expressed by a=(a 1 , a 2 ).
Consider the case of deleting the registered vector from the address table for the address generation function F(X). The following description is made on the assumption that the address table is achieved using an LUT cascade logic circuit.
In the case of deleting the vector a from the address table, F(a)=0. Thus, G(H(a 1 ), a 2 )=0.
On the other hand, provided that one of two variables, variable Y 1 , of a subfunction G(Y 1 , X 2 ) is set as a fixed value H(a 1 ), and a variable X 2 is changed, if a relationship of G(H(a 1 ), X 2 )≠0 is not satisfied with no variables X 2 but X 2 =a 2 , output vectors corresponding to registered vectors other than the vector a in the original address table do not depend on a value of subfunction H(a 1 ). Accordingly, in this case, H(a 1 ) is an “invalid value” and thus may be 0 (H(a 1 )=0).
As understood from the above, the modification of the LUT cascade logic circuit following the deletion of the registered vector a from the address table can be performed based on the following algorithm.
(Algorithm 1)
(Step 1) Among unmodified pq elements, an element nearest to an output side is selected. The selected pq element is represented by E G . A subfunction expressed by the pq element E G is G(H(X 1 ), X 2 ) where (X 1 , X 2 ) ⊂ X and X 1 ∩X 2 =φ. An input vector for (X 1 , X 2 ) is (a 1 , a 2 ). If the pq element E G is furthest from an output side, X 1 =φ and H(X 1 )=φ.
(Step 2) Among output vectors of an LUT stored in the pq element E G , an output vector corresponding to the input vector (H(a 1 ), a 2 ) is referred to as G(H(a 1 ), a 2 )=0. The pq element E G is assumed modified.
(Step 3) It is checked whether any input vector a o corresponding to a partial variable X 2 where an output vector G(H(a 1 ), X 2 ) is nonzero, exists.
(Step 4) if a o does not exist, the processing returns to Step 1; otherwise, the processing is terminated.
(End of Algorithm)
The above algorithm can be easily applied to a general pq element multilevel logic function. The algorithm applied to the general pq element multilevel logic function is as follows.
(Algorithm 2)
(Step 1) A pqcircuit network having s elements can be configured through (s−1) functional decomposition operations. Upon each functional decomposition, pq elements are extracted one by one from an input side and numbered 1 to s. A pq element on the output side is numbered s. The element E 1 numbered 1 is furthest from the output side.
(Step 2) A set of pq elements is represented by p, and an initial value p={E s }.
(Step 3) In a multilevel logic network, functionaldecomposed function G (H 1 (Y 1 ), H 2 (Y 2 ), . . . , H m (Y m )) of the circuit configured using a pelement and the other elements is considered. In this example, Y i is an intermediate variable, and the case where H k (Y k )=Y k is also considered as a special case.
(Step 4) Assuming that G (H 1 (a 1 ), H 2 (a 2 ), . . . , H 2 (a 2 ))=0 where a (=(a 1 , a 2 , . . . , a m )) is an intermediate variable vector, and H i (a i )=d≠0, if a relationship of H i (a i )=d is not established with respect to the other registered vectors b, H i (a i )=0.
(Step 5) If the number of elements in the set p of pq elements is s−1″, the processing is terminated; otherwise, an element assigned the highest number is added to the set p and the processing returns to Step 3.
(End of Algorithm)
(2) Addition of Registered Vector
Next, the case of adding a registered vector a to an address table for an address generation function F(X) is considered. An output vector corresponding to the additional registered vector a is represented by c. The following description is focused on the case where an address table is generated using an LUT cascade logic circuit.
In the case of adding the vector a to the address table, F(a)=c. Thus, G(H(a 1 ), a 2 )=c.
In this example, the registered vector a can correspond onetoone with a value of F(a) as long as a value of a subfunction H(a 1 ) is not 0. To that end, if an output vector of the subfunction H(a 1 ) is 0, the vector should be corrected to any value other than 0. In this case, the correction should be performed not to influence an output value of the other registered vectors, so an output vector of the subfunction H(a 1 ) is changed to an unused value. For example, the smallest one can be selected from among unused values larger than the maximum value of nonzero output values of the subfunction H(X 1 ).
As will be understood from the above, the modification of the LUT cascade logic circuit following the addition of the registered vector a to the address table can be performed according to the following algorithm.
(Algorithm 3)
(Step 1) Among unmodified pq elements, an element furthest from an output side is selected. The selected pq element is represented by E G . A subfunction of the pq element E G is G(H(X 1 ), X 2 ) where (X 1 , X 2 ) ⊂ X and X 1 ∩X 2 =φ. An input vector corresponding to (X 1 , X 2 ) is referred to as (a 1 , a 2 ). Here, if the pq element E G is furthest from an output side, X 1 =φ), H(X 1 )=φ.
(Step 2) Provided that e 0 =G(H(a 1 ), a 2 ), if the pq element E G is nearest to an output side, e=c; otherwise, if e 0 ≠0, e=e 0 , and if e 0 =0, e is set to the smallest one out of positive unused output values among conceivable output values of the pq element E G .
(Step 3) Among output vectors of an LUT stored in the pq element E G , an output vector corresponding to an input vector (H(a 1 ), a 2 ) is {G(H(a 1 ), a 2 )=e}.
(Step 4) If any unmodified pq element is found, the processing returns to Step 1; otherwise, the processing is terminated.
(End of Algorithm)
The above algorithm can be easily applied to a general pq element multilevel logic function. The algorithm applied to the general pq element multilevel logic function is described below.
(Algorithm 4)
(Step 1) A pqcircuit network having s elements can be configured through (s−1) functional decomposition operations. Upon each functional decomposition, pq elements are extracted one by one from an input side and numbered 1 to r. A pq element on the output side is numbered s. The element E 1 numbered 1 is furthest from the output side. An input vector corresponding to an input variable X is a. The pq element E 1 numbered 1 is E G .
(Step 2) The input vector a is applied to the multilevel logic network. In this case, an output vector of the element E G is e 0 .
(Step 3) Provided that the pq element E G is nearest to an output side, e=c; otherwise, if e 0 ≠0, e=e 0 , and if e 0 =0, e is set to the smallest one of positive unused output values among conceivable output values of the pq element E G .
(Step 4) An output vector corresponding to the input vector a among output vectors of an LUT stored in the pq element E G is e.
(Step 5) If E G is a pq element nearest to an output side, the processing is terminated; otherwise, a pq element ranked next to the element E G in Step 1 in is set as E G and the processing returns to Step 2.
(End of Algorithm)
The deletion of the registered vector and the addition of the registered vector are performed as above to enable reconfiguration of a pqelementequipped multilevel logic network in the case of changing an address table for an address generation function. If the pqelementequipped multilevel logic network is an LUT cascade circuit, an address can be added to or deleted from an address table within a time proportional to the number of cells and the number of registered vectors (addresses).
[2] Construction and Operation of the Invention
According to a first constitution of a device to reconfigure multilevel logic networks of the present invention, a device to reconfigure multilevel logic networks, wherein plural pq elements storing LUTs of subfunctions obtained by the functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, due to the logic modification that modifies the output vector F(b) of the objective logic function F(x) for the input vector b to “invalid value”, comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the nearest place to the output terminal, among the unmodified the pq elements;
means to check correspondence that checks whether the input vector corresponding to the output vector c exists other than the input vector b, where c denotes the output vector for the input vector b among the output vectors of LUTs of the pq element E G ;
and means to modify by deleting a vector that changes the state of the pq element E G as modified, and to rewrite the output vector c for the input vector b to “invalid value”, when the input vector b is the only vector that produces the output vector c in the LUTs of the pq element E G
According to this constitution,
(1) first, means to select element selects a pq element onebyone from the nearest pq element E G to the output side among the unmodified pq elements,
(2) next, means to check correspondence checks whether the input vector b corresponds to the output vector c for the input vector b of the pq element E G one to one, and
(3) subsequently, means to modify by deleting a vector rewrites an output value for the input vector b as invalid” value and assigns the pq element E G as modified element in case that the input vector b corresponds to the output vector c one to one in the LUTs of the pq element E G .
The above processes (1) to (3) are repeated to thereby perform logic modification for changing the output vector F(b) for the input vector b to an “invalid value” in the pqelementequipped multilevel logic network as described in Algorithm 1 or 2 above.
Here, the term “multilevel logic network” means a logic circuit configured by plural cascade or treeconnected pq elements, inclusive of an LUT cascade logic circuit. The term “invalid value” means a value indicating that the output vector F(b) is invalid. The “invalid value” is generally 0 but is not limited to 0.
According to a second constitution of a device to reconfigure multilevel networks of the present invention, a device to reconfigure multilevel networks, wherein plural pq elements storing LUTs of subfunctions obtained by functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, due to the logic modification such that the output vector a for the input vector b is appended to the set of the output vectors of the objective logic function F(X), comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the furthest place from the output terminal, among the unmodified the pq elements;
means for association that changes the state of the pq element E G as modified, when the pq element E G is not in the nearest place to the output terminal, and that changes the output vector c to the vector value not used as an output vector of the pq element, when the output vector c for the input vector b is “invalid value” among the output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for the input vector b of LUTs of the pq element E G into the output vector a, and that changes the state of the pq element E G as modified, when the pq element E G is in the nearest place to the output terminal.
According to this constitution,
(1) first, means to select element selects a pq element onebyone from the furthest pq element E G from the output side among the unmodified pq elements,
(2) next, means for association assigns the pq element E G as modified element in case that the pq element E G selected by means to select element is not the nearest to the output side, and changes the output vector c to the vector value not used as an output vector of the pq element in case that output vector c for the input vector b is invalid” value among output vectors of LUTs of the pq element E G , and
(3) subsequently, means to modify by adding a vector rewrites the output vector c for the input vector b of the output vectors of LUTs of the pq element E G in output vector a, and assigns the pq element E G as modified element, in case that the pq element E G selected by means to select element is the nearest to the output side.
The above processes (1) to (3) are repeated to thereby perform logic modification for adding the output vector a for the input vector b in a pqelementequipped multilevel logic network as described in Algorithm 3 or 4 above.
According to a first constitution of a device to modify logic networks of the present invention, a device to modify logic networks, wherein the output vector Q(b i ) of the main logic network for a specific object input vector b i is modified to modification output vector Q′(b i ), where b i is an input vector among the input vectors b applied to the input variables X, and the main logic network implements the objective logic function Q(X) of the input variable X, comprising:
an auxiliary memory that stores the vector for modification P i in the prescribed address A i , to modify the output vector Q(b i ) into the modification output vector Q′(b i ) for the object input vector means to modify that produces the modification output vector Q′(b i ), according to the vector for modification P i and the output vector Q(b i ) produced by the main logic network, when the auxiliary memory produces the vector for modification P i ;
and an address generation circuit that realizes the address generation function F(X), where F(X) produces the address A i for the auxiliary memory that stores the vector for modification P i , when the value of the input variable X equals to the object input vector b i ;
and wherein the address generation circuit is composed of the multilevel logic networks, where plural pq elements that store LUTs of subfunctions obtained by a functional decomposition of the address generation function F(X), are connected to form a network according to connection relation among the inputs and outputs of the subfunctions;
and the auxiliary memory that produces the vector for modification P i to means to modify, when the address A i produced by the address generation circuit is applied.
According to this constitution, if the input vector b is applied to the main logic circuit as an input variable X, the main logic circuit operates the objective logic function to produce the output vector Q(b). On the other hand, the address generation circuit operates the address generation function F(b) for the input vector b. If the input vector b is an object input vector b i , the address generation circuit produces the address A i . The address A i is applied to the auxiliary memory. The auxiliary memory produces the vector for modification P i to the address A i . Then, means to modify outputs the modification output vector Q′(b i ) on the basis of the vector for modification P i and the output vector Q(b i ). As a result, an output value of the objective logic function is changed. If the input vector b is not the object input vector b i , the address generation circuit does not produce the address A i and thus, the auxiliary memory does not produce the vector for modification P i . Accordingly, the output vector Q(b i ) is produced as it is without being modified by means to modify.
According to the present invention, a pqelementequipped multilevel logic network is used as the address generation circuit, so the address generation circuit can be achieved with a small memory capacity as described above. Accordingly, power as well as footprint of the device to modify logic networks can be reduced. Further, logic modification of the address generation circuit can be executed on the basis of above Algorithm 1 or 2 and Algorithm 3 or 4, and if necessary, an output of the main logic circuit can be freely adjusted.
In addition, in the device to modify logic networks according to the present invention, the address generation circuit can be reconfigured only by rewriting a pq element (memory) without changing a line path. Thus, the address generation circuit can be easily modified without considering an influence of wiring delay etc. Moreover, since the modification can be performed without requiring any line change, the circuit can be dynamically modified in real time during operations of the main logic circuit.
According to a second constitution of a device to modify logic networks of the present invention, in the device to modify logic networks according to the first constitution,
the exclusive OR of the vector for modification P i and the output vector Q(b i ) of the main logic network for the object input vector b i , is equal to the modification output vector Q′(b i );
the auxiliary memory that produces the vector for modification P i when the input is the address A i produced by the address generation circuit, and that produces zero for other cases;
and means to modify is the EXOR gates performing the exclusive OR operations between the outputs of the auxiliary memory and the outputs of the main logic network.
According to a third constitution of a device to modify logic networks of the present invention, in the device to modify logic networks according to the first constitution,
means to modify is the tristate buffers connected in the output stage of the main logic network and the auxiliary memory;
the address generation circuit that produces “invalid value” for the input variable X, when the value of the input variable X is different from any of the object input vector b i ;
the tristate buffer in the output stage of the main logic network is in the high impedance state when the output value of the address generation circuit is not “invalid value”, and otherwise in the low impedance state;
and the tristate buffer in the output stage of the auxiliary memory is in the high impedance state when the output value of the address generation circuit is “invalid value”, and otherwise in the low impedance state.
According to a fourth constitution of a device to modify logic network of the present invention, in the device to modify logic network according to any one of the first to third constitutions, the auxiliary memory is the pq element in the final stage of the address generation circuit. Here, it is assumed that the number of outputs of an element in the final stage may be q or more.
According to a fifth constitution of a device to modify logic networks of the present invention, the device to modify logic networks according to any one of the first to fourth constitutions further comprises:
a reconfiguration device to reconfigure the address generation circuit, due to the logic modification that modifies the output vector F(b) of the address generation function F(X) for the input vector b into “invalid value” in the address generation circuit;
wherein the reconfiguration device comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the nearest place to the output terminal, among the unmodified the pq elements;
means to check correspondence that checks whether the input vector corresponding to the output vector c exists other than the input vector b, where c denotes the output vector for the input vector b, among the output vectors of LUTs of the pq element E G ;
and means to modify by deleting a vector that changes the state of the pq element E G as modified, and that rewrite the output vector c for the input vector b to “invalid value”, when the input vector b is the only vector that produces the output vector c in the LUTs of the pq element E G .
According to a sixth constitution of a device to modify logic networks of the present invention, the device to modify logic networks according to any one of the first to fourth constitutions further comprises:
a reconfiguration device to reconfigure the address generation circuit, due to the logic modification such that the output vector a for the input vector b is appended to the set of the output vectors of the objective logic function F(X) in the address generation circuit; wherein
the reconfiguration device comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the furthest place from the output terminal, among the unmodified the pq elements;
means for association that changes the state of the pq element E G as modified, when the pq element E G is not in the nearest place to the output terminal, and that changes the output vector c to the vector value not used as an output vector of the pq element, when the output vector c for the input vector b is “invalid value” among the output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for the input vector b of LUTs of the pq element E G into the output vector a, and that changes the state of the pq element E G as modified, when the pq element E G is in the nearest place to the output terminal.
According to a first constitution of method to reconfigure multilevel logic networks of the present invention, a method to reconfigure multilevel logic networks, wherein plural pq elements storing LUTs of subfunctions obtained by the functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, due to the logic modification that modifies the output vector F(b) of the objective logic function F(X) for the input vector b into “invalid value”, comprising the steps of:
a selecting element step that selects pq elements onebyone from the pq element E G that is in the nearest place to the output terminal, among the unmodified the pq elements;
a checking correspondence step that checks whether the input vector corresponding to the output vector c exists other than the input vector b, where c denotes the output vector for the input vector b, among the output vectors of LUTs of the pq element E G ;
and a modifying by deleting a vector step that changes the state of the pq element E G as modified, and that rewrite the output vector c for the input vector b to “invalid value”, when the input vector b is the only vector that produces the output vector c in the LUTs of the pq element E G ;
and above steps are executed repeatedly.
According to a second constitution of a method to reconfigure multilevel logic networks of the present invention, a method to reconfigure multilevel logic networks, wherein plural pq elements storing LUTs of subfunctions obtained by functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, due to the logic modification such that the output vector a for the input vector b is appended to the set of the output vectors of the objective logic function F(X), comprising the steps of:
a selecting element step that selects pq elements onebyone from the pq element E G that is in the furthest place from the output terminal, among the unmodified the pq elements;
an associating step that changes the state of the pq element E G as modified, when the pq element E G is not in the nearest place to the output terminal, and that changes the output vector c to the vector value not used as an output vector of the pq element, when the output vector c for the input vector b is “invalid value” among the output vectors of LUTs of the pq element E G ;
and a modifying by adding a vector step that rewrites the output vector c for the input vector b of LUTs of the pq element E G into the output vector a, and that changes the state of the pq element E G as modified, when the pq element E G is in the nearest place to the output terminal;
and above steps are executed repeatedly.
According to a first constitution of a reconfigurable multilevel logic network of the present invention, a reconfigurable multilevel logic network wherein plural pq elements storing LUTs of subfunctions obtained by the functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, comprising:
a reconfiguration circuit that modifies the multilevel logic networks, due to the logic modification that modifies the output vector F(b) of the objective logic function F(X) for the input vector b into “invalid value”;
wherein the reconfiguration circuit comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the nearest place to the output terminal, among the unmodified the pq elements;
means to check correspondence that checks whether the input vector corresponding to the output vector c exists other than the input vector b, where c denotes the output vector for the input vector b, among the output vectors of LUTs of the pq element E G ;
and means to modify by deleting a vector that changes the state of the pq element E G as modified, and to rewrite the output vector c for the input vector b to “invalid value”, when the input vector b is the only vector that produces the output vector c in the LUTs of the pq element E G .
With this constitution, as described above, the reconfiguration circuit can easily delete the output vector F(b) of the objective logic function F(X) only by rewriting a pq element (memory). Further, since the deletion can be performed without requiring any line change, the circuit can be dynamically modified in real time during operations of the logic circuit.
According to a first constitution of a reconfigurable multilevel logic network of the present invention, a reconfigurable multilevel logic network wherein plural pq elements storing LUTs of subfunctions obtained by functional decomposition of the objective logic function F(X) with the input variables X, are connected to form a network according to the connection relation among the inputs and outputs of the subfunctions, comprising:
a reconfiguration circuit that performs reconfiguration of the multilevel logic networks, due to the logic modification such that the output vector a for the input vector b is appended to the set of the output vectors of the objective logic function F(X);
wherein the reconfiguration circuit comprising:
means to select element that selects pq elements onebyone from the pq element E G that is in the furthest place from the output terminal, among the unmodified the pq elements;
means for association that changes the state of the pq element E G as modified, when the pq element E G is not in the nearest place to the output terminal, and that changes the output vector c to the vector value not used as an output vector of the pq element, when the output vector c for the input vector b is “invalid value” among the output vectors of LUTs of the pq element E G ;
and means to modify by adding a vector that rewrites the output vector c for the input vector b of LUTs of the pq element E G into the output vector a, and that changes the state of the pq element E G as modified, when the pq element E G is in the nearest place to the output terminal.
With this constitution, as described above, the reconfiguration circuit can easily perform logic modification for adding the output vector a for the input vector b to the output vector set of the objective logic function F(X) only by rewriting a pq element (memory). Further, since the addition can be performed without requiring any line change, the circuit can be dynamically modified in real time during operations of the logic circuit.
Advantages of the Invention
As described above, according to the device to reconfigure multilevel logic networks of the present invention, the reconfiguration of the multilevel logic network configured by pq elements following its logic modification can be performed in a short time. In addition, the reconfiguration processing can be performed in a short time with a small computation amount, and a small memory capacity suffices for reconfiguration calculation. Thus, the circuit can be imbedded into a chip as a dedicated circuit.
Further, according to the device to modify logic networks of the present invention, a pqelementequipped multilevel logic network is used as the address generation circuit. Thus, as described above, the address generation circuit can be realized with a small memory capacity. Hence, power as well as footprint of the device to modify logic networks can be reduced. In addition, logic modification of the address generation circuit can be executed, and if necessary, an output of the main logic circuit can be freely adjusted.
BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 shows functional decomposition of an address generation logic function F;
FIG. 2 shows an example of an address generation circuit (p=10) configured by pq elements;
FIG. 3 shows an example of an address generation circuit (p=11) configured by pq elements;
FIG. 4 shows an example of an address generation circuit (p=12) configured by pq elements;
FIG. 5 shows the configuration of a reconfigurable multilevel logic network according to a first embodiment of the present invention;
FIG. 6 shows a cascade logic circuit including s pq elements E(1), E(2), . . . , E(s) that are connected in series;
FIG. 7 is a flowchart showing processing for deleting a registered vector of an objective logic function F(X) with a reconfiguration device 1 ;
FIG. 8 is a flowchart showing processing for adding a registered vector of an objective logic function F(X) with the reconfiguration device 1 ;
FIG. 9 shows an LUT cascade logic circuit that achieves an address generation function F(X) illustrated in Example 5;
FIG. 10 shows the configuration of a device to modify logic networks 20 according to a second embodiment of the present invention;
FIG. 11 shows the configuration of the device to modify logic networks 20 according to a third embodiment of the present invention;
FIG. 12 shows the configuration of a reconfigurable multilevel logic network according to a fourth embodiment of the present invention;
FIG. 13 show a 4input LUT used in the Xilinx FPGA;
FIG. 14 shows a 12input/1output circuit using three 4input LUTs;
FIG. 15 shows a general LUT cascade logic circuit;
FIG. 16 shows an example of A reference table 9 ;
FIG. 17 shows an example of an index table;
FIG. 18 is a flowchart of registered vector addition processing in a reconfigurable multilevel logic network of the fourth embodiment;
FIG. 19 is a flowchart of registered vector deletion processing in a reconfigurable multilevel logic network of the fourth embodiment; and
FIG. 20 show the configuration of a device to modify logic networks 103 disclosed in Patent Document 1.
DESCRIPTION OF REFERENCE NUMERALS
1 , 1 ′: reconfigurable circuit
2 : means to select element
3 : means to select element
4 : means to check correspondence
5 : means to modify by deleting a vector
6 : means for association
7 : means to modify by adding a vector
8 : index table
9 : reference table
10 : multilevel logic network
11 : input data bus
12 : output data bus
13 : pq element
20 : device to modify logic networks
21 : address generation circuit
22 : auxiliary memory
23 : modifying circuit
24 : EXOR gate
30 : main logic circuit
31 : input bus
32 : output bus
41 _ 0 to 41 _ 15 : Dflipflop (DFF)
42 : multiplexer (MUX)
43 : clock line
44 : registered value input line
44 : data input line
BEST MODES FOR CARRYING OUT THE INVENTION
Hereinafter, best modes for carrying out the present invention will be described with reference to the accompanying drawings.
First Embodiment
FIG. 5 shows the configuration of a reconfigurable multilevel logic network according to a first embodiment of the present invention. This reconfigurable multilevel logic network is configured as a system that combines a multilevel logic network 10 and a reconfiguration device 1 . The reconfiguration circuit 1 is a device for reconfiguring the multilevel logic network 10 along with logic modification of the multilevel logic network 10 .
The multilevel logic network 10 is a logic circuit for operating an objective logic function F(X) with an input variable X. The multilevel logic network 10 includes plural pq elements 13 . Each pq element 13 stores an LUT of a subfunction obtained by functional decomposition of the objective logic function F(X). In addition, the pq elements 13 are connected in circuit according to a connection relation of inputs and outputs of each subfunction. The multilevel logic network 10 may be configured using an LUT cascade circuit or a pq circuit network as illustrated in FIGS. 2 to 4 .
The input variable X is an nary variable of a binary vector. An output variable Y of the objective logic function F(X) is an mary variable of a binary vector. The input variable X can take 2 n values. Among those, k (k<2 n ) input vectors are referred to as registered vectors”. The other vectors are referred to as invalid vectors”.
An input vector b is applied as the input variable X from an input data bus 11 of the multilevel logic network 10 . Further, an output vector a is produced as the output variable Y=F(X) from an output data bus 12 of the multilevel logic network 10 .
The reconfiguration circuit 1 includes means to select element 2 and 3 , means to check correspondence 4 , means to modify by deleting a vector 5 , means for association 6 , means to modify by adding a vector 7 , and the multilevel logic network 10 .
Following logic modification that sets an output vector F(b) corresponding to an input vector b of the objective logic function F(X) as an “invalid value”, deletion processing is executed, and the multilevel logic network 10 is reconfigured. Upon the deletion processing, means to select element 2 selects the unmodified pq elements 13 one by one from the nearest pq element E G to an output side. Means to check correspondence 4 checks whether the input vector b corresponds to an output vector c one to one in the LUTs of the pq element E G . Means to modify by deleting a vector 5 rewrites an output value corresponding to the input vector b as an “invalid value” and considers the pq element E G modified in case that the input vector b corresponds to the output vector c one to one in the LUTs of the pq element E G .
On the other hand, along with logic modification to add an output vector a corresponding to the input vector b to an output vector set of the objective logic function F(X), addition processing is performed, and the multilevel logic network 10 is reconfigured. Upon the addition processing, means to select element 3 selects the unmodified pq elements 13 from the furthest pq element E G from the output side one by one. Means for association 6 considers the pq element E G modified if the pq element E G is not nearest to an output side. Moreover, at this time, if an output vector c corresponding to the input vector b out of the output vectors of the LUT of the pq element E G is an “invalid value”, means for association 6 changes the output vector c into a vector value not used as an output vector of the pq element. Means to modify by adding a vector 7 rewrites an output value corresponding to the input vector b of the LUT of the pq element E G as an output vector a and considers the pq element E G modified if the pq element E G is nearest to an output side.
Operations of the thusconfigured multilevel logic network reconfiguration circuit 1 of the first embodiment will be described hereinbelow.
In the following description, the multilevel logic network 10 is assumed a cascade logic circuit including s pq elements E(1), E(2), . . . , E(s) that are seriesconnected as shown in FIG. 6 . The pq elements are connected in the order of E(1), E(2), . . . , E(s) from an input side.
Provided that X represents an input variable, X=(X 1 , X 2 , . . . , X s ) represents partition of the input variable X, and Y=F(X) represents an output variable of the objective logic function F(X) corresponding to the input variable X, if the objective logic function F(X) is functionaldecomposed to subfunctions G 1 , G 2 , . . . , G s based on Expression (11) below. In Expression (11), U i (i=1, 2, . . . , s−1) represents an intermediate variable.
U
1
=
G
1
(
X
1
)
U
2
=
G
2
(
X
2
,
U
1
)
⋮
U
s
=
G
s
(
X
s
,
U
s

1
)
Y
=
U
s
(
11
)
A pq element E(i)(i=1, 2, . . . , s) stores an LUT of an intermediate function G i . A pq element E(1) receives an input variable X 1 . In response thereto, the pq element E(1) produces an output variable U 1 =G 1 (X 1 ). The pq element E(i) (i=2, 3, . . . , s) receives an output variable U i−1 of a previous pq element E(i−1) and an input variable X i . In response thereto, the pq element E(i) produces an output variable U i =G i (X i , U i−1 ). Further, an output variable U s of a pq element E(s) is an output variable Y.
To begin with, deletion processing for deleting a registered vector of the objective logic function F(X) is described. FIG. 7 is a flowchart showing the deletion processing for deleting a registered vector of the objective logic function F(X) with the reconfiguration circuit 1 .
In this example, reconfiguration of the multilevel logic network 10 following logic modification for deleting a registered vector of the objective logic function F(X) b is discussed. Here, a part value of the input vector b for a part variable X i of the input variable X is represented by b i .
First, in step S 1 , when a target registered vector b is applied, means to select element 2 sets the index i to s. The index i is an index indicating a number of a selected pq element. With this operation, the nearest pq element E(s) to an output side is selected.
Next, in step S 2 , means to select element 2 reads an LUT of the pq element E(i).
Next, in step S 3 , means to modify by deleting a vector 5 sets an output vector u i (b) corresponding to the input vector b as 0 in the read LUT. The output vector u i (b) corresponding to the input vector b is an output vector corresponding to a part value b, and an output vector (b) of a previous pq element E(i−1). The output vector u i−1 (b) of the previous pq element E(i−1) can be obtained by applying the input vector b to the multilevel logic network 10 and executing calculation to derive an intermediate variable U 11 .
Next, in step S 4 , the modified LUT is written to the pq element E(i) to thereby update the pq element E(i).
Next, in step S 5 , means to select element 2 determines whether the index i is 2 or more. If the index i is 1, the registered vector deletion processing is terminated, and otherwise, the processing advances to the next step S 6 .
In step S 6 , means to select element 2 decrements the index i indicating a number of a selected element by 1.
Next, in step S 7 , means to select element 2 reads an LUT of the pq element E(i).
Next, in step S 8 , means to check correspondence 4 extracts an output vector u i (b) corresponding to the input vector b of the pq element E(i). The output vector u i (b) corresponding to the input vector b is an output vector corresponding to a part value b i and an output vector u i−1 (b) of a previous pq element E(i−1) (part value b i if i=1). The output vector u i−1 (b) of the previous pq element E(i−1) can be obtained by applying the input vector b to the multilevel logic network 10 and executing calculation to derive an intermediate variable U i−1 .
Next, in step S 9 , means to check correspondence 4 determines whether any input vector corresponds to the output vector u i (b) besides the input vector b. The determination is completed by checking an output value of an LUT and checking whether two or more vectors take the same value as the output vector u i (b). If two or more input vectors corresponding to the output vector are found, the registered vector deletion processing is terminated, and otherwise, the processing returns to step S 3 .
Through the series of processings, it is possible to execute the reconfiguration of the multilevel logic network 10 following the logic modification for deleting the registered vector of the objective logic function F(X) b. This processing only requires an operation of reading and rewriting an LUT of the pq element E(i) and thus can be performed at high speeds. Further, since this processing does not require complicated computation processing, means to select element 2 , means to check correspondence 4 , and means to modify by deleting a vector 5 can be implemented with a simple circuit.
Next, addition processing for adding a registered vector of the objective logic function F(X) is described. FIG. 8 is a flowchart showing the addition processing for adding a registered vector of the objective logic function F(X) with the reconfiguration circuit 1 .
In this example, following logic modification for adding a registered vector of the objective logic function F(X) b, reconfiguration of the multilevel logic network 10 is performed. Here, an output vector of the objective logic function F(X) corresponding to a registered vector b is represented by a, and a part value of the input vector b corresponding to the part variable X i of the input variable X is represented by b i .
First, in step S 11 , when the registered vector b to be added and the output vector a are applied, means to select element 3 sets the index i indicating the number of a selected pq element as 1. As a result, the nearest pq element E(1) to the input side is selected.
Next, in step S 12 , means to select element 3 reads an LUT of the pq element E(i).
Next, in step S 13 , means for association 6 determines whether the index i is the maximum value s. If i=s, the processing advances to step S 20 , and otherwise, to the next step S 14 .
In step S 14 , means for association 6 calculates an output vector u i (b) corresponding to the input vector b in the read LUT. The output vector u i (b) corresponding to the input vector b is an output vector corresponding to the part value b i and the output vector u i−1 (b) of the previous pq element E(i−1) (part value b i if i=1). The output vector u i−1 (b) of the previous pq element E(i−1) can be obtained by applying the input vector b to the multilevel logic network 10 and executing calculation to derive an intermediate variable U i−1 .
Next, in step S 15 , means for association 6 determines whether the output vector u i (b) is 0. If u i (b)≠0, the processing advances to step S 19 . If s=0, the processing advances to the next step S 16 .
In step S 16 , means for association 6 checks output vectors of the LUT of the pq element E(i) to extract the minimum value (vector) e among values unused as an output vector.
Next, in step S 17 , means for association 6 changes the output vector u i (b) corresponding to the input vector b of the LUT of the pq element E(i) to e.
Next, in step S 18 , means for association 6 writes the updated LUT to the pq element E(i) to thereby update the pq element E(i).
Next, in step S 19 , means to select element 3 increments the index i indicating a number of a selected element by 1 and the processing returns to step S 12 .
On the other hand, in step S 13 , if i=s, in step S 20 , means to modify by adding a vector 7 changes the output vector u i (b) corresponding to the input vector b of the LUT of the pq element E(i) to the output vector a.
Then, in step S 21 , means to modify by adding a vector 7 writes the updated LUT to the pq element E(i) to thereby update the pq element E(i).
Through the series of processings, it is possible to execute the reconfiguration of the multilevel logic network 10 following the logic modification for adding the registered vector of the objective logic function F(X) b. This processing only requires an operation of reading and rewriting an LUT of the pq element E(i) and thus can be performed at high speeds. Further, since this processing does not require complicated computation processing, means to select element 2 and means to modify by deleting a vector 5 can be implemented with a simple circuit.
Further, in the multilevel logic network 10 of this embodiment, reconfiguration can be executed only by rewriting a memory. More specifically, it is necessary to change wiring structure along with the reconfiguration of the multilevel logic network 10 . Thus, the reconfiguration can be easily carried out without considering an influence of wiring delay etc. Moreover, the logic circuit can be dynamically reconfigured in real time during operations of the logic circuit.
Example 5
An address generation function F(X) involving five variables as shown in Table 5 is explained.
TABLE 5
Functional decomposition {F(X)=G(H(X 1 ), X 2 )} is executed on partition X of the input variable X; partition X=(X 1 , X 2 ), X 1 =(x 5 , x 4 , x 3 , x 2 ), X 2 =(x 1 ). As a result, the address generation function F(X) is obtained using an LUT cascade logic circuit including two pq elements as shown in FIG. 9 . In this example, truth tables of subfunctions H and G are Tables 6 and 7. The truth table (Table 6) of the subfunction H is stored as an LUT in a pq element on the input side. Further, the truth table (Table 7) of the subfunction G is stored as an LUT in a pq element on the output side. Numerical values on the left of each row in Tables 6 and 7 each indicate an index of a registered vector in each row.
TABLE 6
TRUTH TABLE FOR FUNCTION H
TABLE 7
TRUTH TABLE FOR FUNCTION G
A registered vector b 7 {b 7 =(x 5 x 4 x 3 x 2 x 1 )=(11001)} of the address generation function F(X) is added. Table 8 is a truth table for the registered vector b 7 . An output vector corresponding to the registered vector b 7 is given (111).
TABLE 8
Next, an LUT of each pq element is rewritten in accordance with a procedure of the flowchart of FIG. 8 . Here, an output vector corresponding to the input vector b of a subfunction H stored in the pq element on the input side is (h 1 , h 2 , h 3 )=(110) with reference to the record of (x 5 x 4 x 3 x 2 )=(1100) in Table 6. Since this value is not 0, an LUT for the subfunction H is not changed. In this case, the input vector b is associated with the record of (x 5 x 4 x 3 x 2 )=(1100) as shown in Table 9.
TABLE 9
TRUTH TABLE FOR FUNCTION H
Next, considering the subfunction G stored in the pq element on the output side, an input vector of the subfunction G corresponding to the input vector b is {(h 1 , h 2 , h 3 x 1 )=(1101)}. Thus, as shown in Table 10, {(h 1 , h 2 , h 3 x 1 f 1 f 2 f 3 )=(1101111)} is added to an LUT for the subfunction G. Thus, reconfiguration of each pq element following the addition of the registered vector b 7 is completed.
TABLE 10
TRUTH TABLE FOR FUNCTION G
Next, reconfiguration of each pq element following deletion of a registered vector is explained. The case of deleting a registered vector b 3 {b 3 =(01100)} from vectors registered in an address table (Table 5) is described by way of example.
An LUT of the pq element on the output side is first rewritten in accordance with a procedure of the flowchart of FIG. 7 . Referring to Table 10, an input vector of the subfunction G corresponding to the registered vector b 3 is {(h 1 , h 2 , h 3 x 1 )=(0110)}. An output vector corresponding to this vector is changed to (000), and the LUT of the pq element on the output side is rewritten as shown in Table 11.
TABLE 11
TRUTH TABLE FOR FUNCTION G
Next, the pq element on the input side is considered. In this case, as is apparent from the truth table for the subfunction G not updated (Table 10), b 4 =(01111) is listed as a registered vector, an output vector (h 1 , h 2 , h 3 ) of a previous LUT of which has nonzero output similar to the output vector (011) for the registered vector b 3 besides b 3 . Thus, an LUT of the pq element on the input side is not rewritten. With this operation, reconfiguration of each pq element following the deletion of the registered vector b 3 is completed.
Next, the case of additionally deleting the registered vector b 4 {b 4 =(01101)} is considered. An LUT of the pq element on the output side is first rewritten in accordance with a procedure of the flowchart of FIG. 7 . Referring to Table 9, an input vector of the subfunction G corresponding to the registered vector b 4 is {(h 1 , h 2 , h 3 x 1 )=(0111)}. An output vector corresponding to the input vector is changed to (000), and the LUT of the pq element on the output side is rewritten as shown in Table 12.
TABLE 12
TRUTH TABLE FOR FUNCTION G
Next, the pq element on the input side is considered. In this case, as is apparent from the truth table for the subfunction G not updated (Table 11), there is no registered vector, an output vector (h 1 , h 2 , h 3 ) of a previous LUT of which has nonzero output similar to an output vector (011) for the registered vector b 4 . Therefore, an output vector {(h 1 , h 2 , h 3 )=(100)} corresponding to an input vector {(x 5 x 4 x 3 x 2 )=(0111)} of the subfunction H corresponding to the registered vector b 4 is changed to (000) with respect to the pq element on the input side. Thus, an LUT of the pq element on the input side is updated as shown in Table 13. In this way, reconfiguration of each pq element following the deletion of the registered vector b 4 is completed.
TABLE 13
TRUTH TABLE FOR FUNCTION H
(End of Example)
Second Embodiment
FIG. 10 shows the configuration of a device to modify logic networks 20 according to a second embodiment of the present invention. In FIG. 10 , a main logic circuit 30 is a logic circuit subjected to logic modification, which is a memory configured as a specific LSI (ASIC), a CPU, or the like. It is assumed that an input variable of the main logic circuit 30 is {X=(x 1 x 2 . . . x n )(εB n , B={0, 1})}, an output variable thereof is {Q=Q(X)=(q 1 q 2 . . . q m ) (εB m )}, and an output variable modified with the device to modify logic networks 20 is {Q′=(q 1 ′ q 2 ′ . . . q m ′) (εB m )}. The main logic circuit 30 operates an objective logic function Q(X) for the input variable X.
The device to modify logic networks 20 changes an output vector Q(b i ) of the main logic circuit 30 corresponding to a particular object input vector b i among input vectors b applied as the input variable X, to a modification output vector Q′(b i ). The device to modify logic networks 20 includes an address generation circuit 21 , an auxiliary memory 22 , a modifying circuit 23 , and the reconfiguration circuit 1 . Here, the reconfiguration circuit 1 is similar to the reconfiguration circuit 1 for a multilevel logic network described in the first embodiment.
The auxiliary memory 22 is such that a vector for modification {P i =(p i1 p i2 . . . p im )} for modifying each output vector Q(b i ) to the modification output vector Q′(b i ) in accordance with each object input vector b i is registered at a prescribed address A i . The auxiliary memory 22 produces the vector for modification P i if the address A i at which the vector for modification P i is registered is applied, and otherwise, produces 0 as an “invalid value”.
If the vector for modification P i produced from the auxiliary memory 22 is produced, the modifying circuit 23 produces a modification output vector Q i ′ based on the vector for modification P i and the output vector Q(b i ) produced from the main logic circuit 30 . In the second embodiment, the modifying circuit 23 is configured by EXOR gates 24 provided for each output line of the main logic circuit 30 . Each EXOR gate 24 calculates the modification output vector Q i ′=(q i1 ′, q i2 ′, . . . , q im ′) through exclusiveOR operation between elements q 1 , q 2 , . . . , q m of the output vector Q and elements p i1 , p i2 , . . . , p im of the vector for modification P i .
q′ j =q j ⊕p ij ( i= 1,2 , . . . , k; j= 1,2, . . . , m ) (12)
Thus, a value of the vector for modification P i is set so as to obtain a target modification output vector Q i ′ based on above Expression (12).
The address generation circuit 21 produces an address of the auxiliary memory 22 in accordance with each input vector b applied as the input variable X. In this example, the address generation circuit 21 operates an address generation function F(X) to produce an address A i where a vector for modification P i is registered, for each object input vector b i and produce an “invalid value” (0) for the other input vectors b.
Further, the address generation circuit 21 is configured by a multilevel logic network including the above pq elements connected in multiple stages.
The reconfiguration circuit 1 reconfigures an LUT of each q element of the address generation circuit 21 , following the modification of the address generation function F(X) operated by the address generation circuit 21 . The reconfiguration process is similar to that of the first embodiment.
Operations of the thusconfigured device to modify logic networks 20 of the second embodiment will be described hereinbelow.
First, if input vectors b other than an object input vector b i are applied as the input variable X, the address generation circuit 21 produces 0 (“invalid value”) as an output vector a. Thus, the auxiliary memory 22 produces 0 as a vector for modification P. Each EXOR gate 24 operates and produces exclusive OR between an output value q j of the main logic circuit 30 and 0 , that is, the output value q j . Accordingly, in this case, the output vector Q is not modified and produced as it is.
On the other hand, if an object input vector b i is applied as the input variable X, the address generation circuit 21 produces an address value Ai of the auxiliary memory 22 , where the vector for modification P i is stored as the output vector a. Thus, the auxiliary memory 22 produces a vector for modification P i as a vector for modification P. Each EXOR gate 24 operates and produces exclusive OR (q ij ′) between the output value q j of the main logic circuit 30 and an element p ij of the vector for modification. In this way, the output vector is modified.
In this embodiment, since the multilevel logic network configuring by connecting pq elements in multiple stages is used as the address generation circuit 21 , footprint of the device to modify logic networks 20 can be reduced. Further, even if logic modification is additionally executed, the address generation circuit 21 can be easily reconfigured using the reconfiguration circuit 1 .
Third Embodiment
FIG. 11 shows the configuration of the device to modify logic networks 20 according to a third embodiment of the present invention. In FIG. 11 , the reconfiguration circuit 1 , the address generation circuit 21 , the auxiliary memory 22 , and the main logic circuit 30 are the same as those of FIG. 10 . In this embodiment, the auxiliary memory 22 stores the modification output vector Q i ′ as it is for each object input vector b i . Further, a tristate buffer (not shown) is provided as means to modify at an output stage of the main logic circuit 30 and the auxiliary memory 22 .
If the address generation circuit 21 produces an “invalid value” if the input variable X applied from the input bus 31 is not equal to the object input vector b i . The tristate buffer at the output stage of the main logic circuit 30 is in a highimpedance state if an output value of the address generation circuit 21 is not an “invalid value”, and otherwise, in a lowimpedance state. Further, the tristate buffer at the output stage of the auxiliary memory 22 is in a highimpedance state if an output value of the address generation circuit 21 is not an “invalid value”, and otherwise, in a lowimpedance state.
Thus, if a value of the input variable X is not equal to the object input vector b i , an output vector of the main logic circuit 30 is produced to the output bus 32 . If a value of the input variable X is equal to the object input vector b i , an output vector of the auxiliary memory 22 is produced to the output bus 32 .
Fourth Embodiment
FIG. 12 shows the configuration of a reconfigurable multilevel logic network according to a fourth embodiment of the present invention. In FIG. 12 , the same components as those of FIG. 15 are denoted by identical reference numerals.
In the reconfigurable multilevel logic network of this embodiment, a reconfiguration circuit 1 ′ additionally includes an index table 8 and a reference table 9 .
As described in the first embodiment, the multilevel logic network 10 is a logic circuit for operating an objective logic function F(X) with an input variable X. The multilevel logic network 10 is a logic circuit including plural pq elements 13 connected in multiple stages. To specifically describe the configuration of the multilevel logic network 10 , the network may be configured using an LUT cascade logic circuit including plural cascaded pq elements 13 (see FIGS. 6 and 15 ) or an LUT tree logic circuit including plural treeconnected pq elements 13 (see FIGS. 2 to 4 ).
The reconfiguration circuit 1 reconfigures the multilevel logic network 10 following the logic modification of the multilevel logic network 10 . The reconfiguration circuit 1 includes means to select element 2 , means to select element 3 , means to check correspondence 4 , means to modify by deleting a vector 5 , means for association 6 , means to modify by adding a vector 7 , the index table 8 , and the reference table 9 . Means to select element 2 , means to select element 3 , means to check correspondence 4 , means to modify by deleting a vector 5 , means to modify by adding a vector 7 , and means for association 6 are the same as those of the first embodiment and thus not described here.
Here, the pq element 13 is not limited to a memory but may be any other circuit having a function similar to the memory.
For example, in FIG. 13 , a 4input LUT used in the Xilinx FPGA is used. The 4input LUT includes 16 synchronous Dflipflops 41 _ 0 to 41 _ 15 and one 16input/1output multiplexer 42 .
This 4input LUT can be used as a shift register by switching its mode and can be rewritten.
In FIG. 13( a ), a mode is set to an SRL16 mode. In this mode, clocks are applied from clock line 43 to each of the DFFs 41 _ 0 to 41 _ 15 . Thus, the DFFs 41 _ 0 to 41 _ 15 can function as a shift register. In this state, registration data is applied from a registered value input line 44 in a serial form to thereby store the registration data in the DFFs 41 _ 0 to 41 _ 15 .
On the other hand, in FIG. 13( b ), a mode is set to a 4input LUT mode. In this mode, no clock is applied to the clock line 43 , and this circuit functions as an LUT. If 4bit data is applied from a data input line 45 to the MUX 42 , the MUX 42 selects one of the DFFs 41 _ 0 to 41 _ 15 based on the input data and produces data stored in the selected DFF. Thus, the circuit functions as a 4input/1output LUT.
FIG. 14 shows a 12input/1output circuit using three 4input LUTs. As shown in FIG. 14 , the circuit can operate AND of outputs of plural LUTs together with the multiplexer in the FPGA. Since this circuit is a 1output circuit, output data of plural bits can be obtained by arranging as many circuits of FIG. 14 as a requisite number of bits, in parallel.
The LUT as shown in FIG. 13 may be used as the pq element 13 .
The reference table 9 stores rail vectors being assigned to each pq element 13 .
The term “rail” means a connection line connected to an input of a pq element in a subsequent stage out of output lines of a pq element in a previous stage in a multilevel logic network including plural pq element connected in multiple stages.
FIG. 15 shows a general LUT cascade logic circuit. Among the output lines of a pq element E(1) in FIG. 15 , a line connected to an input of a pq element E(2) is “rail”. Further, among the output lines of the pq element E(2), a line connected to an input of a pq element E(3) is “rail”. The same applies to subsequent lines. The rails of the LUT tree logic circuits in FIGS. 2 to 4 are similarly defined.
The term “rail vector” means a vector of an output variable produced to a rail on the output side of a particular pq element.
FIG. 16 shows an example of the reference table 9 . The reference table 9 is provided for each pq element of the multilevel logic network 10 in a onetoone correspondence. The reference table 9 provided for one pq element lists rail vectors of the pq element and the number of referenced vectors corresponding thereto. Here, the term the “number of referenced vectors” means the number of registered vector referencing the rail vector.
The index table 8 stores information about whether a vector is being registered. In this example, only one index table 8 is provided. FIG. 17 shows an example of the index table. The index table 9 includes indexes assigned to each registerable vector and a corresponding registration flag indicating whether a registered vector is registered (used).
Registered vector addition/deletion operations of the thusconfigured reconfigurable multilevel logic network of this embodiment will be described hereinbelow.
For ease of illustration, it is assumed that the LUT cascade logic circuit as shown in FIG. 6 is used as the multilevel logic network 10 .
(1) Addition of Registered Vector
In the reconfigurable multilevel logic network of this embodiment, in the case of adding a new registered vector, the index table 8 and the reference table 9 are used to shorten processing time.
FIG. 18 is a flowchart showing registered vector addition processing in the reconfigurable multilevel logic network of the fourth embodiment.
First, in step S 31 , an input vector b to be registered is applied to the reconfiguration circuit 1 ′.
Next, in step S 32 , means to modify by adding a vector 7 references the index table 8 to check whether the input vector b has been registered in the multilevel logic network 10 . If the registration flag is set to 1 for the input vector b in the index table 8 , the processing is terminated.
Next, in step S 33 , means to select element 3 sets the index i indicating a number of a selected element to 1.
Next, in step S 34 , means for association 6 applies the input vector b to the multilevel logic network 10 and reads an output vector u i (b) of a pq element E(i).
Next, in step S 35 , means for association 6 determines whether the output vector u i (b) is 0. If the output vector is 0, the processing advances to step S 38 . If the output vector is not 0, the processing advances to the next step S 36 .
Next, in step S 36 , means for association 6 searches the reference table 9 for the pq element E(i) to find one unreferenced rail vector a. Then, in step S 37 , means to modify by adding a vector 7 rewrites a memory of the pq element E(i) so as to set the output vector u i (b) of the pq element E(i) as the rail vector a.
In step S 38 , means for association 6 increments the number of referenced vectors corresponding to the registered vector u 1 (b) in the reference table for the pq element E(i) by 1.
Next, in step S 39 , means to select element 3 increments the index i indicating a number of a selected element by 1.
Next, in step S 40 , means to select element 3 determines whether i=s. If i<s, the processing returns to step S 34 . If i=s, the processing advances to the next step S 41 .
In step S 41 , means to modify by adding a vector 7 rewrites a memory of a pq element E(s) to set an output vector u s (b) of the pq element E(s) to F(b).
Finally, in step S 42 , means to modify by adding a vector 7 sets the registration flag for the registered vector b to 1 in the index table 8 and terminates the registered vector addition processing.
(2) Deletion of Registered Vector
FIG. 19 is a flowchart showing registered vector deletion processing in the reconfigurable multilevel logic network of the fourth embodiment.
First, in step S 51 , an input vector b to be deleted is applied to the reconfiguration circuit 1 ′.
Next, in step S 52 , means to modify by deleting a vector 5 references the index table 8 to check whether the input vector b is being registered in the multilevel logic network 10 . If a registration flag for the input vector b is set to 0 in the index table 8 , the registered vector deletion processing is terminated.
Next, in step S 53 , means to select element 2 sets the index i indicating a number of a selected element to s.
Next, in step S 54 , means to check correspondence 4 applies the input vector b to the multilevel logic network 10 and reads an output vector u i (b) of the pq element E(i).
Next, in step S 55 , means to check correspondence 4 decrements the number of referenced vectors corresponding to the registered vector u i (b) in the reference table for the pq element E(i) by 1. However, if the number of referenced vectors corresponding to the registered vector u i (b) is 0, the number of referenced vectors corresponding to the registered vector u i (b) is kept 0.
Next, in step S 56 , means to modify by deleting a vector 5 determines whether the number of referenced vectors corresponding to the registered vector u i (b) is 0. If the number of referenced vectors corresponding to the registered vector u i (b) is not 0, the processing returns to step S 58 . If the number of referenced vectors is 0, the processing advances to the next step S 57 .
In step S 57 , means to modify by deleting a vector 5 rewrites a memory of the pq element E(i) so as to set an output vector u i (b) of the pq element E(i) to 0.
In step S 58 , means to select element 2 decrements the index i indicating a number of a selected element by 1.
Next, in step S 59 , means to select element 2 determines whether i=0. If i>0, the processing returns to step S 54 . If i=0, the processing advances to the next step S 60 .
In step S 60 , means to modify by deleting a vector 5 sets a registration flag for the registered vector b to 0 in the index table 8 and terminates the registered vector deletion processing.
The number of steps necessary to add one registered vector to the multilevel logic network 10 in the above processing can be estimated based on the following expression.
Add cas −Op.Cas+s(Op.Cas+k×Acc.Mem+Acc.Mem) (13)
In this expression, OP.Cas represents the number of steps necessary to access the LUT cascade, Acc.Mem represents the number of steps necessary to access the reference table, s represents the number of cells, and k represents the number of registered vectors. The first term gives the estimated number of steps necessary to perform processing in steps S 31 to S 34 in the registered vector addition processing, and the second term gives the estimated number of steps necessary to perform the other processing.
Likewise, the number of steps necessary to delete one registered vector from the multilevel logic network 10 can be estimated based on the following expression.
Del cas −Op.Cas+s(Op.Cas+Acc.Mem) (14)
The first term gives the estimated number of steps necessary to perform processing in steps S 51 to S 54 in the registered vector deletion processing, and the second term gives the estimated number of steps necessary to perform the other processing.
As apparent from Expressions (13) and (14), if the multilevel logic network 10 is an LUT cascade logic circuit, the number of steps necessary to add a registered vector is almost proportional to s and k, and the number of steps necessary to delete a registered vector is almost proportional to s.