We propose Chaperone, a new runtime system which implements an innovative binary-level instrumentation technique that bounds performance degradation of around 14% on average of the total applications execution time, hence it can be used by users in production deployments. Our technique is called Partial Binary Translation. It consists of translating the entire code image and inserting required instrumenting stubs in the translated code at loadtime, and at runtime, differently from normal instrumentation, switching the execution dynamically between original and instrumented code. Using this technology we demonstrate two different use cases of the Chaperone system. The first is a runtime memory checker that detects memory accesses outside the legally allocated heap memory bounds. The second is a dynamic performance tuning of OpenMP applications by automatically setting the optimal number of active OpenMP threads and affinitizing them to the available cores. In both cases we measured low overhead of Chaperone. Moreover, Chaperone shows minimal performance degradation for the Memory Checker and improved performance for OpenMP based applications.

Tools that provide optimization hints for program developers are facing severe obstacles and often unable to provide meaningful guidance on how to parallelize real-life applications. The main reason is due to the high code complexity and its large size when considering commercially valuable code. Such code is often rich with pointers, heavily nested conditional statements, nested while-based loops, function calls, etc. These constructs prevent existing compiler analysis from extracting the full parallelization potential. We propose a new paradigm to overcome this issue by automatically transforming the code' into a much simpler skeleton-like form that is more conductive for auto-parallelization. We then apply existing tools of source-level automatic parallelization on the skeletonized code in order to expose possible parallelization patterns. The skeleton code, along with the parallelized version, are then provided to the programmer in the form of an Integrated Development Environment (IDE) recommendation. The proposed skeletonization algorithm replaces pointers by integer indexes and C-struct references by references to multi-dimensional arrays. For example, the loop while(p ≠ NULL) {p → val + +; p = p → next;} will be skeletonized to: for(Ip = 0; Ip <; N; Ip + +){Aval[Ip] + +;} where Aval[] holds the embedding of the original list. Consequently, the main goal of the skeletonization process is to embed pointer-based data structures into arrays. Though the skeletonized code is not semantically equivalent to the original code, it suggests a possible parallelization pattern for the selected code segment and can be used as an effective parallelization hint to the programmer. We applied the method on the SPEC CPU benchmarks and the skeletonization process detected 27 percent additional loops that can be parallelized/vectorized on top of the compiler auto-parallelizer/vectorizer. A performance gain of up to 45 percent was measured for benchmarks that were manually parallelized based on the generated skeleton code.

Manycore shared memory architectures hold a significant premise to speed up and simplify SOCs. Using many homogeneous small-cores will allow replacing the hardware accelerators of SOCs by parallel algorithms communicating through shared memory. Currently shared memory is realized by maintaining cache-consistency across the cores, caching all the connected cores to one main memory module. This approach, though used today, is not likely to be scalable enough to support the high number of cores needed for highly parallel SOCs. Therefore we consider a theoretical scheme for shared memory wherein: the shared address space is divided between a set of memory modules; and a communication network allows each core to access every such module in parallel. Load-balancing between the memory modules is obtained by rehashing the memory address-space. We have designed a simple generic shared memory architecture, synthesized it to 2,4,8,,..1024-cores for FPGA virtex-7 and evaluated it on several parallel programs. The synthesis results and the execution measurements show that, for the FPGA, all problematic aspects of this construction can be resolved. For example, unlike ASICs, the growing complexity of the communication network is absorbed by the FPGA's routing grid and by its routing mechanism. This makes this type of architectures particularly suitable for FPGAs. We used 32-bits modified PACOBLAZE cores and tested different parameters of this architecture verifying its ability to achieve high speedups. The results suggest that re-hashing is not essential and one hash-function suffice (compared to the family of universal hash functions that is needed by the theoretical construction).

Tools that provide optimization hints for program developers are facing severe obstacles and often unable to provide meaningful guidance on how to parallelize real--life applications. The main reason is due to the high code complexity and its large size when considering commercially valuable code. Such code is often rich with pointers, heavily nested conditional statements, nested while--based loops, function calls, etc. These constructs prevent existing compiler analysis from extracting the full parallelization potential. We propose a new paradigm to overcome this issue by automatically transforming the code into a much simpler skeleton-like form that is more conductive for auto-parallelization. We then apply existing tools of source--level automatic parallelization on the skeletonized code in order to expose possible parallelization patterns. The skeleton code, along with the parallelized version, are then provided to the programmer in the form of an IDE (Integrated Development Environment) recommendation.

In this work we consider the problem of fast parallel evaluation of boolean circuits - namely to evaluate a boolean circuit C, with input leaf values, faster than its depth, which would practically require log depth iterations to complete. Finding a general parallel algorithm that can evaluate any circuit using log depth iterations is known as the Circuit Value Problem (CVP). The CVP and its approximations are known to be P-complete and therefore, a heuristically solution that practically works for all “real-computations” is sought. In this work we propose a new algorithm based on a two players game that can reduce the evaluation time of a boolean circuit C by upto min(h, min(log d, log co - d)) iterations where h is the maximal number of and-or alternations along any path in C and d (and co - d) is the algebraic degree (and co-degree) of C. This improves the theoretical bound of the MRK algorithm (Miller, Ramachandran and Kaltofen 86) for the case of parallel evaluation of boolean circuits. More importantly we show, via experiments, that for circuits emanating from real programs, the proposed algorithm can practically evaluate circuits in log - depth iterations. Each iteration can be evaluated in parallel using a connectivity step, and although it can be implemented using log-depth boolean circuits, we consider an optical switching realization that is based on Optical Ring Resonators (ORR). Due to quantum effects, propagating a light beam through a sequence of ORRs can be done with zero latency, thus making ORRs ideal for implementing the connectivity step required by the proposed algorithm. In order to obtain the needed experiments, we have extended the LLVM compiler to transform C-code into boolean circuits and then simulated the optical evaluation of these circuits using the proposed two player game. Our experiments indeed show that circuits emanating from real applications can be evaluated in log-depth iterations of the proposed algorithm and that the optical implementation is feasible.

A set of clusters (Grid) of multicore machines form an attractive platform for executing parallel programs. However, it is not clear how to program a single coherent parallel program over such a Grid of multicore machines (MCs). The main problem derives from the fact that the shared memory of each single MC machine cannot be scaled to run over a cluster of machines or a Grid. This is due to the fact that shared memory in a multicore machine is handled in hardware using a special cache coherency protocol, whereas over a cluster, the shared memory must be implemented in software using message passing. It is therefore, imperative for a Grid to devise a unified and coherent programming language that would combine both shared memory and message passing constructs, e.g., a language that combines the abilities of both OpenMP and MPI into one coherent language. The proposed language must produce parallel programs that are portable and can support the ability to scale the cluster without the need for re-compilation.

Today's architectures exploit long pipelines in order to increase instruction-level parallelism by grouping sets of consecutive instructions and feeding them into the pipeline with the purpose of executing them in a single cycle.The IBM Power architecture executes programs by dispatching groups of instructions where a dispatch group is fed as a whole into the pipeline to be executed in a single cycle.Such architecture, however, includes many cases of pipeline delays that result from dependencies between the resources of separate groups.As a result, there is a need to optimize the code in order to help the architecture place all the instructions in such a way that will produce as few delays as possible.Optimizing the alignment and the placement of the code is therefore, crucial to the performance of the program in such architectures.We show that in some cases, without proper code alignment, performance can degrade by 40% due to the impact of code alignment on the grouping and pipeline delays.We present a new binary-level and profile-based code alignment algorithm for architectures that make use of group dispatching. We show a steady performance gain of about 2--3% for fully optimized code running on IBM Power 6 while completely eliminating performance instability which can sometimes result in up to 40% variation in performance in the absence of the proposed code alignment algorithm.As the algorithm is based on gathered profiling and applies at binary-level, it can, therefore, be used as part of existing dynamic compilers and enabled on top of the operating system at runtime.

Constraints on the memory size of embedded systems require reducing the image size of executing programs. Common techniques include code compression and reduced instruction sets. We propose a novel technique that eliminates large portions of the executable image without compromising execution time (due to decompression) or code generation (due to reduced instruction sets). Frozen code and data portions are identified using profiling techniques and removed from the loadable image. They are replaced with branches to code stubs that load them in the unlikely case that they are accessed. The executable is sustained in a runnable mode.Analysis of the frozen portions reveals that most are error and uncommon input handlers. Only a minority of the code (less than 1%) that was identified as frozen during a training run, is also accessed with production datasets.The technique was applied on three benchmark suites (SPEC CINT2000, SPEC CFP2000, and MediaBench) and results in image size reductions of up to 73%, 92%, and 85% per suite, The average reductions are 59%, 79%, and 78% per suite.

Summary form only given. We consider the problem of compiling programs, written in a general high-level programming language, into hardware circuits executed by an FPGA (field programmable gate array) unit. In particular, we consider the problem of synthesizing nested loops that frequently access array elements stored in an external memory (outside the FPGA). We propose an aggressive compilation scheme, based on loop unrolling and code flattening techniques, where array references from/to the external memory are overlapped with uninterrupted hardware evaluation of the synthesized loop's circuit. We implement a restricted programming language called DOL based on the proposed compilation scheme and our experimental results provide preliminary evidence that aggressive compilation can be used to compile large code segments into circuits, including overlapping of hardware operations and memory references.

Memory access has proven to be one of the bottlenecks in modern architectures. Improving memory locality and eliminating the amount of memory access can help release this bottleneck. We present a method for link-time profile-based optimization by reordering the global data of the program and modifying its code accordingly. The proposed optimization reorders the entire global data of the program, according to a representative execution rate of each instruction (or basic block) in the code. The data reordering is done in a way that enables the replacement of frequently-executed Load instructions, which reference the global data, with fast Add Immediate instructions. In addition, it tries to improve the global data locality and to reduce the total size of the global data area. The optimization was implemented into FDPR (Feedback Directed Program Restructuring), a post-link optimizer, which is part of the IBM AIX operating system for the IBM pSeries servers. Our results on SPECint2000 show a significant improvement of up to 11% (average 3%) in execution time, along with up to 97.9% (average 83%) reduction in memory references to the global variables via the global data access mechanism of the program.

We define a new type of recurrence equations called "Simple Indexed Recurrences" (SIR). In this type of equations, ordinary recurrences are generalized to X[g(i)]=op/sub i/(X[f(i)], X[g(i)]), where f, g : {1...n}/spl rarr/{1...m}, op/sub i/(x, y) is a binary associative operator and g is distinct, i.e., /spl forall/i/spl ne/j g(i)/spl ne/g(j). This enables us to model certain sequential loops as a sequence of SIR equations. A parallel algorithm that solves a set of SIR equations will, in fact, parallelize sequential loops of the above type. Such a parallel SIR algorithm must be efficient enough to compete with the O(n) work complexity of the original loop. We show why efficient parallel algorithms for the related problems of list ranking and tree contraction, which require O(n) work, cannot be applied to solving SIR. We instead use repeated iterations of pointer jumping to compute the final values of X[] in n/p/spl middot/log p steps and n/spl middot/log p work, with p processors. A sequence of experiments was performed to test the effect of synchronous and asynchronous executions on the actual performance of the algorithm. These experiments show that pointer jumping requires O(n)) work in most practical cases of SIR loops. An efficient solution is given for the special case where we know how to compute the inverse of op/sub i/, and finally, useful applications of SIR to the well-known Livermore loops benchmark are presented.

We consider the problem of obtaining efficient (O(n) work) solutions for parallel evaluation of algebraic circuits.While obtaining efficient sequential evaluation of algebraic circuits is straightforward, this is not the case for parallel evaluation.The general result of Miller, Ramachandran and Kaltofen (1988) uses n3 processors for evaluating general circuits with arbitrary f, * operations.The parallelism in this result ia obtained through matrix multiplications, which is also the reason why so many processors are required.We thus chose to study a variant of algebraic circuits called LAC (Linear Algebraic Circuits), for which there is a different matrix form that eventually yields an efficient parallel algorithm.A lower bound of w(n .p) work (where p is the number of processors) for any algorithm which uses only sparse matrix multiplication steps to evaluate LACs in less than : sparse matrix multiplications steps is given.It follows that using matrix multiplications alone is not sufficient for obtaining a "fully" efficient (O(n) work) parallel solution, even for evaluating LACs.We present instead a CREW PRAM algorithm which, during execution, propagates computed values into future matrix products, and uses a special scheduling of the matrix multiplications to reduce constant factors of the execution time.This algorithm takes at most +-log'p steps; constant factors are important here due 18~3 to the need to compete with the sequential execution of the LAC.A "product measure" for LACs has been defined and a version of the algorithm that can improve the execution time according to this measure has been developed.Experiments for testing the effect of using this algorithm for "bad" cases of this measure has been performed.Finally, we show how such an algorithm can be used for manual parallelizing of sequential loops, which in many practical cases (of generalized recurrences) are actually LACs.Permission to make digital or hard copies of'all or part ot'this work for personal or classroom use is granted without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the tirst page.To copy otherwise, to republish, to post on semers or to redistribute to lists.rquires prior specific permission and/or a fee.