Force Directed Layout Algorithm

The force directed approach to VLSI placement, layout and routing offers significant gains in speed for many graph problems. A circuit is first modeled as directed graph. The nodes in the graph are iteratively positioned by assigning attractive and repellent forces with respect to the other nodes in the graph. The motion is similar to how charged particles behave in real life physical systems. As time progresses, the nodes reach a stabilized position and the algorithm is terminated. Figure 1 shows a VHDL description of a logic circuit. Figure 2 shows the stabilized position of the nodes resulting from the algorithm.

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 – Description of VHDL File

Figure 2 – Layout Obtained from Force Directed Algorithm