Algorithms for wire length improvement of VLSI circuits with concern to critical paths

Abstract

Esta tese objetiva propor algorítmos para a redução do tamanho dos fios em circuitos VLSI considerando elementos críticos dos circuitos. O problema é abordado em duas perspectivas diferentes: posicionamento e roteamento. Na abordagem de posicionamento, a tese explora métodos para realizar posicionamento de um tipo particular de circuito VLSI, que são conhecidos como circuitos 3D. Diferente de trabalhos anteriores, este tese aborda o problema considerando as conexões verticais (chamadas 3D-Vias) e as limitações impostas pelas mesmas. Foi realizado um fluxo completo, iniciando no tratamento de pinos de entrada e saída (E/S), posicionamento global, posicionamento detalhado e posicionamento das 3D-Vias. A primeira etapa espalha os pinos de E/S de maneira equilibrada objetivando auxiliar o posicionamento para obter uma quantidade reduzida de 3D-Vias. O mecanismo de posicionamento global baseado no algorítmo de Quadratic Placement considera informações da tecnologia e requerimento de espaçamento de 3D-Vias para reduzir o comprimento das conexões e equilibrar a distrubuição das células em 3D. Conexes críticas podem ser tratadas através da insercão de redes artificiais que auxiliam a evitar que 3D-Vias sejam usadas em conexões críticas do circuito. Finalmente, 3D-Vias são posicionadas por um algorítmo rápido baseado na legalizaçãao Tetris. O framework completo reforça os potenciais benefícios dos circuitos 3D para a melhora do comprimento das conexões e apresenta algorítmos eficientes projetados para circutos 3D podendo estes serem incorporados em novas ferramentas. Na abordagem de roteamento, um novo algorítmo para obtenção de árvores de Steiner chamado AMAZE é proposto, combinando métodos existentes com novos métodos que são efetivos para produzir fios curtos e de baixo atraso para elementos críticos. Um técnica de biasing atua na redução do tamanho dos fios, obtendo resultados próximos da solução ótima enquanto que dois fatores de timing chamados path-length factor e sharing factor propiciam melhora do atraso para conexões sabidas como críticas. Enquanto que AMAZE apresenta melhorias significativas em um algorítmo padrão na indústria de CAD (Maze Routers), ele produz árvores de roteamento com uso de CPU comparável com algorítmos heurísticos de árvore de Steiner e menor atraso.

This thesis targets the wire length improvement of VLSI circuits considering critical elements of a circuit. It considers the problem from two different perspectives: placement and routing. On placement, it explores methods to perform placement of 3D circuits considering issues related to vertical interconnects (3D-Vias). A complete flow, starting from the I/O pins handling, global placement, detailed placement and 3D-Via placement is presented. The I/O pins algorithm spreads the I/Os evenly and aids the placer to obtain a reduced number of 3D-Vias. The global placement engine based on Quadratic algorithm considers the technology information and 3D-Via pitch to reduce wire length and balance the cells distribution on 3D. Critical connections can be handled by insertion of artificial nets that lead to 3D-Via avoidance for those nets. Finally, 3D-Vias are placed by a fast algorithm based on Tetris legalization. The whole framework enforces the potential benefits of 3DCircuits on wire length improvement and demonstrates efficient algorithms designed for 3D placement that can be incorporated in new tools. On routing, a new flexible Steiner tree algorithm called AMAZE is proposed, combining existing and new methods that are very effective to produce short wire length and low delay to critical elements. A biasing technique provides close to optimal wire lengths while a path length factor and a sharing factor enables a very wide delay and wire length trade-off. While AMAZE presents significant improvements on a industry standard routing algorithm (Maze Routers), it produces routing trees with comparable speed and beter delay than heuristic Steiner tree algorithms such as AHHK and P-Trees.