A distinctive feature of run-time reconfigurable systems is the ability to change the configuration of programmable resources during execution. This opens a number of possibilities such as virtualisation of computational resources, simplified routing and in certain applications lower power. Seamless run-time reconfiguration requires rapid configuration. Commodity programmable devices have relatively long configuration time, which makes them poor candidates for run-time reconfigurable systems. Reducing this reconfiguration time to the order of nano seconds will enable rapid run-time reconfiguration. Having multiple configuration planes and switching between them while processing data is one approach towards achieving rapid reconfiguration. An experimental context switching programmable device, called the Context Switching Reconfigurable Computer (CSRC), has been created by BAE Systems, which provided opportunities to explore context-switching strategies for run-time reconfigurable systems. The work presented here studies this approach for run-time reconfiguration, by applying the concepts to develop applications on a context switching reconfigurable system. The work also discusses the advantages and disadvantages of such an approach and ways of leveraging the concept for efficient computing. / Master of Science

Modern Field Programmable Gate Arrays (FPGAs) can implement entire run-time reconfigurable systems using partial reconfiguration. Module-based run-time reconfiguration permits the construction of custom applications at run-time using pre-compiled Intellectual Property (IP) from a module library. The need for both flexible module placement and custom inter-module communication is mostly ignored by existing modular run-time reconfiguration approaches and few existing tool flows for module generation address the need for automation. This thesis introduces an automated compile-time tool flow for generating dynamic modules that allow flexible run-time placement and communication synthesis. / Master of Science

The configurable computing research community has provided a wealth of evidence that computational platforms based on FPGA technology are capable of cost-effectively accelerating certain kinds of computations. One actively growing area in the research community examines the benefits to computation that can be gained by reconfiguring the FPGAs in a system during the execution of an application. This technique is commonly referred to as run-time reconfiguration. Widespread acceptance of run-time reconfigurable custom computing depends upon the existence of high-level automated design tools. Given the wide variety of available platforms and the rate that the technology is evolving, a set of architecturally independent tools that provide the ability to port applications between different architectures will allow application-based intellectual property to be easily migrated between platforms. A Java implementation of such a toolset, called Janus, is presented and analyzed here. In this environment, developers create a Java class that describes the structural behavior of an application. The design framework allows hardware and software modules to be freely intermixed. During the compilation phase of the development process, the Janus tools analyze the structure of the application and adapt it to the target architecture. Janus is capable of structuring the run-time behavior of an application to take advantage of the resources available on the platform. Examples of applications developed using the toolset are presented. The performance of the applications is reported. The retargeting of applications for multiple hardware architectures is demonstrated. / Ph. D.

In the past, various approaches to the high performance numerical computing problem have been explored. Recently, researchers have begun to explore the possibilities of using Field Programmable Gate Arrays (FPGAs) to solve numerically intensive problems. FPGAs offer the possibility of customization to any given application, while not sacrificing applicability to a wide problem domain. Further, the implementation of data flow graphs directly in silicon makes FPGAs very attractive for these types of problems. Unfortunately, current FPGAs suffer from a number of inadequacies with respect to the task. They have lower transistor densities than ASIC solutions, and hence less potential computational power per unit area. Routing overhead generally makes an FPGA solution slower than an ASIC design. Bit-oriented computational units make them unnecessarily inefficient for implementing tasks that are generally word-oriented. And finally, in large volumes, FPGAs tend to be more expensive per unit due to their lower transistor density. To combat these problems, researchers are now exploiting the unique advantage that FPGAs exhibit over ASICs: reconfigurability. By customizing the FPGA to the task at hand, as the application executes, it is hoped that the cost-performance product of an FPGA system can be shown to be a better solution than a system implemented by a collection of custom ASICs. Such a system is called a Configurable Computing Machine (CCM). Many aspects of the design of the FPGAs available today hinder the exploration of this field. This thesis addresses many of these problems and presents the embodiment of those solutions in the Colt CCM. By offering word grain reconfiguration and the ability to partially reconfigure at computational element resolution, the Colt can offer higher effective utilization over traditional FPGAs. Further, the majority of the pins of the Colt can be used for both normal I/O and for chip reconfiguration. This provides higher reconfiguration bandwidth contrasted with the low percentage of pins used for reconfiguration of FPGAs. Finally, Colt uses a distributed reconfiguration mechanism called Wormhole Run-Time Reconfiguration (RTR) that allows multiple data ports to simultaneously program different sections of the chip independently. Used as the primary example of Wormhole RTR in the patent application, Colt is the first system to employ this computing paradigm. / Ph. D.

The run-time reconfiguration of Field Programmable Gate Arrays (FPGAs) opens new avenues to hardware reuse. Through the use of process migration between hardware and software, an FPGA provides a parallel execution cache. Busy processes can be migrated into hardware-based, parallel processors, and idle processes can be migrated out increasing the utilization of the hardware. The application of hardware/software process migration to the acceleration of Register Transfer Level (RTL) circuit simulation is developed and analyzed. RTL code can exhibit a form of locality of reference such that executing processes tend to be executed again. This property is termed executive temporal locality, and it can be exploited by migration systems to accelerate RTL simulation. In this dissertation, process migration is first formally modeled using Finite State Machines (FSMs). Upon FSMs are built programs, processes, migration realms, and the migration of process state within a realm. From this model, a taxonomy of migration realms is developed. Second, process migration is applied to the RTL simulation of digital circuits. The canonical form of an RTL process is defined, and transformations of HDL code are justified and demonstrated. These transformations allow a simulator to identify basic active units within the simulation and combine them to balance the load across a set of processors. Through the use of input monitors, executive locality of reference is identified and demonstrated on a set of six RTL designs. Finally, the implementation of a migration system is described which utilizes Virtual Machines (VMs) and Real Machines (RMs) in existing FPGAs. Empirical and algorithmic models are developed from the data collected from the implementation to evaluate the effect of optimizations and migration algorithms. / Ph. D.

The growth of high performance computing to date can largely be attributed to continuing breakthroughs in materials and manufacturing.In order to increase computing capacity beyond these physical bounds, new computing paradigms must be developed that make more efficient use of existing manufacturing technologies. Custom Computing Machines (CCMs) are an emerging class of computers that offer promising possibilities for future high-performance computational needs. With the increasing popularity of the run-time reconfigurable (RTR) concept in the CCM community, questions have arisen as to what computational device should be at the heart of an RTR platform. Currently the preferred device, and really the only practical device, has been the RAM-based Field-Programmable Gate Array (FPGA). Unfortunately, for applications that require high performance, FPGAs are limited by their narrow data path and small computational density. The Colt integrated circuit has been designed from the start to be the computational processing element in an RTR platform. Colt is an RTR data-flow processor array with a course-grain architecture (16-bit data path). This thesis covers the VLSI implementation and verification of the Colt integrated circuit, including the approach and methods necessary to make a functionally working integrated circuit. / Master of Science

4 pp. / Converting from Gallons -- to Inches -- to Runtime Hours for Row Crop Drip Irrigation Systems / Many growers in Arizona are switching from surface to drip irrigation. This change requires many changes in water management. One of the changes that growers are having the most difficulty with is the concept of applying gallons of water instead of inches. This paper helps growers make this conversion from inches to gallons and then back again. An accompanying EXCEL program, available on the web, will help growers determine run times and application amounts.

4 pp. / Many growers in Arizona are switching from surface to drip irrigation. This change requires many changes in water management. One of the changes that growers are having the most difficulty with is the concept of applying gallons of water instead of inches. This paper helps growers make this conversion from inches to gallons and then back again. An accompanying EXCEL program, available on the web, will help growers determine run times and application amounts.

Revised; Originally Published: 2007 / 4 pp.

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.