The most attractive feature of field-programmable gate arrays (FPGAs) is their configuration flexibility. However, if the configuration is performed manually, this flexibility places a heavy burden on system designers to choose among a vast number of configuration parameters and program transformations. In this paper, we improve the state-of-the-art with two main innovations: First, we apply compiler-automated transformations to the data layout and program statements to create streaming accesses. Such accesses are turned into streaming interfaces when the kernels are implemented in hardware, allowing the kernels to run efficiently. Second, we use two-step mixed integer programming to first minimize the execution time and then to minimize energy dissipation. Configuration parameters are chosen automatically, including several important ones omitted by existing models. Experimental results demonstrate significant performance gains and energy savings using these techniques.

In this article, we propose a novel state-based fault-localization approach. Given an observed failure that is reproducible under the same program input, this new approach uses two main techniques to reduce the state exploration cost. Firstly, the execution trace to be analyzed for the observed failure is successively narrowed by making the set of trace points in each step a cut of the dynamic dependence graph. Such a cut divides the remaining trace into two parts and, based on the sparse symbolic exploration outcome, one part is removed from further exploration. This process continues until reaching where the fault is determined to be. Second, the cut in each step is chosen such that the union of the program states from the members of the cut is of the minimum size among all candidate cuts. The set of statement instances in the chosen cut is called a minimum debugging frontier set (MDFS). To evaluate our approach, we apply it to 16 real bugs from real world programs and compare our fault reports with those generated by state-of-the-art approaches. Results show that the MDFS approach obtains high quality fault reports for these test cases with considerably higher efficiency than previous approaches.

Run-time error detection and deterministic off-line error replay have received wide attention in recent years as a technique to enhance the programmer's ability to find software errors. To apply this technique to wireless sensor networks (WSN), one must be able to deal with the severe constraint on the memory, the communication bandwidth and the energy source on the sensor motes and the highly dynamic and unpredictable operating environment. All these make it difficult for the application programmer to manually insert operations required for error detection and replay. This paper makes three contributions towards making error detection and replay automatic for WSNs: (i) a domain-specific language, called SensorC, for specifying WSN global properties that must be satisfied when the system and its application software are deployed; (ii) a method to automatically decompose such global properties into a set of local operations to detect global property violations, with the goal to minimize the communication traffic for state information exchanges; and (iii) a new program analysis to identify program sub-traces that can be skipped for replay without losing the accuracy of diagnosis. The proposed techniques, which are implemented in a compiler, are shown by experiments to successfully catch real WSN software errors and to substantially reduce message exchanges for run time error detection.

In this paper, we present a novel state-based fault-localization approach called DelFal. Assuming the availability of the execution trace which leads to the reported program execution failure, this new approach successively selects sets of trace points to allow the performance of efficient automatic explorations on program execution states in order to help the developer locate programming faults responsible for the observed execution failure. With each of such sets of trace points, the program state at each trace point is symbolically altered, by negating a certain atomic predicate, to see whether the same failure occurs with symbolic execution continuing from the corresponding program point in the source code. The set of trace points is chosen such that the union of the program states is of the minimum size among all candidate sets. Such a set of trace points is called a minimum debugging frontier set (abr. MDFS). Depending on the result from the symbolic execution, the next MDFS is determined by moving forward or backward on the remaining program trace. This process of trace shortening goes on until the offending faulty code is found. The MDFS approach requires the execution failing location to be provided, but the specification of the desired program state is optional. With such specification, it may achieve a more accurate fault report. To evaluate our approach, we tried it on 15 real bugs from real world programs. Results show that our approach is effective in explaining failures within reasonable time.

Computational scientists and engineers commonly rely on established software libraries to achieve high performance and reliability in their numerical applications. Unfortunately, this approach does not work well if the desired functionality is absent in existing libraries or if the integration is difficult. In such scenarios, one is often forced to explore alternative algorithms and in-house implementations. Such exploration can be a challenging task for computational scientists and engineers without sufficient computer science background. To address this issue, we design and build an automated rapid prototyping tool for regular grid-based numerical applications. This new tool allows programmers to specify algorithms as composition of familiar computation patterns such as those easily found in open literature expressed as generalized elemental subroutines. The tool then automatically transforms such subroutines into code which adapts to the prescribed data structures and delivers performance expected from the underlying algorithms. We demonstrate the tool in use cases including a production-grade computational fluid dynamic application.

Among techniques for parallelizing sequential codes, privatization is a common and significant transformation performed by both compilers and runtime parallelizing systems. Without privatization, repetitive updates to the same data structures often introduce spurious data dependencies that hide the inherent parallelism. Unfortunately, it remains a significant challenge to compilers to automatically privatize dynamic and recursive data structures which appear frequently in real applications written in languages such as C/C++. This is because such languages lack a naming mechanism to define the address range of a pointer-based data structure, in contrast to arrays with explicitly declared bounds. In this paper we present a novel solution to this difficult problem by expanding general data structures such that memory accesses issued from different threads to contentious data structures are directed to different data fields. Based on compile-time type checking and a data dependence graph, this aggressive extension to the traditional scalar and array expansion isolates the address ranges among different threads, without struggling with privatization based on thread-private stacks, such that the targeted loop can be effectively parallelized. With this method fully implemented in GCC, experiments are conducted on a set of programs from well-known benchmark suites such as Mibench, MediaBench II and SPECint. Results show that the new approach can lead to a high speedup when executing the transformed code on multiple cores.

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.

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.

Due to resource constraints and unreliable communication, wireless sensor network (WSN) programming and debugging remain to be a challenging task. Runtime errors must be constantly monitored, often by checking for violations of certain invariants. Once an error is detected, diagnosis must be performed to identify the origin of the error. Deterministic replay is an error diagnosis method which has long been proposed for distributed systems. However, one of the significant hurdles for applying deterministic replay on WSN is posed by the small program memory on typical sensor nodes. This paper proposes a dependence-based multi-level method for memory-efficient tracing and replay. In the interest of portability across different hardware platforms, the method is implemented as a source-level tracing and replaying tool. To further reduce the code size after tracing instrumentation, a cost model is used for making the decision on which functions to in-line. A prototype for the tool targets C programs is developed on top of the Open64 compiler and is tested using several TinyOS applications running on TelosB motes. Preliminary experimental results show that the test programs, which do not fit the program memory after straightforward instrumentation, can be successfully accommodated in memory using the new method such that the injected errors can be found.

Computational aeroacoustics (CAA) has emerged as a tool to complement theoretical and experimental approaches for robust and accurate prediction of sound levels from aircraft airframes and engines. CAA, unlike computational fluid dynamics (CFD), involves the accurate prediction of small-amplitude acoustic fluctuations and their correct propagation to the far field. In that respect, CAA poses significant challenges for researchers because the computational scheme should have high accuracy, good spectral resolution, and low dispersion and diffusion errors. A high-order compact finite difference scheme, which is implicit in space, can be used for such simulations because it fulfills the requirements for CAA. Usually, this method is parallelized using a transposition scheme; however, that approach has a high communication overhead. In this paper, we discuss the use of a parallel tridiagonal linear system solver based on the truncated SPIKE algorithm for reducing the communication overhead in our large eddy simulations. We report experimental results collected on two parallel computing platforms.

This paper proposes a compiler-automated array compression scheme to reduce the memory bandwidth consumption of programs and thereby to improve their execution speed. Three encoding methods are developed for such compression. Formulas are derived to analyze the cost and benefit of such methods. To ease the programmer's effort for writing and maintaining complex source code that utilizes compression, we implement our technique in a compiler which automatically transforms the program into different versions corresponding to different encoding methods. The compiler also inserts operations to adaptively invoke the preferred version at run time, including the original version which performs no compression. Results show that our compiler-automated adaptive scheme improves the execution speed over the original version by an average of 9% for a set of benchmark programs which perform memory-intensive sparse matrix-vector multiplications (SpMV). These results take into account of overhead to make the adaptive decision. When tested separately, the individual encoding methods speed up program execution by as high as 41%, which compares favorably against previous compression methods manually applied to SpMV.

As multicore chips become the main building blocks for high performance computers, many numerical applications face a performance impediment due to the limited hardware capacity to move data between the CPU and the off-chip memory. This is especially true for large computing problems solved by iterative algorithms because of the large data set typically used. Loop tiling, also known as loop blocking, was shown previously to be an effective way to enhance data locality, and hence to reduce the memory bandwidth pressure, for a class of iterative algorithms executed on a single processor. Unfortunately, the tiled programs suffer from reduced parallelism because only the loop iterations within a single tile can be easily parallelized. In this work, we propose to use the asynchronous model to enable effective loop tiling such that both parallelism and locality can be attained simultaneously. Asynchronous algorithms were previously proposed to reduce the communication cost and synchronization overhead between processors. Our new discovery is that carefully controlled asynchrony and loop tiling can significantly improve the performance of parallel iterative algorithms on multicore processors due to simultaneously attained data locality and loop-level parallelism. We present supporting evidence from experiments with three well-known numerical kernels.

Ad-hoc wireless networks are being deployed in critical applications that require protection against sophisticated adversaries. However, wireless routing protocols, such as the widely-used AODV, are often designed with the assumption that nodes are benign. Cryptographic extensions such as Secure AODV (SAODV) protect against some attacks but are still vulnerable to easily-performed attacks using colluding adversaries, such as the wormhole attack. In this paper, we make two contributions to securing routing protocols. First, we present a protocol called Route Verification (RV) that can detect and isolate malicious nodes involved in routing-based attacks with very high likelihood. However, RV is expensive in terms of energy consumption due to its radio communications. To remedy the high energy cost of RV, we make our second contribution. We propose a multigrade monitoring (MGM) approach. The MGM approach employs a previously developed lightweight local monitoring technique to detect any necessary condition for an attack to succeed. However, local monitoring suffers from false positives due to collisions on the wireless channel. When a necessary condition is detected, the heavy-weight RV protocol is triggered. We show through simulation that MGM applied to AODV generally requires little extra energy compared to baseline AODV, under the common case where there is no attack present. It is also more resource-efficient and powerful than SAODV in detecting attacks. Our work, for the first time, lays out the framework of multigrade monitoring, which we believe fundamentally addresses the tension between security and resource consumption in ad-hoc wireless networks.

Publisher Note: This Guest Editorial by Li and Pande describes a number of related articles originally intended as a special issue but which were published in earlier issues as follows: Auerbach et al., "Low-Latency Time-Portable Real-Time Programming with Exotasks" , appears in TECS 8(2) Article 15 DOI 10.1145/1457255.1457262 Murray et al., "Code Transformation and Instruction Set Extension" , appears in TECS 8(4) Article 26 DOI 10.1145/1550987.1550989 Ahn and Paek, "Register Coalescing Techniques for Heterogeneous Register Architecture with Copy Sifting" , appears in TECS 8(2) Article 16 DOI 10.1145/1457255.1457263 Yan and Zhang, "Analyzing the Worst-Case Execution Time for Instruction Caches with Prefetching" , appears in TECS 8(1) Article 7 DOI 10.1145/1457246.1457253

As the shared memory bus becomes a major performance bottleneck for many numerical applications on multicore chips, understanding how the increased parallelism on chip strains the memory bandwidth and hence affects the efficiency of parallel codes becomes a critical issue. This paper introduces the notion of memory access intensity to facilitate quantitative analysis of program's memory behavior on multicores which employ state-of-the-art prefetching hardware. Three numerical solvers for large scale sparse linear systems are used to demonstrate the estimation of memory access intensity and its effect on program performance.

On today's microprocessors, there often exist several different types of registers, e.g. general purpose registers and floating point registers. A given program may use one type of registers much more frequently than other types. This creates an opportunity to employ the infrequently used registers as spill destinations for the more frequently used register types. In this paper, we present a code optimization method named idle register exploitation (IRE) to exploit such opportunities. We developed a model, called the IRE model, or IREM, to determine the static performance gains of IRE versus spilling to the stack. On a microprocessor with fast data paths between different types of registers, we find that IRE method speeds up the execution of the SPECint benchmark suite from 1.7% to 10%. In contrast, on microprocessors with less efficient data transfer paths, the performance gain is limited. In some cases, performance may even suffer degradation. This result argues strongly for the adoption of fast data paths between different types of registers for the purpose of reducing register spills, which is important in view of the increased significance of memory bottlenecks on future microprocessors.

In many reliable Wireless Sensor Network (WSN) applications, messages have different priorities depending on urgency or importance. For example, a message reporting the failure of all nodes in a region is more important than that for a single node. Moreover, traffic can be bursty in nature, such as when a correlated error is reported by multiple nodes running identical code. Current communication layers in WSNs lack efficient support for these two requirements. We present a priority-driven communication layer, called SeNDORComm, which schedules transmission of packets driven by application-specified priority, buffers and packs multiple messages in a packet, and honors the latency guarantee for a message. We show that SeNDORComm improves energy efficiency, message reliability, and network utilization and delays congestion in a network. We extensively evaluate SeNDORComm using analysis, simulation, and testbed experiments. We demonstrate the improvement in goodput of SeNDORComm over the default communication layer, GenericComm in TinyOS (134.78% for a network of 20 nodes).

Dynamic voltage and frequency scaling can save energy for real-time systems. Frequencies are generally assumed proportional to voltages. Previous studies consider the probabilistic distributions of tasks' execution time to assist dynamic voltage scaling in task scheduling. These studies use probability information for intratask voltage scheduling but do not sufficiently explore the opportunities for intertask scheduling to save more energy. This paper presents a new approach to combine intra- and intertask voltage scheduling for better energy savings in hard real-time systems with uncertain task execution time. Our approach takes three steps: 1) We calculate statistically the optimal voltage schedules for multiple concurrent tasks, using earliest deadline first scheduling for an ideal processor that can change the frequency continuously; 2) we then adapt the solution to a processor with a limited range of discrete frequencies, using a polynomial-time heuristic algorithm; and 3) finally, we improve our solution, considering the time and energy overheads of frequency switching for schedulability and energy reduction. Our simulation shows that the new approach can save more energy than existing solutions while meeting hard deadlines.

This paper presents an energy-aware method to schedule multiple real-time tasks in multiprocessor systems that support dynamic voltage scaling (DVS). The key difference from existing approaches is that we consider the probabilistic distributions of the tasks' execution time to partition the workload for better energy reduction. We analyze the problem of energy-aware scheduling for multiprocessor with probabilistic workload information and derive its mathematical formulation. As the problem is NP-hard, we present a polynomial-time heuristic method to transform the problem into a probability-based load balancing problem that is then solved with worst-fit decreasing bin-packing heuristic. Simulation results with synthetic, multimedia, and stereo-vision tasks show that our method saves significantly more energy than existing methods.

This paper considers the problem of extending the battery lifetime for a portable computer by offloading its computation to a server. Depending on the inputs, computation time for different instances of a program can vary significantly and they are often difficult to predict. Different from previous studies on computation offloading, our approach does not require estimating the computation time before the execution. We execute the program initially on the portable client with a timeout. If the computation is not completed after the timeout, it is offloaded to the server. We first set the timeout to be the minimum computation time that can benefit from offloading. This method is proved to be 2-competitive. We further consider collecting online statistics of the computation time and and the statistically optimal timeout. Finally, we provide guidelines to construct programs with computation offloading. Experiments show that our methods can save up to 17% more energy than existing approaches.

System-level power management has been studied extensively. For further energy reduction, the collaboration from user applications becomes critical. This paper presents a programming environment to ease the construction of energy-aware applications. We observe that energy-aware programs may identify different ways (called options) to achieve the desired functionalities and choose the most energy-efficient option at runtime. Our framework provides a programming interface to obtain the estimated energy consumption for choosing a particular option. The energy is estimated based on runtime energy characterization that records a set of runtime conditions correlated with the energy consumption of the options. We provide the procedure and general guidelines for using the environment to construct energy-aware programs. The prototype demonstrates that (a) energy-aware applications can be programmed easily with our interface, (b) accurate estimates are achieved by integrating multiple runtime conditions, and (c) the framework can make multiple devices collaborate for significant energy savings (15% to 41%) with negligible time and energy overhead (<0.35%).

This article presents a hierarchical approach for detecting faults in wireless sensor networks (WSNs) after they have been deployed. The developers of WSNs can specify “invariants” that must be satisfied by the WSNs. We present a framework, Hierarchical SEnsor Network Debugging (H-SEND), for lightweight checking of invariants. H-SEND is able to detect a large class of faults in data-gathering WSNs, and leverages the existing message flow in the network by buffering and piggybacking messages. H-SEND checks as closely to the source of a fault as possible, pinpointing the fault quickly and efficiently in terms of additional network traffic. Therefore, H-SEND is suited to bandwidth or communication energy constrained networks. A specification expression is provided for specifying invariants so that a protocol developer can write behavioral level invariants. We hypothesize that data from sensor nodes does not change dramatically, but rather changes gradually over time. We extend our framework for the invariants that includes values determined at run-time in order to detect data trends. The value range can be based on information local to a single node or the surrounding nodes' values. Using our system, developers can write invariants to detect data trends without prior knowledge of correct values. Automatic value detection can be used to detect anomalies that cannot be detected in existing WSNs. To demonstrate the benefits of run-time range detection and fault checking, we construct a prototype WSN using CO 2 and temperature sensors coupled to Mica2 motes. We show that our method can detect sudden changes of the environments with little overhead in communication, computation, and storage.

Applications running on the StrongARM SA-1110 or XScale processor cores can specify cache mapping for each virtual page to achieve better cache utilization. In this work, we describe a method to efficiently perform cache mapping. Under this scheme, we select a number of loops for sampling. These loops are selected automatically based on clock profiling information. We formulate the optimal cache mapping problem as an Integer Linear Programming (ILP) problem. Experiments performed on 14 test programs show speedups in 13 of them (over the default mapping) after applying our sample-based cache mapping scheme. The geometric mean of program speedups for all the 14 test programs is 1.098. Furthermore, compared with a previous heuristic method which uses the full memory trace, the sample-based method performs cache mapping faster by an order of magnitude without sacrificing the quality of mapping.

Recent research has shown that programs often exhibit value locality. Such locality occurs when a code segment, although executed repeatedly in the program, takes only a small number of different values as input and, naturally, generates a small number of different outputs. It is potentially beneficial to replace such a code segment by a table, which records the computation results for the previous inputs. When the program execution re-enters the code segment with a repeated input, its computation can be simplified to a table look-up. We discuss a compiler scheme to identify code segments, which are good candidates for computation reuse. We discuss the conditions under which the table look-up costs less than repeating the execution, and we perform profiling to identify candidates, which have many repeated inputs at run time. Compared to previous work, this scheme requires no special hardware support and is therefore particularly useful for resource constrained systems such as handheld computing devices. We implement our scheme and its supporting analyses in GCC. We experiment with several multimedia benchmarks and the GNU Go game by executing them on a handheld computing device. The results show the scheme to improve the performance and to reduce the energy consumption quite substantially for these programs.

This paper proposes using a mobile collector, such as an airplane or a vehicle, to collect sensor data from remote fields. We present three different schedules for the collector: round-robin, rate-based, and min movement. The data are not immediately transmitted to the base station after being sensed but buffered at a cluster head; hence, it is important to ensure the latency is within an acceptable range. We compare the latency and the energy expended of the three schedules. We use the ns-2 network simulator to study the scenarios and illustrate conditions under which rate-based outperforms round-robin in latency, and vice-versa. The benefit of min movement is in minimizing the energy expended.

Efficient program execution on multiprocessor computers requires both sufficient parallelism and good data locality. Recent research found that, using a combination of loop shifting, loop fusion, and array contraction, one can reduce the memory required to execute a sequence of serial loops, thereby to improve the cache locality. This paper studies how to extend such a memory-reduction scheme to a sequence of DOALL loops, which are executed in parallel on multiprocessors. Two methods are proposed to overcome difficulties caused by loop-carried dependences. Data copy-in is performed to remove anti-dependences between different parallel threads, and computation duplication is performed to remove flow dependences. Experiments performed on a number of benchmark programs show that the proposed technique improves both cache locality and parallel execution speed for the DOALL loops. The scheme achieves an average speedup of 1.41 for 17 programs on a 4-processor SUN machine.

Processors such as the Intel StrongARM SA-1110 and the Intel XScale provide flexible control over the cache management to achieve better cache utilization. Programs can specify the cache mapping policy for each virtual page, i.e. mapping it to the main cache, the mini-cache, or neither. For the latter case, the page is marked as non-cacheable. In this paper, we use memory profiling to guide such page-based cache mapping. We model the cache mapping problem and prove that finding the optimal cache mapping is NP-hard. We then present a heuristic to select the mapping. Execution time measurement shows that our heuristics can improve the performance from 1% to 21% for a set of test programs. As a byproduct of performance enhancement, we also save the energy by 4% to 28%.

Many programs can be invoked under different execution options, input parameters and data files. Such different execution contexts may lead to strikingly different execution instances. The optimal code generation may be sensitive to the execution instances. In this paper, we show how to use parametric program analysis to deal with this issue for the optimization problem of computation offloading.Computation offloading has been shown to be an effective way to improve performance and energy saving on mobile devices. Optimal program partitioning for computation offloading depends on the tradeoff between the computation workload and the communication cost. The computation workload and communication requirement may change with different execution instances. Optimal decisions on program partitioning must be made at run time when sufficient information about workload and communication requirement becomes available.Our cost analysis obtains program computation workload and communication cost expressed as functions of run-time parameters, and our parametric partitioning algorithm finds the optimal program partitioning corresponding to different ranges of run-time parameters. At run time, the transformed program self-schedules its tasks on either the mobile device or the server, based on the optimal program partitioning that corresponds to the current values of run-time parameters. Experimental results on an HP IPAQ handheld device show that different run-time parameters can lead to quite different program partitioning decisions.

Array contraction is a program transformation which reduces array size while preserving the correct output. In this paper, we present an aggressive array-contraction technique and study its impact on memory system performance. This technique, called controlled SFC, combines loop shifting and controlled loop fusion to maximize opportunities for array contraction within a given loop nesting. A controlled fusion scheme is used to prevent overfusing loops and to avoid excessive pressure on the cache and the registers. Reducing the array size increases data reuse because of the increased average number of memory operations on the same memory addresses. Furthermore, if the data size of a loop nest fits in the cache after array contraction, then repeated references to the same variable in the loop nest generate cache hits, assuming set conflicts are eliminated successfully.

Iterative stencil loops are used in scientific programs to implement relaxation methods for numerical simulation and signal processing. Such loops iteratively modify the same array elements over different time steps, which presents opportunities for the compiler to improve the temporal data locality through loop tiling. This article presents a compiler framework for automatic tiling of iterative stencil loops, with the objective of improving the cache performance. The article first presents a technique which allows loop tiling to satisfy data dependences in spite of the difficulty created by imperfectly nested inner loops. It does so by skewing the inner loops over the time steps and by applying a uniform skew factor to all loops at the same nesting level. Based on a memory cost analysis, the article shows that the skew factor must be minimized at every loop level in order to minimize cache misses. A graph-theoretical algorithm, which takes polynomial time, is presented to determine the minimum skew factor. Furthermore, the memory-cost analysis derives the tile size which minimizes capacity misses. Given the tile size, an efficient and general array-padding scheme is applied to remove conflict misses. Experiments were conducted on 16 test programs and preliminary results showed an average speedup of 1.58 and a maximum speedup of 5.06 across those test programs.

We investigate the use of data compression to reduce the battery consumed by handheld devices when downloading data from proxy servers over a wireless LAN. To make a careful trade-off between the communication energy and the overhead to perform decompression, we experiment with three universal lossless compression schemes, using a popular handheld device in a wireless LAN environment and we find interesting facts. The results show that, from the battery-saving perspective, the gzip compression software (based on LZ77) to be far superior to bzip2 (based on BWT) and compress (based on LZW). We then present an energy model to estimate the energy consumption for the compressed downloading. With this model, we further reduce the energy cost of gzip by interleaving communication with computation and by using a block-by-block selective scheme based on the compression factor of each block. We also use a threshold file size below which the file is not to be compressed before transferring.

This paper presents a compiler analysis for data communication for the purpose of transforming ordinary programs into ones that run on distributed systems. Such transformations have been used for process migration and computation offloading to improve the performance of mobile computing devices. In a client-server distributed environment, the efficiency of an application can be improved by careful partitioning of tasks between the server and the client. Optimal task partitioning depends on the tradeoff between the computation workload and the communication cost. Our compiler analysis, assisted by a minimum set of user assertions, estimates the amount of data communication between procedures. The paper also presents experimental results based on an implementation in the GCC compiler. The static estimates for several multimedia programs are compared against dynamic measurement performed using Shade, a SUN Microsystem's instruction-level simulator. The results show a high precision of the static analysis for most pairs of the procedures.

We consider handheld computing devices which are connected to a server (or a powerful desktop machine) via a wireless LAN. On such devices, it is often possible to save the energy on the handheld by offloading its computation to the server. In this work, based on profiling information on computation time and data sharing at the level of procedure calls, we construct a cost graph for a given application program. We then apply a partition scheme to statically divide the program into server tasks and client tasks such that the energy consumed by the program is minimized. Experiments are performed on a suite of multimedia benchmarks. Results show considerable energy saving for several programs through offloading.

In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.

Since sequential languages such as Fortran and C are more machine-independent than current parallel languages, it is highly desirable to develop powerful parallelization tools which can generate parallel codes, automatically or semi-automatically, targeting different parallel architectures. Array data-flow analysis is known to be crucial to the success of automatic parallelization. Such an analysis should be performed interprocedurally and symbolically and it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if it is not carefully designed. How to enhance the efficiency of this analysis to a practical level remains an issue largely untouched to date. This paper presents techniques for efficient interprocedural array data-flow analysis and documents experimental results of its implementation in a research parallelizing compiler. Our techniques are based on guarded array regions and the resulting tool runs faster, by one or two orders of magnitude, than other similarly powerful tools.

Tiling is a well-known loop transformation to improve temporal locality of nested loops. Current compiler algorithms for tiling are limited to loops which are perfectly nested or can be transformed, in trivial ways, into a perfect nest. This paper presents a number of program transformations to enable tiling for a class of nontrivial imperfectly-nested loops such that cache locality is improved. We define a program model for such loops and develop compiler algorithms for their tiling. We propose to adopt odd-even variable duplication to break anti- and output dependences without unduly increasing the working-set size, and to adopt speculative execution to enable tiling of loops which may terminate prematurely due to, e.g. convergence tests in iterative algorithms. We have implemented these techniques in a research compiler, Panorama. Initial experiments with several benchmark programs are performed on SGI workstations based on MIPS R5K and R10K processors. Overall, the transformed programs run faster by 9% to 164%.

We propose a new universal High-Level Information (HLI) format to effectively integrate front-end and back-end compilers by passing front-end information to the back-end compiler. Importing this information into an existing back-end leverages the state-of-the-art analysis and transformation capabilities of existing front-end compilers to allow the back-end greater optimization potential than it has when relying on only locally-extracted information. A version of the HLI has been implemented in the SUIF parallelizing compiler and the GCC back-end compiler. Experimental results with the SPEC benchmarks show that HLI can provide GCC with substantially more accurate data dependence information than it can obtain on its own. Our results show that the number of dependence edges in GCC can be reduced by an average of 48% for the integer benchmark programs and an average of 54% for the floating-point benchmark programs studied, which provides greater flexibility to GCC's code scheduling pass. Even with the scheduling optimization limited to basic blocks, the use of HLI produces moderate speedups compared to using only GCC's dependence tests when the optimized programs are executed on MIPS R4600 and R10000 processors.

When parallel programs are executed on multiprocessors with private caches, a set of data may be repeatedly used and modified by different threads. Such data sharing can often result in cache thrashing, which degrades memory performance. This paper presents and evaluates a loop restructuring method to reduce or even eliminate cache thrashing caused by true data sharing in nested parallel loops. This method uses a compiler analysis which applies linear algebra and the theory of numbers to the subscript expressions of array references. Due to this method's simplicity, it can be efficiently implemented in any parallel compiler. Experimental results show quite significant performance improvements over existing static and dynamic scheduling methods.

Array data flow analysis is known to be crucial to the success of array privatization, one of the most important techniques for program parallelization. It is clear that array data flow analysis should be performed interprocedurally and symbolically, and that it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if not carefully designed. How to enhance the efficiency of thk analysis to a practical level remains an issue largely untouched to date. This paper documents our experience with building a highly efficient array data flow analyzer which is based on guarded array regions and which runs faster, by one or two orders of magnitude, than other similarly powerful tools.

Array dataflow information plays an important role for successful automatic parallelization of Fortran programs. This paper proposes a powerful symbolic array dataflow analysis to support array privatization and loop parallelization for programs with arbitrary control flow graphs and acyclic call graphs. Our scheme summarizes array access information using guarded array regions and propagates such regions over a Hierarchical Supergraph (HSG). The use of guards allows us to use the information in IF conditions to sharpen the array dataflow analysis and thereby to handle difficult cases which elude other existing techniques. The guarded array regions retain the simplicity of set operations for regular array regions in common cases, and they enhance regular array regions in complicated cases by using guards to handle complex symbolic expressions and array shapes. Scalar values that appear in array subscripts and loop limits are substituted on the fly during the array information propagation, which disambiguates the symbolic values precisely for set operations. We present efficient algorithms that implement our scheme. Initial experiments of applying our analysis to Perfect Benchmarks show promising results of improved array privatization.

In the decision regarding static scheduling vs. dynamic scheduling, the only argument against the former is the potential imbalance of the workload. However, it has never been clear how the workload distributes in the iterations of Fortran parallel loops. This work examines a set of Perfect benchmarking programs [2] and report two striking results. First, when using operation counts as the measure, almost all the parallel loops identified by the Parafrase 2 compiler [11] in those programs have an equal workload among different iterations. Second, simulation shows that, although run time events on the memory system can lead to considerable variation in the execution time of different iterations which are scheduled statically, the finish time of the slowest processor normally does not exceed the average processor by the mean execution time of one loop iteration. Such workload distribution is as good as any known dynamic scheduling policy can guarantee.

Both hardware-controlled and compiler-directed mechanisms have been proposed for maintaining cache coherence in large-scale shared-memory multiprocessors, but both of these approaches have significant limitations. We examine the potential performance improvement of a new software-hardware controlled cache coherence mechanism. This approach augments the run-time information available to a directory-based coherence mechanism with compile-time analysis that statically identifies write references that cannot cause coherence problems and writes that should be written through to memory. These references are marked as not needing to send invalidation messages to thereby reduce the network traffic produced by the directory while maintaining cache consistency. For those memory references that are ambiguous, due to conditional branches, or due to the need for complex data flow analysis, for instance, the compiler conservatively marks the references and relies on the hardware directory to ensure coherence. Trace-driven simulations are used to emulate the compile-time analysis on memory traces and to estimate potential performance improvement that could be expected from a compiler performing this optimization on the Perfect Club benchmark programs. By reducing the number of invalidations, this optimized directory scheme is capable of reducing the processor-memory network traffic by up to 54 percent compared to an unoptimized directory mechanism. In addition, the overall miss ratio can be reduced up to 42 percent due to a corresponding reduction in the number of write misses.

Dynamiically tagged directories have been recently proposed as a memory-efficient mechanism for maintaining cache coherence in large-scale shared-memory multiprocessors. In order to efficiently use these directories, the number of pointer operations must be minimized and pointers should be allocated as late as possible. If pointers are allocated too early, frequent pointer overflow will occur, which in turn may cause cache thrashing.

In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

Abstract The paper reports on the status of the Fortran translator for the Cedar computer at the end of March 1991. A brief description of the Cedar Fortran language is followed by a discussion of the Fortran‐77 to Cedar Fortran parallelizer that describes the techniques currently being implemented. A collection of experiments illustrate the effectiveness of the current implementation, and point toward new approaches to be incorporated into the system in the near future.

In recent experiments, array privatization played a critical role in successful parallelization of several real programs. This paper presents compiler algorithms for the program analysis for this transformation. The paper also addresses issues in the implementation.

Event variable synchronization is a well-known mechanism for enforcing data dependence in a program that runs in parallel on a shared memory multiprocessor.This paper presents compiler algorithms to automatically generate event variable synchronization code.Previously published algorithms dealt with single parallel loops in which dependence distances are constant and known by the compiler.Howeverj loops in real application programs are often arbitrarily nested.Moreoverj compilers are often unable to determine dependence dist antes.In contrast, our algorithms generate synchronization code based directly on array subscripts and do not require constant distances in data dependence.The algorithms are designed for arbitrarily nested loops, including triangular or trapezoidal loops.

A novel algorithm, called the lambda test, is presented for an efficient and accurate data dependence analysis of multidimensional array references. It extends the numerical methods to allow all dimensions of array references to be tested simultaneously. Hence, it combines the efficiency and the accuracy of both approaches. This algorithm has been implemented in Parafrase, a Fortran program parallelization restructurer developed at the University of Illinois at Urbana-Champaign. Some experimental results are presented to show its effectiveness.>

Some results are reported from an empirical study of program characteristics, that are important in parallelizing compiler writers, especially in the area of data dependence analysis and program transformations. The state of the art in data dependence analysis and some parallel execution techniques are examined. The major findings are included. Many subscripts contain symbolic terms with unknown values. A few methods of determining their values at compile time are evaluated. Array references with coupled subscripts appear quite frequently; these subscripts must be handled simultaneously in a dependence test, rather than being handled separately as in current test algorithms. Nonzero coefficients of loop indexes in most subscripts are found to be simple: they are either 1 or -1. This allows an exact real-valued test to be as accurate as an exact integer-valued test for one-dimensional or two-dimensional arrays. Dependencies with uncertain distance are found to be rather common, and one of the main reasons is the frequent appearance of symbolic terms with unknown values.>

An efficient and precise data dependence analysis is the key to the success of a parallelizing compiler because it is required in almost all phases of the parallelism detection and enhancement in such compilers. However, existing test algorithms are quite weak in analyzing multi-dimensional array references, which are usually where the parallelism is in most programs.

The solution of the divide-and-conquer recurrence\[ M(n)\mathop {\max }\limits_{1 \leqq k < n} (M(k) + M(n - k) + \min (f(k),f(n - k))) \]is found for a variety of functions f. Asymptotic bounds on $M(n)$ are found for arbitrary nondecreasing f, and the exact form of $M(n)$ is determined for f nondecreasing and weakly concave. As a corollary to the asymptotic bounds, it is shown that $M(n)$ remains linear even when f is almost linear. Among the exact forms determined: For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lfloor {\lg n} \rfloor - \nu (n)$ where $\nu (n)$ is the number of 1-bits in the binary representation of n. For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lceil {\lg n} \rceil - 1$, while for $f(x) = \lceil {\lg (x + 1)} \rceil $, thesolution is $M(n) = (M(1) + 2)n - \lfloor {\lg n} \rfloor - \nu (n) - 1$.

In this correspondence we present and prove the correctness of an algorithm for reducing the number of synchronized memory references to shared data elements in multiprocessed loops. Optimizing compilers for shared memory multiprocessors can use this algorithm to reduce synchronization overhead. The algorithm has been implemented as a new module in the multiprocessors version of Parafrase, the restructuring system of the University of Illinois. We present a brief discussion of experiments we performed to asses the effectiveness of this algorithm in reducing the synchronization overhead for the 61 subroutines of EISPACK, a package for computing matrix eigenvectors and eigenvalues.

The effectiveness of multiprocessing a single subroutine in a tightly coupled muir!processor system is highly dependent (among other factors) on the amount of overhead incurred due to synchronized references to shared data items by active processes.In this paper we present a technique to reduce this overhead.This is achieved by reducing the number of synchronized references issued by different processes.We describe the criteria used to identify the variables whose synchronized accesses will eliminate the need to synchronize references to other variables.Our technique can be implemented in optimizing compilers for mnltiprocessor machines.It can also be used when designing parallel algorithms for multiproeessors.We implemented the technique as a pass in the Parafrase system of the University of Illinois.Relevant measurements on all the subroutines of the EISPACK package are reported (61 subroutines).The results show that our technique is quite effective.For subroutines with interprocess communication, it reduced the number of memory references requiring synchronization by 10% in two thirds of these subroutines and by more than 30% for one third of the subroutines.