Synthesis of FPGA-based accelerators implementing recursive algorithms

O desenvolvimento de sistemas computacionais é um processo complexo, com múltiplas etapas, que requer uma análise profunda do problema, levando em consideração as limitações e os requisitos aplicáveis. Tal tarefa envolve a exploração de técnicas alternativas e de algoritmos computacionais para optimizar o sistema e satisfazer os requisitos estabelecidos. Neste contexto, uma das mais importantes etapas é a análise e implementação de algoritmos computacionais. Enormes avanços tecnológicos no âmbito das FPGAs (Field-Programmable Gate Arrays) tornaram possível o desenvolvimento de sistemas de engenharia extremamente complexos. Contudo, o número de transístores disponíveis por chip está a crescer mais rapidamente do que a capacidade que temos para desenvolver sistemas que tirem proveito desse crescimento. Esta limitação já bem conhecida, antes de se revelar com FPGAs, já se verificava com ASICs (Application-Specific Integrated Circuits) e tem vindo a aumentar continuamente. O desenvolvimento de sistemas com base em FPGAs de alta capacidade envolve uma grande variedade de ferramentas, incluindo métodos para a implementação eficiente de algoritmos computacionais. Esta tese pretende proporcionar uma contribuição nesta área, tirando partido da reutilização, do aumento do nível de abstracção e de especificações algorítmicas mais automatizadas e claras. Mais especificamente, é apresentado um estudo que foi levado a cabo no sentido de obter critérios relativos à implementação em hardware de algoritmos recursivos versus iterativos. Depois de serem apresentadas algumas das estratégias para implementar recursividade em hardware mais significativas, descreve-se, em pormenor, um conjunto de algoritmos para resolver problemas de pesquisa combinatória (considerados enquanto exemplos de aplicação). Versões recursivas e iterativas destes algoritmos foram implementados e testados em FPGA. Com base nos resultados obtidos, é feita uma cuidada análise comparativa. Novas ferramentas e técnicas de investigação que foram desenvolvidas no âmbito desta tese são também discutidas e demonstradas.

Visible light communication systems for road safety applications

Esta tese apresenta um estudo exploratório sobre sistemas de comunicação por luz visível e as suas aplicações em sistemas de transporte inteligentes como forma a melhorar a segurança nas estradas. Foram desenvolvidos neste trabalho, modelos conceptuais e analíticos adequados à caracterização deste tipo de sistemas. Foi desenvolvido um protótipo de baixo custo, capaz de suportar a disseminação de informação utilizando semáforos. A sua realização carece de um estudo detalhado, nomeadamente: i) foi necessário obter modelos capazes de descrever os padrões de radiação numa área de serviço pré-definida; ii) foi necessário caracterizar o meio de comunicações; iii) foi necessário estudar o comportamento de vários esquemas de modulação de forma a optar pelo mais robusto; finalmente, iv) obter a implementação do sistema baseado em FPGA e componentes discretos. O protótipo implementado foi testado em condições reais. Os resultados alcançados mostram os méritos desta solução, chegando mesmo a encorajar a utilização desta tecnologia em outros cenários de aplicação.

Integration of geochemical and biological modifications in mining areas: waters, sediments and diatoms

The development of mining activities over thousands of years in the region of Aljustrel is nowadays visible as a vast area of ore tailings, slag and host rocks of sulphides mineralization. The generation of acidic waters by the alteration of pyritic minerals - Acid Mine Drainage (AMD) - causes a significant impact on the river system both in the south of the village (Rib ª. Água Forte) and in the north of it (Rib ª. Água Azeda and Barranco do Farrobo), which is reflected in extremely low pH values (< 3) and high concentrations of As, Cd, Cu, Fe, Mn, Pb, Zn and sulphates. This study aimed to assess the environmental impacts extent, integrating geochemical (surface waters and stream sediments) and biological (diatoms) parameters. Three groups of sites were defined, based on sediments and water analysis, which integration with diatom data showed the same association of groups: Group 1- impacted, with acidic pH (1.9-5.1), high metal contents (0.4-1975 mg L-1) and Fe-Mg-sulphate waters, being metals more bioavailable in waters in cationic form (Me2+); mineralogically the sediments were characterized by phyllosilicates and sulphates/oxy-hydroxysulphate phases, easily solubilized, retaining a high amount of metals when precipitated; dominant taxon was Pinnularia aljustrelica (a new species); Group 2- slightly impacted, weak acid to neutral pH (5.0-6.8), metal contents not so high (0.2-25 mg L-1) and Fe-Mg-sulphate to Mg-chloride waters; dominant taxa were Brachysira neglectissima and Achnanthidium minutissimum; Group 3- unimpacted, alkaline pH (7.0-8.4), low metal contents (0-7 mg L-1) with Mg-chloride waters. In this group, metals were associated to the primary phases (e.g. sulphides), not so easily available; the existence of high chloride contents explained the presence of typical taxa of brackish/marine (e.g. Entomoneis paludosa) waters. Taxonomical aspects of the diatoms were studied (discovery of a new species: Pinnularia aljustrelica Luis, Almeida et Ector sp. nov.), as well as morphometric (size decrease of diatoms valves, as well as the appearance of deformed valves of Eunotia exigua in Group 1 and A. minutissimum in Group 2) and physiological (effective to assess the effects of metals/acidity in the photosynthetic efficiency through PAM Fluorometry) aspects. A study was carried out in an artificial river system (microcosm) that aimed to mimic Aljustrel’s extreme conditions in controlled laboratory conditions. The chronic effects of Fe, SO42- and acidity in field biofilms, inoculated in the artificial rivers, were evaluated as well as their contribution to the communities’ tolerance to metal toxicity, through acute tests with two metals (Cu and Zn). In general, the effects caused by low pH values and high concentrations of Fe and SO42- were reflected at the community level by the decrease in diversity, the predominance of acidophilic species, the decrease in photosynthetic efficiency and the increase of enzymatic (e.g. catalase, superoxide dismutase) and non-enzymatic activities (e.g. total glutathione and total phytochelatins). However, it was possible to verify that acidity performed a protective effect in the communities, upon Cu and Zn addition. A comparative study between Aljustrel mining area and New Brunswick mining area was carried out, both with similar mining and geological conditions, reflected in similar diatom communities in both mines, but in very different geographic and climatic areas.

Context-based wireless mesh networks

In the modern society, new devices, applications and technologies, with sophisticated capabilities, are converging in the same network infrastructure. Users are also increasingly demanding in personal preferences and expectations, desiring Internet connectivity anytime and everywhere. These aspects have triggered many research efforts, since the current Internet is reaching a breaking point trying to provide enough flexibility for users and profits for operators, while dealing with the complex requirements raised by the recent evolution. Fully aligned with the future Internet research, many solutions have been proposed to enhance the current Internet-based architectures and protocols, in order to become context-aware, that is, to be dynamically adapted to the change of the information characterizing any network entity. In this sense, the presented Thesis proposes a new architecture that allows to create several networks with different characteristics according to their context, on the top of a single Wireless Mesh Network (WMN), which infrastructure and protocols are very flexible and self-adaptable. More specifically, this Thesis models the context of users, which can span from their security, cost and mobility preferences, devices’ capabilities or services’ quality requirements, in order to turn a WMN into a set of logical networks. Each logical network is configured to meet a set of user context needs (for instance, support of high mobility and low security). To implement this user-centric architecture, this Thesis uses the network virtualization, which has often been advocated as a mean to deploy independent network architectures and services towards the future Internet, while allowing a dynamic resource management. This way, network virtualization can allow a flexible and programmable configuration of a WMN, in order to be shared by multiple logical networks (or virtual networks - VNs). Moreover, the high level of isolation introduced by network virtualization can be used to differentiate the protocols and mechanisms of each context-aware VN. This architecture raises several challenges to control and manage the VNs on-demand, in response to user and WMN dynamics. In this context, we target the mechanisms to: (i) discover and select the VN to assign to an user; (ii) create, adapt and remove the VN topologies and routes. We also explore how the rate of variation of the user context requirements can be considered to improve the performance and reduce the complexity of the VN control and management. Finally, due to the scalability limitations of centralized control solutions, we propose a mechanism to distribute the control functionalities along the architectural entities, which can cooperate to control and manage the VNs in a distributed way.