Method for optimizing area of ternary FPRM circuit using population migration algorithm

A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, comprises the following steps:

1) Establishing an area estimation model of the ternary FPRM circuit:

11) The ternary FPRM circuit is expressed by a ternary FPRM logic function expression as follows:

where n is the number of variables of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), x n-1 , x n-2 , . . . , x 0 denotes the n input variables of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), p denotes a polarity of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), the polarity p is expressed in ternary form as p n-1 p n-2 . . . p 0 , p j ϵ{0, 1, 2}, j=0, 1, 2, . . . , n−1, ⊕ represents a modulo-3 addition operation, Σ is a summation sign, the symbol “*” represents multiplication, subscript i=0, 1, 2, . . . , 3 n −1, i is expressed in ternary form as i n-1 i n-2 . . . i 0 , a i is a coefficient of FPRM expansion, a i ϵ{0, 1, 2}; Π represents a modulo-3 multiplication operation,

∏ j = 0 n - 1 ⁢ ⁢ x . j i j

has its expansion as follow:

∏ j = 0 n - 1 ⁢ ⁢ x . j i j = x . n - 1 i n - 1 ⁢ x . n - 2 i n - 2 ⁢ ⁢ … ⁢ ⁢ x . 0 i 0 ,

where i j ϵ{0, 1, 2}, {dot over (x)} j =(x j ⊕p j ), {dot over (x)} j 0 =1, {dot over (x)} j 1 ={dot over (x)} j , {dot over (x)} j 2 ={dot over (x)} j *{dot over (x)} j , polarity p and subscript i determine the representation of the variable {dot over (x)} j ;

12) The ternary FPRM logic function under polarity p is composed of two types of multi-input operations which are a multi-input modulo-3 addition operation and a multi-input modulo-3 multiplication operation respectively; based on expansion of a ternary FPRM logic function, the ternary FPRM logic function is decomposed into several multi-input modulo-3 addition operations and several multi-input modulo-3 multiplication operations, then each multi-input operation is individually decomposed into 2-input operations, to obtain 2-input modulo-3 addition operations and 2-input modulo-3 multiplication operations; specifically, the decomposition process is as follows:

The 1 st and the 2 nd input variables of a multi-input operation are taken as two input variables of a first 2-input operation, to obtain an output variable of the first 2-input operation; the output variable of the first 2-input operation and the 3 rd input variable of the multi-input operation are taken as two input variables of a second 2-input operation, to obtain an output variable of the second 2-input operation; the output variable of the second 2-input operation and the 4 th input variable of the multi-input operation are taken as two input variables of a third 2-input operation, to obtain an output variable of the third 2-input operation; and so forth, till all the input variables of the multi-input operation have been taken as an input variable of a 2-input operation, thereby accomplishing the decomposition of the multi-input operation;

The ternary FPRM logic function under polarity p is decomposed into several multi-input modulo-3 addition operations (also referred to as multi-input modulo-3 addition gates) and several multi-input modulo-3 multiplication operations (also referred to as multi-input modulo-3 multiplication gates), then represent N to denote the number of the multi-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p, and represent W to denote the number of the multi-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; each multi-input modulo-3 addition operation is decomposed into several 2-input modulo-3 addition operations (also referred to as 2-input modulo-3 addition gates), and each multi-input modulo-3 multiplication operation is decomposed into several 2-input modulo-3 multiplication operations (also referred to as 2-input modulo-3 multiplication gates); the number of the 2-input modulo-3 addition gates resulted from the decomposition of the h th multi-input modulo-3 addition gate is denoted as No h ._of_Mod 3−A p , h=1, 2, . . . , N; the number of the 2-input modulo-3 multiplication gates resulted from the decomposition of the w th multi-input modulo-3 multiplication gate is denoted as No w ._of_Mod 3−M p , w=1, 2, . . . , W;

Represent

S = ∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod ⁢ ⁢ 3 - A p + ∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod ⁢ ⁢ 3 - M p

be an area estimation model of the ternary FPRM circuit, where S represents the area;

∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod ⁢ ⁢ 3 - A p

represents the total number of 2-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod ⁢ ⁢ 3 - M p

represents the total number of 2-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

2) Establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm:

Population migration algorithm includes the following key factors: population location, attraction of population location, the greatest attractive site, the greatest attraction, ground space of population mobility, concession region, population mobility, population migration and population disperse; the area optimization of the ternary FPRM circuit includes the following key factors: polarity, area size corresponding to polarity, optimal polarity, minimum area, optional polarity space, the zone where the optimal polarity exists, polarity jump to the zone where the optimal polarity exists and jump out of the local optimal polarity;

The population location is mapped to area optimization of the ternary FPRM circuit, and represented as polarity; the attraction of the population location is mapped to area optimization of the ternary FPRM circuit, and represented as the area size corresponding to the polarity; the greatest attractive site is mapped to area optimization of the ternary FPRM circuit, and represented as the optimal polarity; the greatest attraction is mapped to area optimization of the ternary FPRM circuit, and represented as the minimum area; the ground space of population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as an optional polarity space; the concession region is mapped to area optimization of the ternary FPRM circuit, and represented as the zone where the optimal polarity exists; the population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as polarity transition; the population migration is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump to the zone where the optimal polarity exists; the population disperse is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump out of the local optimal polarity;

3) Setting an attraction function for calculating the attraction of the population location in population migration algorithm:

According to the area estimation model, an attraction function for calculating the attraction of the population location in population migration algorithm is set as follows: in population migration algorithm, greater attraction indicates higher economic level of the population location, whereas the area-optimal polarity requires the area to be as small as possible, and therefore, in order to combine both conditions, the reciprocal of the area is employed to represent the attraction, and the attraction function is obtained as follows:

where the symbol “/” denotes a division operation, and attraction represents attraction value, greater attraction value indicates better area optimization effect of the circuit; α is a magnification coefficient, its value is equal to a natural number greater than 1000;

4) Setting relevant parameters of population migration algorithm:

Population migration algorithm has five parameters to be set: population scale s, the number of population mobility times l, population pressure parameter q, shrinkage factor c, and the number of population disperse times z;

Represent the population scale s be equal to the number of input variables of the ternary FPRM logic function, i.e., s=n; the number of population mobility times l is the radius of the region where the population exists, and the radius where the population exists is denoted as Δt, l=Δt, Δt=3 s /s 2 ; the population pressure parameter q is Δt/10; the shrinkage factor c=0.3; when the ternary FPRM circuit is a small-scale circuit, the number of population disperse times z=15, and when the ternary FPRM circuit is a large-scale circuit, the number of population disperse times z=2; a large-scale circuit usually refers to a circuit having 4 or more input variables, and a small-scale circuit usually refers to a circuit having 4 or less input variables;

5) Employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

In this embodiment, an existing mature ternary-FPRM-polarity transform technology is employed to obtain expansion of the ternary FPRM logic function, and population migration algorithm also utilizes an existing mature technology.

A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, comprises the following steps:

1) Establishing an area estimation model of the ternary FPRM circuit:

11) The ternary FPRM circuit is expressed by a ternary FPRM logic function expression as follows:

where n is the number of variables of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), x n-1 , x n-2 , . . . , x 0 denotes the n input variables of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), p denotes a polarity of the function ƒ p (x n-1 , x n-2 , . . . , x 0 ), the polarity p is expressed in ternary form as p n-1 p n-2 . . . p 0 , p j ϵ{0, 1, 2}, j=0, 1, 2, . . . , n−1, ⊕ represents a modulo-3 addition operation, Σ is a summation sign, the symbol “*” represents multiplication, subscript i=0, 1, 2, . . . , 3 n −1, i is expressed in ternary form as i n-1 i n-2 . . . i 0 , a i is a coefficient of FPRM expansion, a i ϵ{0, 1, 2}; Π represents a modulo-3 multiplication operation,

∏ j = 0 n - 1 ⁢ ⁢ x . j i j

has its expansion as follow:

∏ j = 0 n - 1 ⁢ x . j i j = x . n - 1 i n - 1 ⁢ x . n - 2 i n - 2 ⁢ ⁢ … ⁢ ⁢ x . 0 i 0 ,

where i j ϵ{0, 1, 2}, {dot over (x)} j =(x j ⊕p j ), {dot over (x)} j 0 =1, {dot over (x)} j 1 ={dot over (x)} j , {dot over (x)} j 2 ={dot over (x)} j *{dot over (x)} j , polarity p and subscript i determine the representation of the variable {dot over (x)} j ;

12) The ternary FPRM logic function under polarity p is composed of two types of multi-input operations which are a multi-input modulo-3 addition operation and a multi-input modulo-3 multiplication operation respectively; based on expansion of a ternary FPRM logic function, the ternary FPRM logic function is decomposed into several multi-input modulo-3 addition operations and several multi-input modulo-3 multiplication operations, then each multi-input operation is individually decomposed into 2-input operations, to obtain 2-input modulo-3 addition operations and 2-input modulo-3 multiplication operations; specifically, the decomposition process is as follows:

The 1 st and the 2 nd input variables of a multi-input operation are taken as two input variables of a first 2-input operation, to obtain an output variable of the first 2-input operation; the output variable of the first 2-input operation and the 3 rd input variable of the multi-input operation are taken as two input variables of a second 2-input operation, to obtain an output variable of the second 2-input operation; the output variable of the second 2-input operation and the 4 th input variable of the multi-input operation are taken as two input variables of a third 2-input operation, to obtain an output variable of the third 2-input operation; and so forth, till all the input variables of the multi-input operation have been taken as an input variable of a 2-input operation, thereby accomplishing the decomposition of the multi-input operation;

The ternary FPRM logic function under polarity p is decomposed into several multi-input modulo-3 addition operations (also referred to as multi-input modulo-3 addition gates) and several multi-input modulo-3 multiplication operations (also referred to as multi-input modulo-3 multiplication gates), then represent N to denote the number of the multi-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p, and represent W to denote the number of the multi-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; each multi-input modulo-3 addition operation is decomposed into several 2-input modulo-3 addition operations (also referred to as 2-input modulo-3 addition gates), and each multi-input modulo-3 multiplication operation is decomposed into several 2-input modulo-3 multiplication operations (also referred to as 2-input modulo-3 multiplication gates); the number of the 2-input modulo-3 addition gates resulted from the decomposition of the h th multi-input modulo-3 addition gate is denoted as No h ._of_Mod 3−A P , h=1, 2, . . . , N; the number of the 2-input modulo-3 multiplication gates resulted from the decomposition of the w th multi-input modulo-3 multiplication gate is denoted as No w ._of_Mod 3−M p , w=1, 2, . . . , W;

Represent

S = ∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod3 - A p + ∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod3 - M p

be an area estimation model of the ternary FPRM circuit, where S represents the area;

∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod3 - A p

represents the total number of 2-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod3 - M p

represents the total number of 2-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

2) Establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm:

Population migration algorithm includes the following key factors: population location, attraction of population location, the greatest attractive site, the greatest attraction, ground space of population mobility, concession region, population mobility, population migration and population disperse; the area optimization of the ternary FPRM circuit includes the following key factors: polarity, area size corresponding to polarity, optimal polarity, minimum area, optional polarity space, the zone where the optimal polarity exists, polarity jump to the zone where the optimal polarity exists and jump out of the local optimal polarity;

The population location is mapped to area optimization of the ternary FPRM circuit, and represented as polarity; the attraction of the population location is mapped to area optimization of the ternary FPRM circuit, and represented as the area size corresponding to the polarity; the greatest attractive site is mapped to area optimization of the ternary FPRM circuit, and represented as the optimal polarity; the greatest attraction is mapped to area optimization of the ternary FPRM circuit, and represented as the minimum area; the ground space of population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as an optional polarity space; the concession region is mapped to area optimization of the ternary FPRM circuit, and represented as the zone where the optimal polarity exists; the population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as polarity transition; the population migration is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump to the zone where the optimal polarity exists; the population disperse is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump out of the local optimal polarity;

3) Setting an attraction function for calculating the attraction of the population location in population migration algorithm:

According to the area estimation model, an attraction function for calculating the attraction of the population location in population migration algorithm is set as follows: in population migration algorithm, greater attraction indicates higher economic level of the population location, whereas the area-optimal polarity requires the area to be as small as possible, and therefore, in order to combine both conditions, the reciprocal of the area is employed to represent the attraction, and the attraction function is obtained as follows:

where the symbol “/” denotes a division operation, and attraction represents attraction value, greater attraction value indicates better area optimization effect of the circuit; α is a magnification coefficient, its value is equal to a natural number greater than 1000;

4) Setting relevant parameters of population migration algorithm:

Population migration algorithm has five parameters to be set: population scale s, the number of population mobility times l, population pressure parameter q, shrinkage factor c, and the number of population disperse times z;

Represent the population scale s be equal to the number of input variables of the ternary FPRM logic function, i.e., s=n; the number of population mobility times l is the radius of the region where the population exists, and the radius where the population exists is denoted as Δt, l=Δt, Δt=3 s /s 2 ; the population pressure parameter q is Δt/10; the shrinkage factor c=0.3; when the ternary FPRM circuit is a small-scale circuit, the number of population disperse times z=15, and when the ternary FPRM circuit is a large-scale circuit, the number of population disperse times z=2; a large-scale circuit usually refers to a circuit having 4 or more input variables, and a small-scale circuit usually refers to a circuit having 4 or less input variables;

5) Employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

In this embodiment, in the step 5), the calculation process of population migration algorithm is as follows:

51) In the ground space of population mobility, a random function rand( ) is employed to generate population locations in number S, and the population locations in number S are denoted as P 1 , P 2 , . . . , Ps, then the P 1 , P 2 , . . . , Ps are taken as center points respectively, so that the regions in number S where the population exists are determined, according to the radiuses of the regions where the population exists;

52) The attraction function is used to calculate the attraction of the population location Pv, v=1, 2, 3, . . . , s, to obtain the attraction of the population locations P 1 , P 2 , . . . , Ps;

53) By comparing the attraction of the population locations P 1 , P 2 , . . . , Ps, the population location with the greatest attraction is selected as the greatest attractive site, then the greatest attractive site and the greatest attraction are recorded;

54) Population mobility is performed: In the population region corresponding to the population location Pv, a random function is employed to randomly generate a population location P′v, to obtain P′ 1 , P′ 2 , . . . , P′s, then P′ 1 , P′ 2 , . . . , P′s is used to update the population locations P 1 , P 2 , . . . , Ps, namely P 1 =P′ 1 , P 2 =2, . . . , Ps=P′s, where P′v=2*Δt*rand( )+(Pv−Δt), the symbol “*” denotes multiplication operation, Δt denotes the radius of the population region; rand( ) the random function;

55) The updated population locations P 1 , P 2 , . . . , Ps in the step 54) are processed by following the steps 52)-53), to obtain the updated greatest attractive site and the updated greatest attraction;

56) Population migration is performed: the updated greatest attractive site in step 55) is taken as the center point, so that the concession region is determined according to the radius Δt of the population region, then a random function rand( ) is employed to generate population locations in number S in the concession region, so that the obtained population locations in number S are used to again update the population locations P 1 , P 2 , . . . , Ps;

57) The updated population locations P 1 , P 2 , . . . , Ps in the step 56) are processed by following the steps 52)-53), to obtain the again updated greatest attractive site and the again updated greatest attraction;

58) Shrinkage of the concession region is performed: Represent Δt′=(1−c)*Δt and employ Δt′ to update Δt, the steps 56)-57) are repeated until Δt<q;

59) After the concession region is shrunk to a certain extent that Δt<q, population disperse is performed: the steps 51)-58) are repeated, until the number of population disperse times z is met, and so the algorithm ends, to obtain the last updated greatest attractive site and the last updated greatest attraction;

510) The last updated greatest attractive site and the last updated greatest attraction are output, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

In this embodiment, in the step 1), a ternary-FPRM-polarity transform technology is employed to obtain the ternary FPRM logic function, and the specific process is as follows:

1) The required polarity of the ternary FPRM circuit is denoted as p, and p is expressed in ternary form as p=p n-1 p n-2 . . . p 0 , where n represents the number of the input variables;

2) For p j , its corresponding fixed-polarity GF transformation matrix G 3 <p j > is generated; where,

3) The minterm M is expressed in ternary form as a sequence M=M n-1 M n-2 . . . M 0 , M j ϵ{0, 1, 2}, and its corresponding function value is denoted as ƒ(M);

4) According to the formula (3), for each minterm, a new term π j is generated, π j ϵ{0, 1, 2}; According to the formula (4), the contribution of the new item to the FPRM coefficients is calculated, and the contribution value is denoted as v(π);

π j ={t|G 3 <p j > [t,M j ]≠0}, tϵ{ 0,1,2}  (3)

v (π)=( v n-1 ·v n-2 . . . v 0 )·ƒ( M )  (4)

where π=π n-1 π n-2 . . . π 0 , v j =G 3 <p j > [π j ,M j ].

5) An index table is employed to record the generated new term and the contribution value of each new tem, if the generated new term already exists, then the contribution values of the identical new items are superimposed and presented as the contribution value of that new item;

6) The steps 3)-4) are repeated for all the minterms, and the contribution values corresponding to respective new terms are the FPRM expansion coefficients;

7) According to the FPRM expansion coefficients, the ternary FPRM logic function expression is obtained.

The area optimization method of the present invention is compared with whole annealing genetic algorithm in regard to their optimization results, through simulation and verification on 10 MCNC Benchmark circuits in Windows 7 64-bit operating system, under the operating environment of Intel® Core™ i3-2130 CPU 3.40 GHZ, 4G RAM, with implementation of C programs compiled with VC6.0.

The search results for the area-optimal polarity of the ternary FPRM circuit are shown in Table 1. in Table 1, column 1 shows the names of the circuits; column 2 indicates the number of input variables of the ternary circuits, respectively; column 3, column 4, column 5 and column 6 indicate the searched optimal polarity, the number of modulo-3 addition operations, the number of modulo-3 multiplication operations and the running time of whole annealing genetic algorithm in order, respectively; column 7, column 8, column 9 and column 10 indicate the searched optimal polarity, the number of modulo-3 addition operations, the number of modulo-3 multiplication operations and the algorithm running time of the method of the present invention in order, respectively.

Compared with whole annealing genetic algorithm, the area-saving and time-saving (in percentage) achieved by the optimization method of the present invention are as shown in Table 2. The percentages of area-saving and time-saving are defined respectively as follows:

where, Save Area represents the area-saving, Save Time represents the time-saving in running the algorithm; Area WAGA represents the optimized area achieved by whole annealing genetic algorithm, Time WAGA represents the optimization time of whole annealing genetic algorithm; Area PMA represents the optimized area achieved by the method of the present invention, Time PMA represents the optimization time of the optimization method of the present invention.

As inferred from analysis of data in Table 2, the area optimization method of the present invention has an obvious effect of optimization. Compared with whole annealing genetic algorithm, the method of the present invention leads to average area-saving of 10.04% and average time-saving of 56.59% on 10 testing circuits.

Unless otherwise indicated, the numerical ranges involved in the invention include the end values. While particular embodiments of the invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications may be made without departing from the invention in its broader aspects, and therefore, the aim in the appended claims is to cover all such changes and modifications as fall within the true spirit and scope of the invention.