Search

Data-dependence profiling is a dynamic program-analysis technique to discover potential parallelism in sequential programs. Unlike purely static analysis, which may overestimate the number of dependences because it does not know many pointers values and array indices at compile time, profiling has the advantage of recording data dependences that actually occur at runtime. But it has the disadvantage of significantly slowing down program execution, often by a factor of 100. In our earlier work, we lowered the overhead of data-dependence profiling by excluding polyhedral loops, which can be handled statically using certain compilers. However, neither does every program contain polyhedral loops, nor are statically identifiable dependences restricted to such loops. In this paper, we introduce an orthogonal approach, focusing on data dependences between accesses to scalar variables - across the entire program, inside and outside loops. We first analyze the program statically and identify memory-access instructions that create data dependences that would appear in any execution of these instructions. Then, we exclude these instructions from instrumentation, allowing the profiler to skip them at runtime and avoid the associated overhead. We evaluate our approach with 49 benchmarks from three benchmark suites. We improved the profiling time of all programs by at least 38%, with a median reduction of 61% across all the benchmarks.

Recent studies have shown promising performance benefits when multiple stages of a pipelined stencil application are mapped to different parts of a GPU to run concurrently. An important factor for the computing efficiency of such pipelines is the granularity of a task. In previous programming frameworks that support true pipelined computations on GPU, the choice has to be made by the programmers during the application development time. Due to many difficulties, programmers' decisions are often far from optimal, causing inferior performance and performance portability. This paper presents GOPipe, a granularity-oblivious programming framework for efficient pipelined stencil executions on GPU. With GOPipe, programmers no longer need to specify the appropriate task granularity. GOPipe automatically finds it, and dynamically schedules tasks of that granularity for efficiency while observing all inter-task and inter-stage data dependencies. In our experiments on six real-life applications and various scenarios, GOPipe outperforms the state-of-the-art system by 1.39X on average with a much better programming productivity.

In this paper, a warp scheduler is proposed for the improvement of multi-core stream processor based GP-GPU performance. The proposed warp schedulers are divided into odd and even warps, which are issued separately by applying the dual-warp issue. Furthermore, it can simultaneously process up to four instructions because each warp can issue two instructions through superscalar issue. The superscalar issue has a limitation in that it cannot simultaneously process two instructions having data dependence. To solve this limitation, the warp scheduler determines the instruction issuance by testing the issuing condition of the multi-core processor and the read/write register dependence. For scheduling algorithm, the round-robin algorithm was used. To measure the performance of multi-core stream processors, the Gaussian filter mask processing result of the GP-GPU using the proposed warp scheduler was compared with that of the multi-core CPU on various embedded platforms. The experiment results showed that the processing speed of the GP-GPU using the warp scheduler was 6-7 times faster. The GP-GPU also performed better on an image processing application.

Data-dependence profiling is a program-analysis technique to discover potential parallelism in sequential programs. Contrary to purely static dependence analysis, profiling has the advantage that it captures only those dependences that actually occur during execution. Lacking critical runtime information such as the value of pointers and array indices, purely static analysis may overestimate the amount of dependences. On the downside, dependence profiling significantly slows down the program, not seldom prolonging execution by a factor of 100. In this paper, we propose a hybrid approach that substantially reduces this overhead. First, we statically identify persistent data dependences that will appear in any execution. We then exclude the affected source-code locations from instrumentation, allowing the profiler to skip them at runtime and avoiding the associated overhead. At the end, we merge static and dynamic dependences. We evaluated our approach with 38 benchmarks from two benchmark suites and obtained a median reduction of the profiling time by 62% across all the benchmarks.

Nowadays, multicore is widely used in servers which are shared by many users. Besides the tasks submitted by different users are usually data-independent. However, the existing scheduling algorithms for multicore always take data dependence into consideration which limit the performance of multicore. As a consequence, we propose a heuristic algorithm called HITSM for independent task scheduling in multicore. In the proposed HITSM, we take makespan and load balancing into consideration. The experiment results demonstrate that, compared to First Come First service (FCFS) and Min-min algorithm, the proposed HITSM respectively reduces the makespan by 9.4% and 6.8%, and separately increases the performance on load balancing by 27.6 and 25.2 times on the heterogeneous cores.

Although intra-layer parallelism is commonly used to expedite CNN execution, it is difficult to achieve inter-layer parallelism because of data dependence between layers. In the paper, we propose a two-phase prediction and correction mechanism to break the data dependence between CNN layers so as to enable inter-layer parallelism. Our technique achieves one more order of magnitude (from the order of 10 to the order of 100) CNN acceleration compared to other three state-of-the-art GPU based CNN acceleration mechanisms.

Identifying data dependence among loop iterations is a fundamental step in the parallelisation process. Generally, code instrumentation provides for such information at the expense of high runtime performance penalty. This paper proposes an efficient method that trades slight accuracy reduction with significant performance gain to generate an approximate dependence graph. The proposed method relies on replicating the loop under test, providing for instrumented and not instrumented code versions, and adaptively switching between them, as well as deciding on the analysis detail, depending on the stability of measured dependence distances. Moreover, the method utilises random sampling, decreasing the chances of missing dependent irregular memory accesses. An initial performance investigation of the method is conducted using the Pin binary instrumentation tools, results on selected PolyBench kernels shows up to 8.5× improvement in instrumentation time, with no missed dependencies in 14 kernels, and 45% missed dependencies in one kernel.

An efficient recovery method for thread-level speculation (TLS) is proposed. The method tracks the inter-thread data dependence as a method for identifying those threads that are obviously unaffected by a data dependence violation. The method is simple to implement. Still, the simulation results using benchmark applications show that the method can significantly reduce the number of unnecessary thread restarts and consequently improve the performance of TLS. Specifically, when compared with the baseline TLS, TLS with the proposed method is 2.3 times faster for IS, 1.7 times faster for equake, and 3.5 times faster for mcf with the use of 64 cores. With the method, the performance of TLS increases steadily up to 64 cores for IS, equake, and mcf, while the speedup of the baseline TLS starts to saturate at 8 or 16 cores.

To reduce the processor energy consumption under low workload and low clock frequency executions, a possible solution is to use ALU cascading while keeping the supply voltage unchanged. This cascading scheme uses a single cycle to execute multiple ALU instructions which have a data dependence relationship between them and thus saves clock cycles for the whole execution. Since the processor energy consumption is the product result of both power and execution time, ALU cascading is expected to help energy optimization for microprocessors operating under low frequency status. To implement ALU cascading in a current superscalar processor, a specific instruction scheduler is required to wakeup a pair of cascadable instructions simultaneously despite there being a data dependence relationship between them. Furthermore, ALU cascading is only applied under low clock frequency execution mode so that the instruction scheduler must support standard scheduling for the normal clock frequency execution. In this paper, we propose an instruction scheduling method that enables the additional wakeup features for the utilization of ALU cascading without large hardware extensions. With this scheduler, the average IPC improvement becomes 3.7% in SPECint2000 and 6.4% in Mediabench, as compared to the baseline execution. The delay of additional hardware required for the ALU cascading purpose is also evaluated to study the complexity of ALU cascading.

Extracting data dependences from programs serves as the foundation of many program analysis and transformation methods, including automatic parallelization, runtime scheduling, and performance tuning. To obtain data dependences, more and more related tools are adopting profiling approaches because they can track dynamically allocated memory, pointers, and array indices. However, dependence profiling suffers from high runtime and space overhead. To lower the overhead, earlier dependence profiling techniques exploit features of the specific program analyses they are designed for. As a result, every program analysis tool in need of data-dependence information requires its own customized profiler. In this paper, we present an efficient and at the same time generic data-dependence profiler that can be used as a uniform basis for different dependence-based program analyses. Its lock-free parallel design reduces the runtime overhead to around 86× on average. Moreover, signature-based memory management adjusts space requirements to practical needs. Finally, to support analyses and tuning approaches for parallel programs such as communication pattern detection, our profiler produces detailed dependence records not only for sequential but also for multi-threaded code.

An OpenMP approach was proposed to parallelize the sequential molecular dynamics (MD) code on shared memory machines. When a code is converted from the sequential form to the parallel form, data dependence is a main problem. A traditional sequential molecular dynamics code is anatomized to find the data dependence segments in it, and the two different methods, i. e., recover method and backward mapping method were used to eliminate those data dependencies in order to realize the parallelization of this sequential MD code. The performance of the parallelized MD code was analyzed by using some performance analysis tools. The results of the test show that the computing size of this code increases sharply form 1 million atoms before parallelization to 20 million atoms after parallelization, and the wall clock during computing is reduced largely. Some hot-spots in this code are found and optimized by improved algorithm. The efficiency of parallel computing is 30% higher than that of before, and the calculation time is saved and larger scale calculation problems are solved.

In this paper, the results of parallelizing chaotic block encryption algorithm based on a piecewise nonlinear map are presented. A data dependence analysis of loops was applied in order to parallelize this algorithm. An OpenMP standard is used for presenting the parallelism of the algorithm. The efficiency measurement for a parallel program is shown.

In this paper the results of parallelizing a block cipher based on chaotic neural networks are presented. A data dependence analysis of loops is applied in order to parallelize the algorithm. The parallelism of the algorithm is demonstrated in accordance with the OpenMP standard. As a result of this study, it is stated that the most time-consuming loops of the algorithm are suitable for parallelization. The efficiency measurements of a parallel algorithm working in standard modes of operation are shown.

Nowadays, more and more program analysis tools adopt profiling approaches in order to obtain data dependences because of their ability of tracking dynamically allocated memory, pointers, and array indices. However, dependence profiling suffers from high time overhead. To lower the overhead, former dependence profiling techniques either exploit features of the specific program analyses they are designed for, or let the profiling process run in parallel. Although they successfully lowered the time overhead of dependence profiling by a certain amount, none of them have tried to solve the fundamental problem that causes the high time overhead: the memory operations that are repeatedly executed in loops. In most of the time, these memory operations lead to exactly the same data dependences. However, a profiling method has to profile all these memory operations over and over again in order to not miss a single dependence that may occur just once. In this paper, we present a method that allow a dependence profiling technique to skip memory operations that are repeatedly executed in loops without missing any single data dependence. Our method works with all types of loops and does not require any prepossessing like source annotation of the input code. Experiment results show that our method can lower the time overhead of data-dependence profiling by up to 52 %.

State-of-the-art processors achieve high performance by executing multiple instructions in parallel. However, the parallel execution of instructions is ultimately limited by true data dependencies between individual instructions. The objective of this paper is to present and quantify the benefits of static data dependence collapsing, a non-speculative technique for reducing the impact of true data dependencies on program execution time. Data dependence collapsing involves combining a pair of instructions when the second instruction is directly dependent on the first. The two instructions are then treated as a single entity and are executed together in a single functional unit that is optimised to handle functions with three input operands instead of the traditional two inputs. Dependence collapsing can be accomplished either dynamically at run time or statically at compile time. Since dynamic dependence collapsing has been studied extensively elsewhere, this paper concentrates on static dependence collapsing. To quantify the benefits of static dependence collapsing, we added a new dependence collapsing option to the Hatfield Superscalar Scheduler (HSS), a state-of-the-art instruction scheduler that targets the Hatfield Superscalar Architecture (HSA). We demonstrate that the addition of dependence collapsing to HSS delivers a significant performance increase of up to 15%. Furthermore, since HSA already executes over four instructions in each processor cycle without dependence collapsing, dependence collapsing enables 0.4 additional instructions to be executed in each processor cycle.

Data dependence analysis is the most essential process while parallelizing a sequential program. Most current data dependence tests cannot handle array subscripts that are non-linear expressions. In this paper, we present a new parallelization algorithm, called non-linear array subscripts (NLA) test, to deal with non-linear or complex array subscripts. In this scheme, the iterations subject to loop-carried dependence are scheduled into different wavefronts, while the iterations with no loop-carried dependence are assigned into the same wavefront. Based on the wavefront information, the original loop is then transformed into parallel code. Our experimental results on shared-memory parallel machines HP SPP2000 and ALR Quad6 prove the high effectiveness of the NLA test.

An approach is developed for parallel detection and evaluation of arithmetic operations at inter instruction level. Parallelism exploitation is targeted at inter instruction level. Data dependence analysis is carried out since dependence will limit the number of parallel operations. Arithmetic expressions with +, -, *, / as permissible operators, variables and constants as operands are considered in the implementation. Transputers are used in the implementation.

The Java processor is suitable for Internet appliances or embedded controllers due to its speed and low memory requirement. However, its performance is severely limited by true data dependence. In this work, we present a smart and dynamic stack operations folding – POC model‐based folding. The stack instructions are classified into P,O, and C three types. The folding algorithm can automatically determine the folding relations among all the instructions based on the type and folding attributes of each instruction. The proposed algorithm has no requirement to match different patterns. A typical folding mechanism design based on this model is then introduced. Also, the performance of various folding methods based on the POC model is evaluated. Simulation data indicate that the 4‐foldable method eliminates 84% of all stack operations. Furthermore, the 2‐, 3‐, and 4‐foldable methods accelerate the overall program by 1.22, 1.32 and 1.34, respectively, as compared to a Java processor without folding.

Writing programs for a distributed-memory system (DMS) is a difficult job. In this paper, a method for parallelising sequential programs for DMS is presented. The input programs are C programs and the output parallel versions are programs containing routines for the Parallel Virtual Machine (PVM). PVM allows a group of computers in a network to be specified as a DMS and provides the routines for task activation and communication. The main task in this parallelisation of program is to process the loops in the source program and determine if there exists any data dependences or not. If the loop iterations are independent, the body will be transformed to tasks that will run independently for PVM.

JAPS is an automatic parallelizing system based on JAVA running on NOW. It implements the automatic process from dependence analysis to parallel execution. The current version of JAPS can exploit functional parallelism and the detection of data parallelism will be incorporated in the new version, which is underway. The framework and key techniques of JAPS are presented. Specific topics discussed are task partitioning, summary information collection, data dependence analysis, pre-scheduling and dynamic scheduling, etc.

International audience; This paper describes a tool using one or more executions of a sequential program to detect parallel portions of the program. The tool, called Parwiz, uses dynamic binary instrumentation, targets various forms of parallelism, and suggests distinct parallelization actions, ranging from simple directive tagging to elaborate loop transformations. The first part of the paper details the link between the program's static structures (like routines and loops), the memory accesses performed by the program, and the dependencies that are used to highlight potential parallelism. This part also describes the instrumentation involved, and the general architecture of the system. The second part of the paper puts the framework into action. The first study focuses on loop parallelism, targeting OpenMP parallel- for directives, including privatization when necessary. The second study is an adaptation of a well-known vectorization technique based on a slightly richer dependence description, where the tool suggests an elaborate loop transformation. The third study views loops as a graph of (hopefully lightly) dependent iterations. The third part of the paper explains how the overall cost of data- dependence profiling can be reduced. This cost has two major causes: first, instrumenting memory accesses slows down the program, and second, turning memory accesses into dependence graphs consumes processing time. Parwiz uses static analysis of the original (binary) program to provide data at a coarser level, moving from individual accesses to complete loops whenever possible, thereby reducing the impact of both sources of inefficiency.

Efficacy of automatic parallelization techniques that rely on source code analysis alone is often limited due to lack of information about runtime characteristics of target applications. In order to exploit runtime application behavior for its parallelization, we need: (1) tools/techniques for dynamic instrumentation and profiling; and (2) a methodology to identify areas of application that are amenable for explicit and speculative parallelization. In this paper, we present an infrastructure that provides above-mentioned facilities to analyze ELF binaries in an emulated runtime environment. The infrastructure, which is implemented as an extension to quick emulator (QEMU), includes a profiling mechanism to capture runtime behavior of an application and an inter-function dependence metric for quantitatively measure the potential for function level parallelism. The dependence metric is an extension of data dependence densities effort [7]. We ran sequential versions of NAS benchmarks through this infrastructure to determine their function level parallelization potential. Resulting data can be consumed for manual parallelization efforts as well as for automated parallelization through compiler feedback during build process.

Based on three OpenMP program models, the technology of parallel region reconstruction is mainly discussed to implement the improved loop level OpenMP program. Parallel region reconstruction is to expand and merge parallel regions. When reconstructing parallel regions, there are two things should be noted, that is to keep data attribute and data dependence before and after optimization. Experimental results of PPOPP show that after parallel region reconstruction, the improvement of lu1k is maximally up to 28.1%, and the improvement of erle64 is the lowest about 1.87%. The reason of lu1k's highest improvement is that a parallel region is expanded outside a loop of 1024 iterations, which reduce 1023 times of the parallel region creation. The experimental results indicate the technology of parallel region reconstruction reduces the creation of parallel region, and improves the performance of the OpenMP program.

Retrofitting existing software for the increasingly dominant multicore microprocessors has a strong appeal from the economic point of view. One of the key issues in such an effort is to fully understand the data dependences in the existing software. Unfortunately, current compilers have quite limited ability to analyze data dependences. Therefore, execution-driven data dependence profiling has gained significant interest because it can resolve memory access ambiguity exactly during program execution, which allows data dependences to be analyzed exactly. Although such dependence profiling is valid for specific inputs only, the insight it provides can be highly valuable to software engineers in their parallelization effort. On the other hand, dependence profiling itself can take tremendous memory and machine time. In this paper, we propose a novel dependence profiling method which, with the support of several new compiler and runtime techniques, partitions the profiling task into many independent slices, each requiring significantly less memory. Different slices can be profiled in parallel, producing subgraphs which are eventually combined automatically into the complete data dependence graph by the compiler. The slices can be extracted with different degrees of granularity. Experiments show that, for several well-known benchmark programs, our parallel scheme shortens the profiling time by a few orders of magnitude.

Execution-driven data dependence profiling has gained significant interest as a tool to compensate the weakness of static data dependence analysis. Although such dependence profiling is valid for specific inputs only, its result can be used in many ways for program parallelization. Unfortunately, traditional hash-based dependence profiling can take tremendous memory and machine time, which severely limits its practical use. In this paper, we propose new compiler-based techniques to perform fast loop-level data dependence profiling. Firstly, using type consistency and alias information, our compiler embeds memory tags into the data structures in the original program such that memory addresses can be efficiently compared for dependence testing. This approach avoids the bytewise hashing overhead in conventional profiling methods. Secondly, we prove that a partial dependence graph obtained from profiling is sufficient for loop-level reordering transformations and parallelization. Such partial dependence graph can be obtained very fast, without having to exhaustively enumerate all dependence edges. Thirdly, our compiler partitions the profiling task into independent slices. Such slices can be profiled in parallel, producing subgraphs which are eventually combined automatically into the complete data dependence graph by the compiler. Experiments show that these techniques significantly reduce the memory use and shorten the profiling time (by an order of magnitude for several SPEC2006 benchmarks). Benchmarks too big to profile at all loop levels by previous methods can now be profiled fully within several hours.

Data speculation technique has been heavily exploited in various scenarios of architecture design. It bridges the time or space gap between data producer and data consumer, which gives opportunities to processors to gain significant speedups. However, large instruction windows, deep pipeline and increasing latency of on-chip communication make data misspeculation very expensive in modern processors.This paper proposes a Distributed Replay Protocol(DRP) that addresses data misspeculation in a distributed uniprocessor, named TFlex. The partition feature of distributed uniprocessors aggravates the penalty of data misspeculation. After detecting misspeculation, DRP avoids squashing pipeline; on the contrary, it retains all instructions in the window and selectively replays the instructions that depend on the misspeculative data. As one possible use of DRP, We apply it to recovery from data dependence speculation. We also summarize the challenges of implementing selective replay mechanism on distributed uniprocessors, and then come up with two variations of DRP to effectively solve these challenges. The evaluation results show that without data speculation, DRP achieves 99% of the performance of perfect memory disambiguation. It speeds up diverse applications over baseline TFlex(with a state-of-art data dependence predictor) by a geometric mean of 24%.

International audience; Register allocation recently regained much interest due to new decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination. A common assumption of existing copy elimination approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs.

In this paper, we present the results of parallelizing the Lian et al. discrete chaotic block encryption algorithm. The data dependence analysis of loops was applied in order to parallelize this algorithm. The OpenMP standard is chosen for presenting the parallelism of the algorithm. We show that the algorithm introduced by Lian et al. can be divided into parallelizable and unparallelizable parts. As a result of our study, it was stated that the most timeconsuming loops of the algorithm are suitable for parallelization. The efficiency measurement for a parallel program is presented.

Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations. In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.

SPEFY (Scotia Programming Environment and Facility) is a new software development environment designed to simplify and accelerate the development of large-scale programs in a manner that makes the most efficient use of the supercomputers on which they run. The centerpiece of SPEFY is the Parallelism Analysis and Optimization tool, which is an interactive facility for analyzing code, detecting data dependence, and optimizing the program by parallelism-enhancing transformations. A significant feature of the analysis is that it is performed both across and within procedures, and greatly increase the precision of data flow and dependence information. The objective of this paper is to describe the Parallelism Analysis and Optimization tool of SPEFY. It discusses data dependence, interprocedural analysis by determining the relevant effects of procedure calls, data dependence analysis incorporating interprocedural information, and program restructuring optimization techniques.

Speculative parallelization is a runtime technique that optimistically executes sequential code in parallel, checking that no dependence violations appear. In this paper, we address the problem of minimizing the number of threads that should be restarted when a data dependence violation is found. We present a new mechanism that keeps track of inter-thread dependencies in order to selectively stop and restart offending threads, and all threads that have consumed data from them. Results show a reduction of 38.5% to 81.8% in the number of restarted threads for real application loops and up to a 10% speedup, depending on the amount of local computation.

We propose a method for optimizing shared-memory MIMD programs containing parallel loops with loop-carried data dependences of various distances. The optimization consists in reducing the number of synchronizations necessary to satisfy the dependences by identifying dependences which are redundant and neet not be synchronized. The idea of dependence chaining is presented. Next, conditions for dependence arc elimination are formulated. A proposal for application of nested forward dependences in dependence chaining so as to achieve extra arc elimination is put forward. Theoretical considerations are accompanied by the description of the algorithm which implements the proposed method and an example of its application.

Curare, the program restructurer described in this paper automatically transforms a sequential Lisp program into an equivalent concurrent program that runs on a multiprocessor. Data dependences constrain the program's concurrent execution because, in general, two conflicting statements cannot execute in a different order without affecting the program's result. Not all dependences are essential to produce the program's result.Curare attempts to transform the program so it computes its result with fewer conflicts. An optimized program will execute with less synchronization and more concurrency. Curare then examines loops in a program to find those that are unconstrained or lightly constrained by dependences. By necessity,Curare treats recursive functions as loops and does not limit itself to explicit program loops. Recursive functions offer several advantages over explicit loops since they provide a convenient framework for inserting locks and handling the dynamic behavior of symbolic programs. Loops that are suitable for concurrent execution are changed to execute on a set of concurrent server processes. These servers execute single loop iterations and therefore need to be extremely inexpensive to invoke. Restructured programs execute significantly faster than the original sequential programs. This improvement is large enough to attract programmers to a multiprocessor, particularly since it requires little effort on their part.

In this paper, we discuss an OpenMP implementation of an evolutionary LSOR method, the MBLSOR method, for solution of system of linear equations related to reservoir simulation on SMPs. MBLSOR method not only can improve the data locality by spatial computational domain decomposition technique, but it also can parallel the sub blocks with no data dependence. We compare the performance of different parallel LSOR methods in terms of efficiency and data locality. Numerical results on SMPs indicate that MBLSOR algorithm is more efficient.

Redundant computation is an execution of a program statement(s) that does not contribute to the program output. The same statement on one execution may exhibit redundant computation whereas on a different execution, it contributes to the program output. A redundant (dead) statement always exhibits redundant computation, i.e., its execution is always redundant. However, a statement that exhibits redundant computation is not necessarily a redundant statement. Redundant computation represents a partial redundancy of a statement. A high degree of redundant computation in a program may indicate a performance deficiency. Therefore, elimination (or reduction) of redundant computation may improve program's performance. In this paper we present an approach of automated detection of redundant computation in programs and show its application in performance analysis. We developed a tool that automatically detects redundant computations in C programs and identifies potential performance deficiencies related to redundant computation. We have performed an experimental study that showed that redundant computation is a commonly occurring phenomenon in programs, and it is frequently a source of performance deficiency.

The differences found between the superscalar performance in x86 and non-x86 processors and the peculiar characteristics of the x86 ISA recommend to carry out a thorough analysis of the available parallelism at the machine language layer. However, computer architecture evaluation requires new tools that complement the customary simulations and, in this sense, the traditional graph theory can help to create a new frame for fine-grain parallelism analysis. We construct the matrix representation associated to the data dependence graph of execution traces. In this paper, we explain how this matrix characterizes the corresponding code in a mathematical manner, fulfills a number of properties and restrictions, and provides information about the ability of the code to be processed concurrently. Besides, we also show how different data dependence sources can be composed, thus providing a mechanism to explore their final influence on the parallelism degree. These techniques are applied to an example from which some conclusions are derived

Comparison of six data dependence analysis algorithms is presented. The algorithms are purposed for a parallel compiler that is being developed for a configurable multi-DSP system PARNEU. The algorithms are implemented in SUIF compiler framework and benchmarked with Perfect Club, Audio Signal Processing, and Media Bench test problems. Proprietary PARNEU programs that have been manually parallelised are also included. Performance in terms of accuracy and execution time of the data dependence algorithms has been measured and compared. The results show that the Omega test is the most accurate but also takes most execution time for benchmarks with for-loop parallelism.

Partitioning of loops is a very important optimization issue and requires the efficient and exact data dependence analysis. Although several methods exist in order to parallelize loops with non-uniform dependences, most of them perform poorly due to irregular and complex dependence constraints. This paper proposes Improved Region Partitioning Method for minimizing the size of the sequential region and maximizing parallelism. Our approach is based on the Convex Hull theory that has adequate information to handle non-uniform dependences. By parallelizing anti dependence region using variable renaming, we will divide the iteration space into two parallel regions and one or less sequential region. Comparison with other schemes shows more parallelism than the existing techniques.

In this paper, TOPAS-a new parallel programming environment for distributed systems-is presented. TOPAS automatically analyzes data dependence among tasks and synchronizes data, which reduces the time needed for parallel program developments. TOPAS also provides supports for scheduling, dynamic load balancing and fault tolerance. Experiments show simplicity and efficiency of parallel programming in TOPAS environment with fault-tolerant integration, which provides graceful performance degradation and quick reconfiguration time for application recovery.

Under the existing framework for dependence analysis, every time a program is modified, exhaustive reanalysis has to be carried out to restructure the program. Often the changes in the program may be limited to a small portion. This may not affect a major part of the value based dependences. Therefore, a framework for incremental dependence analysis which would only recompute dependences pertaining to modified code, is desirable. Incremental analyzers modify only the affected parts of the solution, and hence can quickly reflect the affect of the changes on the solutions. In this work we present a framework for incremental dependence analysis for value based dependences.

Basic concepts in array layout are summarized, and unhonored preferences and residual data motion are discussed. A technique for minimizing such motion is presented. For each array the source program is divided into regions, each associated with a single home. This enables efficient handling of residual data motion. The partitioning into regions is based on control flow and data dependence. Preliminary results obtained with this technique show an order-of-magnitude improvement for certain classes of programs. >

We present an experimental tool for identifying coarse-grained parallelism in Pascal programs. The tool produces a net description of a sequential program where statements that could potentially be executed in parallel have been identified. Conventional control and data dependence analysis is used to map the statements in a sequential program into execution steps in a dependency net. We introduce the concept of dependency strength and show how it is used to guide the grouping of statements. A simulation based on laws adapted from electrostatics and mechanics is performed where the statements are allowed to attract and repel one another to affect their position within the dependency net. Statements that must be executed sequentially are coalesced together. Several translation parameters can be modified and their effects on the resulting net descriptions can be studied.

Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing non-numeric programs, which tend to use irregular data structures with pointers and have complex flows of control. Proper thread formation is crucial to obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general, and supports a wide variety of threads, such as speculative threads, non-speculative threads, loop-centric threads, and out-of-order thread spawning. The compiler uses profiling, intra-procedural pointer analysis, data dependence information and control dependence information. The compiler is implemented on the SUIF-MachSUIF platform. A simulation-based evaluation of the generated threads shows that an average speedup of 3 can be obtained with 6 processing elements for non-numeric programs. This speedup reduces to 2 if we use only loop-based threads.

In this article, we give a new formulation of acyclic scheduling problem under registers and resources constraints in multiple instructions issuing processors (VLIW and superscalar) Given a direct acyclic data dependence graph G = (V, E), the complexity of our integer linear programming model is bounded by O(|V|2) variables and O(|E| + |V|2) constraints according to a target architecture description. This complexity is better than the complexity of the existing techniques which includes a worst total schedule time factor.

Slicing is a well-known program analysis technique for analyzing sequential programs and found useful in debugging, testing and reverse engineering. This paper extends the notion of slicing to concurrent programs with shared memory, interleaving semantics and mutual exclusion. Interference among concurrent threads or processes complicates the computation of slices of concurrent programs. Further, unlike slicing of sequential programs, a slicing algorithm for concurrent programs needs to differentiate between loop-independent data dependence and certain loop-carried data dependences. We show why previous methods do not give precise solutions in the presence of nested threads and loops and describe our solution that correctly and efficiently computes precise slices. Though the complexity of this algorithm is exponential on the number of threads, a number of optimizations are suggested. Using these optimizations, we are able to get near linear behavior for many practical concurrent programs.

Increasing the instruction level parallelism (ILP) is one of the key issues to boost the performance of future generation processors. Current processor organizations include different mechanisms to overcome the limitations imposed by name and control dependencies but no mechanisms targeting to data dependencies. Thus, these dependencies will become one of the main bottlenecks in the future. Data value speculation is gaining popularity as a mechanism to overcome the limitations imposed by data dependencies by predicting the values that flow through them. In this work, we present a study of the potential of data value speculation to boost the limits of instruction level parallelism using both perfect and realistic predictors. Speedups obtained by data value speculation are very huge for an infinite window and still significant for a limited window. Different prediction schemes oriented to single thread and multiple threads (from a single program) architectures have been studied. The latter shows a significant improvement respect to the former for FP benchmarks although the difference is much smaller for integer programs.

Introduces an instruction reissue mechanism in order to enhance dynamic data dependence speculation using data address prediction. Since instructions which are not data-dependent upon speculatively executed instructions are not squashed, the effect of data dependence speculation is enhanced. We extend the register update unit to reissue misspeculated instructions. The overhead caused by the extension is small, and thus it does not have any impact on processor cycle time. From the experimental evaluation, we have found that instruction reissue with dynamic data dependence speculation improves the processor performance even for those application programs whose performance is degraded when instruction squashing is used.