Arquitecturas reconfiguráveis para problemas de optimização combinatória

Abstract

Os problemas combinatórios têm uma gama extremamente ampla de aplicações numa variedade de áreas de engenharia, incluindo teste de circuitos electrónicos, reconhecimento de padrões, síntese lógica, etc. Muitos dos problemas de interesse pertencem às classes NP-hard e NP-complete, o que implica que os algoritmos relevantes têm no pior caso complexidade exponencial. Este facto impede a solução de muitos problemas práticos com a ajuda de computadores convencionais. As implementações em circuitos integrados específicos também não são viáveis, em particular por causa da própria heterogeneidade dos problemas combinatórios. Uma solução alternativa consiste no uso de dispositivos reconfiguráveis que podem ser personalizados para um algoritmo específico e reutilizados para outros algoritmos via uma simples reprogramação da sua estrutura interna. As implementações baseadas em hardware reconfigurável permitem optimizar a execução dos algoritmos relevantes com a ajuda de técnicas tais como processamento paralelo, unidades funcionais personalizadas, etc. Tais implementações possibilitam conter o efeito de crescimento exponencial do tempo de computação, permitindo deste modo a solução de problemas combinatórios complexos. Recentemente foram desenvolvidos vários sistemas reconfiguráveis destinados a resolver problemas combinatórios. Estes são principalmente baseados na ideia de hardware específico para a instância, em que para cada instância do problema é gerado um circuito particular. Nesta tese exploramos duas abordagens alternativas. A primeira é orientada para o domínio e permite processar uma variedade de problemas da área da computação combinatória. Para tal é projectado e implementado um processador combinatório reconfigurável e são desenvolvidos métodos e ferramentas que asseguram a sua reconfiguração dinâmica parcial. A segunda abordagem é orientada para a aplicação e é destinada a resolver um problema combinatório específico. Em particular, é proposta uma arquitectura inovadora para a solução do problema de satisfação booleana com a ajuda de uma combinação de software e de hardware reconfigurável. A técnica adoptada elimina a compilação de hardware específica à instância e permite processar problemas que excedem os recursos lógicos disponíveis. São também exploradas as possibilidades de implementação em hardware reconfigurável de estratégias evolutivas para o caso do problema do caixeiro viajante. Esta tese estende o domínio de aplicação da computação reconfigurável ao demonstrar que esta é capaz de acelerar algoritmos com fluxos de controlo complexos.

Combinatorial problems have an extremely wide range of practical applications in a variety of engineering areas, including the testing of electronic circuits, pattern recognition, logic synthesis, etc. Many of the problems of interest belong to the classes NP-hard and NP-complete, which implies that the relevant algorithms have an exponential worst-case complexity. This fact precludes the solution of many practical problems with conventional computers. ASIC-based implementations are also not viable, in particular because of the inherent heterogeneity of combinatorial problems. Reconfigurable devices offer an alternative solution, which can be customized to the requirements of a specific algorithm and reutilized for other algorithms via a simple reprogramming of their internal structure. Implementations based on reconfigurable hardware permit the execution of the relevant algorithms to be optimized with the aid of such techniques as parallel processing, personalized functional units, etc. Such implementations allow the effect of exponential growth in the computation time to be delayed, thus enabling more complex problem instances to be solved. Recently, a few reconfigurable engines for combinatorial problems have been developed. They are mainly based on the idea of instance-specific hardware, which assumes that a particular circuit is generated for each problem instance. In this thesis we explore two alternative approaches. The first, domain-specific, approach enables a variety of problems in the area of combinatorial computation to be addressed. For this purpose, a reconfigurable combinatorial processor has been designed and implemented and a number of methods and tools that support its partial dynamic reconfiguration have been developed. The second, application-specific, approach is oriented towards solving individual combinatorial problems. In particular, a novel architecture is proposed for solving the Boolean satisfiability problem with the aid of software and reconfigurable hardware. The adopted technique avoids instance-specific hardware compilation and permits problems that exceed the available logic resources to be solved. The possibility of implementing evolutionary strategies for the traveling salesman problem in reconfigurable hardware is also explored. This thesis extends the application domain of reconfigurable computing by demonstrating that it is effective in accelerating algorithms with complex control flows.