Placement

PLACEMENT • Placement – next step to synthesis (technology mapping) • Design has netlist of logical components to be assigned to physical components of FPGA • Connection to be established by wiring • Steps 2 & 3 called as placement and routing.

• Placement is the assignment of the logic components to the particular physical components on the FPGA. • Placement in FPGAs is two dimensional x,y • FPGA placement – not concerned about device utilization, compaction and block orientations • But certain cases do allow these. • the orientation of logic blocks may be fixed • Some input and output pins may be swapped – for better placement & routing

GOALS •Guarantee the router can complete the routing step •Minimize all the critical net delays •Make the chip as dense as possible

OBJECTS •Minimize power dissipation •Minimize cross talk between signals

Placement constraints • Locking some i/o blocks as required by user • Aligning tri-state buffers in a line • Minimization of total interconnection wirelength • Minimization of total prog. Elements • Congestion reduction to ensure routability • Minimization of connections across different regions of the chip.

• Placement cost function gives an approximate value Different algorithms for placement • • • •

Min-cut based placement Kernighan Lin Algorithm Iterative improvement Simulated Annealing

Min-cut based placement • Aim – to cluster tightly connected components into a single partition. • Realized using partitioning methods • Net – wire connecting two components • Cut – net which connects components each in one partition • Cutset – set of nets cut • Cutsize – number of nets cut

The min­cut placement method uses successive application  of partitioning. 1.             Cut the placement area into two pieces.  2.             Swap the logic cells to minimize the cut cost.  3.             Repeat the process from step 1, cutting smaller pieces  until all the logic cells are placed. 

Kernighan Lin Algorithm • modified min-cut based algorithm Steps involved • start with a random partition • A seq. of pairwise tentative swaps of nodes b/w partitions done • results in the decrease of cutsize or least increase in the cutsize • The best subseq. of the swaps chosen as real swaps. • New bisection formed – steps repeated till best solution is got

Iterative improvement algorithm • used to improve placement given an initial placement Steps involved • Select 2 blocks • Interchange locations • If cost function is improved, accept else reject • If too many interchanges are rejected, stop else return to first step of alg. • N(N-1)/2 – operations involved

Simulated Annealing •

Previous methods – greedy approach – increase in cost function not accepted • Increase of cost function to a local maximum and reduces to a global minimum which is the least value • Solid annealed to obtain required characteristic – problem of finding the feasible solution of a problem Steps involved • A solution is taken • Pair-wise exchange takes place • New solution accepted if cost function Enew is less than previous value Ebest ∆E = Enew – Ebest

• If ∆E ≥ 0, then also move accepted with Boltzman probability e - ∆E /T • Update Ebest if cost function is better • T is changed and if no improvement is seen then stop the process. • T – controls the probability of accepting moves which result in an increased cost