RPC-FPGA is a remote procedure call protocol implementation of the Open Network Computing ONC-RPC specification for use in FPGA accelerators. The implementation involves the generation of High-Level Synthesis (HLS) interface stubs to call a hardware procedure and stream the data between the processor and the FPGA. The RPC protocol is extended to accept variable-length arrays with multiple dimensions. This extension is required to support optimizing nested loop transformations on multidimensional arrays stored in the reconfigurable logic. The major benefits of RPC-FPGA are: hardware procedures running on an FPGA accelerator become accessible for any client in the network, multiple hardware procedures run in a truly parallel fashion and the development time of the communication interface between the processor and the FPGA is largely reduced. Using RPC-FPGA a speedup gain of 17 to 20 is demonstrated on a square matrix multiplication of N=4096 with network speeds 100 Mbps and 1 Gbps respectively.

Low-power, high-performance computing nowadays relies on accelerator cards to speed up the calculations. Combining the power of GPUs with the flexibility of FPGAs enlarges the scope of problems that can be accelerated [2, 3]. We describe the performance analysis of a desktop equipped with a GPU Tesla 2050 and an FPGA Virtex-6 LX240T. First, the balance between the I/O and the raw peak performance is depicted using the roofline model [4]. Next, the performance of a number of image processing algorithms is measured and the results are mapped onto the roofline graph. This allows to compare the GPU and the FPGA and also to optimize the algorithms for both accelerators. A programming toolchain is implemented, consisting of OpenCL for the GPU and several High-Level Synthesis compilers for the FPGA. Our results show that the HLS compilers outperform handwritten code and offer a performance comparable to the GPU. In addition the FPGA compilers reduce the development time by an order of magnitude, at the expense of an increased resource consumption. The roofline model also shows that both accelerators are equally limited by the input/output bandwidth to the host. A well-tuned accelerator-based codesign, identifying the parallelism, the computation and data patterns of different classes of algorithms, will enable to maximize the performance of the combined GPU/FPGA system [1].

Nowadays, processors alone cannot deliver what computation hungry image processing applications demand. An alternative is to use hardware accelerators such as Graphics Processing Units (GPUs) or Field Programmable Gate Arrays (FPGAs). Applications, however, exhibit different performance characteristics depending on the accelerator. This paper describes the hybrid platform and the programming environment that allows to efficiently create programs on a combined GPU/FPGA desktop. We use the roofline model to identify the most appropriate accelerator for each application and High-Level Synthesis (HLS) tools to reduce the FPGA development time. To introduce our platform and tool chain both accelerators are compared by implementing a basic image operation. Next, a promising algorithm is explored and implemented, splitting and distributing the work between GPU, FPGA and CPU in order to validate the hybrid concept. Our results show that their combination exhibits a higher performance for computational intensive image processing applications than a GPU only.

Application-specific hardware accelerators can significantly improve a system's performance. In a Java-based system, we then have to consider a hybrid architecture that consists of a Java Virtual Machine running on a general-purpose processor connected to the hardware accelerator. In such a hybrid architecture, data communication between the accelerator and the general-purpose processor can incur a significant cost, which may even annihilate the original performance improvement of adding the accelerator. A careful layout of the data in the memory structure is therefore of major importance to maintain the acceleration performance benefits. This article addresses the reduction of the communication cost in a distributed shared memory consisting of the main memory of the processor and the accelerator's local memory, which are unified in the Java heap. Since memory access times are highly nonuniform, a suitable allocation of objects in either main memory or the accelerator's local memory can significantly reduce the communication cost. We propose several techniques for finding the optimal location for each Java object's data, either statically through profiling or dynamically at runtime. We show how we can reduce communication cost by up to 86% for the SPECjvm and DaCapo benchmarks. We also show that the best strategy is application dependent and also depends on the relative cost of remote versus local accesses. For a relative cost higher than 10, a self-learning dynamic approach often results in the best performance.

In name and in practice, the World-Wide Web (hereafter Web) is used around the World beyond English-speaking areas. This creates a tremendous need to internationalize standard terminology used in the technologies that make the Web possible. Existing efforts on XML internationalization (i18n) and localization (i10n) have focused on the content of XML documents instead of the terms used in markup (annotations) such as elements and attributes. The SGML standard ISO 8879 supports the use of Unicode (ISO 10646) throughout a document, including markups. However, most elements and attributes of XML documents are still defined in English, thereby limiting their use among non-English speakers. This paper presents an XSLT-based method that can completely localize the markup of XML documents into different natural languages. We also describe how the proposed technique can be applied to translation problems in programming (e.g. C and Java) or documentation (e.g. LATEX or other formatting languages) so that a program or a document can be converted to and from an XML format. Copyright © 2004 John Wiley & Sons, Ltd.

Nonuniform distance loop dependences are a known obstacle to find parallel iterations. To find the outermost loop parallelism in these "irregular" loops, a novel method is presented based on recurrence chains. The scheme organizes nonuniformly dependent iterations into lexicographically ordered monotonic chains. While the initial and final iterations of monotonic chains form two parallel sets, the remaining iterations form an intermediate set that can be partitioned further. When there is only one pair of coupled array references, the nonuniform dependences are represented by a single recurrence equation. In that case, the chains in the intermediate set do not bifurcate and each can be executed as a WHILE loop. The independent and the initial iterations of monotonic dependence chains constitute the outermost parallelism. The proposed approach compares favorably with other treatments of nonuniform dependences in the literature. When there are multiple recurrence equations, a dataflow parallel execution can be scheduled using the technique to find maximum loop parallelism.

The intermediate representation (IR) forms the information exchanged among different passes of program compilation. The intermediate format proposed for extensibility and persistence is written in XML. In this way, the program transformations that were internal to the compiler become visible. The hierarchical structure of XML makes a natural representation for the abstract syntax tree (AST). A compiler can parse the program source into an IR, then output it as an XML document. Separated by orthogonal namespaces, other IRs are also presented in the same XML document, gathering program information such as dependence vectors, transforming matrices, iteration spaces dependence graphs and cache reuse distances. This XML document can be exchanged between the compiler and program visualizers for parallelism and locality.

Advanced computer architectures rely mainly on compiler optimizations for parallelization, vectorization, and pipelining. Efficient-code generation is based on a control dependence analysis to find the basic blocks and to determine the regions of control. However, unstructured branch statements, such as jumps and goto's, render the control flow analysis difficult, time-consuming, and result in poor code generation. Branches are part of many programming languages and occur in legacy and maintenance code as well as in assembler, intermediate languages, and byte code. A simple and effective technique is presented to convert unstructured branches into hammock graph control structures. Using three basic transformations, an equivalent program is obtained in which all control statements have a well-defined scope. In the interest of predication and branch prediction, the number of control variables has been minimized, thereby allowing a limited code replication. The correctness of the transformations has been proven using an axiomatic proof rule system. With respect to previous work, the algorithm is simpler and the branch conditions are less complex, making the program more readable and the code generation more efficient. Additionally, hammock graphs define single entry single exit regions and therefore allow localized optimizations. The restructuring method has been implemented into the parallelizing compiler FPT and allows to extract parallelism in unstructured programs. The use of hammock graph transformations in other application areas such as vectorization, decompilation, and assembly program restructuring is also demonstrated.

The global cache misses ratio of a program does not reveal the time distribution of the memory reference patterns in detail. On the other hand, cache visualization is hampered by the huge amount of memory references to display. Therefore, many visualizers focus on a snapshot of the cache content, instead of viewing all memory transactions. A cache visualizer is introduced which presents the integral cache behavior of a program in several complementary views: the density view of the cache misses shows the hot spots of the program; the reuse distances view shows the data locality and its effect on performance; the histogram view shows the periodical patterns that occurs in the trace. In a number of experiments, the visualizer has been used to characterize the cache behavior and effectively improve the cache behavior and program performance.

A new technique to parallelize loops with variable distance vectors is presented. The method extends previous methods in two ways. First, the present method makes it possible for array subscripts to be any linear combination of all loop indices. The solutions to the linear dependence equations established from such array subscripts are characterized by a pseudo distance matrix (PDM). Second, it allows us to exploit loop parallelism from the PDM by applying unimodular and partitioning transformations that preserve the lexicographical order of the dependent iterations. The algorithms to derive the PDM, to find a suitable loop transformation and to generate parallel code are described, showing that it is possible to parallelize a wider range of loops automatically.

Program parallelization is inhibited by unstructured control statements such as GOTOs, causing interacting and overlapping execution trajectories. In this contribution, a program restructuring method is proposed to convert unstructured control statements into block if statements and while loops. Furthermore, an algorithm is presented to transform a common type of while loops into do loops. The technique works for while loops of which the control variables satisfy a linear recurrence relation. As a result, the loop carried dependencies generated by the control variables are removed. If there are no other loop carried dependencies, the do loop may then be converted into a doall loop. The algorithm has been used to test and convert a significant number of while loops into doall loops for a suite of well-known numerical benchmarks.

A general method for the identification of the independent subsets in loops with constant dependence vectors is presented. It is shown that the dependence relation remains invariant under a unimodular transformation. Then a unimodular transformation is used to bring the dependence matrix into a form where the independent subsets are obtained by a direct and inexpensive partitioning algorithm. This leads to a procedure for the automatic conversion of a serial loop into a nest of parallel DO-ALL loops. Another unimodular transformation results in an algorithm to label the dependent iterations of an n-fold nested loop in O(n/sup 2/) time. This provides a multithreaded dynamic scheduling scheme requiring only one fork and one join primitive.>