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.