Posicionamento visando redução do comprimento das conexões

Abstract

Este trabalho será focado no problema de posicionamento de células lógicas em circuitos integrados. Neste problema necessitamos organizar as portas lógicas reduzindo o comprimento dos fios que as conectam da melhor forma possível. Para entender o problema e as soluções existentes é descrita uma explanação sobre técnicas e algoritmos que são utilizados atualmente ou que são historicamente importantes, de forma a conduzir o texto para as técnicas apresentadas neste trabalho. As técnicas que serão apresentadas neste trabalho têm objetivos individualmente diferentes, porém conduzem a novos resultados e perspectivas em posicionamento. Todas as técnicas são baseadas na modificação e análise do grafo do posicionamento. Neste trabalho serão apresentadas quatro técnicas para melhorar a solução do problema de posicionamento. O primeiro trabalho a ser apresentado será a Critical Star que aplicado alguns nodos e arestas extras no grafo original para reduzir os caminhos críticos. A segunda técnica é a Logical Core I, ela traz um novo método de análise da dificuldade de posicionar um circuito VLSI. A terceira técnica, que tem forte conexão com a segunda, é a Logical Core II, mais focada em tempo de execução da técnica, ela gera um vetor com todas as dificuldades de posicionar cada célula no circuito. As duas técnicas aumentam o conhecimento do posicionador a respeito do problema e com isso vão de encontro a um ponto muito importante e ainda pouco abordado, a evolução da controlabilidade no posicionamento. A quarta técnica que será apresentada é a Logical Cluster. É uma técnica baseada na Logical Core II, e foi desenvolvida para otimizar os posicionadores já existentes no estado da arte. A técnica é muito eficiente e reduz o tempo de execução do posicionamento e muitas vezes reduz o comprimento de fio.

This work is focused on placement problem of VLSI circuits. The goal is organize the logic gates reducing the total wirelength that connect them. A non-effective placement assignment will not only affect the circuit performance but might also make it non-manufacturable by producing excessive wirelength. Then the next step in the assembly line, the routing problem could be insolvable. In this work will be presents four differents techniques. The techniques are based on changing the graph to improve the placement results. The first one is the Critical Star that applies some extra nodes and edges to reduce the critical paths. The second algorithm is the Logical Core I which brings a new method to analyze the circuit hardness to place a circuit. The third algorithm is called Logical Core II and the focus is generate a vector with hardness to place each cell in the circuit, and increasing the placer information about the problem. The Logical Core I and II, both improving the possibility to compare the hardnesses, in different abstraction levels, and improve the placement controllability. The fourth algorithm is a fast algorithm, based on use the Logical Core II, it creates an effective clustering technique to improve the state-of-art placers results. Reducing the runtime and sometimes improving the wirelength results.