Ferramentas para Síntese Aula anterior… Automática de ...johann/cmp241/aula02.graph.ppt.pdf · CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Aula 02 : Slide 1CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Ferramentas para SínteseAutomática de Circuitos IntegradosProfs: Ricardo Reis e Marcelo Johann

Grafos


Aula anterior…Design Tools

Síntese de alto nível Síntese lógica Síntese Física (projeto Físico)

Diagrama YAções de Projeto (pedido como leitura)Metodologias de Projeto (a ser tratado…)


Eixo ComportamentalSistêmico

Algorítmico

Micro arquitetural

Lógico

Elétrico

Eixo Estrutural

Eixo Geométrico

processadores,memórias, barramentos

módulos de hardware

registradores, multiplexadores, operadores

Portas lógicas, flip-flops

Transistores, resistores, capacitores, indutores






Leiaute das máscaras, retângulos, polígonos

Células de biblioteca, modelos de posição de pinos

Macro-células, planta baixa de blocos

Módulos, clusters, cores, planos de clock/alimentação

Partições físicas, componentes, placas






Funções de transferência, equações diferenciais

Equações booleanas, tabelas verdade, BDDs

Máquinas de estado finitas, operações

Algoritmos

Especificações funcionais




Algoritmos



EDIF

LEF / DEF

Spice

VHDL

C, C++,Hardware C

Java

Spice

CIF,GDS2


Algorítmico

Micro arquitetural

Lógico

Elétrico

Eixo Estrutural

Eixo Geométrico














Algoritmos



Ações de Projeto Síntese - de nível superior para inferior

agregam informação = composição

Análise - de nível inferior para superior extraem informação = decomposição

Otimização - atuam no mesmo nível

Ferramentas de Gerenciamento Base de Dados Visões e Versões Colaboração Interfaces e visualização



Algorítmico

Micro arquitetural

Lógico

Elétrico

Eixo Estrutural

Eixo Geométrico














Algoritmos


1- síntese lógica

2- simulação

3- mapeamento

4- place&route

5- fabricação


Tecnologias de Fabricação Personalizáveis por todas as máscaras

CPUS, muitos ASICs Personalizáveis por algumas as máscaras

Gate arrays Structured ASICs

Personalizáveis após a fabricaçãoou programáveis em campo

FPGAs

Structured ASICs



Metodologias de ProjetoGeneral Purpose

Full-custom Semi-custom Standard-Cell Platform-Based Module generators

ASICAula 02 : Slide 10CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

HOJE: GRAFOS

Definições Implementação Classes Problemas Algoritmos


Definição de GRAFO Um grafo G é definido como uma

dupla (V,E), onde: V é o conjunto de elementos,

chamados de vértices ou nodos E é o conjunto de relacionamentos,

chamados de arestas ou arcos(edges).

E é então definido como umconjuntos de pares (e1,e2) onde e1 ee2 pertencem a V.


Representação gráfica Seja dado o grafo G = ({a,b,c},{(a,b),(a,c)}).


Adjacência Dois vértices (nodos) u e v são ditos

adjacentes (ou vizinhos) se o par (u,v)pertence a E, ou seja, se existe um arcounindo estes vértices.

Pode-se definir conjuntos Adj(v) para cadavértice v como sendo os conjuntos de todosos nodos adjacentes a v.

Diz-se também que uma aresta (arco) a =(u,v) é incidente sobre os vértices u e v, quesão os pontos onde a inicia e termina


Grafos completos Um grafo completo de n vértices é o grafo

no qual cada vértice é adjacente a todos osdemais vértices, ou seja, no qual existemarestas entre todos os possíveis pares devértices.

Denota-se este tipo de grafo por Kn, onde né o número de vértices.

O grafo K4 é:

Desenhe os grafos K2, K3, K5 e K6.


Grafo complementar Um grafo H é o complemento de um grafo

G=(V,E) se e somente se H=(V,F) ondeF=E(K|V|)-E, ou seja, se H tem o mesmoconjunto de vértices e seu conjunto dearestas é igual às arestas de um grafocompleto menos as arestas presentes em G.

A seguinte figura mostra um grafo e seucomplemento


Sub-grafos Um grafo G’=(V’,E’) é um subgrafo de

G=(V,E) se e somente se V’⊆ V e E’⊆ E., ouseja, se o conjunto de vértices é umsubconjunto dos vértices de G e o conjuntodas arestas também é um subconjunto dasarestas de G.

Um subgrafo induzido por vértices é umsubgrafo G’ de G onde E’ = {(u,v)|(u,v) ∈ E eu,v ⊆ V }.


Walks, tours and paths Uma caminhada (walk) em um grafo G é

uma seqüência P = v0,e1,v1,...,vk-1,ek,vk devértices vi e arestas ej tal que ei = (vi-1,vj)para 1 ≤ i ≤ k, ou seja, uma seqüência ondecada aresta parte do vértice antecessor echega até o vértice sucessor da lista,formando uma cadeia.


Walks, tours and paths Um passeio (tour) é uma caminhada onde

todas as arestas ej são distintas.


Walks, tours and paths Por sua vez, um caminho (path) é uma

caminhada onde todos os vértices vi sãodistintos.


Comprimento de caminhos O comprimento de uma caminhada ou

passeio ou caminho como definidos acima ék, ou seja o número de arcos utilizados.

Um caminho de u a v é um caminho onde ovértice v0 = u e o vértice vk = v, e pode-serepresentá-lo por Pu-v.


Ciclos …e o prisioneiro assassino! Um ciclo é um caminho de comprimento k >

2 onde onde v0 = vk, ou seja, um caminhoque começa e termina no mesmo nodo.

Os ciclos podem ser pares ou ímpares,conforme for par ou ímpar o valor de k, seucomprimento medido em arestas.

A presença de ciclos pares ou ímpares temimplicações consideráveis na solução dediversos problemas de grafos.


Conexão Dois vértices u e v são ditos conectados em

um grafo se existe um caminho Pu-v. Um grafo conectado é aquele grafo no qual

todos os pares de vértices estão conectados. Um componente conectado de um grafo G

é um subgrafo conectado maximal de G.


Arco de corte Um arco e é um arco de corte em G se sua

remoção de G aumentar o número decomponentes conectados de G.

O arco (a,d) é um exemplo de arco de corte,pois sua remoção isolaria a,b,c de d,e. Oarco (f,g) não é um arco de corte


Árvore (versão não dirigida) e clique Uma árvore é um grafo conectado sem

ciclos. Um clique é um subgrafo completo maximal

de um grafo.


Grafos Dirigidos Um grafo dirigido G é um par de conjuntos

(V,E) onde V é um conjunto de vértices e E éum conjunto de pares ordenados de vértices,chamados de arcos dirigidos ou arestasdirigidas. Um arco dirigido e é definidocomo um par ordenado de vértices (u,v)onde u é o ínicio do arco e v é o final doarco.


Graus de entrada e saída O grau de entrada de um vértice u é

denotado por d-(u) e é definido como onúmero de arestas de entrada de u, ouseja, o numero de arestas e =(x,u), queterminam em u. De forma semelhante, ograu de saída de um vértice u é denotadopor d+(u) e é definido como o número dearestas de saída de u, ou seja, o numero dearestas e =(u,x), que iniciam em u.


Definições em Grafos dirigidos As definições anteriores de subgrafo,

caminho, entre outras, são facilmenteestendidas para grafos dirigidos.


DAG Um grafo dirigido acíclico (Directed Acyclic

Graph, ou DAG) é um grafo dirigido que nãocontém ciclos dirigidos.

Um vértice v é descendente de um vértice use existe um caminho dirigido Pu,v em G.


Árvore Dirigida Uma árvore dirigida é um grafo dirigido

acíclico onde todos os vértices exceto ovértice chamado raiz têm um grau deentrada igual a 1, enquanto este vértice raiztem grau de entrada igual a 0.

Uma folha é um vértice de uma árvoredirigida que não tem nenhum descendente,ou seja, com grau de saída igual a 0.


RepresentaçãoAdjacency Matrix Tells which pair is connectedList of Edges Enumarates each pairList of Neighbors Is a vector of listsGenerating function A successor operatorDedicated Uses implicit graph structure


Grafos de Intervalo In graph theory, an interval graph is the

intersection graph of a set of intervals on thereal line. [Wikipedia]


Grafos de Permutação A permutation graph is the intersection

graph of a family of line segments thatconnect two parallel lines in the Euclideanplane.


Grafos Circulares a circle graph is a

graph whose verticescan be associatedwith chords of a circlesuch that two verticesare adjacent if andonly if thecorresponding chordsin the circle intersect.


Grafos Bipartidos


Outras classes Intersecção

Cordais

Grafos duais

Grafos Planares

Grafos perfeitoshttp://en.wikipedia.org/wiki/Perfect_graph


Galeria de Grafos com nome http://en.wikipedia.org/wiki/Gallery_of_name

d_graphs

E Glossário:

http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Strongly_connected_component


Problemas MIS - Máximo Conjunto Independente


Problemas Coloração e número cromático


Problemas Coloração e número cromático


Algoritmos

No livro do Gerez, Sherwani, outros…

Próxima aula…

Tarefa Extra-classeListar uma variedade de problemas de grafos e

algoritmos (nomes e/ou referências) que osresolvem.


Próxima Aula

Algoritmos de Pesquisa de Caminhos

Programação em C/C++/STL

Documents

Ferramentas para Síntese Aula anterior… Automática de ...johann/cmp241/aula02.graph.ppt.pdf · CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1