compaction by balachandar

1D-COMPACTION : 

1D-COMPACTION PRESENTED BY BALACHANDAR.K (111040004) M.TECH. VLSI DESIGN

INTRODUCTION : 

INTRODUCTION Process of minimization of layout area without altering functionality. Minimization of cost. Improvement of performance . Reduction of chip size.

GOAL OF COMPACTION : 

GOAL OF COMPACTION

PROPERTIES OF COMPACTION : 

PROPERTIES OF COMPACTION Should not violate Design rules. Complex phase in Physical design cycle. Should not affect functionality

PROBLEM FORMULATION : 

PROBLEM FORMULATION Given: M = {M1, M2, …., Mn} Set Of Geometric Features. s(Mi), The Minimum Feature Size. d(Mi, Mj), minimum separation between Mi & Mj. Objective: Minimize the layout such that size(Mi) ≥ s(Mi). dist(Mi, Mj) ≥ d(Mi, Mj). Where size(Mi), dist(Mi, Mj) are size of feature Mi & distance between features Mi and Mj after compaction

CLASSIFICATION : 

CLASSIFICATION

BASED ON DIRECTION OF MOVEMENT : 

BASED ON DIRECTION OF MOVEMENT 1D – COMPACTION X- Compaction  Feature moved along X-axis. Y- Compaction  Feature moved along Y-axis. 2D – COMPACTION Moved along both X & Y direction.

1D-COMPACTION : 

1D-COMPACTION

2D-COMPACTION : 

2D-COMPACTION

BASED ON MINIMUM DISTANCE BETWEEN FEATURES : 

BASED ON MINIMUM DISTANCE BETWEEN FEATURES CONSTRAINT BASED GRAPH VIRTUAL GRID BASED GRAPH

CONSTRAINT GRAPH : 

CONSTRAINT GRAPH Weighted directed graph. Concentrates on physical connectivity & Separation constraints  linear inequalities. Represented as G(V,E). Each vertex ‘v’ Є ‘V’ represents each component. ‘E’ represents Constraints.

CONTD… : 

CONTD…

TYPES CONSTRAINTS : 

TYPES CONSTRAINTS

CONNECTIVITY CONSTRAINT : 

CONNECTIVITY CONSTRAINT Consider 2 blocks ‘C’ & ‘W’. Placed with in distance ‘s’. Physical connectivity constraint  cycle of 2 edges. Inequality is given as |Cx – Wx | ≤ s. Edge weight is given by –s between Cx & Wx .

SEPARATION CONSTRAINT : 

SEPARATION CONSTRAINT Consider 2 blocks ‘A’ & ‘B’ . Requires separation of d units Inequality is given as Bx ≥ Ax + d. Separation constraint  edge with weight d between A to B

SHADOW PROPAGATION ALGORITHM : 

SHADOW PROPAGATION ALGORITHM Shadow of feature  propagated along direction of compaction. Imaginary light source  illuminates Feature under consideration. Shadow of one feature obstructed by other  make constraint. Remove obstructed part

CONTD… : 

CONTD…

ALGORITHM EXPLANATION : 

ALGORITHM EXPLANATION

CONSTRAINT GRAPH FOR A : 

CONSTRAINT GRAPH FOR A

VIRTUAL GRID COMPACTION : 

VIRTUAL GRID COMPACTION Transforms entire layout on grids. Each component  Attached to grid line. Compaction operation  Along grid lines. Easily implemented. Between two adjacent grid-lines depends on the components Does not produce compact layouts (now a days not used).

HIERARCHICAL COMPACTION : 

HIERARCHICAL COMPACTION Classified based on the hierarchy of circuits. Applied to Different levels of layouts. Combination of both virtual grid & constraint graph method.

REFERENCES : 

REFERENCES

Slide 24: 

THANK YOU