Custom hardware instructions are frequently used to accelerate software. However, the number of active custom instructions - and speedup opportunities - are limited in resourceconstrained systems, such as those using small embedded FPGAs (eFPGAs). Hence, it is desirable to be able to dynamically reconfigure this resource to allow an application to change the accelerator logic. While an existing method called CX Table is described the Draft CX Specification to manage accelerators, it is not suitable for lightweight embedded systems because (1) virtual memory is required to isolate processes, and (2) an implied table lookup is required when switching custom instruction sets. This paper presents CIA Direct, a lightweight alternative to CX Table. It moves the table into a privileged control register to avoid virtual memory and external memory accesses. It provides inter-process virtualization of accelerator state, but intra-process virtualization has performance limitations. This paper also describes CxBex, the first ASIC implementation of CIA Direct. It contains a hard RISC-V processor with an eFPGA to support multiple custom instruction accelerators under dynamic reconfiguration. Unique to CxBex, context switching keeps multiple independent state context intact in eFPGA block during reconfiguration. Intended for lightweight embedded systems, this work demonstrates that the CIA Direct approach is simpler, reduces CPU complexity, eliminates dependence on external memory, and manages dynamic reconfiguration using exceptions.

Conventional computing has been dominated by one or more uniform processor cores coupled with Dynamic RAM. However, heterogeneous computing (processor cores coupled with accelerators such as FPGAs) are becoming readily available to a broad market. Also, with the introduction of novel technologies (Hybrid Memory Cube, High Bandwidth Memory, etc.), memory performance characteristics are changing abruptly. This paper proposes Volcan, a framework that abstracts the different memory technologies, leverages high-level synthesis, and partial reconfiguration to increase the portability and productivity of application developers interested in heterogeneous computing. Three platforms were tested with three sample applications. The results indicate that the framework introduces little overhead while exposing the bandwidth advantages of these new memory technologies.

Heterogeneous many-core architectures combined with scratch-pad memories are attractive because they promise better energy efficiency than conventional architectures and a good balance between single-thread performance and multi-thread throughput. However, programmers will need an environment for finding and managing the large degree of parallelism, locality, and system resilience. We propose a Python-based task parallel programming model called PyDac to support these objectives. PyDac provides a two-level programming model based on the divide-and-conquer strategy. The PyDac runtime system allows threads to be run on unreliable hardware by dynamically checking the results without involvement from the programmer. To test this programming model and runtime, an unconventional heterogeneous architecture consisting of PowerPC and ARM cores was developed and emulated on an FPGA device. We inject faults during the execution of micro-benchmarks and show that through the use of double and triple modular redundancy we are able to complete the benchmarks with the correct results while only incurring a proportional performance penalty.

A Digital Wireless Channel Emulator (DWCE) is a system that is capable of emulating the RF environment for a group of wireless devices. A major issue with current designs is that they do not scale to a large enough number of nodes to emulate meaningful network. A reason for this lack of scalability is the large amount of computations and network capacity required for such a system. Previously documented DWCE systems implement a hub-and-spoke configuration that inhibits them from simply adding additional hardware to scale. This paper investigates the use of a FPGA cluster configured as a distributed system to provide the computational and network structure to scale a DWCE to support 1250 wireless devices. This scale is approximately two orders of magnitude larger than any other previously documented system. This paper presents multiple FPGA cluster configurations that use currently available hardware and describes the algorithms used to route the signals through the network and place the computational hardware on each FPGA. The low level VHDL Signal Path Component (SPC) is synthesized and mapped under different parameters to interpolate is resource utilization. One example FPGA build with enough SPCs to fill 80% of the FPGA resources is successfully run through the Xilinx tool-chain to determine the maximum FPGA system clock speed. Finally, the scaling results are presented that detail the maximum sample frequency of various sized DWCE systems which could be used to examine a variety of wireless devices.

This paper designed a MPI-like Message Passing Engine (MPE) as part of the on-chip network, providing point-to-point and collective communication primitives in hardware. On one hand, the MPE offloads the communication workload from the general processing elements. On the other hand, the MPE provides direct interface to the heterogeneous processing elements which can eliminate the data path going around the OS and libraries. The experimental results have shown that the MPE can significantly reduce the communication time and improve the overall performance, especially for heterogeneous computing systems.

The conventional matrix multiplication algorithms that are suitable for dense matrices do not perform well on the corresponding Sparse Matrix-Matrix Multiplication (SMMM) operation. In particular, they do not utilize the sparsity of the matrix. This paper describes a new technique for performing the SMMM operation using a novel storage format for sparse matrices. To demonstrate the feasibility of this technique, the SMMM operation is implemented on an FPGA and various parameters that affect the performance of the design are explored.

Current trends in Reconfigurable Computing point to an ever-increasing need for logic resources. This has led to the development and deployment of systems consisting of multiple FPGAs. These systems are advancing from scores of FPGAs to hundreds of FPGAs. Programming and administering these kind of systems while maintaining a non-intrusive physical footprint is expected to remain a continuing challenge. Future systems demand lower FPGA configuration and initialization turn-around times while maintaining a high degree of resource availability. Also, support for new configuration methodologies and portability to the latest generations of FPGA platforms is required. This paper describes an improved suite of tools with new features like job scheduling, bit stream management, multiple session control, debugging capabilities and remote access that will enable large scale High Performance Reconfigurable Computing.

A Digital Wireless Channel Emulator (DWCE) is a system that is capable of emulating the RF environment for a group of radios. A major issue with current designs is that they do not scale to a large enough number of nodes to emulate meaningful network due to the amount of computations required for such a system. This paper proposes a novel DWCE design based on a cluster of FPGA devices. By decentralizing the signal processing it is possible to increase the available computational resources to the point where they are no longer the limiting factor to scalability. It demonstrates feasibility by analyzing the computational and network requirements of the application and showing how the proposed design meets those needs. The paper also describes the physical design of a new 64 node FPGA cluster that is being manufactured. An implementation on prototype nodes of this cluster demonstrates the machine will support a high fidelity emulation for 32 radios or a lower-fidelity emulation for 128 radios.

This paper describes the design and implementation of an open source FPGA-based SATA2 core. It provides the ability to directly interface with hardware cores which is beneficial for high performance and embedded computing applications. Additionally, the core has a bus interface and DMA engine that makes it available to the operating system through a Linux block device driver. Measurements with solid state drives reveal that our FPGA-based implementation achieves performance close to the disks' theoretical peak. In contrast, we find that software overhead on a modern Linux server prevents exploiting the full potential of these high speed storage devices. Native Command Queueing is supported by the core and the performance results highlight its importance in the context of SSDs, especially for small block transfers. The small size of our SATA core (1.5% of the logic resources on a Virtex-6 FPGA) indicates that an on-chip RAID storage system is feasible.

As FPGA resources continue to increase, FPGAs present attractive features to the High Performance Computing community. These include the power-efficient computation and application-specific acceleration benefits, as well as tighter integration between compute and I/O resources. This paper considers the ability of an FPGA to address another, increasingly important, feature - resiliency. Specifically, a minimally-invasive monitoring infrastructure operating over a sideband network is presented. This includes a multi-chip protocol, IP cores that implement the protocol, and a tool to instrument existing hardware accelerator FPGA designs. To demonstrate the functionality, the system has been implemented on a cluster of FPGA devices running off-the-shelf MPI and Linux. We demonstrate the ability to do integrated software and hardware accelerator check pointing with restart under a variety of injected faults.

Many FPGA based Network-on-Chip (NoC) and directly connected clusters use routers implemented in the FPGA fabric. Existing projects have optimized the routers for low resource utilization, low latency, and high bandwidth, often at the cost of programmability and manageability. Developers using the existing FPGA networks often have no way to specify a source or destination of a message except by using the physical locations of the nodes in the network. This low level of abstraction limits developer productivity and the ability of the network to adapt to changing conditions. We present an FPGA network that resolves these issues by allowing the developer to use familiar 32-bit addresses similar to an IP address and a router that uses a software managed routing table. The implementation presented here demonstrates similar resource utilization and bandwidth with a minimal increase in latency when compared to existing FPGA router implementations.

This paper demonstrates the benefits and pit-falls of implementing the collective communication operation reduce in the reconfigurable resources of an FPGA device across a cluster of all-FPGA compute nodes. Specifically, the communication and computation semantics of the MPI_Reduce call from the de facto Message-Passing Interface have been implemented. Using a synthetic benchmark a cluster of 32 FPGA nodes with a 300 MHz PowerPC processor, custom high speed network, and reduce core is compared against a conventional commodity cluster with 3.2 GHz Xeon processors and Gigabit Ethernet. The design is customized to support performing many reduce operations on small datasets while minimizing the amount of on-chip resources used, which is an increasingly common demand from domain scientists. Speedups of ≈2x to ≈800x are reported over that of a commodity cluster for small datasets, which provides significant motivation to continue the investigation into supporting additional collective communication operations directly in hardware.

BLASTn is a tool universally used by biologists to identify similarities between nucleotide based biological genome sequences. This report describes an hardware implementation designed to accelerate algorithm maintaining the same results yielded by the software developed at NCBI. A detailed profile study identifies the Blast_Nt_Scan function as the computationally intensive part of the algorithm. A hardware component has been designed and implemented for this critical section. Rather then trying to implement more of the computation on the FPGA chip, our focus is on improving workload performance. Hence, the hardware has been designed to be replicated and placed on the FPGA to reduce initial comparison latencies between multiple short sequences(queries) and a subject database. Tests reveal the current implementation achieves an approximate 4X speedup over the software run on a modern general purpose computer generating identical results.

The Reconfigurable Computing Cluster Project at the University of North Carolina at Charlotte is investigating the feasibility of using FPGAs as compute nodes to scale to PetaFLOP computing. To date the Spirit cluster, consisting of 64 FPGAs, has been assembled for the initial analysis. One important question is how to efficiently communicate among compute cores on-chip as well as between nodes. Tight integration between both the on-chip and off-chip networks is crucial in obtaining high performance and parallelism while minimizing communication overhead. This paper introduces AIREN - Architecture Independent REconfigurable Network - the integration of an on-chip crossbar switched network with an off-chip k-ary d-cube network and presents the results of integrating AIREN with the Spirit cluster.

Many natural processes exhibit exponential decay and, consequently, computational scientists make extensive use of e-χx in computer simulation experiments. While it is common to implement transcendental functions (sine, cosine, exponentiation, etc.) in hardware using the well-known CORDIC algorithm, many contemporary FPGA implementations either use fixed point or reduced precision floating-point operations (which suffers from a high average/mean error). Unfortunately, these solutions are unacceptable for many computational scientist who require the accuracy of doubleprecision values.

Message-Passing is the dominant programming model for distributed memory parallel computers and Message-Passing Interface (MPI) is the standard. Along with point-to-point send and receive message primitives, MPI includes a set of collective communication operations that are used to synchronize and coordinate groups of tasks. The MPI_Barrier, one of the most important collective procedures, has been extensively studied on a variety of architectures over last twenty years. However, a cluster of Platform FPGAs is a new architecture and offers interesting, resource-efficient options for implementing the barrier operation. This paper describes an FPGA implementation of MPI_Barrier. The premise is that barrier (and other collective communication operations) are very sensitive to latency as the number of nodes scales to the tens-of-thousands. The relatively slow processors found on FPGAs will significantly cap performance. The FPGA hardware design implements a tree-based algorithm and is tightly integrated with the custom high-speed on-chip/off-chip network. MPI access is available through a specially-designed kernel module. This effectively offloads the work from the CPU and OS into hardware. The evaluation of this design shows significant performance gains compared with a conventional software implementation on both an FPGA cluster and a commodity cluster. Further, it suggests that moving other MPI collective operations into hardware would be beneficial.

This paper discusses field programmable gate array(FPGA) session control software that incorporates the functionality of R-Boot with a client-server model and a custom command set running over a standard TCP/IP network. The ability to remotely access the FPGAs from anywhere on or off campus gives students the unique ability to work on labs and research without stepping in to the laboratory. FSC improves the remote FPGA experience by providing a single GUI-based client and improves lab administration.

This short paper aims to describe a number of recent developments and report some key performance results. One development is additional functionality added to the custom networking board that was not originally anticipated or reported. The two other developments include Spirit's programming model for computational scientists, and the performance of two compute accelerators (an FPU and e-x) that have been implemented.

This short paper describes a remote laboratory facility for platform FPGA education. With the addition of an inexpensive piece of hardware, many commercial off-the-shelf FPGA development boards can be made suitable for use in a remote laboratory. The hardware and software required to implement a remote laboratory has been developed and a remote laboratory facility deployed at the University of North Carolina at Charlotte. Advantages, concerns, and actual costs are reported. The experience of using this facility in a senior/first-year graduate-level platform FPGA course is also described. Although these data are preliminary, survey results and first-hand experience with the laboratory were very encouraging and suggests that further studies on student learning are warranted.

This paper introduces hthreads, a unifying programming model for specifying application threads running within a hybrid computer processing unit (CPU)/field-programmable gate-array (FPGA) system. Presently accepted hybrid CPU/FPGA computational models-and access to these computational models via high level languages-focus on programming language extensions to increase accessibility and portability. However, this paper argues that new high-level programming models built on common software abstractions better address these goals. The hthreads system, in general, is unique within the reconfigurable computing community as it includes operating system and middleware layer abstractions that extend across the CPU/FPGA boundary. This enables all platform components to be abstracted into a unified multiprocessor architecture platform. Application programmers can then express their computations using threads specified from a single POSIX threads (pthreads) multithreaded application program and can then compile the threads to either run on the CPU or synthesize them to run within an FPGA. To enable this seamless framework, we have created the hardware thread interface (HWTI) component to provide an abstract, platform-independent compilation target for hardware-resident computations. The HWTI enables the use of standard thread communication and synchronization operations across the software/hardware boundary. Key operating system primitives have been mapped into hardware to provide threads running in both hardware and software uniform access to a set of sub-microsecond, minimal-jitter services. Migrating the operating system into hardware removes the potential bottleneck of routing all system service requests through a central CPU.

Traditional FPGA education either involves a physical laboratory room with workstations connected to individual FPGA experimenter boards or simulation platforms. Physical labs are expensive to maintain and require substantial floor space. In addition, students need to be physically present in the laboratories to access the FPGA boards. On the other hand, it is often the case that simulation platforms do not provide the students an adequate, in-depth understanding of concepts (such as synthesis on FPGAs). In this short paper, a third option - a remote FPGA Laboratory - is illustrated. This option uses software to allow students and researchers in geographically distributed locations to remotely access a pool of 64 Xilinx ML-310 Boards over the Internet. To the best of our knowledge, a remote FPGA facility of this kind is unique. The infrastructure described here gives remote users the ability to dynamically power on/off the FPGA boards, upload/download files, configure the boards online and execute synthesized designs while sending input and output through the Internet. Advantages include considerable savings in space, greater accessibility for users, ease of maintenance, and the ability to better schedule resources.

While medium- and large-sized computing centers have increasingly relied on clusters of commodity PC hardware to provide cost-effective capacity and capability, it is not clear that this technology will scale to the PetaFLOP range. It is expected that semiconductor technology will continue its exponential advancements over next fifteen years; however, new issues are rapidly emerging and the relative importance of current performance metrics are shifting. Future PetaFLOP architectures will require system designers to solve computer architecture problems ranging from how to house, power, and cool the machine, all the while remaining sensitive to cost. The reconfigurable computing cluster (RCC) project is a multi-institution, multi-disciplinary project investigating the use of Platform FPGAs to build cost-effective petascale computers. This paper describes the nascent project's objectives and a 64-node prototype cluster. Specifically, the aim is to provide an detailed motivation for the project, describe the design principles guiding development, and present a preliminary performance assessment. Microbenchmark results are reported to answer several pragmatic questions about key subsystems, including the system software, network performance, memory bandwidth, power consumption of nodes in the cluster. Results suggest that the approach is sound.

The benefits of high performance computing (HPC) can be seen in a wide range of applications. From science and medicine to industries as diverse as oil exploration, financial, and entertainment, access to cost-effective HPC is becoming a critical part of our national infrastructure. Although exponential semiconductor advances are giving computational scientists faster computing speeds, applications with large amounts of data may not necessarily solve problems faster. More specifically, technology trends are working against system designers: computation rates and memory capacity are both rising faster than the bandwidth between these two components. This so called "Memory Wall" was predicted for general-purpose computing over a decade ago, but to date large on-chip caches are able to compensate for the growing disparity. FPGA designers do not have the luxury of large caches, so to be successful, high-performance designs must include custom memory hierarchies and data paths as well as application-specific computations.

In this paper we investigate several common bus architectures and measure effective bandwidth between High Performance Computing cores and off-chip memory. Contributions of this paper include (i) characterizing the behavior of four common organizations using off-the-shelf IP cores, (ii) an investigation of the effect of multiple computational cores sharing the bus structures, and (iii) the development of a testing methodology which simulates different access patterns and accurately measures bandwidth. The results show that while some bus architectures are clearly better than others, none approach the theoretical bandwidth of the memory interface. Furthermore, negotiating the bus protocol is a significant source of overhead. So much so that it effectively hides any performance one might gain from trying to access the off-chip DRAMs using an "intelligent" access pattern.

In this paper, we present hthreads, a unifying programming model for specifying application threads running within a hybrid CPU/FPGA system. Threads are specified from a single pthreads multithreaded application program and compiled to run on the CPU or synthesized to run on the FPGA. The hthreads system, in general, is unique within the reconfigurable computing community as it abstracts the CPU/FPGA components into a unified custom threaded multiprocessor architecture platform. To support the abstraction of the CPU/FPGA component boundary, we have created the hardware thread interface (HWTI) component that frees the designer from having to specify and embed platform specific instructions to form customized hardware/software interactions. Instead, the hardware thread interface supports the generalized pthreads API semantics, and allows passing of abstract data types between hardware and software threads. Thus the hardware thread interface provides an abstract, platform independent compilation target that enables thread and instruction-level parallelism across the software/hardware boundary

Modern FPGA devices, which include (multiple) processor core(s) as diffused IP on the silicon die, provide an excellent platform for developing custom multiprocessor systems-on-programmable chip (MPSoPC) architectures. As researchers are investigating new methods for migrating portions of applications into custom hardware circuits, it is also critical to develop new run-time service frameworks to support these capabilities. Hthreads (HybridThreads) is a multithreaded RTOS kernel for hybrid FPGA/CPU systems designed to meet this new growing need. A key capability of hthreads is the migration of thread management, synchronization primitives, and run-time scheduling services for both hardware and software threads into hardware. This paper describes the hthreads scheduler, a key component for controlling both software-resident threads (SW threads) and threads implemented in programmable logic (HW threads). Run-time analysis shows that the hthreads scheduler module helps in reducing unwanted system overhead and jitter when compared to historical software schedulers, while fielding scheduling requests from both hardware and software threads in parallel with application execution. Run time analysis shows the scheduler achieves constant time scheduling for up to 256 active threads with a total of 128 different priority levels, while using uniform APIs for threads requesting OS services from either side of the hardware/software boundary

This work advocates a merit-based reconfiguration policy. In the merit-based approach, each kernel that has a hardware implementation also has a software implementation. A runtime system performs continuous profiling of the application to decide which hardware reconfigurations are most profitable at any given time. Such a system can minimize thrashing, keeping the set of hardware-resident functionality constant over short intervals while still adapting to phased behavior in the application. Consequently, the system is better able to tolerate reconfiguration latencies. The main contribution of this work is the exhibition of a simple "merit" heuristic that can be used to direct reconfiguration. In this synopsis we present a brief overview of our ongoing work. First, a simple online algorithm for calculating a figure-of-merit for RTR systems is formalized. Next we describe its implementation and demonstrate a working prototype.

With increasingly larger FPGA devices, it is tempting to continue using conventional code generation techniques to construct hardware designs from high-level languages. However, in this paper we make a case against the application of conventional techniques to hardware design in favor of a new code generation approach that enables the use of heavily customized, parameterizable modules. This approach moves a portion of the generation functionality into tiles, which handle the negotiation of a module's parameters and subsequently the instantiation of the parameterized module. Furthermore, the tiles are automatically discovered at run-time and dynamically loaded into the design generator, which allows the system to be readily extended. This approach has been implemented in a collaborative, problem-solving design environment for reconfigurable computing. It is shown --- with respect to latency, throughput, and size --- that the proposed approach to hardware design generation is significantly more efficient than the conventional code generation techniques.

The requirements for placing modules in an automatic run-time reconfigurable (RTR) system differ from those of ASIC and other static environments. The most notable difference is the continual addition and removal of modules from the FPGAs. We examine the effectiveness of a collection of two-dimensional placement decision algorithms in a RTR environment. New algorithms are proposed in addition to several which have been adapted from their one-dimensional counterparts. All of the algorithms have been tested on a set of benchmark applications. Six programs used for testing include examples from encryption, image processing and matrix manipulations, as well as arithemetic, assignment, and looping benchmarks. These applications are multiplexed and simulated to run on our RTR system. A simple last-accessed removal scheme with no compaction is currently implemented. The merit of each algorithm is determined by a set of factors that include fragmentation, chip utilization, decision time, and program run-time benefit.

In this paper, we describe Arches, an object-oriented framework for building domain-specific PSEs. The framework was designed to support a wide range of problem domains and to be extendable in a way that allows it to target very different high-performance computing models. To demonstrate this flexibility we describe two PSEs that have been developed from the same framework yet solve different problems and target very different computing platforms. The Coven PSE supports parallel applications that need the large-scale parallelism that is found in cost-effective Beowulf clusters. In contrast, the RCADE PSE targets reconfigurable computing (FPGA-based) platforms with fine-grain parallelism. RCADE was designed to aid NASA Earth scientists interested in studying satellite instrument data and who are unlikely to be schooled in low-level hardware design.

The high overhead of generic protocols like TCP/IP provides strong motivation for the development of a better protocol architecture for cluster-based parallel computers. Reconfigurable computing has a unique opportunity to contribute hardware level protocol acceleration while retaining the flexibility to adapt to changing needs. Thus, it is possible to provide application-specific protocol processing to improve performance and to reduce space utilization. Reducing space utilization permits the use of a greater portion of the FPGA for other application-specific processing. This paper focuses on work to create a set of components that can be put together as needed to obtain a customized protocol for each application. The components are parameterizable, increasing the protocol's flexibility. To study the feasibility of such an architecture, hardware components for the reconfigurable logic on the NIC were built such that they can be stitched together as required to provide the required functionality. Feasibility is demonstrated using four different protocol configurations in this paper. The different configurations illustrate trade-offs between chip space and functionality.

The high overhead of generic protocols like TCP/IP provides strong motivation for the development of a better protocol architecture for cluster-based parallel computers. Reconfigurable computing has a unique opportunity to contribute hardware level protocol acceleration while retaining the flexibility to adapt to changing needs. Specifically, applications on a cluster have various quality of service needs. In addition, these applications typically run for a long time relative to the reconfiguration time of an FPGA. Thus, it is possible to provide application-specific protocol processing to improve performance and reduce space utilization. Reducing space utilization permits the use of a greater portion of the FPGA for other application-specific processing. This paper focuses on work to create a set of parameterizable components that can be put together as needed to obtain a customized protocol for each application. To study the feasibility of such an architecture, hardware components were built that can be stitched together as needed to provide the required functionality. Feasibility is demonstrated using four different protocol configurations, namely: (1) unreliable packet transfer; (2) reliable, unordered message transfer without duplicate elimination; (3) reliable, unordered message transfer with duplicate elimination; and (4) reliable, ordered message transfer with duplicate elimination. The different configurations illustrate trade-offs between chip space and functionality.

Abstract With a focus on commodity PC systems, Beowulf clusters traditionally lack the cutting edge network architectures, memory subsystems, and processor technologies found in their more expensive supercomputer counterparts. Many users find that what Beowulf clusters lack in technology, they more than make up for with their significant cost advantage. In this paper, an architectural extension that adds reconfigurable computing to the network interface of Beowulf clusters is proposed. The proposed extension, called an intelligent network interface card (or INIC), enhances both the network and processor capabilities of the cluster, which has a significant impact on the performance of a crucial class of applications. Furthermore, for some applications, the proposed extension partially compensates for weaknesses in the PC memory subsystem. A prototype of the proposed architecture was constructed and analyzed. In addition, two applications, the 2D Fast Fourier Transform (2D‐FFT) and integer sorting, which benefit from the resulting architecture, are discussed and analyzed on the proposed architecture. Specifically, results indicate that the 2D‐FFT is performed 15–50% faster when using the prototype INIC rather than the comparable Gigabit Ethernet. Early simulation results also indicate that integer sorting will receive a 21–32% performance boost from the prototype. The significant improvements seen with a relatively limited prototype lead to the conclusion that cluster network interfaces enhanced with reconfigurable computing could significantly improve the Beowulf architecture. Copyright © 2003 John Wiley & Sons, Ltd.

With a focus on commodity PC systems, Beowulf clusters traditionally lack the cutting edge network architectures, memory subsystems, and processor technologies found in their more expensive supercomputer counterparts. What Beowulf clusters lack in technology, they more than make up for with their significant cost advantage over traditional supercomputers. We propose an architectural extension that adds reconfigurable computing to the network interface of Beowulf clusters. This enhances both the network and processor capabilities of the cluster. Furthermore, for some applications, the proposed extension partially compensates for weaknesses in the PC memory subsystem. We discuss two applications, the 2D Fast Fourier Transform (FFT) and integer sorting, which benefit from the resulting architecture.

With a focus on commodity PC systems, Beowulf clusters traditionally lack the cutting edge network architectures, memory subsystems, and processor technologies found in their more expensive supercomputer counterparts. What Beowulf clusters lack in technology, they more than make up for with their significant cost advantage over traditional supercomputers. This paper presents the cost implications of an architectural extension that adds reconfigurable computing to the network interface of Beowulf clusters. A quantitative idea of cost-effectiveness is formulated to evaluate computing technologies. Here, cost-effectiveness is considered in the context of two applications: the 2D Fast Fourier Transform (2D-FFT) and integer sorting.

The development of a unimodular transformation theory and associated algorithms has renewed interest in FORTRAN DO loops that are not perfectly (or tightly) nested. We summarize a number of techniques that convert imperfectly nested loops into perfectly nested loops. We examined over 25,000 lines of scientific FORTRAN kernels and benchmarks. Statistics are reported on how often imperfect loops occur and how effective two transformations (scalar forward substitution and loop distribution) are at converting imperfectly nested loops into perfectly nested loops. Further, we describe a compiler that integrates scalar forward substitution, loop distribution, and unimodular transformations while maintaining the basic philosophy of unimodular transformation theory. While our data indicate that imperfectly nested loops still present a problem, the compiler we describe is no more limited by perfectly nested loops than other restructuring compilers available today.>