Many scientific or engineering applications involve matrix operations, in which reduction of vectors is a common operation. If the core operator of the reduction is deeply pipelined, which is usually the case, dependencies between the input data elements cause data hazards. To tackle this problem, we propose a new reduction method with low latency and high pipeline utilization. The performance of the proposed design is evaluated for both single data set and multiple data set scenarios. Further, QR decomposition is used to demonstrate how the proposed method can accelerate its execution. We implement the design on an FPGA and compare its results to other methods.

Hardware accelerators such as FPGAs and GPUs in heterogeneous systems are being increasingly important for many applications. For high performance computing, the flexibility and efficiency of FPGA makes it an attractive alternative to other approaches. However, for applications that have to decompose large matrices, not many scalable solutions can be found on FPGAs. In this paper, we propose a scalable QR matrix decomposer on FPGAs based on the latest advances in tiled matrix decomposition algorithms for high performance linear algebra. The proposed design can decompose a matrix of size limited only by off-chip memory and has the potential to achieve high performance.

The emergence of multi-core architectures makes it essential for optimizing compilers to automatically extract parallelism for large scientific applications composed of many subroutines residing in different files. Inlining is a well-known technique which can be used to erase procedural boundaries and enable more aggressive loop parallelization. However, conventional inlining cannot be applied to external libraries where the source code is not available, and when overly applied, it can degrade the effectiveness of compiler optimizations due to excessive code complexity. This paper highlights some obstacles we encountered while applying conventional inlining combined with automatic loop parallelization using the Polaris optimizing compiler and presents a new approach, annotation-based inlining, to effectively overcome these obstacles. Our experimental results show that the annotation-based inlining approach can eliminate negative impact of conventional inlining while enhancing the effectiveness of interprocedural parallelization for a majority of applications from the PERFECT benchmark suite.

Abstract As part of its type‐safety regime, Java's semantics require precise exceptions at runtime when programs attempt out‐of‐bound array accesses. This paper describes a Java implementation that utilizes a multiphase approach to identifying safe array accesses. This approach reduces runtime overhead by spreading the out‐of‐bounds checking effort across multiple phases of compilation and execution: production of mobile code from source code, just‐in‐time (JIT) compilation in the virtual machine, application method invocations, and the execution of individual array accesses. The code producer uses multiple passes (including common subexpression elimination, load elimination, induction variable substitution, speculation of dynamically verified invariants, and inequality constraint analysis) to identify unnecessary bounds checks and prove their redundancy. During class‐loading and JIT compilation, the virtual machine verifies the proofs, inserts code to dynamically validate speculated invariants, and generates code specialized under the assumption that the speculated invariants hold. During each runtime method invocation, the method parameters and other inputs are checked against the speculated invariants, and execution reverts to unoptimized code if the speculated invariants do not hold. The combined effect of the multiple phases is to shift the effort associated with bounds‐checking array access to phases that are executed earlier and less frequently, thus, reducing runtime overhead. Experimental results show that this approach is able to eliminate more bounds checks than prior approaches with minimal overhead during JIT compilation. These results also show the contribution of each of the passes to the overall elimination. Furthermore, this approach increased the speed at which the benchmarks executed by up to 16%. Copyright © 2010 John Wiley & Sons, Ltd.

Many scientific or engineering applications perform reduction of sets of sequential data streams. If the core operator of the reduction is deeply pipelined, dependencies between the input data elements cause data hazards in the pipeline. To tackle this problem, we propose a multiple set variable length reduction design with low latency and high pipeline utilization in this paper. We prove the buffer size and execution time bounds, and then show its performance on practical multiple data set scenarios. We apply the proposed method to the Householder QR decomposition and compare its performance to other methods with superior results. The proposed design is implemented on FPGAs with resource usage and performance presented.

Many scientific applications involve reduction or accumulation operations on sequential data streams. Examples such as matrix-vector multiplication include multiple inner product operations on different data sets. If the core operator of the reduction is deeply pipelined, which is usually the case, dependencies between the input data cause data hazards in the pipeline and ask for a proper design. In this paper, we propose a modified design of the reduction operation based on Sips and Lin's method. We analyze the performance of the proposed design to prove the correctness of the timing and demonstrate its performance against previous methods.

Abstract The semantics of the Java programming language require that the out‐of‐bounds array accesses be caught at runtime. In general, this requires dynamic checks at the time the array element is accessed. Some of these checks can be eliminated statically during just‐in‐time (JIT) compilation, but the most precise analyses are too expensive to run in JIT compilers. This paper presents a framework in which thorough static range analyses can be used safely during the less‐performance‐critical compilation of Java source into machine‐independent mobile code. In this framework, the static analysis results are used to derive proofs that certain linear inequality constraints hold. These linear constraints and their proofs are then added to the mobile code as annotations. The annotation framework is designed so that proofs can be verified efficiently. This allows the JIT compiler to safely eliminate array bounds checks during compilation without an expensive runtime analysis. Experiments with a prototype system that can generate and verify these annotations demonstrate that this framework is more precise than prior work and that verification is efficient. Copyright © 2008 John Wiley & Sons, Ltd.

High-end parallel and multicore processors rely on compilers to perform the necessary optimizations and exploit concurrency in order to achieve higher performance. However, the source code for high-performance computers is extremely complex to analyze and optimize. In particular, program analysis techniques often do not take into account complex expressions during the data dependence analysis phase. Most data dependence tests are only able to analyze linear expressions, even though nonlinear expressions occur very often in practice. Therefore, considerable amounts of potential parallelism remain unexploited. In this paper, we propose new data dependence analysis techniques to handle such complex instances of the dependence problem and increase program parallelization. Our method is based on a set of polynomial-time techniques that can prove or disprove dependences in source codes with nonlinear and symbolic expressions, complex loop bounds, arrays with coupled subscripts, and if-statement constraints. In addition, our algorithm can produce accurate and complete direction vector information, enabling the compiler to apply further transformations. To validate our method, we performed an experimental evaluation and comparison against the I-Test, the Omega test, and the Range test in the Perfect and SPEC benchmarks. The experimental results indicate that our dependence analysis tool is accurate, efficient, and more effective in program parallelization than the other dependence tests. The improved parallelization results into higher speedups and better program execution performance in several benchmarks.

Accurate data dependence testing allows a compiler to perform safe automatic code optimization and parallelization. It has been shown that factors, such as loop variants and nonlinear expressions, limit opportunity for data dependence testing and parallelization. Recently, the NLVI-Test has been introduced as new technology to enable exact data dependence testing on nonlinear expressions. Apart from this work, analyses that utilize the Chains of Recurrences formalism have been shown to boost a dependence test's ability to analyze expressions. In this paper we present techniques for applying the NLVI-Test ideas in conjunction with Chains of Recurrences analysis, to couple the benefits of both. In addition, we develop a "Parallelization Index" which describes the upper bound of the total parallelization obtainable for our compiler infrastructure. We perform an experimental evaluation of our efforts on scientific benchmarks. Results show our techniques result in higher numbers of total parallel loops discovered, and moreover, that we consistently expose a majority of the parallelism obtainable.

Matrix decomposition applications that involve large matrix operations can take advantage of the flexibility and adaptability of reconfigurable computing systems to improve performance. The benefits come from replication, which includes vertical replication and horizontal replication. If viewed on a space-time chart, vertical replication allows multiple computations executed in parallel, and horizontal replication renders multiple functions on the same piece of hardware. In this paper, the reconfigurable architecture that supports replications for matrix decomposition applications on reconfigurable computing systems is described, and issues including the comparison of algorithms on the system and data movement between the internal computation cores and the external memory subsystem are addressed. A prototype of such a system is implemented to prove the concept. It is expected to improve the performance and scalability of matrix decomposition involving large matrices.

QR decomposition, especially through the means of Householder transformation, is often used to solve least squares problems. A matrix to be decomposed with this method is usually very large, often large enough that it is not able to fit into the main memory of a workstation, let alone the internal memory of an FPGA nowadays. Efficient out-of-core algorithms have been developed to address the factorization of large matrices. This paper describes the application of variants of Householder QR decomposition on FPGA-based systems. More specifically, issues on applying out-of-core algorithms to the relatively small internal memory architecture of FPGA's are investigated.

With the appearance of multi-gigabit network infrastructure, a typical network intrusion detection system (NIDS) has to cope with the network speed. By examining each packet flowing through a network segment, suspicious packets are detected and reported to assure security. Up to 57% of the execution time in a NIDS is found to compare string against a predefined/known pattern. It is hard to implement a multi-gigabit performance NIDS without hardware support. This paper proposes a very high speed string matching algorithm which can be easily implemented into FPGAs. The parallel matching design takes a segment of text from the payload of a packet and detects all possible tokens including those crossing text segment boundaries. Simulation results show a throughput of 23.43 Gbps with a moderate operating frequency of 366.2 MHz

Optimizing compilers rely upon program analysis techniques to detect data dependences between program statements. Data dependence information captures the essential ordering constraints of the statements in a program that need to be preserved in order to produce valid optimized and parallel code. Data dependence testing is very important for automatic parallelization, vectorization, and any other code transformation. In this paper, we examine the impact of data dependence analysis in practice. A number of data dependence tests have been proposed in the literature. In each test, there are different trade offs between accuracy and efficiency. We present an experimental evaluation of several data dependence tests, including the Banerjee test, the I-Test, and the Omega test. We compare these tests in terms of data dependence accuracy, compilation efficiency, effectiveness in parallelization, and program execution performance. We analyze the reasons why a data dependence test can be inexact and we explain how the examined tests handle such cases. We run various experiments using the Perfect Club Benchmarks and the scientific library Lapack. We present the measured accuracy of each test and the reasons for any approximation. We compare these tests in term's of efficiency and we analyze the trade offs between accuracy and efficiency. We also determine the impact of each data dependence test on the total compilation time. Finally, we measure the number of loops parallelized by each test and we compare the execution performance of each benchmark on a multiprocessor. Our results indicate that the Omega test is more accurate, but also very inefficient in the cases where the other two tests are inaccurate. In general, the cost of the Omega test is high and uses a significant percentage of the total compilation time. Furthermore, the difference in accuracy of the Omega test over the Banerjee test and the l-Test does not improve parallelization and program execution performance.

Optimizing compilers rely upon program analysis techniques to detect data dependences between program statements. Data dependence information captures the essential ordering constraints of the statements in a program that need to be preserved in order to produce valid optimized and parallel code. Data dependence testing is very important for automatic parallelization, vectorization and any other code transformation. In this paper we examine the impact of data dependence analysis in practice. A number of data dependence tests have been proposed in the literature. In each test there are different tradeoffs between accuracy and efficiency. We present an experimental evaluation of several data dependence tests, including the Banerjee test, the I-Test and the Omega test. We compare these tests in terms of data dependence accuracy, compilation efficiency, effectiveness in parallelization and program execution performance. We analyze the reasons why a data dependence test can be inexact and we explain how the examined tests handle such cases. We run various experiments using the Perfect Club Benchmarks and the scientific library Lapack. We present the measured accuracy of each test and the reasons for any approximation. We compare these tests in terms of efficiency and we analyze the tradeoffs between accuracy and efficiency. We also determine the impact of each data dependence test on the total compilation time. Finally, we measure the number of loops parallelized by each test and we compare the execution performance of each benchmark on a multiprocessor. Our results indicate that the Omega test is more accurate, but also very inefficient in the cases where the other two tests are inaccurate. In general the cost of the Omega test is high and a significant percentage of the total compilation time. Furthermore, the difference in accuracy of the Omega test over the Banerjee test and the I-Test does not improve parallelization and program execution performance.

Parallelizing compilers rely on data dependence information in order to produce valid parallel code. Polynomial data dependence analysis techniques, such as the Banerjee test and the I-Test, can efficiently compute data dependence information for simple instances of the data dependence problem. In more complicated cases such as triangular or trapezoidal loop regions with direction vector constraints these tests, including the triangular Banerjee test, ignore or simplify many of the constraints and thus introduce further approximations. The I-Test and the Omega test are two data dependence tests that can provide exact data dependence information. In addition the Omega test can accurately handle complex loop regions but at a higher computation cost. We extend the ideas behind the I-Test to handle such complex regions which are frequently found in actual source code. In particular, we provide a polynomial-time algorithm, the VI-Test that can detect data dependences in loops with triangular bounds and symbolic variables subject to any direction vector. We also perform an extensive experimental evaluation of the various dependence tests, including the I-Test, the VI-Test and the Omega test. We run several experiments using the Perfect Club Benchmarks and the scientific libraries Eispack, Linpack and Lapack. We present accuracy results, reasons for inconclusive answers, and comparative efficiency metrics.

Efficient and fair use of buffer space in ATM switches is essential to gain high throughput and low cell-loss performance from the network. A shared buffer architecture associated with threshold based virtual partition among output ports is proposed. Thresholds are updated based on traffic characteristics on each outgoing link, so as to adapt to traffic loads. System behavior under varying traffic patterns is investigated via simulation. Cell loss rate is the quality of service (QoS) measure that is used in this paper. The study shows that the threshold based adaptive buffer allocation scheme ensures fair share of the buffer space even under bursty loading conditions.

In an earlier work, a Threshold Scheduling Algorithm was proposed to schedule the functional parallelism in a program on distributed memory systems. In this work, we address the issue of regeneration of the schedule for a set of distributed memory architectures with different communication costs. A new concept of dominant edges of a schedule is introduced to denote those edges which dictate schedule regeneration due to the changes in their communication costs. It is shown that under certain conditions, schedule on the whole or at least part of the graph can be reused for a different architecture reducing the cost of program re-partitioning and re-scheduling. The usefulness of this method is demonstrated by incorporating it in the scheduler of the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on a family of Intel i860 architectures : Gamma, Delta and Paragon which vary in their communication costs. It is shown that almost SO to 65 % of the schedule can be reused, thereby, avoiding program re-partitioning to a large degree.

Parallelizing Compilers rely upon subscript analysis to detect data dependences between pairs of array references inside loop nests. The most widely used approximate subscript analysis tests are the GCD test and the Banerjee test. In an earlier work we proposed the I test, an improved subscript analysis test. The I test extends the accuracy of a combination of the GCD test and the Banerjee test. It is also able to provide exact data dependence information at no additional computation cost. In the present work we perform an empirical study on the Perfect Club benchmarks to demonstrate the effectiveness and practical importance of the I Test. We compare its performance with that of the GCD test and the Banerjee test. We show that the I test is always an exact test in practice.

The GCD and Banerjee tests are the standard data dependence tests used to determine whether a loop may be parallelized/vectorized. In an earlier work, (1991) the authors presented a new data dependence test, the I test, which extends the accuracy of the GCD and the Banerjee tests. In the original presentation, only the case of general dependence was considered, i.e., the case of dependence with a direction vector of the form (*,*,...,*). In the present work, the authors generalize the I test to check for data dependence subject to an arbitrary direction vector.>

The GCD test and the Banerjee-Wolfe test are the two tests traditionally used to determine statement data dependence, subject to direction vectors, in automatic vectorization / parallelization of loops. In an earlier study [14] a sufficient condition for the accuracy of the Banerjee-Wolfe test was stated and proved. In the original presentation only the case of general data dependence was considered, i.e., the case of data dependence without direction vector information. In this paper we extend the previous work to the case of data dependence subject to an arbitrary direction vector. We also state and prove a sufficient condition for the accuracy of a combination of the GCD and the Banerjee-Wolfe test. Finally, we demonstrate how these results can be used in actual practice to obtain exact data dependence information.

Article Free Access Share on Extending the I test to direction vectors Authors: Kleanthis Psarris Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New Jersey Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New JerseyView Profile , Xiangyun Kong Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New Jersey Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New JerseyView Profile , David Klappholz Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New Jersey Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, Hoboken, New JerseyView Profile Authors Info & Claims ICS '91: Proceedings of the 5th international conference on SupercomputingJune 1991 Pages 330–340https://doi.org/10.1145/109025.109106Online:01 June 1991Publication History 1citation190DownloadsMetricsTotal Citations1Total Downloads190Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The I test is a subscript dependence test which extends both the range of applicability and the accuracy of the GCD and Banerjee tests (U. Banerjee, 1976), standard subscript dependence tests used to determine whether loops may be parallelized/vectorized. It is shown that the I test is useful when, in the event that a positive result must be reported, a definitive positive is of more use than a tentative positive and when insufficient loop iterations are known for the Banerjee test to apply.>

The Banerjee test is commonly considered to be the more accurate of the two major approximate data dependence tests used in automatic vectorization/parallelization of loops, the other being the GCD test. From its derivation, however, there is no simple explanation of why the Banerjee test should be nearly as accurate as it is given credit for. We present a set of sufficient conditions for the Banerjee test's accuracy, and explain its perceived accuracy in actual practice by proving that under circumstances which occur extremely frequently in actual code, the Banerjee test is, in fact, not approximate, but perfectly accurate.