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.

Molecular study of cell degeneration and evolution induced by mRNA mistranslation

As proteínas existentes nas células são produzidas pelo mecanismo de tradução do mRNA, no qual a informação genética contida nos genes é descodificada em cadeias polipeptídicas. O código genético, que define as regras de descodificação do genoma, minimiza os erros de tradução do mRNA, garantindo a síntese de proteínas com elevada fidelidade. Esta é essencial para a estabilidade do proteoma e para a manutenção e funcionamento dos processos celulares. Em condições fisiológicas normais, os erros da tradução do mRNA ocorrem com frequências que variam de 10-3 a 10-5 erros por codão descodificado. Situações que aumentam este erro basal geralmente estão associadas ao envelhecimento, stresse e a doenças; no entanto, em certos organismos o código genético é traduzido naturalmente com elevado erro, indicando que a síntese de proteínas aberrantes pode de algum modo ser vantajosa. A fim de estudar a resposta celular aos erros de tradução do mRNA, construímos leveduras que incorporam serina no proteoma em resposta a um codão de leucina, usando a expressão constitutiva de um tRNASer mutante. Este fenómeno genético artificial provocou uma forte diminuição da esporulação, da viabilidade e da eficiência de mating, afectando imensamente a reprodução sexual da levedura. Observou-se também uma grande heterogeneidade no tamanho e na forma das células e elevada instabilidade genómica, com o aparecimento de populações poliplóides e aneuplóides. No sentido de clarificar as bases celulares e moleculares daqueles fenótipos e compreender melhor a biologia do erro de tradução do mRNA, construímos também células de levedura que inserem serina em resposta a um codão de leucina de modo indutível e controlado. Utilizaram-se perfis de mRNA total e de mRNA associado a polissomas para elucidar a resposta celular ao erro de tradução do mRNA. Observou-se a indução de genes envolvidos na resposta ao stresse geral, stresse oxidativo e na unfolded protein response (UPR). Um aumento significativo de espécies reactivas de oxigénio (ROS) e um forte impacto negativo na capacidade das células pós-mitóticas re-iniciarem o crescimento foram também observados. Este fenótipo de perda de viabilidade celular foi resgatado por scavangers de ROS, indicando que o stresse oxidativo é a principal causa de morte celular causada pelos erros de tradução. Este estudo levanta a hipótese de que o stresse oxidativo e a acumulação de ROS, ao invés do colapso súbito do proteoma, são as principais causas da degeneração celular e das doenças humanas associadas aos erros de tradução do genoma. ABSTRACT: Proteins are synthesized through the mechanism of translation, which uses the genetic code to transform the nucleic acids based information of the genome into the amino acids based information of the proteome. The genetic code evolved in such a manner that translational errors are kept to a minimum and even when they occur their impact is minimized by similar chemical properties of the amino acids. Protein synthesis fidelity is essential for proteome stability and for functional maintenance of cellular processes. Indeed, under normal physiological conditions, mistranslation occurs at frequencies that range from 10-3 to 10-5 errors per codon decoded. Situations where this basal error frequency increases are usually associated to aging and disease. However, there are some organisms where genetic code errors occur naturally at high level, suggesting that mRNA mistranslation can somehow be beneficial. In order to study the cellular response to mRNA mistranslation, we have engineered single codon mistranslation in yeast cells, using constitutive expression of mutant tRNASer genes. These mistranslating strains inserted serines at leucine-CUG sites on a proteome wide scale due to competition between the wild type tRNALeu with the mutant tRNASer. Such mistranslation event decreased yeast sporulation, viability and mating efficiencies sharply and affected sexual reproduction strongly. High heterogeneity in cell size and shape and high instability in the genome were also observed, with the appearance of some polyploid or aneuploid cell populations. To further study the cellular and molecular basis of those phenotypes and the biology of mRNA mistranslation, we have also engineered inducible mRNA misreading in yeast and used total mRNA and polysome associated mRNA profiling to determine whether codon misreading affects gene expression. Induced mistranslation up-regulated genes involved in the general stress response, oxidative stress and in the unfolded protein response (UPR). A significant increase in reactive oxygen species (ROS) and a strong negative impact on the capacity of post-mitotic cells to re-initiate growth in fresh media were also observed. This cell viability phenotype was rescued by scavengers of ROS, indicating that oxidative stress is the main cause of cell death caused by mRNA mistranslation. This study provides strong support for the hypothesis that oxidative stress and ROS accumulation, rather than sudden proteome collapse or major proteome disruption, are the main cause of the cellular degeneration observed in human diseases associated mRNA mistranslation.

Performance analysis of 4G wireless networks using system level simulator

In the last decade, mobile wireless communications have witnessed an explosive growth in the user’s penetration rate and their widespread deployment around the globe. In particular, a research topic of particular relevance in telecommunications nowadays is related to the design and implementation of mobile communication systems of 4th generation (4G). 4G networks will be characterized by the support of multiple radio access technologies in a core network fully compliant with the Internet Protocol (all IP paradigms). Such networks will sustain the stringent quality of service (QoS) requirements and the expected high data rates from the type of multimedia applications (i.e. YouTube and Skype) to be available in the near future. Therefore, 4G wireless communications system will be of paramount importance on the development of the information society in the near future. As 4G wireless services will continue to increase, this will put more and more pressure on the spectrum availability. There is a worldwide recognition that methods of spectrum managements have reached their limit and are no longer optimal, therefore new paradigms must be sought. Studies show that most of the assigned spectrum is under-utilized, thus the problem in most cases is inefficient spectrum management rather spectrum shortage. There are currently trends towards a more liberalized approach of spectrum management, which are tightly linked to what is commonly termed as Cognitive Radio (CR). Furthermore, conventional deployment of 4G wireless systems (one BS in cell and mobile deploy around it) are known to have problems in providing fairness (users closer to the BS are more benefited relatively to the cell edge users) and in covering some zones affected by shadowing, therefore the use of relays has been proposed as a solution. To evaluate and analyse the performances of 4G wireless systems software tools are normally used. Software tools have become more and more mature in recent years and their need to provide a high level evaluation of proposed algorithms and protocols is now more important. The system level simulation (SLS) tools provide a fundamental and flexible way to test all the envisioned algorithms and protocols under realistic conditions, without the need to deal with the problems of live networks or reduced scope prototypes. Furthermore, the tools allow network designers a rapid collection of a wide range of performance metrics that are useful for the analysis and optimization of different algorithms. This dissertation proposes the design and implementation of conventional system level simulator (SLS), which afterwards enhances for the 4G wireless technologies namely cognitive Radios (IEEE802.22) and Relays (IEEE802.16j). SLS is then used for the analysis of proposed algorithms and protocols.

Multi-purpose adaptable business tier components based on Call Level Interfaces

Call Level Interfaces (CLI) play a key role in business tiers of relational and on some NoSQL database applications whenever a fine tune control between application tiers and the host databases is a key requirement. Unfortunately, in spite of this significant advantage, CLI are low level API, this way not addressing high level architectural requirements. Among the examples we emphasize two situations: a) the need to decouple or not to decouple the development process of business tiers from the development process of application tiers and b) the need to automatically adapt business tiers to new business and/or security needs at runtime. To tackle these CLI drawbacks, and simultaneously keep their advantages, this paper proposes an architecture relying on CLI from which multi-purpose business tiers components are built, herein referred to as Adaptable Business Tier Components (ABTC). Beyond the reference architecture, this paper presents a proof of concept based on Java and Java Database Connectivity (an example of CLI).