FPGAs (Field Programmable Gate Arrays) dinamicamente reconfiguráveis (DR-FPGAs) são soluções promissoras para muitos sistemas embarcados devido a potencial redução de área de silício. Metodologias de projeto e ferramentas CAD relacionadas são ainda muito limitadas para auxiliarem os projetistas a encontrarem soluções dinamicamente reconfiguráveis para diferentes aplicações. Este trabalho propõe uma metodologia de projeto que combina modelos de alto nível em SystemC, técnicas de projeto de baixo nível e a metodologia de projeto modular da XILINX. SystemC foi utilizada para representar o comportamento de alto nível não temporizado e não-RTL, bem como o baixo nível RTL-DCS (Chaveamento Dinâmico de Circuitos). Um estudo de caso da Banda Base de um Controlador Bluetooth foi desenvolvido. Duas partições temporais foram testadas em nove diferentes DR-FPGAs. A exploração espacial mostrou que 33% das soluções investigadas atenderam a restrição da especificação de 625µs de tempo do quadro do pacote Bluetooth, deixando diferentes parcelas de recursos livres que podem ser explorados para acomodar outros módulos IP de sistemas mais complexos no mesmo dispositivo. / Dynamically Reconfigurable Field Programmable Gate Arrays (DR-FPGAs) are promising solutions for many embedded systems due to the potential silicon area reduction. Design methodologies and related CAD tools are still very limited to assist designers to encounter dynamically reconfigurable solutions for different applications. This work proposes a design methodology that combines high level SystemC models and design techniques with the low level modular design proposed by Xilinx. SystemC has been used to represent the high level untimed non-RTL behavior as well as the low level RTL-DCS (Dynamic Circuit Switching). A Bluetooth Baseband unit case study was performed. Two temporal-functional partitions were evaluated on nine different target DR-FPGAs. The design space exploration showed that 33% of the investigated solutions complied with the 625µs Bluetooth packet time frame specification leaving different amounts if free resources that may be explored to accommodate other IP modules of more complex systems on the same device.

FPGAs (Field Programmable Gate Arrays) dinamicamente reconfiguráveis (DR-FPGAs) são soluções promissoras para muitos sistemas embarcados devido a potencial redução de área de silício. Metodologias de projeto e ferramentas CAD relacionadas são ainda muito limitadas para auxiliarem os projetistas a encontrarem soluções dinamicamente reconfiguráveis para diferentes aplicações. Este trabalho propõe uma metodologia de projeto que combina modelos de alto nível em SystemC, técnicas de projeto de baixo nível e a metodologia de projeto modular da XILINX. SystemC foi utilizada para representar o comportamento de alto nível não temporizado e não-RTL, bem como o baixo nível RTL-DCS (Chaveamento Dinâmico de Circuitos). Um estudo de caso da Banda Base de um Controlador Bluetooth foi desenvolvido. Duas partições temporais foram testadas em nove diferentes DR-FPGAs. A exploração espacial mostrou que 33% das soluções investigadas atenderam a restrição da especificação de 625µs de tempo do quadro do pacote Bluetooth, deixando diferentes parcelas de recursos livres que podem ser explorados para acomodar outros módulos IP de sistemas mais complexos no mesmo dispositivo. / Dynamically Reconfigurable Field Programmable Gate Arrays (DR-FPGAs) are promising solutions for many embedded systems due to the potential silicon area reduction. Design methodologies and related CAD tools are still very limited to assist designers to encounter dynamically reconfigurable solutions for different applications. This work proposes a design methodology that combines high level SystemC models and design techniques with the low level modular design proposed by Xilinx. SystemC has been used to represent the high level untimed non-RTL behavior as well as the low level RTL-DCS (Dynamic Circuit Switching). A Bluetooth Baseband unit case study was performed. Two temporal-functional partitions were evaluated on nine different target DR-FPGAs. The design space exploration showed that 33% of the investigated solutions complied with the 625µs Bluetooth packet time frame specification leaving different amounts if free resources that may be explored to accommodate other IP modules of more complex systems on the same device.

Data-flow (DF) testing was introduced more than thirty years ago aiming at verifying a program by extensively exploring its structure. It requires tests that traverse paths in which the assignment of a value to a variable (a definition) and its subsequent reference (a use) is verified. This relationship is called definition-use association (dua). While control-flow (CF) testing tools have being able to tackle systems composed of large and long running programs, DF testing tools have failed to do so. This situation is in part due to the costs associated with tracking duas at run-time. Recently, an algorithm, called Bitwise Algorithm (BA), which uses bit vectors and bitwise operations for tracking intra-procedural duas at run-time, was proposed. This research presents the implementation of BA for programs compiled into Java bytecodes. Previous DF approaches were able to deal with small to medium size programs with high penalties in terms of execution and memory. Our experimental results show that by using BA we are able to tackle large systems with more than 250 KLOCs and 300K required duas. Furthermore, for several programs the execution penalty was comparable with that imposed by a popular CF testing tool. / Teste de fluxo de dados (TFD) foi introduzido há mais de trinta anos com o objetivo de criar uma avaliação mais abrangente da estrutura dos programas. TFD exige testes que percorrem caminhos nos quais a atribuição de valor a uma variável (definição) e a subsequente referência a esse valor (uso) são verificados. Essa relação é denominada associação definição-uso. Enquanto as ferramentas de teste de fluxo de controle são capazes de lidar com sistemas compostos de programas grandes e que executam durante bastante tempo, as ferramentas de TFD não têm obtido o mesmo sucesso. Esta situação é, em parte, devida aos custos associados ao rastreamento de associações definição-uso em tempo de execução. Recentemente, foi proposto um algoritmo --- chamado \\textit (BA) --- que usa vetores de bits e operações bit a bit para monitorar associações definição-uso em tempo de execução. Esta pesquisa apresenta a implementação de BA para programas compilados em Java. Abordagens anteriores são capazes de lidar com programas pequenos e de médio porte com altas penalidades em termos de execução e memória. Os resultados experimentais mostram que, usando BA, é possível utilizar TFD para verificar sistemas com mais de 250 mil linhas de código e 300 mil associações definição-uso. Além disso, para vários programas, a penalidade de execução imposta por BA é comparável àquela imposta por uma popular ferramenta de teste de fluxo de controle.

Processing power is a key technical challenge holding back the development of a high-performance software defined radio (SDR). Traditionally, SDR has utilized digital signal processors (DSPs), but increasingly complex algorithms, higher data rates, and multi-tasking needs have exceed the processing capabilities of modern DSPs. Reconfigurable computers, such as field-programmable gate arrays (FPGAs), are popular alternatives because of their performance gains over software for streaming data applications like SDR. However, FPGAs have not yet realized the ideal SDR because architectures have not fully utilized their partial reconfiguration (PR) capabilities to bring needed flexibility. A reconfigurable processor architecture is proposed that utilizes PR in reconfigurable computers to achieve a more sophisticated SDR. The proposed processor contains run-time swappable blocks whose parameters and interconnects are programmable. The architecture is analyzed for performance and flexibility and compared with available alternate technologies. For a sample QPSK algorithm, hardware performance gains of at least 44x are seen over modern desktop processors and DSPs while most of their flexibility and extensibility is maintained.

This thesis consists of six papers. In Paper I, we give an algorithm for merging sorted lists of monomials and together with a projection technique, we obtain a new complexity bound for the Buchberger-Möller algorithm and the FGLM algorithm. In Paper II, we discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give complexity bounds. As an application we drastically improve the computational algebra approach to the reverse engineering of gene regulatory networks. In Paper III, we introduce the concept of multiplication matrices for ideals of projective dimension zero. We discuss various applications and, in particular, we give a new algorithm to compute the variety of an ideal of projective dimension zero. In Paper IV, we consider a subset of projective space over a finite field and give a geometric description of the minimal degree of a non-vanishing form with respect to this subset. We also give bounds on the minimal degree in terms of the cardinality of the subset. In Paper V, we study an associative version of an algorithm constructed to compute the Hilbert series for graded Lie algebras. In the commutative case we use Gotzmann's persistence theorem to show that the algorithm terminates in finite time. In Paper VI, we connect the commutative version of the algorithm in Paper V with the Buchberger algorithm. / At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: Manuscript

Multi-stage programming is a valuable technique for improving the performance of computer programs through run-time optimization. Current implementations of multi-stage programming do not support run-time type introspection, which is a significant feature of modern object-oriented platforms such as Java and C#. This is unfortunate because many programs that use type introspection in these languages could be improved with multi-staging programming. The aim of this research is to investigate the interaction between multi-stage programming and object-oriented type introspection. This is done by the invention of a new programming language that is a multi-stage extension to C#. The language is capable of expressing traditional multi-stage programs as well as a new style of multi-stage programs that incorporate type introspection, most notably polytypic algorithms such as object serialization. A compiler for the language is implemented and freely available. The language is significant because it is the first object-oriented, multi-stage language; the first attempt to combine type introspection with multi-stage programming; and the first exploration of polytypic programming in a multi-stage context.

The vision of automated driving demands a highly available system, especially in safety-critical functionalities. In automated driving when a driver is not binding to be a part of the control loop, the system needs to be operational even after failure of a critical component until driver regain the control of vehicle. In pursuit of such a fail-operational behavior, the developed design process with software redundancy in contrast to conventional dedicated backup requires the support of automatic configurator for scheduling relevant parameters to ensure real-time behavior of the system. Multiple implementation methods are introduced to provide an automatic service which also considers task criticality before assigning task to the processor. Also, a generic method is developed to generate adaptation plans automatically for an already monitoring and reconfiguration service to handle fault occurring environment.

Memorization of a method is a commonly used re-factoring wherein developer modules the code of a method to save return values for some or all incoming parameter values. Whenever a parameter-tuple is received for the second or subsequent time, the method's execution can be elided and the corresponding saved value can be returned. It is quite challenging for developers to identify suitable methods for memorization, as these may not necessarily be the methods that account for a high fraction of the running time in the program. What are really sought are the methods that cumulatively incur signi_cant execution time in invocations that receive repeat parameter values. Our primary contribution is a novel dynamic analysis approach that emits a report that contains, for each method in an application, an estimate of the execution time savings to be expected from memorizing this method. The key technical novelty of our approach is a set of design elements that allow our approach to target real-world programs, and to compute the estimates in a re-grained manner. We describe our approach in detail, and evaluate an implementation of it on several real-world programs. Our evaluation reveals that there do exist many methods with good estimated savings that the approach is reasonably ancient, and that it has good precision (relative to actual savings).

Correct behavior of programs can be defined by their temporal properties. One of the options for formal specification of such properties is  linear temporal logic - LTL . This master's thesis describes design and implementation of a tool for automatic checking of temporal properties of programs, that are specified using Past-Time LTL formulae. The trace of a given program is analyzed in run-time and any violation of given formulae is reported in details to help to find the code location with a root cause of the bug.

No description available.