Cad Tools For Vlsi Design Ppt

Download

Skip this Video

Loading SlideShow in 5 Seconds..

C2: VLSI CAD Tools Problems and Algorithms PowerPoint Presentation

C2: VLSI CAD Tools Problems and Algorithms

C2: VLSI CAD Tools Problems and Algorithms. Marcelo Johann. EAMTA 2006. Outline. FIRST PART Tools and CAD The Placement Problem The Routing Problem Complexity, Graphs and Optimization SECOND PART Routing Algorithms Placement Algorithms Interconnections Methodology Aspects. Outline.

Uploaded on Oct 05, 2014

• int
• side side
• space place
• cad tools
• push ref source
• space place side 1

Download Presentation

C2: VLSI CAD Tools Problems and Algorithms

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

Presentation Transcript

---

1. C2: VLSI CAD Tools Problems and Algorithms Marcelo Johann EAMTA 2006

2. Outline FIRST PART • Tools and CAD • The Placement Problem • The Routing Problem • Complexity, Graphs and Optimization SECOND PART • Routing Algorithms • Placement Algorithms • Interconnections • Methodology Aspects

3. Outline THIRD PART • Layout Compaction • Logic Synthesis, BDDs • Technology Mapping • Simmulation vs Formal Verification • Voltage Drop by Random Walks FOURTH PART • High-Level Synthesis • CDFG, Allocation, Scheduling, Generation

4. Tools A long time ago we discovered the first tools…

5. Tools …tools started to get more sophisticated…

6. Tools …more sophisticated and complex…

7. Tools …and then came VLSI CAD tools!

8. Tools Designers use CAD tools to make Chips

9. g++ STL Tools Math CS EE CE EE And there is a chain of tools that make tools.

10. Tools Programming Algorithms Graph Theory Optimization Math CS EE CE EE EE Phy Che g++ STL VLSI Design Foundry

11. But why CAD tools??? • Complexity > 100.000.000 xtores • Efficiency • Effort, + productivity

12. Time to Market receita Desaparecimento do Mercado Crescimento do Mercado perda atraso tempo

13. Design Flow Projetista faz descrição inicial (ex:VHDL) e usa um método, um conjunto de operações com ferramentas para obter o circuito • Síntese de alto-nível; • Síntese Lógica; • Síntese Física: Placement Routing

14. The Routing Problem

15. The Placement Problem

16. c d e f a b i j g h l k The Placement Problem But why this way?

17. c d e f a b i j g h l k The Placement Problem And not this way?

18. The Placement Problem Because in some dispositions cells to connect are a lot closer

19. The Placement Problem c d e f a b i j g h l k The Placement Problem Ok. Lets see how many options we have… 12 ! That's 479.001.600 for a circuit with only 12 cells!!!

20. Algorithms and Data Algorithm Sequence of steps to solve a problem • Fundamental area of math and CS theory Data Sctructures The way data is organized is as important as an algorithm in order to efficiently solve a problem • Fundamental area of applied CS;

21. Graph Theory Graph A Set and a set or Pairs Relation Each pair element belongs to the other set Function There is a single element from one set associated to each element of the first set

22. componentes redes v1 v2 v3 v4 v5 v6 v7 v8 v9 Representation Circuito representado por um grafo G=(V,E)

23. A Placement Algorithm SA512.ppt

24. The Routing Problem Back again… After placement • Lets see how we can add connections to the cells so that we build a real circuit • Switch to Glauco's Routing Intro - part 1 = +

25. The Maze Router

26. The Maze Router

27. g++ Maze Router's expansion void print(void); int bfs(int source, int target) { queue<int> q; q.push(source); while (!q.empty()) { int n = q.front(); q.pop(); if (n==target) return 1; if (Space[n] != 'X') { Space[n] = 'X'; print(); getchar(); q.push(WEST(n)); q.push(EAST(n)); q.push(NORTH(n)); q.push(SOUTH(n)); } } return 0; } #include <iostream> #include <queue> using namespace std; #define SIDE 20 #define PLACE(x,y) ((y)*SIDE+(x)) #define WEST(n) (n-1) #define EAST(n) (n+1) #define NORTH(n) (n-SIDE) #define SOUTH(n) (n+SIDE) char Space[SIDE*SIDE]; void init (void) { for (int i=0; i<SIDE*SIDE; ++i) Space[i] = ' '; for (int i=0; i<SIDE; ++i) { Space[PLACE(i,0)] = 'X'; Space[PLACE(i,SIDE-1)] = 'X'; Space[PLACE(0,i)] = 'X'; Space[PLACE(SIDE-1,i)] = 'X'; } for (int i=3; i<SIDE-3; ++i) Space[PLACE(i,10)] = 'X'; }

28. g++ Maze Router's tracking typedef pair<int,int> Ref; char Expansion[SIDE*SIDE]; char Taken[SIDE*SIDE]; int bfs(int source, int target) { queue<Ref> q; q.push(Ref(source,0)); while (!q.empty()) { int n = q.front().first; int p = q.front().second; q.pop(); if (n==target) return 1; if (Expansion[n] == 0 && Taken[n] == ' ') { Expansion[n] = p; q.push(Ref(WEST(n),n)); . . . } } return 0; } 1-You have to store the node and where it came from in the queue using a pair<int,int> 2-Instead of Space, use Expansion[n] to store where the nodes came from and Taken to represent obstacles and routes 4-Write backtrack(t,s) from target to source following Expansion[n]

29. Solution Space Methods to find a valid solution Combinatorial Optimazation Algorithms • Key areas of Computer Science http://www.rci.rutgers.edu/~cfs/305_html/ProblemSolving_Planning/TOH3DiskSol.html

30. Complexity

31. Complexity vs Speed Both are important in practice Complexity • When the problem's instance size increases Speed • When the problem's instance size is bounded

32. Algorithms • Exact Algorithms • Heuristic and Meta-Heuristic Algorithms • Randomized Algorithms

33. Graphs Representation Adjacency Matrix • Tells which pair is connected List of Edges • Enumarates each pair List of Neighbors • Is a vector of lists Generating function • A successor operator Dedicated • Uses implicit graph structure

34. Marcelo Johann johann@inf.ufrgs.br www.inf.ufrgs.br/~johann C2: VLSI CAD Tools Problems and Algorithms Part 1 ends EAMTA 2006

Cad Tools For Vlsi Design Ppt

Source: https://www.slideserve.com/zuzela/c2-vlsi-cad-tools-problems-and-algorithms

Posted by: hardertraturness.blogspot.com

Share this post