37872646
The Cedar System And An Initial Performance Study
In this paper, we give an overview of the Cedar mutliprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks@ . We also present a methodology f o r judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.
31492830
On Reducing Data Synchronization in Multiprocessed Loops
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.
14156120
A compiler scheme for reusing intermediate computation results
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.
5807481
Compiler algorithms for event variable synchronization
Event variable synchronization is a well known mecha nism for enforcing data dependences in a program that runs in parallel on a shared memory multiprocessor This paper presents compiler algorithms to automati cally generate event variable synchronization code Pre viously published algorithms dealt with single parallel loops in which dependence distances are constant and known by the compiler However loops in real appli cation programs are often arbitrarily nested Moreover compilers are often unable to determine dependence dis tances In contrast our algorithms generate synchro nization code based directly on array subscripts and do not require constant distances in data dependences The algorithms are designed for arbitrarily nested loops in cluding triangular or trapezoidal loops
20563509
A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing
Cache thrashing due to true data sharing can degrade the performance of parallel programs significantly. Our previous work showed that parallel task alignment via program transformations can be quite effective for the reduction of such cache thrashing. In this paper, we present a theoretical foundation for such program transformations. Based on linear algebra and the theory of numbers, our work analyzes the data dependences among the tasks created by a fork-join parallel program and determines at compile time how these tasks should be assigned to processors in order to reduce cache thrashing due to true data sharing. Our analysis and program transformations can be easily performed by compilers for parallel computers.
12948247
Interprocedural Analysis Based on Guarded Array Regions
Array data flow information plays an important role for successful automatic parallelization of Fortran programs. This chapter proposes a powerful symbolic array data flow summary scheme to support array privatization and loop parallelization for programs with arbitrary control flow graphs and acyclic call graphs. Our approach summarizes array access information interprocedurally, using guarded array regions. The use of guards allows us to use the information in IF conditions to do path-sensitive data flow summary and thereby to handle difficult cases. We also provide a mechanism to overcome the disadvantages of nonclosed union and difference operations. This improves not only the exactness of summaries, but also the efficiency of the summarizing procedure. Our preliminary result on array privatization shows that our summary scheme is fast and powerful.
19202401
Making fast buffer insertion even faster via approximation techniques
14010825
C-Miner: Mining Block Correlations in Storage Systems
Block correlations are common semantic patterns in storage systems. These correlations can be exploited for improving the effectiveness of storage caching, prefetching, data layout and disk scheduling. Unfortunately, information about block correlations is not available at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough to be used for discovering block correlations in storage systems. 
 
In this paper, we propose C-Miner, an algorithm which uses a data mining technique called frequent sequence mining to discover block correlations in storage systems. C-Miner runs reasonably fast with feasible space requirement, indicating that it is a practical tool for dynamically inferring correlations in a storage system. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12-25% compared to the base case, and 7-20% compared to the commonly used sequential prefetching scheme.
206924248
The impact of topology on overlay routing service
A moderate amount of recent work has been dedicated to using overlay network to support value-added network service, such as overlay multicast, OverQoS, etc. Overlay service network is a generic service framework which is designed to provide a variety of services to overlay service customers. To design an overlay service network, the first step is to choose an overlay topology connecting all the overlay service nodes. For example, RON [Anderson, DG et al., 2001] has used full mesh topology connecting all the nodes. In this paper, we did a study on the impact of topology on the overlay routing service. We found that the overlay topology has significant impact on the overlay routing in terms of routing performance and routing overhead. For example, the full mesh topology does not always give us the best performance. Moreover, the physical topology information can benefit us a lot to construct an efficient overlay topology. In addition, some alternative topologies can provide us with better performance when considering both the routing performance and overhead.
6468095
Factoring systems of linear PDEs with finite-dimensional solution spaces
A D-finite system is a finite set of linear homogeneous partial differential equations in several independent and dependent variables, whose solution space is of finite dimension. Let L be a D-finite system with rational function coefficients. We present an algorithm for computing all hyperexponential solutions of L, and an algorithm for computing all D-finite systems whose coefficients are also rational functions, and whose solutions are contained in the solution space of L.
6048187
Fast video shot retrieval by trace geometry matching in principal component space
Content-based video retrieval technology holds the key to the efficient management and sharing of video content from different sources, in different scales, across different platforms, and shared over different communication channels. In this work we present a fast retrieval algorithm based on matching the geometry of video sequence traces in the principal component space. Techniques to address scale (spatial and temporal) issues, as well as, noise and other possible distortions, such as frame dropping, are discussed. Experimental results demonstrate the effectiveness of the proposed approach.