This research focuses on a novel integrated approach for computing and representing complex numbers as a single entity without the use of any dedicated multiplier for calculating the fast Fourier transform algorithm (FFT), using the Distributed Arithmetic (DA) technique and Complex Binary Number Systems (CBNS). The FFT algorithm is one of the most used and implemented technique employed in many Digital Signal Processing (DSP) applications in the field of science, engineering, and mathematics. The DA approach is a technique that is used to compute the inner dot product between two vectors without the use of any dedicated multipliers. These dedicated multipliers are fast but they consume a large amount of hardware and are quite costly. The DA multiplier process is accomplished by shifting and adding only without the need of any dedicated multiplier. In today's technology, complex numbers are computed using the divide and conquer approach in which complex numbers are divided into two parts: the real and imaginary. The CBNS technique however, allows for each complex addition and multiplication to be computed in one single step instead of two. With the combined DA-CBNS approach for computing the FFT algorithm, those dedicated multipliers are being replaced with a DA system that utilize a Rom-based memory for storing the twiddle factor 'wn' value and the complex arithmetic operations being represented as a single entity, not two, with the CBNS approach. This architectural design was implemented by coding in a very high speed integrated circuit (VHSIC) hardware description language (VHDL) using Xilinx ISE design suite software program version 14.2. This computer aided tool allows for the design to be synthesized to a logic gate level in order to be further implemented onto a Field Programmable Gate Array (FPGA) device. The VHDL code used to build this architecture was downloaded on a Nexys 4 DDR Artix-7 FPGA board for further testing and analysis. This novel technique resulted in the use of no dedicated multipliers and required half the amount of complex arithmetic computations needed for calculating an FFT structure compared with its current traditional approach. Finally, the results showed that for the proposed architecture design, for a 32 bit, 8-point DA-CBNS FFT structure, the results showed a 32% area reduction, 41% power reduction, 59% reduction in run-time, 42% reduction in logic gate cost, and 66% increase in speed. For a 28 bit, 16-point DA-CBNS FFT structure, its area size, power consumption, run-time, and logic gate, were also found to be reduced at approximately 30%, 37%, 60%, and 39%, respectively, with an increase of speed of approximately 67% when compared to the traditional approach that employs dedicated multipliers and computes its complex arithmetic as two separate entities: the real and imaginary.

Made available in DSpace on 2015-04-22T22:00:47Z (GMT). No. of bitstreams: 1 jose.pdf: 2255469 bytes, checksum: cebe37770c4719e5ebf2b60e4ae0d2a6 (MD5) Previous issue date: 2013-06-07 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Currently, the majority of multicarrier transmission systems are based on the Fourier transform, which is used as frequency multiplexing technique. The main advantages of this approach include multipath immunity and low computational complexity, due to the use of a family of fast algorithms, known as Fast Fourier Transform (FFT). However, when used to provide a robust transmission, this technique presents some disadvantages, like the need for a cyclic prefix, which demands part of the useful datarate. In this work, a study for verifying the possibility of replacing the FFT, by the wavelet transform, was carried out, which has the potential to raise some advantages, such as the removal of the cyclic prefix and a simpler synchronization procedure. A computational model for the transmission layer of the Integrated Services Digital Broadcasting Terrestrial, Brazilian version (ISDB-Tb) was created, aiming to provide a direct comparison between two versions: the traditional one, which is based on FFT, and a new proposal, which is based on wavelets. Such an evaluation was performed through the relation between error bit rate and signal-to-noise ratio, in additive white gaussian noise, Rayleigh and Rician fading and also in frequency-selective Rayleigh fading channels. Similar comparisons were also performed for the ETSI TS 101 475 (HIPERLAN-2) and Digital Video Broadcasting Terrestrial (DVB-T) systems. The simulation results show that the wavelet-based systems present a similar performance, when compared with the FFT-based ones, for the chosen channel models, and without employing a cyclic prefix, which allows a more efficiente spectrum use. / Atualmente, uma grande parte dos sistemas de transmissão multiportadoras é baseada na transformada de Fourier, como técnica de multiplexação em frequência. Dentre as suas principais vantagens, encontram-se a imunidade a multipercursos e a baixa complexidade computacional, através de algoritmos rápidos conhecidos como Fast Fourier Transform (FFT). Esta técnica, entretanto, para proporcionar uma transmissão robusta, apresenta a desvantagem de exigir prefixo cíclico, o que resulta no consumo de uma fatia do espectro útil. Neste trabalho, um estudo para se verificar a viabilidade de substituição da FFT pela transformada wavelet foi realizado, o que promete trazer algumas vantagens, tais como a não exigência de prefixo cíclico e uma sincronização mais simples. Um modelo computacional para a camada de transmissão do Integrated Services Digital Broadcasting - Terrestrial, Brazilian version (ISDB-Tb) foi criado, com o objetivo de proporcionar uma comparação entre duas versões: a atual, baseada em FFT, e uma nova proposta, baseada em wavelets. Tal avaliação foi realizada em termos das curvas de taxa de erro de bit versus relação sinal ruído, em canais com adição de ruído gaussiano branco, com desvanecimento plano de Rayleigh e Rice e também com desvanecimento seletivo em frequência de Rayleigh. Comparações similares também foram realizadas para os sistemas ETSI TS 101 475 (HIPERLAN-2) e Digital Video Broadcasting Terrestrial (DVB-T). Os resultados obtidos mostram que os sistemas baseados em wavelets apresentam desempenhos similares aos dos baseados em FFT, para os modelos de canal simulados, com a vantagem adicional de não utilizarem prefixo cíclico, o que promove um uso mais eficiente do espectro.

In this dissertation a novel approach to protein-ligand docking is presented. First an existing method to predict putative active sites is employed. These predictions are then used to cut down the search space of an algorithm that uses the fast Fourier transform to calculate the geometrical and electrostatic complementarity between a protein and a small organic ligand. A simplified hydrophobicity score is also calculated for each active site. The docking method could be applied either to dock ligands in a known active site or to rank several putative active sites according to their biological feasibility. The method was evaluated on a set of 310 protein-ligand complexes. The results show that with respect to docking the method with its initial parameter settings is too coarse grained. The results also show that with respect to ranking of putative active sites the method works quite well.

La théorie d'homogénéisation élastodynamique des matériaux hétérogènes initiée par J.R. Willis il y a environ une trentaine d'années a récemment reçu une très grande attention. D'après cette théorie qui est mathématiquement exacte, la loi constitutive homogénéisée est non locale en espace et en temps ; le tenseur des contraintes dépend non seulement du tenseur des déformations mais aussi de la vitesse ; la quantité du mouvement dépend à la fois de la vitesse et du tenseur des déformations, faisant apparaître en général une masse anisotrope. Ces propriétés constitutives effectives, qui pourraient être surprenantes d'un point de vue mécanique classique, se révèlent en fait très utiles pour la conception de métamatériaux acoustiques et de capes acoustiques. Ce travail de thèse consiste essentiellement à proposer et développer deux méthodes numériques efficaces pour déterminer les propriétés élastodynamiques effectives des matériaux périodiquement hétérogènes. La première méthode relève de la méthode des éléments finis alors que la deuxième méthode est basée sur la transformée de Fourier rapide. Ces deux méthodes sont d'abord élaborées pour une microstructure périodique 3D quelconque et ensuite implantées pour une microstructure périodique 2D quelconque. Les avantages et les inconvénients de chacune de ces deux méthodes sont comparés et discutés. A l'aide des méthodes numériques élaborées, la théorie de Willis est appliquée au calcul élastodynamique sur un milieu infini hétérogène et celui homogénéisé. Les différents cas d'homogénéisabilité et de non-homogénéisabilité sont discutés / The elastodynamic homogenization theory of heterogeneous materials initiated by J.R. Willis about thirty years ago has recently received considerable attention. According to this theory which is mathematically exact, the homogenized constitutive law is non-local in space and time; the stress tensor depends not only on the strain tensor but also on the velocity; the linear momentum depends on both the velocity and the strain tensor, making appear an anisotropic mass tensor in general. These effective constitutive properties, which may be surprising from a classical mechanical point of view, turn out in fact to be very useful for the design of acoustic metamaterials and acoustic cloaks. The present work is essentially to propose and develop two efficient numerical methods for determining the effective elastodynamic properties of periodically heterogeneous materials. The first method belongs to the finite element method while the second method is based on the fast Fourier transform. These two methods are first developed for any 3D periodic microstructure and then implanted for any 2D periodic microstructure. The advantages and disadvantages of each of these two methods are compared and discussed. Using the elaborated numerical methods, the Willis theory is applied to the elastodynamic computation over the infinite heterogeneous medium and the homogenized one. The various cases of homogeneisability and non-homogeneisability are discussed

Ce travail est dédié au calcul des propriétés de transfert thermique et de transport dans les milieux hétérogènes périodiques. Les résultats sont établis dans le cadre d'homogénéisation périodique pour lequel les propriétés macroscopiques sont obtenues par la résolution de problèmes élémentaires pour la cellule irréductible. Plusieurs contributions sont ainsi apportées, visant à établir de nouvelles estimations par des approches analytiques ou en développant des méthodes numériques adaptées. Ainsi dans une première partie, on s'intéresse à la modélisation des propriétés non linéaires de filtration dans les milieux poreux. A l'échelle microscopique l'écoulement est régi par l'équation de Navier-Stokes. En développant la solution en série, on obtient par homogénéisation, une loi de filtration polynomiale. Tous les coefficients constitutifs de cette loi sont alors obtenus en résolvant en cascade des problèmes élémentaires sur la cellule à l'aide de schémas itératifs utilisant sur la transformée de Fourier rapide. On propose ensuite de nouvelles expressions analytiques pour les propriétés de conductivité thermique de composites périodiques renforcés par des inclusions sphériques. On résout l'équation intégrale de Lippmann-Schwinger par des développements en série de Neumann et en choisissant une polarisation constante dans les inclusions. Des expressions analytiques sont alors obtenues pour diverses configurations spatiales : réseaux cubiques et répartitions aléatoires isotropes. Dans la dernière partie de ce travail, on détermine les propriétés de transfert thermique par conduction et convection dans les milieux poreux saturés par un fluide. A nouveau, on propose des schémas de résolution basés sur la transformée de Fourier rapide pour le calcul du tenseur de diffusivité de milieux poreux / In this work, we determine the macroscopic properties of thermal transfer and mass transport in periodic heterogeneous materials. All the results are established in the framework of periodic homogenization, for which, the macroscopic properties are deduced by solving elementary problems for the irreducible cell. Various contributions are provided, leading to the derivation of new closed-form expressions for the effective properties or by developing numerical tools. In the first part, we determine the nonlinear filtration properties of porous media. At the microscopic scale, the fluid flow obeys to the Navier-Stokes equation. By expanding the solution into power series, we obtain, after homogenization, a polynomial type macroscopic filtration law. All the constitutive coefficients of are determined by solving a hierarchy of cell problems by means of a numerical approach based on the Fast Fourier Transform algorithm. The problem of conductivity of periodic composites reinforced by spherical inclusions is thereafter considered by an analytic approach. We solve the Lippmann-Schwinger integral equation using Neumann series and a constant polarization in the inclusion. Closed-form estimate of the macroscopic conductivity are then obtain for different spatial configurations: cubic lattice and isotropic distribution of inclusions. In the last part, we determine the thermal transfer properties by conduction and convection of porous media fulfilled by a viscous fluid. Again, numerical tools based on FFT are considered to solve the unit cell problems and to compute the diffusivity tensor

The fast Fourier transform (FFT), even though it has been widely applicable in Physics and Engineering, it has become attractive in Finance as well for it’s enhancement of computational speed. Carr and Madan succeeded in implementing the FFT for pricing of an option. This project, inspired by Carr and Madan’s paper, attempts to elaborate and connect the various mathematical and theoretical concepts that are helpful in understanding of the derivation. Further, we derive the characteristic function of the risk neutral probability for the logarithmic terminal stock price. The Black-Scholes-Merton (BSM) model is also revised including derivation of the partial deferential equation and the formula. Finally, comparison of the BSM numerical implementation with and without the FFT method is done using MATLAB.

This master’s thesis deals with signal evaluation using Fourier transform. In the theoretical section, different methods of signal analysis with an emphasis on a Fast Fourier Transform are described. Theoretical section also contains description of common machinery faults and their diagnosis using frequency spectrum analysis. In the practical section, an algorithm for signal evaluation with an emphasis on coherence condition was designed in the Matlab environment. This algorithm was later used to evaluate submitted signals.

Classical Molecular Dynamics simulation (MD) models the interactions of thousands to millions of particles through the iterative application of basic Physics. MD is one of the core methods in High Performance Computing (HPC). While MD is critical to many high-profile applications, e.g. drug discovery and design, it suffers from the strong scaling problem, that is, while large computer systems can efficiently model large ensembles of particles, it is extremely challenging for {\it any} computer system to increase the timescale, even for small ensembles. This strong scaling problem can be mitigated with low-latency, direct communication. Of all Commercial Off the Shelf (COTS) Integrated Circuits (ICs), Field Programmable Gate Arrays (FPGAs) are the computational component uniquely applicable here: they have unmatched parallel communication capability both within the chip and externally to couple clusters of FPGAs. This thesis focuses on the acceleration of the long range (LR) force, the part of MD most difficult to scale, by using FPGAs. This thesis first optimizes LR acceleration on a single-FPGA to eliminate the amount of on-chip communication required to complete a single LR computation iteration while maintaining as much parallelism as possible. This is achieved by designing around application specific memory architectures. Doing so introduces data movement issues overcome by pipelined, toroidal-shift multiplexing (MUXing) and pipelined staggering of memory access subsets. This design is then evaluated comprehensively and comparatively, deriving equations for performance and resource consumption and drawing metrics from previously developed LR hardware designs. Using this single-FPGA LR architecture as a base, FPGA network strategies to compute the LR portion of larger sized MD problems are then theorized and analyzed.

No description available.

The Discrete Fourier Transform (DFT) and its improved formulations, the Fast Fourier Transforms (FFTs), are vital for scientists and engineers in a range of domains from signal processing to the solution of partial differential equations.  A growing trend in Scientific Computing is heterogeneous computing, where accelerators are used instead or together with CPUs. This has led to problems for developers in unifying portability, performance, and productivity.  This thesis first motivates this work by showing the importance of having efficient DFT calculations, describes the DFT algorithm and a formulation based on matrix-factorizations which has been developed to formulate FFT algorithms and express their parallelism to exploit modern computer architectures, such as accelerators. The first paper is a motivating study of the breakdown of the performance and scalability of the high-performance Molecular Dynamics code GROMACS where DFT calculations are a main performance bottleneck. In particular, the long-range interactions are solved with the Particle-Mesh Ewald algorithm which uses a three-dimensional Fast Fourier Transform.  The two following papers present two approaches to leverage factorization with the help of two different frameworks using Intermediate Representation and compiler technology, for the development of fast and portable code. The second paper presents a front-end and a pipeline for code generation in a domain-specific language based on Multi-Level Intermediate Representation (MLIR) for developing Fast Fourier Transform libraries. The last paper investigates and optimizes an implementation of an important kernel within the matrix-factorization framework: the batched DFT. It is implemented with data-centric programming and a data-centric intermediate representation called Stateful Dataflow multi-graphs (SDFG). The paper evaluates strategies for complex-valued data layout for performance and portability and we show that there is a trade-off between portability and maintainability in using the native complex data type and that an SDFG-level abstraction could be beneficial for developing higher-level applications. / Den diskreta Fouriertransformen och dess snabba implementeringar är viktiga för vetenskap och ingenjörskonst. Den har tillämningar i ämnen som singnal behnadling, lösning av partiella diffrentialekvationer och många andra ämnen inom vetenskapliga beräkningar. En växande trend inom ämnet är heterogena datorer där acceleratorer som är specialicerade till vissa beräkningar kan användas som stöd för traditionella processorer. Detta leder till problem med portabilitet, prestanda och produktivitet.  Avhandligen inleds med att beskriva diskret Fouriertransform och ett ramverk för faktorisering till glesa strukturerade matriser som tillsammans representerar snabb Fouriertransform (FFT, Eng.) och som kan användas för att uttrycka parallelism i algorithmerna. För att motivera arbete med FFT i vetenskapliga beräkningar så utväreras den parallela prestandan av GROMACS: en kod för simulering av Molekyldynmik. GROMACS använder en tredimensionell diskret Fouriertransform för att finna den elektrostatiska potentialen med hjälp av Particle-Mesh Ewald-tekniken.  De följande två artiklarna presenterar två olika ramverk för att utnyttja mellankod (IR Eng.) och kompilatorteknik, för utvecklandet av  snabb och portabel kod. Den andra artikeln beskriver arbetet att utveckla ett domänspecifikt språk baserat på Multi-Level Intermediate Representation för design av snabba Fouriertransformer baserat på matrisfaktorisering. Den sista artikeln undersöker och optimerar en viktig komponent för matrisfaktorisering av diskreta Fouriertransformen: att beräkna flera små diskreta Fouriertransformer parallelt. Detta är gjort med DaCe som är ramverk för data-centrisk programmering som använder en mellankod kallad SDFG. I artikeln utvärderas strategier för data format av komplexa tal för prestanda och portabilitet, och visar att en abstraktion med hjälp av SDFG kan motiveras. / <p>QC 20230522</p>