Many large-scale Java applications suffer from runtime bloat. They execute large volumes of methods and create many temporary objects, all to execute relatively simple operations. There are large opportunities for performance optimizations in these applications, but most are being missed by existing optimization and tooling technology. While JIT optimizations struggle for a few percent improvement, performance experts analyze deployed applications and regularly find gains of 2× or more. Finding such big gains is difficult, for both humans and compilers, because of the diffuse nature of runtime bloat. Time is spread thinly across calling contexts, making it difficult to judge how to improve performance. Our experience shows that, in order to identify large performance bottlenecks in a program, it is more important to understand its dynamic dataflow than traditional performance metrics, such as running time. This article presents a general framework for designing and implementing scalable analysis algorithms to find causes of bloat in Java programs. At the heart of this framework is a generalized form of runtime dependence graph computed by abstract dynamic slicing , a semantics-aware technique that achieves high scalability by performing dynamic slicing over bounded abstract domains. The framework is instantiated to create two independent dynamic analyses, copy profiling and cost-benefit analysis , that help programmers identify performance bottlenecks by identifying, respectively, high-volume copy activities and data structures that have high construction cost but low benefit for the forward execution. We have successfully applied these analyses to large-scale and long-running Java applications. We show that both analyses are effective at detecting inefficient operations that can be optimized for better performance. We also demonstrate that the general framework is flexible enough to be instantiated for dynamic analyses in a variety of application domains.

Many opportunities for easy, big-win, program optimizations are missed by compilers. This is especially true in highly layered Java applications. Often at the heart of these missed optimization opportunities lie computations that, with great expense, produce data values that have little impact on the program's final output. Constructing a new date formatter to format every date, or populating a large set full of expensively constructed structures only to check its size: these involve costs that are out of line with the benefits gained. This disparity between the formation costs and accrued benefits of data structures is at the heart of much runtime bloat.

In this paper, we present an approach to automatically detect high impact coding errors in large Java applications which use frameworks. These high impact errors cause serious performance degradation and outages in real world production environments, are very time-consuming to detect, and potentially cost businesses thousands of dollars. Based on 3 years experience working with IBM customer production systems, we have identified over 400 high impact coding patterns, from which we have been able to distill a small set of pattern detection algorithms. These algorithms use deep static analysis, thus moving problem detection earlier in the development cycle from production to development. Additionally, we have developed an automatic false positive filtering mechanism based on domain specific knowledge to achieve a level of usability acceptable to IBM field engineers. Our approach also provides necessary contextual information around the sources of the problems to help in problem remediation. We outline how our approach to problem determination can be extended to multiple programming models and domains. We have implemented this problem determination approach in the SABER tool and have used it successfully to detect many serious code defects in several large commercial applications. This paper shows results from four such applications that had over 60 coding defects.

For a program with sufficient parallelism, reducing synchronization costs is one of the most important objectives for achieving efficient execution on any parallel machine. This paper presents a novel methodology for reducing synchronization costs of programs compiled for SPMD execution. This methodology combines data flow analysis with communication analysis to determine the ordering between production and consumption of data on different processors, which helps in identifying redundant synchronization. The resulting framework is more powerful than any that have been previously presented, as it provides the first algorithm that can eliminate synchronization messages even from computations that need communication. We show that several commonly occurring computation patterns such as reductions and stencil computations with reciprocal producer-consumer relationship between processors lend themselves well to this optimization, an observation that is confirmed by an examination of some HPF benchmark programs. Our framework also recognizes situations where the synchronization needs for multiple data transfers can be satisfied by a single synchronization message. This analysis, while applicable to all shared memory machines as well, is especially useful for those with a flexible cache-coherence protocol, as it identifies efficient ways of moving data directly from producers to consumers, often without any extra synchronization.

This paper presents a framework, based on global array data-flow analysis, to reduce communication costs in a program being compiled for a distributed memory machine. We introduce available section descriptor, a novel representation of communication involving array sections. This representation allows us to apply techniques for partial redundancy elimination to obtain powerful communication optimizations. With a single framework, we are able to capture optimizations like (1) vectorizing communication, (2) eliminating communication that is redundant on any control flow path, (3) reducing the amount of data being communicated, (4) reducing the number of processors to which data must be communicated, and (5) moving communication earlier to hide latency, and to subsume previous communication. We show that the bidirectional problem of eliminating partial redundancies can be decomposed into simpler unidirectional problems even in the context of an array section representation, which makes the analysis procedure more efficient. We present results from a preliminary implementation of this framework, which are extremely encouraging, and demonstrate the effectiveness of this analysis in improving the performance of programs.

We describe pHPF, an research prototype HPF compiler for the IBM SP series parallel machines. The compiler accepts as input Fortran 90 and Fortran 77 programs, augmented with HPF directives; sequential loops are automatically parallelized. The compiler supports symbolic analysis of expressions. This allows parameters such as the number of processors to be unknown at compile-time without significantly affecting performance. Communication schedules and computation guards are generated in a parameterized form at compile-time. Several novel optimizations and improved versions of well-known optimizations have been implemented in pHPF to exploit parallelism and reduce communication costs. These optimizations include elimination of redundant communication using data-availability analysis; using collective communication; new techniques for mapping scalar variables; coarse-grain wavefronting; and communication reduction in multi-dimensional shift communications. We present experimenta...

Article Free Access Share on Factoring: a practical and robust method for scheduling parallel loops Authors: Susan Flynn Hummel CRI, Ecole Nationale Supérieure des Mines de Paris, 35, rue saint-honoré, 77305 Fontainebleau, France and IBM T.J. Watson Research Center and Polytechnic University, New York CRI, Ecole Nationale Supérieure des Mines de Paris, 35, rue saint-honoré, 77305 Fontainebleau, France and IBM T.J. Watson Research Center and Polytechnic University, New YorkView Profile , Edith Schonberg IBM Research, T.J. Watson Research Center, Yorktown Heights, NY IBM Research, T.J. Watson Research Center, Yorktown Heights, NYView Profile , Lawrence E. Flynn Mathematics Department, Hampton University, Hampton, VA Mathematics Department, Hampton University, Hampton, VAView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 610–632https://doi.org/10.1145/125826.126137Online:01 August 1991Publication History 31citation340DownloadsMetricsTotal Citations31Total Downloads340Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

One of the major disadvantages of parallel programming with shared memory is the nondeterministic behavior caused by uncoordinated access to shared variables, known as access anomalies. Monitoring program execution to detect access anomalies is a promising and relatively unexplored approach to this problem. We present a new algorithm, referred to as task recycling, for detecting anomalies, and compare it to an existing algorithm. Empirical results indicate several significant conclusions: (i) While space requirements are bounded by O(T × V), where T is the maximum number of threads that may potentially execute in parallel and V is the number of variable monitored, for typical programs space requirements are on average O(V). (ii) Task recycling is more efficient in terms of space requirements and often in performance. (iii) The general approach of monitoring to detect access anomalies is practical.

The two prevailing styles of scientific parallel programming are discussed. In the SPMD (single program, multiple data) style, all processors execute the same program, with sequential code executed redundantly and parallel code executed cooperatively. In the fork-join style, a sequential thread of control spawns multiple threads to execute a portion of the code concurrently. The authors describe an automatic method for approaching the efficiency of SPMD-style execution for programs written in the more-structured fork-join style. Analysis at compile-time and proper support at run-time yield execution efficiency that approaches the SPMD model. Moreover, a greater degree of portability is achieved by regulating the burden of deciding what should be in an SPMD parallel region to the compiler, which is probably more familiar with architectural detail than most programmers.>

Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called merging and subtraction. Upper bounds on storage are shown to be V × N2 for merging and V × N for subtraction.

Experimental results for the recognition of general curves in three-space using registered range and intensity images are presented. the matching algorithm uses fast Fourier transforms to determine the least-squares difference between sequences of points sampled at equal intervals along two piecewise linear approximations of curves in three-space and returns the rotation and translation required to bring one of the curves into closest juxtaposition with the other. Performance of the algorithm is demonstrated by matching curves in three-space which are the boundaries of regions of contrasting reflectivity on curved surfaces. the experiments use a recently developed range sensor which is able to generate a 512 × 460 × 12 bit range image (with registered intensity image) in 40 s.