Dissertação
Paralelização da Deteção de Caminhos Condicionais em Grafos EVALUATED
A detecção de situações de curto-circuito em circuitos lógicos tem vindo a ganhar foco devido às novas técnicas de fabricação de circuitos. O conceito por detrás desta análise está ligado com o problema fundamental de encontrar caminhos num grafo entre 2 nós. O tipo de circuito lógicos onde a análise se foca é constituído por transistores que funcionam como interruptores, ou estão fechados e a corrente passa por eles, ou estão abertos e não há condução. Estes circuitos podem ser representados como um grafo onde a existência ou não de um arco é determinada por uma expressão lógica que é função de um conjunto de variáveis comuns a todos os arcos. Este é um problema de complexidade elevada, implicando a solução de um problema SAT para todos os possíveis caminhos entre os 2 nós em análise. Nesta tese, fazemos referência aos trabalhos desenvolvidos nesta área, especificamente um método muito eficiente baseado em Quantified Boolean Formulas que permite resolver problemas de dimensão elevada através de uma abordagem e solução incrementais. O objectivo do nosso trabalho é estudar e otimizar o método apresentado pelo grupo de investigação ALGOS, desenvolvendo um algoritmo paralelo em versão OpenMP para determinar a existência de caminhos entre 2 nós de um grafo em que os arcos são funções de um conjunto de variáveis de entrada do circuito. A solução descrita é suportada com um conjunto de benchmarks que mostram a eficácia da nossa implementação paralela, permitindo abordar uma maior variedade de instâncias de circuitos elétricos eficientemente.
setembro 19, 2018, 9:0
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