Multi-cores such as the Intel®1 Core™2 Duo processor, facilitate efficient thread-level parallel execution of ordinary programs, wherein the different threads-of-execution are mapped onto different physical processors. In this context, several techniques have been proposed for auto-parallelization of programs. Recently, thread-level speculation (TLS) has been proposed as a means to parallelize difficult-to-analyze serial codes. In general, more than one technique can be employed for parallelizing a given program. The overlapping nature of the applicability of the various techniques makes it hard to assess the intrinsic performance potential of each. In this paper, we present a tight analysis of the (unique) performance potential of both: (a) TLS in general and (b) specific types of thread-level speculation, viz., control speculation, data dependence speculation and data value speculation, for the SPEC2 CPU2006 benchmark suite in light of the various limiting factors such as the threading overhead and misspeculation penalty. To the best of our knowledge, this is the first evaluation of TLS based on SPEC CPU2006 and accounts for the aforementioned real-life con-straints. Our analysis shows that, at the innermost loop level, the upper bound on the speedup uniquely achievable via TLS with the state-of-the-art thread implementations for both SPEC CINT2006 and CFP2006 is of the order of 1%.

Emergence of chip multiprocessors has created a need for exploitation of beyond DOALL-type thread-level parallelism (TLP). This calls for development of efficient thread synchronization techniques to exploit TLP in general parallel programs with dependences. For this, several thread synchronization techniques have been proposed in the past. However, these limit the exploitation of fine-grain TLP due to large run-time overhead. Furthermore, the existing approaches can potentially result in (i) deadlocks between the different threads and (ii) non-deterministic run-time execution behavior as these techniques are oblivious of the underlying memory model. In this paper, we propose lightweight lock-free thread synchronization methods to exploit TLP in general parallel programs with dependences. Each synchronization method intrinsically guarantees the following in a multithreaded program: (a) sequential consistency, (b) atomicity of writes to the shared synchronization construct and (c) absence of deadlocks. This reduces the programming effort considerably, thereby easing the development of software for multithreaded systems. For each method we formally prove that there cannot occur a deadlock between the different threads. This obviates the cumbersome and time-consuming process of detecting and eliminating deadlocks from the programmer. Experiments show that our synchronization methods incur a minimal overhead of 7.16% on an average. Further, we achieve performance speedups upto 3.39x on kernels extracted from the industry standard SPEC OMPM 2001 benchmarks, on a dedicated Intel® Xeon® 2.78 GHz 4-way multiprocessor.

Recent research in thread-level speculation (TLS) has proposed several mechanisms for optimistic execution of difficult-to-analyze serial codes in parallel. Though it has been shown that TLS helps to achieve higher levels of parallelism, evaluation of the unique performance potential of TLS, i.e., performance gain that be achieved only through speculation, has not received much attention. In this paper, we evaluate this aspect, by separating the speedup achievable via true TLP (thread-level parallelism) and TLS, for the SPEC CPU2000 benchmark. Further, we dissect the performance potential of each type of speculation --- control speculation, data dependence speculation and data value speculation. To the best of our knowledge, this is the first dissection study of its kind. Assuming an oracle TLS mechanism --- which corresponds to perfect speculation and zero threading overhead --- whereby the execution time of a candidate program region (for speculative execution) can be reduced to zero, our study shows that, at the loop-level, the upper bound on the arithmetic mean and geometric mean speedup achievable via TLS across SPEC CPU2000 is 39.16% (standard deviation = 31.23) and 18.18% respectively.

This paper discusses a repertoire of well-known and new compiler optimizations that help produce excellent server application performance and investigates their performance contributions. These optimizations combined produce a 40% speed-up in on-line transaction processing (OLTP) performance and have been implemented in the Intel C/C++ Itanium compiler. In particular, the paper presents compiler optimizations that take advantage of the Itanium register stack, proposes an enhanced Linux preemption model and demonstrates their performance potential for server applications.

In recent years, there have been tremendous advances in mathematical modeling of derivative securities, many of which are computational intensive. On the other hand, there have also been tremendous advances in computing technologies with rapidly improved computing performance. However, little research has been done on the impact of high performance computers on the design of efficient algorithms for financial modeling. The authors show that careful design of computer algorithms will make full use of the potential computing power of modern high performance computers. In particular, most computers have memory hierarchies to improve the performance of memory accesses. They show that a good design of data structures for lattice based algorithms can significantly improve the performance of the algorithm.

Discovery of association rules is an important database mining problem.Mining forassociation nrlesinvolves extracting patterns from large databases and inferring useful rules from them.Several parallel arsd sequential algorithms have been proposed in the literature tosolve this problem.Almost all of these algorithms make repeated passes over thedatabase todetennine the commonly occurring patterns oritemsets (set ofitems), thus incurnnghigh I/O overhead.Intheparallel case, these algorithms do a reduction at the end of each pass to construct the global patterns, thus incurnng high synchronization cost,In this paper we describes new parallel association reining algorithm, Our algorithm is a result of detailed study of the available parallelism and the properties of associations.The algorithm usesa scheme to cluster related frequent itemsets together, and to partition them among the processors, At the same time it also uses a different database layout which clusters related transactions together, and selectively replicates the database so that theportion of thedatabase needed for the computation of associations is local to each processor.After the initial set-up phase, the algorithm eliminates the need for further communication or synchronization, 'rlrealgorit hmfurtherscanst helocal database partition only three times, thus minimizing I/O overheads.Urdikeprevious approaches, thealgorithms uses simple intersection operations to compute frequent item sets and doesn 't have to maintain or search complex hash structures.Our experimental testbed is a 32-processor DEC Alpha clusterinter-connected bythe Memory Channel network.Wepresent results on the performance of our algorithm on various databases, andcompare itagainst awellknown parallel algorithm, Ouralgorithm outperforms it by an more than an order of magnitude.Award (CCR-9409 120) and ARPA contract F19628-94-C-O057.Pemlissiotl 10 moke digilal/h2rd copies ot':111 or pflll 01'[111s nullcn;ll Iilr pwwnnl or classroom ust is grnnled \Yilhool lit pro\,idcd 11101 (he wspics are noI m:ide or dis[ritw led I'01 proli[ or comnterci; i] odwm(agc, Ilw cop\lright notice, the title oftlm pul?lico[lon Jml IIS d;LIC I , ppmr.:md nolic~s i.\ given tlvsl cqyiglll is hy pem)wion ot'lhe .i~il.Inc. "1"0 tq)y oll)er\vis.2, 10 reptthlisll.10 post on wrvcrs or 10 rcdlstrihu(c 10 lisw.rctltlirm spccilic permission and/or fee .V'AA 97 Ne\vpwr,Rhode [S1;1111{ [ :$/4 ~opyrigl)t 1997 ACM 0.89791 -X9(J-W97/06 ,.$'3.50

In this paper, we study the problem of scheduling parallel loops at compile time for a heterogeneous network of workstations. We consider heterogeneity in various aspects of parallel programming: program, processor, memory and network. A heterogeneous program has parallel loops with different amounts of work being done in each iteration; heterogeneous processors have different speeds; heterogeneous memory refers to the different amounts of user-available memory on the machines and a heterogeneous network has different communication costs between processors. We propose a simple yet comprehensive model for use in compiling for a network of processors, and develop compiler algorithms for generating optimal and near-optimal schedules of loops for load balancing, communication optimizations, network contention and memory heterogeneity. Experiments show that a significant performance improvement is achieved using our techniques.

Our previous experience with an off-line Java optimizer has shown that some traditional algorithms used in compilers are too slow for a JIT compiler. In this paper we propose and implement faster ways of performing analyses needed for our optimizations. For instance, we have replaced reaching definitions with constant values and loop induction variables with loop-defined variables. As a result, our JIT compiler, Briki, is very fast, so that its running time is negligible even when the data sets used with our benchmarks result in execution times of only a few seconds. The impact for the same benchmarks running on more realistic problem sizes would be even smaller. Currently the speedups resulting from applying our optimizations are between 10% and 20%, but when the JIT compiler performs standard optimizations which are absent in the current version of the JIT compiler used by us, thespeedups should be similar to the ones observed for Fortran programs – up to 50%. © 1997 John Wiley & Sons, Ltd.

We have developed a research compiler for Java class files. The compiler, which we call Briki, is designed to test new compilation techniques. We focus on optimizations which are only possible or much easier to perform on a high-level intermediate representation. We have designed such a representation, JavaIR, and have written a front-end which recovers the high-level structure from the information from the class file. Some of the high-level optimizations can be performed by the Java compiler which produces the class file. There is, however, a set of machine-dependent optimizations which have to be customized for the specific architecture and so can only be performed when the machine code is generated from the bytecodes, e.g. in a just-in-time (JIT) compiler. We choose memory hierarchy optimizations as an example of machine-dependent techniques. We show that there is an intersection of the set of machine-dependent optimizations and the set of high-level optimizations. One such example is array remapping, which requires multi-dimensional array references which are not present in the bytecodes and at the same time requires information about memory organization and the mapping of bytecodes to machine instructions. We develop a set of optimizations for accessing array elements and object fields and show their impact on a set of benchmarks which we run on two machines with a JIT compiler. The execution times are reduced by as much as 50% and we argue that the improvement could be even higher with a more mature JIT technology. © 1997 John Wiley & Sons, Ltd.

Load balancing involves assigning to each processor work proportional to its performance, minimizing the execution time of the program. Although static load balancing can solve many problems (e.g., those caused by processor heterogeneity and non uniform loops) for most regular applications, the transient external load due to multiple users on a network of workstations necessitates a dynamic approach to load balancing. We examine the behavior of global vs. local, and centralized vs. distributed, load balancing strategies. We show that different schemes are best for different applications under varying program and system parameters. Therefore, customized load balancing schemes become essential for good performance. We present a hybrid compile time and run time modeling and decision process which selects (customizes) the best scheme, along with automatic generation of parallel code with calls to a run time library for load balancing.

Data mining is an emerging research area, whose goal is to extract significant patterns or interesting rules from large databases. High-level inference from large volumes of routine business data can provide valuable information to businesses, such as customer buying patterns, shelving criterion in supermarkets and stock trends. Many algorithms have been proposed for data mining of association rules. However, research so far has mainly focused on sequential algorithms. In this paper we present parallel algorithms for data mining of association rules, and study the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor. We further present a set of optimizations for the sequential and parallel algorithms.Experiments show that a significant improvement of performance is achieved using our proposed optimizations. We also achieved good speed-up for the parallel algorithm, but we observe a need for parallel I/O techniques for further performance gains.

In this paper we study the problem of scheduling parallel loops at compile-time for a heterogeneous network of machines. We consider heterogeneity in three aspects of parallel programming: program, processor and network. A heterogeneous program has parallel loops with different amount of work in each iteration; heterogeneous processors have different speeds; and a heterogeneous network has different cost of communication between processors. We propose a simple yet comprehensive model for use in compiling for a network of processors, and develop compiler algorithms for generating optimal and sub-optimal schedules of loops for load balancing, communication optimizations and network contention. Experiments show that a significant improvement of performance is achieved using our techniques.

Almost every modern processor is designed with a memory hierarchy organized into several levels, each of which is smaller, faster, and more expensive than the level below.High performance requires the effective use of the cached data, i.e. cache locality.Smart compiler transformations can relieve the programmer from hand-optimizing for the specific machine architectures.Most of the existing compiler optimizations are developed for dense matrix programs.Irregular problems, on the other hand, have to rely on runtime optimizations, since the data access patterns are unknown at the compile-time.However, many scientific computing problems result in solving linear systems where the matrix of coefficients is banded, a structure known at the compile-time, but more complicated than the dense matrices.Banded matrix problems are interesting since substantial savings can be made by exploiting the mathematical properties of the handedness.The complicated memory access patterns in the banded matrix programs make the existing compile-time optimization impossible to use.In this paper, we present a new compile-time technique for optimizing banded-matrix programs.We first develop a new data reuse model and an algorithm called height reduction to improve cache locality.Then with the height reduction algorithm, we extend loop tiling to exploit not only intra-tile data Iocality but also inter-tile data locality.We call the new tiling a#irrity tiling.We show that the algorithms also helps to eliminate or reduce false sharing in multiprocessor systems.With the height reduction algorithm and affinity tiling, significant performance improvement (speedups from 2,5 to 10) has been observed on HP workstations (over the original sequential code) and KSR1 multiprocessors (over the original parallel code), *This work WJS supported m ptit by m NSF Research Initiation Award (CCR-9409 120) and ARPA contract F] 9628

We present a unified approach to locality optimization that employs both data and control transformations. Data transformations include changing the array layout in memory. Control transformations involve changing the execution order of programs. We have developed new techniques for compiler optimizations for distributed shared-memory machines, although the same techniques can be used for sequential machines with a memory hierarchy.

No abstract available.

In scalable parallel machines, processors can make local memory accesses much faster than they can make remote memory accesses. Additionally, when a number of remote accesses must be made, it is usually more efficient to use block transfers of data rather than to use many small messages. To run well on such machines, software must exploit these features. We believe it is too onerous for a programmer to do this by hand, so we have been exploring the use of restructuring compiler technology for this purpose. In this article, we start with a language like HPF-Fortran with user-specified data distribution and develop a systematic loop transformation strategy called access normalization that restructures loop nests to exploit locality and block transfers. We demonstrate the power of our techniques using routines from the BLAS (Basic Linear Algebra Subprograms) library. An important feature of our approach is that we model loop transformation using invertible matrices and integer lattice theory.

In scalable parallel machines, processors can make local memory accesses much faster than they can make remote memory accesses. In addition, when a number of remote accesses must be made, it is usually more efficient to use block transfers of data rather than to use many small messages. To run well on such machines, software must exploit these features. We believe it is too onerous for a programmer to do this by hand, so we have been exploring the use of restructuring compiler tecnology for this purpose. In this paper, we start with a language like FORTRAN-D with user-specified data distribution and develop a systematic loop transformation strategy called access normalization that restructures loop nests to exploit locality and block transfers. We demonstrate the power of our techniques using routines from the BLAS (Basic Linear Algebra Subprograms) library. An important feature of our approach is that we model loop transformations using invertible matrices and integer lattice theory, thereby generalizing Banerjee's framework of unimodular matrices [5].