Dissertação
{en_GB=Parallel Multilevel Monte Carlo Algorithm for Capacitance Extraction in Non-Manhattan Geometries} {} EVALUATED
{pt=Quanto mais o número de componentes de circuitos integrados aumenta, maior há uma procura por algoritmos eficientes que analisem e encontrem falhas nos projetos de circuitos. Um dos problemas que se procura são capacitâncias parasíticas. Os métodos de extração de capacitância elétrica mais utilizados são algoritmos Monte Carlo pois estes são facilmente paralelizáveis e portanto capazes de resolver problemas de larga escala em tempo útil. Estes algoritmos têm sido objeto de estudo ao longo dos anos e surgiram algumas técnicas que permitem que tenham um melhor desempenho. Nesta tese, apresentamos as várias soluções que existem e discutimos as vantagens e desvantagens de cada uma. Propomos uma nova solução, usando a técnica Multinível com algoritmo Walk-On-Spheres. Esta técnica melhora o desempenho de métodos Monte Carlo através da redução da sua variância estatística. Esta técnica já foi implementada com sucesso para outros problemas mas é nova nesta área. A complexidade do algoritmo é reduzida de O(e^3) para O(e^2 log^2(e)), onde "e" é o erro máximo erro permitido, usando esta técnica. Os resultados obtidos mostram um decréscimo no tempo de computação na ordem de grandeza que era esperada e mostram também que a paralelização permite a escala eficiente do desempenho do algoritmo., en=As the number and density of components in integrated circuits increases, the more there is a need for efficient algorithms to analyse and find flaws in circuit design, especially before production. One of the problems to look for in the designs are parasitic capacitances, and that analysis is done by calculating the electrical capacitance. Parallelization is required for handling large scale problems, and Monte Carlo methods are the exact fit for this as they can be easily parallelized. Some parallel Monte Carlo solutions already exist, and some research has been done into improving these algorithms. We discuss the advantages and disadvantages of the existing solutions. We propose and have developed a new solution by applying a Multilevel technique to the Walk-On-Spheres algorithm. This technique does variance reduction, which leads to a smaller sampling size and thus better performance. It has been applied in several problems but is novel in this area. We decrease the running time complexity from O(e^3) to O(e^2 log^2(e)) where e is the maximum error of the result. The results show this improvement and show that the parallel performance scales almost perfectly.}
maio 31, 2017, 10:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
José Carlos Alves Pereira Monteiro
Departamento de Engenharia Informática (DEI)
Professor Catedrático
