Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Projecto de uma caixa de velocidades eléctrica por meio da variação do número de pólos para motores em disco de rotor em alumínio e em materiais supercondutores de alta temperatura (SAT)

Nesta dissertação apresenta-se um motor em disco polifásico inovador bem como uma estratégia de controlo com base no método de variação de velocidade por comutação do número de pares de pólos. A configuração das bobinas aliada à escolha das correntes e tensões que se injectam nas bobinas dos estatores, permite comutar electronicamente o número de pólos do motor entre 2, 4 6 e 8 pólos, conseguindo-se controlar a característica binário/velocidade do motor. O motor em disco possui a bobinagem feita em cobre com dois semi-estatores, em que quando utiliza o rotor em alumínio (com condutividade diferente de zero) comporta-se como um motor de indução convencional. Quando se substitui o rotor em alumínio por um constituído por um supercondutor de alta temperatura (SAT), o dispositivo comporta-se como um motor de histerese. O princípio de funcionamento do motor em disco convencional é baseado na indução de força electromotrizes no rotor e, consequentemente, uma vez que o alumínio é bom condutor eléctrico, correntes eléctricas induzidas, originadas por haver um campo magnético variável que é criado pelos semi-estatores. O comportamento deste tipo de motores, no que diz respeito a principais características (como o binário/velocidade para os diferentes números de pares de pólos), circuito equivalente de Steinmetz, entre outras teorias associadas é já conhecido há bastante tempo. O princípio de funcionamento do motor SAT é diferente do apresentado anteriormente, funciona com base na dinâmica de vórtices e devido ao facto de aparecer o fenómeno de ancoragem de fluxo (flux pinning) nos supercondutores de alta temperatura. Como o campo magnético varia, então o disco roda. Este motor tem um princípio de funcionamento muito mais complexo que o motor de indução sendo a obtenção do modelo do motor SAT complicada. A obtenção do modelo do motor SAT não é abordado nesta dissertação. Os comportamentos e modos de operação do motor com disco de alumínio e em materiais SAT são simulados através de um programa comercial de elementos finitos, nesta dissertação, sendo a supercondutividade simulada com base na relação entre o campo eléctrico e a densidade de corrente pela lei da potenciação (E-J power law). Com as simulações pretende-se comparar o rendimento electromecânico de ambos os motores.

Geração automática de controladores em FPGA integrando animação gráfica

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Parallel texts alignment

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

A shared-disk parallel cluster file system

Dissertação apresentada para obtenção do Grau de Doutor em Informática Pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

A debugging engine for parallel and distributed programs

Dissertação apresentada para a obtenção do Grau de Doutor em Informática pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia.

Optimization of multi-stage amplifiers in deep-submicron CMOS using a distributed/parallel genetic algorithm

IEEE International Symposium on Circuits and Systems, pp. 724 – 727, Seattle, EUA

Petri nets based components within globally asynchronous locally synchronous systems

Dissertação apresentada na Faculdade de Ciências e Tecnologias da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e Computadores

A study on parallel versus sequential relational fuzzy clustering methods

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Parallel run-time for CO-OPN

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Parallel programming in biomedical signal processing

Dissertação para obtenção do Grau de Mestre em Engenharia Biomédica

Validation of NASA rotor 67 with openFOAM's transonic density-based solver

Dissertação para obtenção do Grau de Mestre em Engenharia Mecânica

A system’s approach to cache hierarchy-aware decomposition of data-parallel computations

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Optimization of breast tomosynthesis image reconstruction using parallel computing

Breast cancer is the most common cancer among women, being a major public health problem. Worldwide, X-ray mammography is the current gold-standard for medical imaging of breast cancer. However, it has associated some well-known limitations. The false-negative rates, up to 66% in symptomatic women, and the false-positive rates, up to 60%, are a continued source of concern and debate. These drawbacks prompt the development of other imaging techniques for breast cancer detection, in which Digital Breast Tomosynthesis (DBT) is included. DBT is a 3D radiographic technique that reduces the obscuring effect of tissue overlap and appears to address both issues of false-negative and false-positive rates. The 3D images in DBT are only achieved through image reconstruction methods. These methods play an important role in a clinical setting since there is a need to implement a reconstruction process that is both accurate and fast. This dissertation deals with the optimization of iterative algorithms, with parallel computing through an implementation on Graphics Processing Units (GPUs) to make the 3D reconstruction faster using Compute Unified Device Architecture (CUDA). Iterative algorithms have shown to produce the highest quality DBT images, but since they are computationally intensive, their clinical use is currently rejected. These algorithms have the potential to reduce patient dose in DBT scans. A method of integrating CUDA in Interactive Data Language (IDL) is proposed in order to accelerate the DBT image reconstructions. This method has never been attempted before for DBT. In this work the system matrix calculation, the most computationally expensive part of iterative algorithms, is accelerated. A speedup of 1.6 is achieved proving the fact that GPUs can accelerate the IDL implementation.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.