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.

Contributos para a análise estatística de séries de contagem

A análise das séries temporais de valores inteiros tornou-se, nos últimos anos, uma área de investigação importante, não só devido à sua aplicação a dados de contagem provenientes de diversos campos da ciência, mas também pelo facto de ser uma área pouco explorada, em contraste com a análise séries temporais de valores contínuos. Uma classe que tem obtido especial relevo é a dos modelos baseados no operador binomial thinning, da qual se destaca o modelo auto-regressivo de valores inteiros de ordem p. Esta classe é muito vasta, pelo que este trabalho tem como objectivo dar um contributo para a análise estatística de processos de contagem que lhe pertencem. Esta análise é realizada do ponto de vista da predição de acontecimentos, aos quais estão associados mecanismos de alarme, e também da introdução de novos modelos que se baseiam no referido operador. Em muitos fenómenos descritos por processos estocásticos a implementação de um sistema de alarmes pode ser fundamental para prever a ocorrência de um acontecimento futuro. Neste trabalho abordam-se, nas perspectivas clássica e bayesiana, os sistemas de alarme óptimos para processos de contagem, cujos parâmetros dependem de covariáveis de interesse e que variam no tempo, mais concretamente para o modelo auto-regressivo de valores inteiros não negativos com coeficientes estocásticos, DSINAR(1). A introdução de novos modelos que pertencem à classe dos modelos baseados no operador binomial thinning é feita quando se propõem os modelos PINAR(1)T e o modelo SETINAR(2;1). O modelo PINAR(1)T tem estrutura periódica, cujas inovações são uma sucessão periódica de variáveis aleatórias independentes com distribuição de Poisson, o qual foi estudado com detalhe ao nível das suas propriedades probabilísticas, métodos de estimação e previsão. O modelo SETINAR(2;1) é um processo auto-regressivo de valores inteiros, definido por limiares auto-induzidos e cujas inovações formam uma sucessão de variáveis independentes e identicamente distribuídas com distribuição de Poisson. Para este modelo estudam-se as suas propriedades probabilísticas e métodos para estimar os seus parâmetros. Para cada modelo introduzido, foram realizados estudos de simulação para comparar os métodos de estimação que foram usados.

Integer-valued APARCH processes in the analysis of time series of counts

The Asymmetric Power Arch representation for the volatility was introduced by Ding et al.(1993) in order to account for asymmetric responses in the volatility in the analysis of continuous-valued financial time series like, for instance, the log-return series of foreign exchange rates, stock indices or share prices. As reported by Brannas and Quoreshi (2010), asymmetric responses in volatility are also observed in time series of counts such as the number of intra-day transactions in stocks. In this work, an asymmetric power autoregressive conditional Poisson model is introduced for the analysis of time series of counts exhibiting asymmetric overdispersion. Basic probabilistic and statistical properties are summarized and parameter estimation is discussed. A simulation study is presented to illustrate the proposed model. Finally, an empirical application to a set of data concerning the daily number of stock transactions is also presented to attest for its practical applicability in data analysis.

Characterization of the methanol recovery process at Prio Biocombustíveis S. A.

In a industrial environment, to know the process one is working with is crucial to ensure its good functioning. In the present work, developed at Prio Biocombustíveis S.A. facilities, using process data, collected during the present work, and historical process data, the methanol recovery process was characterized, having started with the characterization of key process streams. Based on the information retrieved from the stream characterization, Aspen Plus® process simulation software was used to replicate the process and perform a sensitivity analysis with the objective of accessing the relative importance of certain key process variables (reflux/feed ratio, reflux temperature, reboiler outlet temperature, methanol, glycerol and water feed compositions). The work proceeded with the application of a set of statistical tools, starting with the Principal Components Analysis (PCA) from which the interactions between process variables and their contribution to the process variability was studied. Next, the Design of Experiments (DoE) was used to acquire experimental data and, with it, create a model for the water amount in the distillate. However, the necessary conditions to perform this method were not met and so it was abandoned. The Multiple Linear Regression method (MLR) was then used with the available data, creating several empiric models for the water at distillate, the one with the highest fit having a R2 equal to 92.93% and AARD equal to 19.44%. Despite the AARD still being relatively high, the model is still adequate to make fast estimates of the distillate’s quality. As for fouling, its presence has been noticed many times during this work. Not being possible to directly measure the fouling, the reboiler inlet steam pressure was used as an indicator of the fouling growth and its growth variation with the amount of Used Cooking Oil incorporated in the whole process. Comparing the steam cost associated to the reboiler’s operation when fouling is low (1.5 bar of steam pressure) and when fouling is high (reboiler’s steam pressure of 3 bar), an increase of about 58% occurs when the fouling increases.

Self-exciting threshold binomial autoregressive processes

We introduce a new class of integer-valued self-exciting threshold models, which is based on the binomial autoregressive model of order one as introduced by McKenzie (Water Resour Bull 21:645–650, 1985. doi:10.1111/j.1752-1688.1985. tb05379.x). Basic probabilistic and statistical properties of this class of models are discussed. Moreover, parameter estimation and forecasting are addressed. Finally, the performance of these models is illustrated through a simulation study and an empirical application to a set of measle cases in Germany.