Logic Circuit
Partitioning Algorithm Using Evolutionary Computation
Circuit partitioning is a common problem in
VLSI design. It involves dividing a circuit into two or more subsections called
partitions. The set of wires that interconnect between two partitions is called
the cutset. The main goal for this
optimization problem is to find a configuration where the cutset
is as small as possible. A smaller cutset means a
more efficient circuit, since interconnecting wires have a slow transmission
rate. A larger cutset also increases the cost of
manufacturing. If the size of the cutset is too high
then fabricating a circuit implementation may be impossible if it is beyond the
design specifications of the system.
Another criterion that must be taken into
account is the number of circuit elements (“nodes”) in each partition.
If the numbers of nodes in each partition in the circuit are equal, then the
partitions are said to be balanced. A balanced circuit will usually mean
that the chip area is being used efficiently.
The evolutionary computational approach
(sometimes called a genetic algorithm) that was used represents the circuit as
a chromosome. In a chromosome, each node is given a fixed index in an integer
array; and the value at each index determines which partition a node belongs to.
For example, if we wished to place each node in a circuit into either Partition
0 or Partition 1, then the entire circuit configuration could be represented as
a string of ones and zeros called a chromosome.
A unique chromosome exists for every possible
circuit configuration in the solution space. Each chromosome has a weight that
is determined by the size of the cutset and how
balanced the circuit is. The best solution will have the lowest weight. In a
circuit with 10 million nodes, the size of the solution space would be 210,000,000
chromosomes. The best solution of such a problem would probably not be found in
the next 14 billion years when running on the fastest computers of today. For
this reason we do not concern ourselves with trying to find the best solutions,
but only a good solution that is considered acceptable.
In order to solve the problem, an iterative
approach is used. For each iteration a series of techniques
called genetic mutation and genetic crossover are applied to the
chromosomes, resulting in new offspring chromosomes. The best
chromosomes are repeatedly mated and evolved until a solution
with acceptable parameters is declared the winner. The winner will determine
what the final circuit configuration will look like, including which partition
each node will be contained in.
Our program is implemented by reading in a VHDL
file describing the structural configuration of the circuit. This configuration
is converted into a directed hypergraph, and
from there into a chromosome. After the winning chromosome is determined, it is
used to construct a VHDL representation of the resulting partitioned circuit.
Figure 2 shows the results generated by
applying our procedure to the small structural VHDL file given in Figure 1.
|
library IEEE; use IEEE.std_logic_1164.all; entity c17 is port(
PI1, PI2, PI3, PI4, PI5 : in std_logic; PO1, PO2 :
out std_logic); end c17; architecture Structural of c17 is component NAND2 port( E1,
E2 : in std_logic; A : out std_logic); end component; signal G10, G11, G16, G19 : std_logic; begin G10_NAND2 : NAND2 port map( E1 => PI1, E2 =>
PI3, A => G10); G11_NAND2 : NAND2 port map( E1 => PI3, E2 =>
PI4, A => G11); G16_NAND2 : NAND2 port map( E1 => PI2, E2 =>
G11, A => G16); G19_NAND2 : NAND2 port map( E1 => G11, E2 =>
PI5, A => G19); G22_NAND2 : NAND2 port map( E1 => G10, E2 =>
G16, A => PO1); G23_NAND2 : NAND2 port map( E1 => G16, E2 =>
G19, A => PO2); end Structural; |
Figure 1 – VHDL
file to be partitioned (c17.vhd)
|
LIBRARY IEEE; USE IEEE.std_logic_1164.all; ENTITY c17_SKELETON IS PORT ( PI1 :
IN std_logic; PI2 : IN std_logic; PI3 : IN std_logic; PI4 : IN std_logic; PI5 : IN std_logic; PO1 : OUT std_logic; PO2 : OUT std_logic); END c17_SKELETON; ARCHITECTURE Structural OF c17_SKELETON IS COMPONENT c17_PARTITION_0 PORT ( PI1 :
IN std_logic; PI3 : IN std_logic; G16 : INOUT std_logic; PO1 : OUT std_logic); END COMPONENT; COMPONENT c17_PARTITION_1 PORT ( PI4 :
IN std_logic; PI3 : IN std_logic; G16 : INOUT std_logic; G11 : INOUT std_logic; PI2 : IN std_logic); END COMPONENT; COMPONENT c17_PARTITION_2 PORT ( PI5 :
IN std_logic; G16 : INOUT std_logic; PI3 : IN std_logic; G11 : INOUT std_logic; PO2 : OUT std_logic); END COMPONENT; SIGNAL G11 : std_logic; SIGNAL G16 : std_logic; BEGIN P0:c17_PARTITION_0 PORT MAP (PI1, PI3, G16, PO1); P1:c17_PARTITION_1 PORT MAP (PI4, PI3, G16, G11, PI2); P2:c17_PARTITION_2 PORT MAP (PI5, G16, PI3, G11, PO2); END Structural; |
(a) c17_SKELETON.vhd
|
LIBRARY IEEE; USE IEEE.std_logic_1164.all; ENTITY c17_PARTITION_0 IS PORT ( PI1 :
IN std_logic; PI3 : IN std_logic; G16 : INOUT std_logic; PO1 : OUT std_logic); END c17_PARTITION_0; ARCHITECTURE Structural OF c17_PARTITION_0 IS COMPONENT NAND2 PORT ( E1 :
IN std_logic; E2 : IN std_logic; A : OUT std_logic); END COMPONENT; SIGNAL G10 : std_logic; BEGIN G22_NAND2:NAND2 PORT MAP (G10, G16, PO1); G10_NAND2:NAND2 PORT MAP (PI1, PI3, G10); END Structural; |
(b) c17_PARTITION_0.vhd
|
LIBRARY IEEE; USE IEEE.std_logic_1164.all; ENTITY c17_PARTITION_1 IS PORT ( PI4 :
IN std_logic; PI3 : IN std_logic; G16 : INOUT std_logic; G11 : INOUT std_logic; PI2 : IN std_logic); END c17_PARTITION_1; ARCHITECTURE Structural OF c17_PARTITION_1 IS COMPONENT NAND2 PORT ( E1 :
IN std_logic; E2 : IN std_logic; A : OUT std_logic); END COMPONENT; BEGIN G16_NAND2:NAND2 PORT MAP (PI2, G11, G16); G11_NAND2:NAND2 PORT MAP (PI3, PI4, G11); END Structural; |
(c) c17_PARTITION_1.vhd
|
LIBRARY IEEE; USE IEEE.std_logic_1164.all; ENTITY c17_PARTITION_2 IS PORT ( PI5 :
IN std_logic; G16 : INOUT std_logic; PI3 : IN std_logic; G11 : INOUT std_logic; PO2 : OUT std_logic); END c17_PARTITION_2; ARCHITECTURE Structural OF c17_PARTITION_2 IS COMPONENT NAND2 PORT ( E1 :
IN std_logic; E2 : IN std_logic; A : OUT std_logic); END COMPONENT; SIGNAL G19 : std_logic; BEGIN G19_NAND2:NAND2 PORT MAP (G11, PI5, G19); G23_NAND2:NAND2 PORT MAP (G16, G19, PO2); END Structural; |
(d) c17_PARTITION_2.vhd
Figure 2 -
Output from partitioning algorithm when set to make 3 partitions: (a) skeleton
file, and (b),(c), (d) each partition file.