Dissertação

{pt_PT= Paralelização da Deteção de Caminhos Condicionais em Grafos} {} EVALUATED

{pt=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., en=The analysis of input conditions that may cause a short-circuit in a logic circuit has recently become a critical issue, due to the new place and route layout challenges during circuit design. The concept of this analysis is strongly related with the intriguing problem of determining paths in a graph whose edges are defined by related logic functions. These logic circuits can be modeled as a generic graph, where edges are a logic function of static input variable combinations, representing transistors that act like logic switches. It implies an exceptionally complex SAT-problem with an extensive inspection of all possible paths between 2 nodes, the power supply and ground. In this thesis, we describe and tackle the most relevant findings in this field, specifically a very efficient Quantified Boolean Formula (QBF) based method that approaches these highly complex problems in an incremental way. The goal of our work was to study an efficient solution to this method through the development of a parallel version of the algorithm described for conditional path detection between a pair of nodes in graphs, making use of the OpenMP libraries, in a multi-core shared-memory machine. The solution presented is supported with a set of benchmarks that show the effectiveness of our parallel implementation, allowing to address instances of transistor-level circuits for a wide range of inputs and internal nodes efficiently.}
{pt=Circuitos lógicos, Análise de Curto-Circuitos, QBF, SAT, Algoritmo Paralelo, OpenMP, en=Logic circuits, Short-circuit analysis, QBF, SAT, Parallel Algorithm, OpenMP}

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