Use este identificador para citar ou linkar para este item: https://rd.uffs.edu.br/handle/prefix/3351
Tipo: Monografia
Título: Análise de aproximações da MRST para o problema de roteamento de componentes de circuitos com obstáculos
Autor(es): Puton, Marco Aurélio Alves
Primeiro Orientador: Wuerges, Emílio
Resumo: Ao projetar VLSIs, é necessário conectar vários componentes evitando colidir com obstáculos, utilizando o menor comprimento possível de ligações. Para resolver este problema, é necessário encontrar a Minimum Rectilinear Steiner Tree (MRST) entre os componentes, mas encontrar a mesma é um problema NP-Completo, sendo necessário fazer o uso de aproximações. Uma aproximação simples é encontrar a MST (Minimum Spanning Tree), mas como os circuitos podem ser muito grandes, torna-se inviável realizar a busca em todo o espaço para conectar os componentes, sendo necessário reduzir o espaço de busca. Gerar a grade de Hanan, além de reduzir o espaço de busca, garante que a MRST esteja contida nela, mas como a maioria dos casos envolve circuitos muito grandes, mesmo utilizando a grade de Hanan, torna-se inviável em recurso de memória, uma vez que a quantidade de pontos gerados ainda é muito grande. Dessa forma, partindo da aproximação da MST utilizando a grade de Hanan, este trabalho faz a comparação com outra aproximação, analisando os resultados obtidos ao aplicar no problema de roteamento de circuitos, realizando estimativas com o intuito de decidir qual abordagem se aplica melhor ao caso.
Abstract/Resumen: Hen designing VLSIs, it is necessary to connect several components avoiding to collide with obstacles and using the smallest set of connections. To solve this problem, it is necessary to find the Minimum Rectilinear Steiner Tree (MRST) between the components, but to find the same is a NP-complete problem, being necessary to do the use of approximations to the MRST. A simple approach is to find the Minimal Spanning Tree (MST), but as the circuits can be very large, it becomes impracticable to carry out the search in all the space to connect the components, being necessary to reduce the search space. Generating the Hanan grid, in addition to reducing the search space, ensures that the MRST is contained in it, but since most cases involve very large circuits, even using the Hanan grid, it becomes unfeasible in memory resource, once the number of points generated is still very large. Thus, starting from the approximation of the MST using the Hanan grid, this work makes the comparison with another approach, analyzing the results obtained when applying to the circuit routing problem, making estimations in order to decide which approach best applies to the case.
Palavras-chave: Algoritmos
Ciência da computação
Idioma: por
País: Brasil
Instituição: Universidade Federal da Fronteira Sul
Sigla da Instituição: UFFS
Faculdade, Instituto ou Departamento: Campus Chapecó
Tipo de Acesso: Acesso Aberto
URI: https://rd.uffs.edu.br/handle/prefix/3351
Data do documento: 2019
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PUTON.pdf1,16 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.