2143299
Experience with efficient array data flow analysis for array privatization
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.
15170626
New tiling techniques to improve cache temporal locality
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%.
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.
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.
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
833146
Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs
This paper discusses the techniques used to hand-parallelize, for the Alliant FX/80, four Fortran programs from the Perfect-Benchmark suite. The paper also includes the execution times of the programs before and after the transformations. The four programs considered here were not effectively parallelized by the automatic translators available to the authors. However, most of the techniques used for hand parallelization, and perhaps all of them, have wide applicability and can be incorporated into existing translators.
62540162
Longest-path selection for delay test under process variation
Under manufacturing process variation, a path through a net is called longest if there exists a process condition under which the path has the maximum delay among all paths through the net. There are often multiple longest paths for each net, due to different process conditions. In addition, a local defect, such as resistive open or a resistive bridge, increases the delay of the affected net. To detect delay faults due to local defects and process variation, it is necessary to test all longest paths through each net. Previous approaches to this problem were inefficient because of the large number of paths that are not longest. This paper presents an efficient method to generate the set of longest paths for delay test under process variation. To capture both structural and process correlation between path delays, we use linear delay functions to express path delays under process variation. A novel technique is proposed to prune paths that are not longest, resulting in a significant reduction in the number of paths. In experiments on International Symposium on Circuits and Systems (ISCAS) circuits, our number of longest paths is 1-6% of the previous best approach, with 300/spl times/ less running time.
856534
On achieving optimal throughput with network coding
With the constraints of network topologies and link capacities, achieving the optimal end-to-end throughput in data networks has been known as a fundamental but computationally hard problem. In this paper, we seek efficient solutions to the problem of achieving optimal throughput in data networks, with single or multiple unicast, multicast and broadcast sessions. Although previous approaches lead to solving NP-complete problems, we show the surprising result that, facilitated by the recent advances of network coding, computing the strategies to achieve the optimal end-to-end throughput can be performed in polynomial time. This result holds for one or more communication sessions, as well as in the overlay network model. Supported by empirical studies, we present the surprising observation that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.
19202401
Making fast buffer insertion even faster via approximation techniques
2459398
On increasing end-to-end throughput in wireless ad hoc networks
One of the main characteristics of wireless ad hoc networks is their node-centric broadcast nature of communication, leading to interferences and spatial contention between adjacent wireless links. Due to such interferences, pessimistic concerns have been recently raised with respect to the decreasing network capacity in wireless ad hoc networks when the number of nodes scales to several orders of magnitude higher. In this paper, we argue that in all cases of end-to-end data communications - including one-to-k unicast and multicast data dissemination as well as k-to-one data aggregation - the maximum achievable end-to-end data throughput (measured on the sources) heavily depends on the strategy of arranging the topology of transmission between sources and destinations, as well as possible per-node operations such as coding. An optimal strategy achieves better end-to-end throughput than an arbitrary one. We present theoretical studies and critical insights with respect to how these strategies may be designed so that end-to-end throughput may be increased
13554203
WICCAP: from semi-structured data to structured data
Web data extraction is a technique for extracting and integrating data from Web based semistructured data. Wrappers function like the kernel of Web data extraction systems providing information mediator between users and a large number of heterogeneous data sources. Typically, they process semistructured documents generated from structured databases based on rules that are usually hidden to users. Much research has been done to use various methods to represent the knowledge of hidden rules and exploit techniques such as grammar induction, inductive logic programming, etc., to discover these rules that can be used by wrappers to extract data. An important property of semistructured data is its hierarchical structure. Intuitively, we can devise a method that can use this structure information to generate wrappers. We describe a Web data extraction system - WICCAP and its internal Web Data Extraction Language (WDEL) that provides unified view of Web data resources and extracted data. We describe some rule generation features of WICCAP and provide detailed description of the internal language and its implementation. We have conducted experiments to show the ease on generating wrappers with this approach.