Dissertação
Parallel Multilevel Monte Carlo Algorithm for Capacitance Extraction in Non-Manhattan Geometries EVALUATED
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.
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
