A busca por entender e copiar o majestoso mundo que nos cerca fez do homem um curioso por natureza. Santos Dumont realizou a proeza de alcançar um dos sonhos mais antigos do homem, voar. Charles Darwin escreveu a Teoria da Evolução como um paradigma para a nossa existência, inspirando John Holland a desenvolver os Algoritmos Genéticos. Atualmente, com o grande crescimento da demanda no transporte aéreo, o homem volta seus esforços na busca por soluções que garantam a segurança da sociedade. Recentemente o pesquisador Naufal reuniu todos esses conceitos e desenvolveu um Modelo de Otimização de Demanda para o setor aeronáutico. Tal modelo visa amenizar a carga de trabalho dos controladores de tráfego aéreo na busca por aumentar a qualidade do serviço prestado por esse profissional, garantindo dessa forma níveis aceitáveis de segurança. Embora o modelo tenha se mostrado eficiente, ele apresentou uma deficiência quanto aos tempos despendidos para alcançar bons resultados. Na tentativa de otimizar os tempos do modelo atual, este trabalho de pesquisa adicionou o conceito de pressão seletiva, que representa a influência do meio ambiente. A representação da influência que o meio ambiente tem dentro da teoria da evolução de Darwin pode gerar uma implementação mais realista dos algoritmos genéticos. Este trabalho propõe a aplicação dos métodos de controle da pressão seletiva como alternativa de diminuir os tempos despendidos pelo modelo de otimização de demanda na busca por aumentar a segurança do setor aeroviário. / The search for understanding and copying the magnificent world that surrounds us has made man curious by nature. Santos Dumont achieved one of man?s most ancient dreams, to fly. Charles Darwin wrote the Theory of Evolution as a paradigm of our existence, inspiring John Holland to develop genetic algorithms. Presently, because of the growth of demand in air transportation, men concentrate their efforts in the search for solutions that can guarantee the safety of our society. Recently, researcher Naufal has gathered all these concepts and developed a Demand Optimization Model for the aeronautical sector. This model aims to ease the workload of air traffic controllers, in a search for increasing the quality of this service and guaranteeing acceptable levels of safety. Although his model has proved to be efficient, it has presented a weak point when it comes to time spent to reach good results. In an attempt to optimize time in the existing model, this research added the concept of selective pressure, which represents the influence of the environment. The representation of the influence that the environment has inside Darwin?s Theory of Evolution can generate a more realistic implementation of genetic algorithms. This work proposes an application of selective pressure control methods as an alternative to diminish time spent by the Demand Optimization Model in a search for increasing safety for the aeronautical sector.

A busca por entender e copiar o majestoso mundo que nos cerca fez do homem um curioso por natureza. Santos Dumont realizou a proeza de alcançar um dos sonhos mais antigos do homem, voar. Charles Darwin escreveu a Teoria da Evolução como um paradigma para a nossa existência, inspirando John Holland a desenvolver os Algoritmos Genéticos. Atualmente, com o grande crescimento da demanda no transporte aéreo, o homem volta seus esforços na busca por soluções que garantam a segurança da sociedade. Recentemente o pesquisador Naufal reuniu todos esses conceitos e desenvolveu um Modelo de Otimização de Demanda para o setor aeronáutico. Tal modelo visa amenizar a carga de trabalho dos controladores de tráfego aéreo na busca por aumentar a qualidade do serviço prestado por esse profissional, garantindo dessa forma níveis aceitáveis de segurança. Embora o modelo tenha se mostrado eficiente, ele apresentou uma deficiência quanto aos tempos despendidos para alcançar bons resultados. Na tentativa de otimizar os tempos do modelo atual, este trabalho de pesquisa adicionou o conceito de pressão seletiva, que representa a influência do meio ambiente. A representação da influência que o meio ambiente tem dentro da teoria da evolução de Darwin pode gerar uma implementação mais realista dos algoritmos genéticos. Este trabalho propõe a aplicação dos métodos de controle da pressão seletiva como alternativa de diminuir os tempos despendidos pelo modelo de otimização de demanda na busca por aumentar a segurança do setor aeroviário. / The search for understanding and copying the magnificent world that surrounds us has made man curious by nature. Santos Dumont achieved one of man?s most ancient dreams, to fly. Charles Darwin wrote the Theory of Evolution as a paradigm of our existence, inspiring John Holland to develop genetic algorithms. Presently, because of the growth of demand in air transportation, men concentrate their efforts in the search for solutions that can guarantee the safety of our society. Recently, researcher Naufal has gathered all these concepts and developed a Demand Optimization Model for the aeronautical sector. This model aims to ease the workload of air traffic controllers, in a search for increasing the quality of this service and guaranteeing acceptable levels of safety. Although his model has proved to be efficient, it has presented a weak point when it comes to time spent to reach good results. In an attempt to optimize time in the existing model, this research added the concept of selective pressure, which represents the influence of the environment. The representation of the influence that the environment has inside Darwin?s Theory of Evolution can generate a more realistic implementation of genetic algorithms. This work proposes an application of selective pressure control methods as an alternative to diminish time spent by the Demand Optimization Model in a search for increasing safety for the aeronautical sector.

Achieving high computation efficiency, in terms of Cycles per Instruction (CPI), for high-performance computing kernels is an interesting and challenging research area. Dense Linear Algebra (DLA) computation is a representative high-performance computing ap- plication, which is used, for example, in LU and QR factorizations. Unfortunately, mod- ern off-the-shelf microprocessors fall significantly short of achieving theoretical lower bound in CPI for high performance computing applications. In this thesis, we perform an in-depth analysis of the available parallelisms and propose suitable algorithmic and architectural variation to significantly improve the computation efficiency. There are two standard approaches for improving the computation effficiency, first, to perform application-specific architecture customization and second, to do algorithmic tuning. In the same manner, we first perform a graph-based analysis of selected DLA kernels. From the various forms of parallelism, thus identified, we design a custom processing element for improving the CPI. The processing elements are used as building blocks for a commercially available Coarse-Grained Reconfigurable Architecture (CGRA). By per- forming detailed experiments on a synthesized CGRA implementation, we demonstrate that our proposed algorithmic and architectural variations are able to achieve lower CPI compared to off-the-shelf microprocessors. We also benchmark against state-of-the-art custom implementations to report higher energy-performance-area product. DLA computations are encountered in many engineering and scientific computing ap- plications ranging from Computational Fluid Dynamics (CFD) to Eigenvalue problem. Traditionally, these applications are written in highly tuned High Performance Comput- ing (HPC) software packages like Linear Algebra Package (LAPACK), and/or Scalable Linear Algebra Package (ScaLAPACK). The basic building block for these packages is Ba- sic Linear Algebra Subprograms (BLAS). Algorithms pertaining LAPACK/ScaLAPACK are written in-terms of BLAS to achieve high throughput. Despite extensive intellectual efforts in development and tuning of these packages, there still exists a scope for fur- ther tuning in this packages. In this thesis, we revisit most prominent and widely used compute bound algorithms like GMM for further exploitation of Instruction Level Parallelism (ILP). We further look into LU and QR factorizations for generalizations and exhibit higher ILP in these algorithms. We first accelerate sequential performance of the algorithms in BLAS and LAPACK and then focus on the parallel realization of these algorithms. Major contributions in the algorithmic tuning in this thesis are as follows: Algorithms: We present graph based analysis of General Matrix Multiplication (GMM) and discuss different types of parallelisms available in GMM We present analysis of Givens Rotation based QR factorization where we improve GR and derive Column-wise GR (CGR) that can annihilate multiple elements of a column of a matrix simultaneously. We show that the multiplications in CGR are lower than GR We generalize CGR further and derive Generalized GR (GGR) that can annihilate multiple elements of the columns of a matrix simultaneously. We show that the parallelism exhibited by GGR is much higher than GR and Householder Transform (HT) We extend generalizations to Square root Free GR (also knows as Fast Givens Rotation) and Square root and Division Free GR (SDFG) and derive Column-wise Fast Givens, and Column-wise SDFG . We also extend generalization for complex matrices and derive Complex Column-wise Givens Rotation Coarse-grained Recon gurable Architectures (CGRAs) have gained popularity in the last decade due to their power and area efficiency. Furthermore, CGRAs like REDEFINE also exhibit support for domain customizations. REDEFINE is an array of Tiles where each Tile consists of a Compute Element and a Router. The Routers are responsible for on-chip communication, while Compute Elements in the REDEFINE can be domain customized to accelerate the applications pertaining to the domain of interest. In this thesis, we consider REDEFINE base architecture as a starting point and we design Processing Element (PE) that can execute algorithms in BLAS and LAPACK efficiently. We perform several architectural enhancements in the PE to approach lower bound of the CPI. For parallel realization of BLAS and LAPACK, we attach this PE to the Router of REDEFINE. We achieve better area and power performance compared to the yesteryear customized architecture for DLA. Major contributions in architecture in this thesis are as follows: Architecture: We present design of a PE for acceleration of GMM which is a Level-3 BLAS operation We methodically enhance the PE with different features for improvement in the performance of GMM For efficient realization of Linear Algebra Package (LAPACK), we use PE that can efficiently execute GMM and show better performance For further acceleration of LU and QR factorizations in LAPACK, we identify macro operations encountered in LU and QR factorizations, and realize them on a reconfigurable data-path resulting in 25-30% lower run-time