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