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.

Study of multiferroic materials

The present PhD work aims the research and development of materials that exhibit multiferroic properties, in particular having a significant interaction between ferromagnetism and ferroelectricity; either directly within an intrinsic single phase or by combining extrinsic materials, achieving the coupling of properties through mechanic phenomena of the respective magnetostriction and piezoelectricity. These hybrid properties will allow the cross modification of magnetic and electric polarization states by the application of cross external magnetic and/or electric fields, giving way to a vast area for scientific investigation and potential technological applications in a new generation of electronic devices, such as computer memories, signal processing, transducers, sensors, etc. Initial experimental work consisted in chemical synthesis of nano powders oxides by urea pyrolysis method: A series of ceramic bulk composites with potential multiferroic properties comprised: of LuMnO3 with La0.7Sr0.3MnO3 and BaTiO3 with La0.7Ba0.3MnO3; and a series based on the intrinsic multiferroic LuMn1-zO3 phase modified with of Manganese vacancies. The acquisition of a new magnetron RF sputtering deposition system, in the Physics Department of Aveiro University, contributed to the proposal of an analogous experimental study in multiferroic thin films and multilayer samples. Besides the operational debut of this equipment several technical upgrades were completed like: the design and construction of the heater electrical contacts; specific shutters and supports for the magnetrons and for the substrate holder and; the addition of mass flow controllers, which allowed the introduction of N2 or O2 active atmosphere in the chamber; and the addition of a second RF generator, enabling co-deposition of different targets. Base study of the deposition conditions and resulting thin films characteristics in different substrates was made from an extensive list of targets. Particular attention was given to thin film deposition of magnetic phases La1-xSrxMnO3, La1-xBaxMnO3 and Ni2+x-yMn1-xGa1+y alloy, from the respective targets: La0.7Sr0.3MnO3, La0.7Ba0.3MnO3; and NiGa with NiMn. Main structural characterization of samples was performed by conventional and high resolution X-Ray Diffraction (XRD); chemical composition was determined by Electron Dispersion Spectroscopy (EDS); magnetization measurements recur to a Vibrating Sample Magnetometer (VSM) prototype; and surface probing (SPM) using Magnetic-Force (MFM) and Piezo-Response (PFM) Microscopy. Results clearly show that the composite bulk samples (LuM+LSM and BTO+LBM) feat the intended quality objectives in terms of phase composition and purity, having spurious contents below 0.5 %. SEM images confirm compact grain packaging and size distribution around the 50 nm scale. Electric conductivity, magnetization intensity and magneto impedance spreading response are coherent with the relative amount of magnetic phase in the sample. The existence of coupling between the functional phases is confirmed by the Magnetoelectric effect measurements of the sample “78%LuM+22%LSM” reaching 300% of electric response for 1 T at 100 kHz; while in the “78%BTO+22%LBM” sample the structural transitions of the magnetic phase at ~350 K result in a inversion of ME coefficient the behavior. A functional Magneto-Resistance measurement system was assembled from the concept stage until the, development and operational status; it enabled to test samples from 77 to 350 K, under an applied magnetic field up to 1 Tesla with 360º horizontal rotation; this system was also designed to measure Hall effect and has the potential to be further upgraded. Under collaboration protocols established with national and international institutions, complementary courses and sample characterization studies were performed using Magneto-Resistance (MR), Magneto-Impedance (MZ) and Magneto-Electric (ME) measurements; Raman and X-ray Photoelectron Spectroscopy (XPS); SQUID and VSM magnetization; Scanning Electron Microscopy (SEM) and Rutherford Back Scattering (RBS); Scan Probe Microscopy (SPM) with Band Excitation Probe Spectroscopy (BEPS); Neutron Powder Diffraction (NPD) and Perturbed Angular Correlations (PAC). Additional collaboration in research projects outside the scope of multiferroic materials provided further experience in sample preparation and characterization techniques, namely VSM and XPS measurements were performed in cubane molecular complex compounds and enable to identify the oxidation state of the integrating cluster of Ru ions; also, XRD and EDS/SEM analysis of the acquired targets and substrates implied the devolution of some items not in conformity with the specifications. Direct cooperation with parallel research projects regarding multiferroic materials, enable the assess to supplementary samples, namely a preliminary series of nanopowder Y1-x-yCaxØyMn1O3 and of Eu0.8Y0.2MnO3, a series of micropowder composites of LuMnO3 with La0.625Sr0.375MnO3 and of BaTiO3 with hexagonal ferrites; mono and polycrystalline samples of Pr1-xCaxMnO3, La1-xSrxMnO3 and La1-xCaxMnO3.

Cooperative communications in multi-rate IEEE 802.11 networks

Esta tese apresenta um estudo sobre alguns dos protocolos de cooperação MAC para redes sem fios utilizando o sistema IEEE 802.11 multi-débito. É proposto um novo modelo de arquitetura para a categorização e análise da cooperação em redes sem fios, tendo este modelo sido aplicado a protocolos cooperativos existentes para camada MAC. É investigado como as características do meio físico, assim como os requisitos de níveis superiores podem ser aplicados ao processo de cooperação, com vista a melhorar as características de funcionamento da rede de comunicações. Para este propósito são exploradas as métricas mais relevantes para o processo de cooperação. São igualmente estudados os limites impostos pelos protocolos da camada MAC e as limitações práticas impostas por protocolos da família de normas que compõem o IEEE 802.11. Neste trabalho foi criada uma métrica multicamada, que permite considerar os requisitos aplicacionais de performance e o tipo de tráfego, assim como a mobilidade dos dispositivos, no funcionamento dos mecanismos de cooperação. Como forma de validação, e para corretamente avaliar o impacto da métrica, um novo protocolo de cooperação foi desenvolvido e implementado. O seu funcionamento é descrito de forma analítica assim como validado através de a um ambiente de simulação. Os resultados obtidos mostram que a utilização de uma métrica multicamada é uma técnica robusta, fornecendo melhorias consistentes no contexto de redes IEEE 802.11. São igualmente demonstradas várias outras características de funcionamento com impacto para as comunicações. Estes dados fornecem uma visão real e encorajadora para a realização de mais pesquisas para a melhoria da performance dos protocolos cooperativos, assim como a sua utilização num variado número de aplicações futuras. No final do documento são apresentados alguns desafios para a continuação da investigação deste tópico.

Precoding techniques for coordinated multicell systems

Coordenação Multicélula é um tópico de investigação em rápido crescimento e uma solução promissora para controlar a interferência entre células em sistemas celulares, melhorando a equidade do sistema e aumentando a sua capacidade. Esta tecnologia já está em estudo no LTEAdvanced sob o conceito de coordenação multiponto (COMP). Existem várias abordagens sobre coordenação multicélula, dependendo da quantidade e do tipo de informação partilhada pelas estações base, através da rede de suporte (backhaul network), e do local onde essa informação é processada, i.e., numa unidade de processamento central ou de uma forma distribuída em cada estação base. Nesta tese, são propostas técnicas de pré-codificação e alocação de potência considerando várias estratégias: centralizada, todo o processamento é feito na unidade de processamento central; semidistribuída, neste caso apenas parte do processamento é executado na unidade de processamento central, nomeadamente a potência alocada a cada utilizador servido por cada estação base; e distribuída em que o processamento é feito localmente em cada estação base. Os esquemas propostos são projectados em duas fases: primeiro são propostas soluções de pré-codificação para mitigar ou eliminar a interferência entre células, de seguida o sistema é melhorado através do desenvolvimento de vários esquemas de alocação de potência. São propostas três esquemas de alocação de potência centralizada condicionada a cada estação base e com diferentes relações entre desempenho e complexidade. São também derivados esquemas de alocação distribuídos, assumindo que um sistema multicelular pode ser visto como a sobreposição de vários sistemas com uma única célula. Com base neste conceito foi definido uma taxa de erro média virtual para cada um desses sistemas de célula única que compõem o sistema multicelular, permitindo assim projectar esquemas de alocação de potência completamente distribuídos. Todos os esquemas propostos foram avaliados em cenários realistas, bastante próximos dos considerados no LTE. Os resultados mostram que os esquemas propostos são eficientes a remover a interferência entre células e que o desempenho das técnicas de alocação de potência propostas é claramente superior ao caso de não alocação de potência. O desempenho dos sistemas completamente distribuídos é inferior aos baseados num processamento centralizado, mas em contrapartida podem ser usados em sistemas em que a rede de suporte não permita a troca de grandes quantidades de informação.

Design and optimization next generation passive all-optical networks

Este trabalho investiga novas metodologias para as redes óticas de acesso de próxima geração (NG-OAN). O trabalho está dividido em quatro tópicos de investigação: projeto da rede, modelos numéricos para efeitos não lineares da fibra ótica, impacto dos efeitos não lineares da fibra ótica e otimização da rede. A rede ótica de acesso investigada nesse trabalho está projetado para suprir os requisitos de densidade de utilizadores e cobertura, isto é, suportar muitos utilizadores ( 1000) com altas velocidades de conexão dedicada ( 1 Gb/s) ocupando uma faixa estreita do espectro ( 25 nm) e comprimentos de fibra ótica até 100 km. Os cenários são baseados em redes óticas passivas com multiplexagem por divisão no comprimento de onda de alta densidade (UDWDM-PON) utilizando transmissores/receptores coerentes nos terminais da rede. A rede é avaliada para vários ritmos de transmissão usando formatos de modulação avançados, requisitos de largura de banda por utilizador e partilha de banda com tecnologias tradicionais de redes óticas passivas (PON). Modelos numéricos baseados em funções de transferência das séries de Volterra (VSTF) são demonstrados tanto para a análise dos efeitos não lineares da fibra ótica quanto para avaliação do desempenho total da rede. São apresentadas as faixas de potência e distância de transmissão nas quais as séries de Volterra apresentam resultados semelhantes ao modelo referência Split-Step Fourier (SSF) (validado experimentalmente) para o desempenho total da rede. Além disso, um algoritmo, que evita componentes espectrais com intensidade nulo, é proposto para realizar cálculos rápidos das séries. O modelo VSTF é estendido para identificar unicamente os efeitos não lineares da fibra ótica mais relevantes no cenário investigado: Self-Phase Modulation (SPM), Cross-Phase Modulation (XPM) e Four-Wave Mixing (FWM). Simulações numéricas são apresentadas para identificar o impacto isolado de cada efeito não linear da fibra ótica, SPM, XPM e FWM, no desempenho da rede com detecção coerente UDWDM-PON, transportando canais com modulação digital em fase (M-ária PSK) ou modulação digital em amplitude (M-ária QAM). A análise numérica é estendida para diferentes comprimentos de fibra ótica mono modo (SSMF), potência por canal e ritmo de transmissão por canal. Por conseguinte, expressões analíticas são extrapoladas para determinar a evolução do SPM, XPM e FWM em função da potência e distância de transmissão em cenários NG-OAN. O desempenho da rede é otimizada através da minimização parcial da interferência FWM (via espaçamento desigual dos canais), que nesse caso, é o efeito não linear da fibra ótica mais relevante. Direções para melhorias adicionas no desempenho da rede são apresentados para cenários em que o XPM é relevante, isto é, redes transportando formatos de modulação QAM. A solução, nesse caso, é baseada na utilização de técnicas de processamento digital do sinal.

Channel estimation and parameters acquisition systems employing cooperative diversity

This work investigates new channel estimation schemes for the forthcoming and future generation of cellular systems for which cooperative techniques are regarded. The studied cooperative systems are designed to re-transmit the received information to the user terminal via the relay nodes, in order to make use of benefits such as high throughput, fairness in access and extra coverage. The cooperative scenarios rely on OFDM-based systems employing classical and pilot-based channel estimators, which were originally designed to pointto-point links. The analytical studies consider two relaying protocols, namely, the Amplifyand-Forward and the Equalise-and-Forward, both for the downlink case. The relaying channels statistics show that such channels entail specific characteristics that comply to a proper filter and equalisation designs. Therefore, adjustments in the estimation process are needed in order to obtain the relay channel estimates, refine these initial estimates via iterative processing and obtain others system parameters that are required in the equalisation. The system performance is evaluated considering standardised specifications and the International Telecommunication Union multipath channel models.

Behavioral modeling optimization and enhancement for high-speed analog mixed-signal I/O interfaces

A integridade do sinal em sistemas digitais interligados de alta velocidade, e avaliada através da simulação de modelos físicos (de nível de transístor) é custosa de ponto vista computacional (por exemplo, em tempo de execução de CPU e armazenamento de memória), e exige a disponibilização de detalhes físicos da estrutura interna do dispositivo. Esse cenário aumenta o interesse pela alternativa de modelação comportamental que descreve as características de operação do equipamento a partir da observação dos sinais eléctrico de entrada/saída (E/S). Os interfaces de E/S em chips de memória, que mais contribuem em carga computacional, desempenham funções complexas e incluem, por isso, um elevado número de pinos. Particularmente, os buffers de saída são obrigados a distorcer os sinais devido à sua dinâmica e não linearidade. Portanto, constituem o ponto crítico nos de circuitos integrados (CI) para a garantia da transmissão confiável em comunicações digitais de alta velocidade. Neste trabalho de doutoramento, os efeitos dinâmicos não-lineares anteriormente negligenciados do buffer de saída são estudados e modulados de forma eficiente para reduzir a complexidade da modelação do tipo caixa-negra paramétrica, melhorando assim o modelo standard IBIS. Isto é conseguido seguindo a abordagem semi-física que combina as características de formulação do modelo caixa-negra, a análise dos sinais eléctricos observados na E/S e propriedades na estrutura física do buffer em condições de operação práticas. Esta abordagem leva a um processo de construção do modelo comportamental fisicamente inspirado que supera os problemas das abordagens anteriores, optimizando os recursos utilizados em diferentes etapas de geração do modelo (ou seja, caracterização, formulação, extracção e implementação) para simular o comportamento dinâmico não-linear do buffer. Em consequência, contributo mais significativo desta tese é o desenvolvimento de um novo modelo comportamental analógico de duas portas adequado à simulação em overclocking que reveste de um particular interesse nas mais recentes usos de interfaces de E/S para memória de elevadas taxas de transmissão. A eficácia e a precisão dos modelos comportamentais desenvolvidos e implementados são qualitativa e quantitativamente avaliados comparando os resultados numéricos de extracção das suas funções e de simulação transitória com o correspondente modelo de referência do estado-da-arte, IBIS.