Algoritmos de roteamento dirigidos a desempenho

Abstract

Este trabalho realiza uma avaliação e comparação abrangente dos algoritmos de roteamento encontrados na literatura, através do uso de várias métricas de desempenho e topológicas, com o uso de parâmetros de resistência e capacitância de tecnologias nanométricas, em cenários de interconexões comprometidos com o estado da arte. As avaliações e comparações de algoritmos encontradas na literatura costumam ser limitadas, tendo resultados baseados em cenários restritos, considerando aspectos limitados dos casos reais (ou mesmo tratar apenas casos abstratos, sem comprometimento com cenários de interconexões reais), com somente algumas tecnologias, grades restritas e modelos arbitrários. Para este trabalho foi definida uma metodologia de acordo com características de tecnologias e dispositivos comprometidas com o estado da arte. Estes dados utilizados formam um conjunto de cenários de experimentos que possibilita a avaliação dos algoritmos de roteamento de uma forma abrangente e que não é encontrada na literatura. Os resultados obtidos mostraram que os algoritmos dirigidos a desempenho do caminho crítico apresentam os melhores desempenhos para o atraso deste caminho, na média dos resultados e também mostram que o algoritmo AMAZE-share apresenta ótimo desempenho para cenários de interconexões mais curtas, que possuem grade menor e parâmetros tecnológicos relacionados às camadas mais baixas de metal (parâmetros RC para camadas de metal intermediárias). O algoritmo SERT-C apresentou, em média, os melhores resultados e também os mais consistentes, estando sempre nas duas primeiras posições do ordenamento utilizando os atrasos de caminho crítico. Já considerando-se o maior atraso da rede, os algoritmos que apresentaram os melhores resultados foram AMAZE-share, SERT, AHHK e ATREE, com destaque para os dois primeiros, que, na maioria dos casos, apresentam médias de valores de atrasos muito similares. Tais resultados mostram claramente que qualquer avaliação e comparação de algoritmos de roteamento é afetada pelos cenários de interconexões com os quais esta é feita. Por isso, o uso de cenários adequados torna-se um dos principais pontos quando se quer realizar uma avaliação que realmente tenha significado prático. Este trabalho também mostra que os modelos de atraso utilizados como estimativa no cálculo de atraso não apresentam resultados confiáveis para este tipo de avaliação, por mostrarem diferenças muito significativas no ordenamento dos algoritmos de roteamento quando comparadas com o ordenamento feito com os resultados de simulação elétrica.

This work makes a comprehensive evaluation and comparison of routing algorithms in the literature through the use of various performance and topologic metrics, using parameters of resistance and capacitance of nano-technologies, in scenarios of interconnections committed to the state of the art. The evaluations and comparisons of algorithms in the literature are often limited, with results based on restricted scenarios, considering limited aspects of actual cases (or even just dealing with abstract cases, without commitment to real scenarios of interconnections), with only a few technologies, few grids and arbitrary models. For this work a methodology was defined according to characteristics of technologies and devices committed to the state of the art. The data used are a set of experiments scenarios that allows the evaluation of routing algorithms in a comprehensive manner and that is not found in the literature. The results showed that the Critical Sink Routing Tree algorithms are the best performers for the delay of critical path, considering the average of the results. These results also show that the algorithm AMAZE-share has great performance for smaller interconnect scenarios, which have smaller grid size and technological parameters related to the lower metal layers (RC parameters for intermediate metal layers). The SERT-C algorithm presented best average results and also the most consistent ones, always being in the first two positions of the rank using the critical path delay. Now considering the worst delay of the network, the algorithms that produced the best results were AMAZE-share, SERT, AHHK and ATREE, especially the first two, which, in most cases, have average values of delays very similar. These results clearly show that any evaluation and comparison of routing algorithms is affected by the interconnect scenarios defined. Therefore, the use of appropriate scenarios becomes a major point when we want to make a comparison that actually has practical significance. This study also shows that the models used to estimate delay not present reliable results for this type of evaluation, showing significant differences in the ranking of routing algorithms when compared with the ranking done with results of electrical simulation.