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.
Redução da Variância, Multnível, Monte Carlo, Cálculo de Capacitância, Walk-on-Spheres

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

ORIENTADOR

Francisco Manuel Bernal Martinez

Ecole Politechnique de Paris

Investigador