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.

Multilayer optimization in radio resource allocation for the packet transmission in wireless networks

Na última década tem-se assistido a um crescimento exponencial das redes de comunicações sem fios, nomeadamente no que se refere a taxa de penetração do serviço prestado e na implementação de novas infra-estruturas em todo o globo. É ponto assente neste momento que esta tendência irá não só continuar como se fortalecer devido à convergência que é esperada entre as redes móveis sem fio e a disponibilização de serviços de banda larga para a rede Internet fixa, numa evolução para um paradigma de uma arquitectura integrada e baseada em serviços e aplicações IP. Por este motivo, as comunicações móveis sem fios irão ter um papel fundamental no desenvolvimento da sociedade de informação a médio e longo prazos. A estratégia seguida no projecto e implementação das redes móveis celulares da actual geração (2G e 3G) foi a da estratificação da sua arquitectura protocolar numa estrutura modular em camadas estanques, onde cada camada do modelo é responsável pela implementação de um conjunto de funcionalidades. Neste modelo a comunicação dá-se apenas entre camadas adjacentes através de primitivas de comunicação pré-estabelecidas. Este modelo de arquitectura resulta numa mais fácil implementação e introdução de novas funcionalidades na rede. Entretanto, o facto das camadas inferiores do modelo protocolar não utilizarem informação disponibilizada pelas camadas superiores, e vice-versa acarreta uma degradação no desempenho do sistema. Este paradigma é particularmente importante quando sistemas de antenas múltiplas são implementados (sistemas MIMO). Sistemas de antenas múltiplas introduzem um grau adicional de liberdade no que respeita a atribuição de recursos rádio: o domínio espacial. Contrariamente a atribuição de recursos no domínio do tempo e da frequência, no domínio espacial os recursos rádio mapeados no domínio espacial não podem ser assumidos como sendo completamente ortogonais, devido a interferência resultante do facto de vários terminais transmitirem no mesmo canal e/ou slots temporais mas em feixes espaciais diferentes. Sendo assim, a disponibilidade de informação relativa ao estado dos recursos rádio às camadas superiores do modelo protocolar é de fundamental importância na satisfação dos critérios de qualidade de serviço exigidos. Uma forma eficiente de gestão dos recursos rádio exige a implementação de algoritmos de agendamento de pacotes de baixo grau de complexidade, que definem os níveis de prioridade no acesso a esses recursos por base dos utilizadores com base na informação disponibilizada quer pelas camadas inferiores quer pelas camadas superiores do modelo. Este novo paradigma de comunicação, designado por cross-layer resulta na maximização da capacidade de transporte de dados por parte do canal rádio móvel, bem como a satisfação dos requisitos de qualidade de serviço derivados a partir da camada de aplicação do modelo. Na sua elaboração, procurou-se que o standard IEEE 802.16e, conhecido por Mobile WiMAX respeitasse as especificações associadas aos sistemas móveis celulares de quarta geração. A arquitectura escalonável, o baixo custo de implementação e as elevadas taxas de transmissão de dados resultam num processo de multiplexagem de dados e valores baixos no atraso decorrente da transmissão de pacotes, os quais são atributos fundamentais para a disponibilização de serviços de banda larga. Da mesma forma a comunicação orientada à comutação de pacotes, inenente na camada de acesso ao meio, é totalmente compatível com as exigências em termos da qualidade de serviço dessas aplicações. Sendo assim, o Mobile WiMAX parece satisfazer os requisitos exigentes das redes móveis de quarta geração. Nesta tese procede-se à investigação, projecto e implementação de algoritmos de encaminhamento de pacotes tendo em vista a eficiente gestão do conjunto de recursos rádio nos domínios do tempo, frequência e espacial das redes móveis celulares, tendo como caso prático as redes móveis celulares suportadas no standard IEEE802.16e. Os algoritmos propostos combinam métricas provenientes da camada física bem como os requisitos de qualidade de serviço das camadas superiores, de acordo com a arquitectura de redes baseadas no paradigma do cross-layer. O desempenho desses algoritmos é analisado a partir de simulações efectuadas por um simulador de sistema, numa plataforma que implementa as camadas física e de acesso ao meio do standard IEEE802.16e.

Nonaqueous sol-gel routes to doped metal oxide nanoparticles: synthesis, characterization, assembly and properties

The results presented in this thesis have been achieved under the Ph.D. project entitled “Nonaqueous Sol-Gel routes to doped metal oxide nanoparticles: Synthesis, characterization, assembly and properties”. The purpose of this study is the investigation of metal oxide nanostructures doped with metals of a diverse nature, leading to different type of applications. The easier control over the reaction kinetics in solvothermal routes, compared to aqueous methods, allows to better match the reactivity between metal oxide precursors, paving the way to a facile and low temperature production of doped oxides. In this manuscript diverse examples of the exploitation of the “Benzyl Alcohol Route” are discussed. Such a powerful pathway was utilized for the synthesis of transition metal doped zirconia, hafnia and various perovskites, and the study of their magnetic properties, as well as the synthesis of rare earth doped zirconium oxide. A further extension, proving the solidity of the synthetic method, is shown for the preparation of Li4Ti5O12 nanocrystals carrying excellent electrochemical properties for lithium-ion battery applications. Finally, the effect of doping and other reaction parameters on the assembly of the nanocrystals is discussed. These studies were carried out principally at the University of Aveiro, as well as at the University of Montpellier II and at the Seoul National University due to complementary available expertises and equipments.

Fiber optic sensors for the biomechanical study of the intervertebral disc

O presente trabalho teve como objetivo principal estudar o comportamento mecânico do disco intervertebral recorrendo a sensores em fibra ótica. Na expetativa de efetuar o melhor enquadramento do tema foi efetuada uma revisão exaustiva das várias configurações de sensores em fibra ótica que têm vindo a ser utilizadas em aplicações biomédicas e biomecânicas, nomeadamente para medição de temperatura, deformação, força e pressão. Nesse âmbito, procurou-se destacar as potencialidades dos sensores em fibra ótica e apresentá-los como uma tecnologia alternativa ou até de substituição das tecnologias associadas a sensores convencionais. Tendo em vista a aplicação de sensores em fibra ótica no estudo do comportamento do disco intervertebral efetuou-se também uma revisão exaustiva da coluna vertebral e, particularmente, do conceito de unidade funcional. A par de uma descrição anatómica e funcional centrada no disco intervertebral, vértebras adjacentes e ligamentos espinais foram ainda destacadas as suas propriedades mecânicas e descritos os procedimentos mais usuais no estudo dessas propriedades. A componente experimental do presente trabalho descreve um conjunto de experiências efetuadas com unidades funcionais cadavéricas utilizando sensores convencionais e sensores em fibra ótica com vista à medição da deformação do disco intervertebral sob cargas compressivas uniaxiais. Inclui ainda a medição in vivo da pressão intradiscal num disco lombar de uma ovelha sob efeito de anestesia. Para esse efeito utilizou-se um sensor comercial em fibra ótica e desenvolveu-se a respetiva unidade de interrogação. Finalmente apresenta-se os resultados da investigação em curso que tem como objetivo propor e desenvolver protótipos de sensores em fibra ótica para aplicações biomédicas e biomecânicas. Nesse sentido, são apresentadas duas soluções de sensores interferométricos para medição da pressão em fluídos corporais.

Optimisation of viscoelastic treatments using genetic algorithms

Viscoelastic treatments are one of the most efficient treatments, as far as passive damping is concerned, particularly in the case of thin and light structures. In this type of treatment, part of the strain energy generated in the viscoelastic material is dissipated to the surroundings, in the form of heat. A layer of viscoelastic material is applied to a structure in an unconstrained or constrained configuration, the latter proving to be the most efficient arrangement. This is due to the fact that the relative movement of both the host and constraining layers cause the viscoelastic material to be subjected to a relatively high strain energy. There are studies, however, that claim that the partial application of the viscoelastic material is just as efficient, in terms of economic costs or any other form of treatment application costs. The application of patches of material in specific and selected areas of the structure, thus minimising the extension of damping material, results in an equally efficient treatment. Since the damping mechanism of a viscoelastic material is based on the dissipation of part of the strain energy, the efficiency of the partial treatment can be correlated to the modal strain energy of the structure. Even though the results obtained with this approach in various studies are considered very satisfactory, an optimisation procedure is deemed necessary. In order to obtain optimum solutions, however, time consuming numerical simulations are required. The optimisation process to use the minimum amount of viscoelastic material is based on an evolutionary geometry re-design and calculation of the modal damping, making this procedure computationally costly. To avert this disadvantage, this study uses adaptive layerwise finite elements and applies Genetic Algorithms in the optimisation process.

NMR in the characterization of heavy residual procedural streams

The main objective of this work was to monitor a set of physical-chemical properties of heavy oil procedural streams through nuclear magnetic resonance spectroscopy, in order to propose an analysis procedure and online data processing for process control. Different statistical methods which allow to relate the results obtained by nuclear magnetic resonance spectroscopy with the results obtained by the conventional standard methods during the characterization of the different streams, have been implemented in order to develop models for predicting these same properties. The real-time knowledge of these physical-chemical properties of petroleum fractions is very important for enhancing refinery operations, ensuring technically, economically and environmentally proper refinery operations. The first part of this work involved the determination of many physical-chemical properties, at Matosinhos refinery, by following some standard methods important to evaluate and characterize light vacuum gas oil, heavy vacuum gas oil and fuel oil fractions. Kinematic viscosity, density, sulfur content, flash point, carbon residue, P-value and atmospheric and vacuum distillations were the properties analysed. Besides the analysis by using the standard methods, the same samples were analysed by nuclear magnetic resonance spectroscopy. The second part of this work was related to the application of multivariate statistical methods, which correlate the physical-chemical properties with the quantitative information acquired by nuclear magnetic resonance spectroscopy. Several methods were applied, including principal component analysis, principal component regression, partial least squares and artificial neural networks. Principal component analysis was used to reduce the number of predictive variables and to transform them into new variables, the principal components. These principal components were used as inputs of the principal component regression and artificial neural networks models. For the partial least squares model, the original data was used as input. Taking into account the performance of the develop models, by analysing selected statistical performance indexes, it was possible to conclude that principal component regression lead to worse performances. When applying the partial least squares and artificial neural networks models better results were achieved. However, it was with the artificial neural networks model that better predictions were obtained for almost of the properties analysed. With reference to the results obtained, it was possible to conclude that nuclear magnetic resonance spectroscopy combined with multivariate statistical methods can be used to predict physical-chemical properties of petroleum fractions. It has been shown that this technique can be considered a potential alternative to the conventional standard methods having obtained very promising results.

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue μ of multiplicity m. A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (k ,t)-regular if it induces a k -regular subgraph and every vertex not in the subset has t neighbors in it. We investigate the graphs having a (k,t)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.

Bioinformatics analysis of the Pedobacter sp. NL19 genome

The last decades of the 20th century defined the genetic engineering advent, climaxing in the development of techniques, such as PCR and Sanger sequencing. This, permitted the appearance of new techniques to sequencing whole genomes, identified as next-generation sequencing. One of the many applications of these techniques is the in silico search for new secondary metabolites, synthesized by microorganisms exhibiting antimicrobial properties. The peptide antibiotics compounds can be classified in two classes, according to their biosynthesis, in ribosomal or nonribosomal peptides. Lanthipeptides are the most studied ribosomal peptides and are characterized by the presence of lanthionine and methylanthionine that result from posttranslational modifications. Lanthipeptides are divided in four classes, depending on their biosynthetic machinery. In class I, a LanB enzyme dehydrate serine and threonine residues in the C-terminus precursor peptide. Then, these residues undergo a cyclization step performed by a LanC enzyme, forming the lanthionine rings. The cleavage and the transport of the peptide is achieved by the LanP and LanT enzymes, respectively. Although, in class II only one enzyme, LanM, is responsible for the dehydration and cyclization steps and also only one enzyme performs the cleavage and transport, LanT. Pedobacter sp. NL19 is a Gram-negative bacterium, isolated from sludge of an abandon uranium mine, in Viseu (Portugal). Antibacterial activity in vitro was detected against several Gram-positive and Gram-negative bacteria. Sequencing and in silico analysis of NL19 genome revealed the presence of 21 biosynthetic clusters for secondary metabolites, including nonribosomal and ribosomal peptides biosynthetic clusters. Four lanthipeptides clusters were predicted, comprising the precursor peptides, the modifying enzymes (LanB and LanC), and also a bifunctional LanT. This result revealed the hybrid nature of the clusters, comprising characteristics from two distinct classes, which are poorly described in literature. The phylogenetic analysis of their enzymes showed that they clustered within the bacteroidetes clade. Furthermore, hybrid gene clusters were also found in other species of this phylum, revealing that it is a common characteristic in this group. Finally, the analysis of NL19 colonies by MALDI-TOF MS allowed the identification of a 3180 Da mass that corresponds to the predicted mass of a lanthipeptide encoded in one of the clusters. However, this result is not fully conclusive and further experiments are needed to understand the full potential of the compounds encoded in this type of clusters. In conclusion, it was determined that NL19 strain has the potential to produce diverse secondary metabolites, including lanthipeptides that were not functionally characterized so far.