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.