Summary We investigate the challenges of building an end‐to‐end cloud pipeline for real‐time intelligent visual inspection system for use in automotive manufacturing. Current methods of visual detection in automotive assembly are highly labor intensive, and thus prone to errors. An automated process is sought that can operate within the real‐time constraints of the assembly line and can reduce errors. Components of the cloud pipeline include capture of a large set of high‐definition images from a camera setup at the assembly location, transfer and storage of the images as needed, execution of object detection, and notification to a human operator when a fault is detected. The end‐to‐end execution must complete within a fixed time frame before the next car arrives in the assembly line. In this article, we report the design, development, and experimental evaluation of the tradeoffs of performance, accuracy, and scalability for a cloud system.

In this paper, we present methods for prediction of key performance indicators relating to a manufacturing environment. This work represents a current snapshot of machine learning methods that are being used to provide actionable insight into events that may affect the following three indicators: number of units produced, number of defects per unit, and amount of rework time per defect.

Artificial Intelligence (AI) and Deep Learning has been steadily gaining importance due it’s potential for a broad set of science and industry applications. The success of deep learning techniques has found many applications, e.g. in the domain of computer vision and natural language understanding. Developing AI applications is a complex task with many challenges related to data collection, model training, and deployment.In this paper, we evaluate architectures, models and deployment issues related to the usage of deep learning techniques in the automotive manufacturing domain. Particularly, we focus on different computer vision problems in automotive manufacturing processes, e.g., in logistics processes. We developed several deep learning models that help to improve the quality and efficiency of these processes. Finally, we provide an analysis of the architecture, datasets and models used, and provide performance metrics for each of the different models.

Deep learning models are associated with various deployment challenges. Inference of such models is typically very compute-intensive and memory-intensive. In this paper, we investigate the performance of deep learning models for a computer vision application used in the automotive manufacturing industry. This application has demanding requirements that are characteristic of Big Data systems, including high volume and high velocity. The application has to process a very large set of high-definition images in real-time with appropriate accuracy requirements using a deep learning-based object detection model. Meeting the run time, accuracy, and resource requirements require a careful consideration of the choice of model, model parameters, hardware, and environmental support. In this paper, we investigate the trade-offs of the most popular deep neural network-based object detection models on four hardware platforms. We report the trade-offs of resource consumption, run time, and accuracy for a realistic real-time application environment.

This paper presents a systematic evaluation of Amazon Kinesis and Apache Kafka for meeting highly demanding application requirements. Results show that Kinesis and Kafka can provide high reliability, performance and scalability. Cost and performance trade-offs of Kinesis and Kafka are presented for a variety of application data rates, resource utilization, and resource configurations.

Data is increasingly affecting the automotive industry, from vehicle development, to manufacturing and service processes, to online services centered around the connected vehicle. Connected, mobile and Internet of Things devices and machines generate immense amounts of sensor data. The ability to process and analyze this data to extract insights and knowledge that enable intelligent services, new ways to understand business problems, improvements of processes and decisions, is a critical capability. Hadoop is a scalable platform for compute and storage and emerged as de-facto standard for Big Data processing at Internet companies and in the scientific community. However, there is a lack of understanding of how and for what use cases these new Hadoop capabilities can be efficiently used to augment automotive applications and systems. This paper surveys use cases and applications for deploying Hadoop in the automotive industry. Over the years a rich ecosystem emerged around Hadoop comprising tools for parallel, in-memory and stream processing (most notable MapReduce and Spark), SQL and NOSQL engines (Hive, HBase), and machine learning (Mahout, MLlib). It is critical to develop an understanding of automotive applications and their characteristics and requirements for data discovery, integration, exploration and analytics. We then map these requirements to a confined technical architecture consisting of core Hadoop services and libraries for data ingest, processing and analytics. The objective of this paper is to address questions, such as: What applications and datasets are suitable for Hadoop? How can a diverse set of frameworks and tools be managed on multi-tenant Hadoop cluster? How do these tools integrate with existing relational data management systems? How can enterprise security requirements be addressed? What are the performance characteristics of these tools for real-world automotive applications? To address the last question, we utilize a standard benchmark (TPCx-HS), and two application benchmarks (SQL and machine learning) that operate on a dataset of multiple Terabytes and billions of rows.

The motivation of the project is to allow for analysis of sensitive car data. This data is in the form of XML files. To protect the data, a synthetic dataset that is representative of the real world data is generated. This ensures the integrity of the data while protecting the manufacturer and customer.

This work proposes and evaluates improvements to previously known algorithms for redundancy elimination.

Effective scheduling is critical for the performance of an application launched onto the Grid environment. Finding effective scheduling algorithms for this problem is a challenging research area. Many scheduling algorithms have been proposed, studied and compared on heterogeneous parallel computers but there are few studies comparing the performance of scheduling algorithms in Grid environments. The Grid is unique because of the drastic cost differences between inter-cluster and the intra-cluster data transfers. In this paper, we compare several scheduling algorithms that represent two classes of schedulers used for Grid computing. We analyze the results to explain how different resource environments and workflow application structures affect the performance of these algorithms. Based on our experiments, we introduce a new measurement called effective aggregated computing power (EACP) that could drastically improve the performance of some schedulers.

Matlab is one of the most popular computer languages for technical and scientific programming. However, until recently, it has been limited to running on uniprocessors. One strategy for overcoming this limitation is to introduce global distributed arrays, with those arrays distributed across the processors of a parallel machine. In this paper, we describe the compilation technology we have designed for Matlab D, a distributed-array extension of Matlab. Our approach is distinguished by a two-phase compilation technology with support for a rich collection of data distributions. By precompiling array operations and communication steps into Fortran plus MPI, the time to compile an application using those operations is significantly reduced. This paper includes preliminary results that demonstrate that this approach can dramatically improve performance, scaling well to at least 32 processors.

Over the past years grid infrastructures have been deployed at larger and larger scales, with envisioned deployments incorporating tens of thousands of resources. Therefore, application scheduling algorithms can become unscalable (albeit polynomial) and thus unusable in large-scale environments. One reason for unscalability is that these algorithms perform implicit resource selection. One can achieve better scalability by performing explicit resource selection independently from scheduling in a "decoupled' approach. Furthermore, we hypothesize that one can achieve similar or even better performance as with the non-decoupled approach, which we call the "one step" approach, by selecting resources judiciously. Leveraging the Virtual Grid abstraction, we demonstrate that the decoupled approach is indeed both scalable and effective in large-scale and highly heterogeneous resource environments.

Loop fusion and tiling are both recognized as effective transformations for improving memory performance of scientific applications. However, because of their sensitivity to the underlying cache architecture and their interaction with each other it is difficult to determine a good heuristic for applying these transformations profitably across architectures. In this paper, we present a model-guided empirical tuning strategy for profitable application of loop fusion and tiling. Our strategy consists of a detailed cost model that characterizes the interaction between the two transformations at different levels of the memory hierarchy. The novelty of our approach is in exposing key architectural parameters within the model for automatic tuning through empirical search. Preliminary experiments with a set of applications on four different platforms show that our strategy achieves significant performance improvement over fully optimized code generated by state-of-the-art commercial compilers. The time spent in searching for the best parameters is considerably less than with other search strategies.

With the expansion of the Internet, the grid has become an attractive platform for scientific computing. Java, with a platform-independent execution model and built-in support for distributed computing is an inviting choice for implementation of applications intended for grid execution. Recent work has shown that an accurate performance model combined with a load-balancing scheduling strategy can significantly improve the performance of distributed applications on a heterogeneous computing platform, such as the grid. However, current performance modeling techniques are not suitable for Java applications, as the virtual machine execution model presents several difficulties: 1) a significant amount of time is spent on compilation at the beginning of the execution, 2) the virtual machine continuously profiles and recompiles the code during the execution, 3) garbage collection can have unpredictable effects on memory hierarchy, 4) some applications can spend more time garbage collecting than computing for certain heap sizes and 5) small variations in virtual machine implementation can have a large impact on the application's behavior. In this paper, we present a practical profile-based strategy for performance modeling of Java scientific applications intended for execution on the grid. We introduce two novel concepts for the Java execution model: point of predictability (PoP) and point of unpredictability (PoU). PoP accounts for the volatile nature of the effects of the virtual machine on execution time for small problem sizes. PoU accounts for the effects of garbage collection on certain applications that have a memory footprint that approaches the total heap size. We present an algorithm for determining PoP and PoU for Java applications, given the hardware platform, virtual machine and heap size. We also present a code-instrumentation-based mechanism for building the algorithm complexity model for a given application. We introduce a technique for calibrating this model that is able to accurately predict the execution time of Java programs for problem sizes between PoP and PoU. Our preliminary experiments show that techniques can achieve load balancing with more than 90% average CPU utilization.

Large-scale distributed systems offer computational power at unprecedented levels. In the past, HPC users typically had access to relatively few individual supercomputers and, in general, would assign a one-to-one mapping of applications to machines. Modern HPC users have simultaneous access to a large number of individual machines and are beginning to make use of all of them for single-application execution cycles. One method that application developers have devised in order to take advantage of such systems is to organize an entire application execution cycle as a workflow. The scheduling of such workflows has been the topic of a great deal of research in the past few years and, although very sophisticated algorithms have been devised, a very specific aspect of these distributed systems, namely that most supercomputing resources employ batch queue scheduling software, has heretofore been omitted from consideration, presumably because it is difficult to model accurately. In this work, we augment an existing workflow scheduler through the introduction of methods which make accurate predictions of both the performance of the application on specific hardware, and the amount of time individual workflow tasks will spend waiting in batch queues. Our results show that although a workflow scheduler alone may choose correct task placement based on data locality or network connectivity, this benefit is often compromised by the fact that most jobs submitted to current systems must wait in overcommited batch queues for a significant portion of time. However, incorporating the enhancements we describe improves workflow execution time in settings where batch queues impose significant delays on constituent workflow tasks.

Grid applications require allocating a large number of heterogeneous tasks to distributed resources. A good allocation is critical for efficient execution. However, many existing grid toolkits use matchmaking strategies that do not consider overall efficiency for the set of tasks to be run. We identify two families of resource allocation algorithms: task-based algorithms, that greedily allocate tasks to resources, and workflow-based algorithms, that search for an efficient allocation for the entire workflow. We compare the behavior of workflow-based algorithms and task-based algorithms, using simulations of workflows drawn from a real application and with varying ratios of computation cost to data transfer cost. We observe that workflow-based approaches have a potential to work better for data-intensive applications even when estimates about future tasks are inaccurate.

In this work, we describe new strategies for scheduling and executing workflow applications on grid resources using the GrADS [Ken Kennedy et al., 2002] infrastructure. Workflow scheduling is based on heuristic scheduling strategies that use application component performance models. The workflow is executed using a novel strategy to bind and launch the application onto heterogeneous resources. We apply these strategies in the context of executing EMAN, a bio-imaging workflow application, on the grid. The results of our experiments show that our strategy of performance model based, in-advance heuristic workflow scheduling results in 1.5 to 2.2 times better makespan than other existing scheduling strategies. This strategy also achieves optimal load balance across the different grid sites for this application.

Scalarization is a process that converts array statements into loop nests so that they can run on a scalar machine. One technical difficulty of scalarization is that temporary storage often needs to be allocated in order to preserve the semantics of array syntax - "fetch before store". Many techniques have been developed to reduce the size of temporary storage requirement in order to improve the memory hierarchy performance. With the emergence of short vector units on modern microprocessors, it is interesting to see how to extend the preexisting scalarization methods so that the underlying vector infrastructure is fully utilized, while at the same time keep the temporary storage minimized. In this paper, we extend a loop alignment algorithm for scalarization on short vector machines. The revised algorithm not only achieves vector execution with minimum temporary storage, but also handles data alignment properly, which is very important for performance. Our experiments on two types of widely available architectures demonstrate the effectiveness of our strategy

Abstract This paper presents a strategy, called almost‐whole‐program compilation, for extending the benefits of whole‐program optimization to large collections of Java components that are packaged as a group after the development phase. This strategy has been implemented in a framework that uses Java visibility and scoping rules to transform a collection of classes into a package that is amenable to whole‐program optimizations, without precluding extensions to the optimized and compiled code. Thus, it enables the Java developer to balance performance against flexibility of the program after the development phase, without compromising the design process. The transformation is shown to incur only modest performance penalties, which are more than compensated for by the interprocedural optimizations it enables. The paper concludes with experimental results showing the benefits that can be achieved using this approach. Copyright © 2005 John Wiley & Sons, Ltd.

The software gap - the discrepancy between the need for new software and the aggregate capacity of the workforce to produce it - is a serious problem for scientific software. Although users appreciate the convenience (and, thus, improved productivity) of using relatively high-level scripting languages, the slow execution speeds of these languages remain a problem. Lower level languages, such as C and Fortran, provide better performance for production applications, but at the cost of tedious programming and optimization by experts. If applications written in scripting languages could be routinely compiled into highly optimized machine code, a huge productivity advantage would be possible. It is not enough, however, to simply develop excellent compiler technologies for scripting languages (as a number of projects have succeeded in doing for MATLAB). In practice, scientists typically extend these languages with their own domain-centric components, such as the MATLAB signal processing toolbox. Doing so effectively defines a new domain-specific language. If we are to address efficiency problems for such extended languages, we must develop a framework for automatically generating optimizing compilers for them. To accomplish this goal, we have been pursuing an innovative strategy that we call telescoping languages. Our approach calls for using a library-preprocessing phase to extensively analyze and optimize collections of libraries that define an extended language. Results of this analysis are collected into annotated libraries and used to generate a library-aware optimizer. The generated library-aware optimizer uses the knowledge gathered during preprocessing to carry out fast and effective optimization of high-level scripts. This enables script optimization to benefit from the intense analysis performed during preprocessing without repaying its price. Since library preprocessing is performed only at infrequent "language-generation" times, its cost is amortized over many

In this work, we describe new strategies for scheduling and executing workflow applications on Grid resources using the GrADS infrastructure. Workflow scheduling is based on heuristic scheduling strategies that use combined computational and memory hierarchy application component performance models. The workflow is executed using a novel strategy to bind and launch the application onto heterogeneous resources. We apply these strategies in the context of launching EMAN, a bio-imaging workflow application, onto the Grid.

Telescoping languages is a strategy to automatically generate highly-optimized domain-specific libraries. The key idea is to create specialized variants of library procedures through extensive offline processing. This paper describes a telescoping system, called ARGen, which generates high-performance Fortran or C libraries from prototype Matlab code for the linear algebra library, ARPACK. ARGen uses variable types to guide procedure specializations on possible calling contexts. ARGen needs to infer Matlab types in order to speculate on the possible variants of library procedures, as well as to generate code. This paper shows that our type-inference system is powerful enough to generate all the variants needed for ARPACK automatically from the Matlab development code. The ideas demonstrated here provide a basis for building a more general telescoping system for Matlab.

This paper presents a fast new algorithm for modeling and reasoning about interferences for variables in a program without constructing an interference graph. It then describes how to use this information to minimize copy insertion for ϕ-node instantiation during the conversion of the static single assignment (SSA) form into the control-flow graph (CFG), effectively yielding a new, very fast copy coalescing and live-range identification algorithm.This paper proves some properties of the SSA form that enable construction of data structures to compute interference information for variables that are considered for folding. The asymptotic complexity of our SSA-to-CFG conversion algorithm is where-is the number of instructions in the program.Performing copy folding during the SSA-to-CFG conversion eliminates the need for a separate coalescing phase while simplifying the intermediate code. This may make graph-coloring register allocation more practical in just in time (JIT) and other time-critical compilers For example, Sun's Hotspot Server Compiler already employs a graph-coloring register allocator[10].This paper also presents an improvement to the classical interference-graph based coalescing optimization that shows adecrease in memory usage of up to three orders of magnitude and a decrease of a factor of two in compilation time, while providing the exact same results.We present experimental results that demonstrate that our algorithm is almost as precise (within one percent on average) as the improved interference-graph-based coalescing algorithm, while requiring three times less compilation time.

Abstract High‐Performance Fortran (HPF) was envisioned as a vehicle for modernizing legacy Fortran codes to achieve scalable parallel performance. To a large extent, today's commercially available HPF compilers have failed to deliver scalable parallel performance for a broad spectrum of applications because of insufficiently powerful compiler analysis and optimization. Substantial restructuring and hand‐optimization can be required to achieve acceptable performance with an HPF port of an existing Fortran application, even for regular data‐parallel applications. A key goal of the Rice dHPF compiler project has been to develop optimization techniques that enable a wide range of existing scientific applications to be ported easily to efficient HPF with minimal restructuring. This paper describes the challenges to effective parallelization presented by complex (but regular) data‐parallel applications, and then describes how the novel analysis and optimization technologies in the dHPF compiler address these challenges effectively, without major rewriting of the applications. We illustrate the techniques by describing their use for parallelizing the NAS SP and BT benchmarks. The dHPF compiler generates multipartitioned parallelizations of these codes that are approaching the scalability and efficiency of sophisticated hand‐coded parallelizations. Copyright © 2002 John Wiley & Sons, Ltd.

To ameliorate the need to spend significant programmer time modifying parallel programs to achieve high-performance, while maintaining compact, comprehensible source codes, the paper advocates the use of telescoping language technology to automatically apply, during the normal compilation process, high-level performance enhancing transformations to applications using a high-level domain-specific I/O library. We believe that this approach will be more acceptable to application developers than new language extensions, but will be just as amenable to optimization by advanced compilers, effectively making it a domain-specific language extension for I/O. The paper describes a domain-specific I/O library for irregular block-structured applications based on the KeLP library, describes high-level transformations of the library primitives for improving performance, and describes how a high-level domain-specific optimizer for applying these transformations could be constructed rising the telescoping languages framework.

At Rice University, we have undertaken a project to construct a framework for generating high-level problem solving languages that can achieve high performance on a variety of platforms.The underlying strategy, called telescoping languages, builds problem-solving systems from domain-specific libraries and scripting langauges. To accomplish this it extensively preanalyzes and transforms the library to produce a scripting language precompiler that optimizes library calls within the scripts as if they were primitives in the underlying language.

Reusing data in cache is critical to achieving high performance on modern machines because it reduces the impact of the latency and bandwidth limitations of direct memory access. To date, most studies of software memory hierarchy management have focused on the latency problem. However today's machines are increasingly limited by insufficient memory bandwidth-on these machines, latency-oriented techniques are inadequate because they do not seek to minimize the total memory traffic over the whole program. This paper explores the potential for addressing bandwidth limitations by increasing global cache reuse-that is, reusing data across whole program and over the entire data collection. To this end, the paper explores a two-step global strategy. The first step fuses computations on the same data to enable the caching of repeated accesses. The second step groups data used by the same computation to bring about contiguous access to memory. While the first step reduces the frequency of memory accesses, the second step improves their efficiency. The paper demonstrates the effectiveness of this strategy and shows how to automate it in a production compiler.

Loop fusion is important to optimizing compilers because it is an important tool in managing the memory hierarchy. By fusing loops that use the same data elements, we can reduce the distance between accesses to the same datum and avoid costly cache misses. Unfortunately the problem of optimal loop fusion for reuse has been shown to be NP-hard, so compilers must resort to heuristics to avoid unreasonably long compile times. Greedy strategies are often excellent heuristics that produce high-quality solutions quickly. We present an algorithm for greedy weighted fusion, in which the heaviest edge (the one with the most reuse) is selected for possible fusion on each step. The algorithm is shown to be fast in the sense that it takes O(V(E+V)) time, which is arguably optimal for this problem.

As the speed gap between CPU and memory widens, memory hierarchy has become the primary factor limiting program performance. Until now, the principal focus of hardware and software innovations has been overcoming latency. However, the advent of latency tolerance techniques such as non-blocking cache and software prefetching begins the process of trading bandwidth for latency by overlapping and pipelining memory transfers. Since actual latency is the inverse of the consumed bandwidth, memory latency cannot be fully tolerated without infinite bandwidth. This perspective has led us to two questions. Do current machines provide sufficient data bandwidth? If not, can a program be restructured to consume less bandwidth? This paper answers these questions in two parts. The first part defines a new bandwidth-based performance model and demonstrates the serious performance bottleneck due to the lack of memory bandwidth. The second part describes a new set of compiler optimizations for reducing bandwidth consumption of programs.

As both machines and programs have become more complex, the programming process has become correspondingly more labor-intensive. This has created a software gap between the need for new software and the aggregate capacity of the current workforce to produce it. This problem has been compounded by the slow growth of programming productivity over the past two decades. One way to bridge this gap is to make it possible end users to develop programs in high-level domain-specific programming systems. The principal impediment to the success of these systems in the past has be the poor performance of the resulting applications. To address this problem, we have developed a new compiler technology that supports script-based telescoping languages, which can be built from base languages and domain-specific libraries. By exhaustively compiling the libraries in advance, we can ensure that the performance and portability of the applications produced by such systems are high, while the compile times for scripts are acceptable to the end user These qualities are essential if script-based systems are to be practical for development of production applications.

Recently, there have been several experimental and theoretical results showing significant performance benefits of recursive algorithms on both multi-level memory hierarchies and on shared-memory systems. In particular, such algorithms have the data reuse characteristics of a blocked algorithm that is simultaneously blocked at many different levels. Most existing applications, however, are written using ordinary loops. We present a new compiler transformation that can be used to convert loop nests into recursive form automatically. We show that the algorithm is fast and effective, handling loop nests with arbitrary nesting and control flow. The transformation achieves substantial performance improvements for several linear algebra codes even on a current system with a two level cache hierarchy. As a side-effect of this work, we also develop an improved algorithm for transitive dependence analysis (a powerful technique used in the recursion transformation and other loop transformations)that is much faster than the best previously known algorithm in practice.

Give-N-Take is a code placement framework which uses a generic producer-consumer mechanism. An instance of this could be a communication step between a processor that computes (produces) some data, and other processors that subsequently reference (consume) these data in an expression. An advantage of Give-N-Take over traditional partial redundancy elimination techniques is its concept of production regions , instead of single locations, which can be beneficial for general latency hiding. Give-N-Take also guarantees balanced production, i.e., each production will be started and stopped exactly once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. Give-N-Take can place production either before or after consumption, and it also provides the option to speculatively hoist code out of potentially zero-trip loop (nest) constructs. Give-N-Take uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases. We have implemented Give-N-Take as partof a Fortran D compiler prototype, where it solves various communication generation problems associated with compiling data-parallel languages onto distributed-memory architectures.

The gap between CPU speed and memory speed in modern computer systems is widening as new generations of hardware are introduced.Loop blocking and prefetching transformations help bridge this gap for regular applications; however, these techniques aren't as effective for irregular applications.This paper investigates using data and computation reordering to improve memory hierarchy utilization for irregular applications on systems with multi-level memory hierarchies.We evaluate the impact of data and computation reordering using space-filling curves and introduce multi-Ievel blocking as a new computation reordering strategy for irregular applications.In experiments that applied specific combinations of data and computation reorderings to two irregular programs, overall execution time dropped by a factor of two for one program and a factor of four for the second.* This research was supported

With the rapid improvement of processor speed, performance of the memory hierarchy has become the principal bottleneck for most applications. A number of compiler transformations have been developed to improve data reuse in cache and registers, thus reducing the total number of direct memory accesses in a program. Until now, however, most data reuse transformations have been static---applied only at compile time. As a result, these transformations cannot be used to optimize irregular and dynamic applications, in which the data layout and data access patterns remain unknown until run time and may even change during the computation.In this paper, we explore ways to achieve better data reuse in irregular and dynamic applications by building on the inspector-executor method used by Saltz for run-time parallelization. In particular, we present and evaluate a dynamic approach for improving both computation and data locality in irregular programs. Our results demonstrate that run-time program transformations can substantially improve computation and data locality and, despite the complexity and cost involved, a compiler can automate such transformations, eliminating much of the associated run-time overhead.

In this paper we investigate a unique problem associated with fusing loops within a High Performance Fortran (HPF) program. In particular, we discuss the issue of performing loop fusion in an HPF compiler when compiling Fortran90 array assignment statements for execution on a distributedmemory machine. During compilation of an HPF program, Fortran90 array assignment statements must be scalarized into loop nests. We show how a certain class of these loop nests, when fused, can cause problems for the compiler's distributed-memory code generator. We then present an algorithm which not only prevents the fusion of these loops, but also increases the amount of useful fusion that can be performed. 1 Introduction High-Performance Fortran (HPF)[12], an extension of Fortran90, has attracted considerable attention as a promising language for writing portable parallel programs. HPF offers a simple programming model shielding programmers from the intricacies of concurrent programming and managing ...

The goal of languages like Fortran D or High Performance Fortran (HPF) is to provide a simple yet efficient machine-independent parallel programming model. After the algorithm selection, the data layout choice is the key intellectual challenge in writing an efficient program in such languages. The performance of a data layout depends on the target compilation system, the target machine, the problem size, and the number of available processors. This makes the choice of a good layout extremely difficult for most users of such languages. If languages such as HPF are to find general acceptance, the need for data layout selection support has to be addressed. We beleive that the appropriate way to provide the needed support is through a tool that generates data layout specifications automatically. This article discusses the design and implementation of a data layout selection tool that generates HPF-style data layout specifications automatically. Because layout is done in a tool that is not embedded in the target compiler and hence will be run only a few times during the tuning phase of an application, it can use techniques such as integer programming that may be considered too computationally expensive for inclusion in production compilers. The proposed framework for automatic data layout selection builds and examines search spaces of candidate data layouts. A candidate layout is an efficient layout for some part of the program. After the generation of search spaces, a single candidate layout is selected for each program part, resulting in a data layout for the entire program. A good overall data layout may require the remapping of arrays between program parts. A performance estimator based on a compiler model, an execution model, and a machine model are needed to predict the execution time of each candidate layout and the costs of possible remappings between candidate data layouts. In the proposed framework, instances of NP-complete problems are solved during the construction of candidate layout search spaces and the final selection of candidate layouts from each search space. Rather than resorting to heuristics, the framework capitalizes on state-of-the-art 0-1 integer programming technology to compute optimal solutions of these NP-complete problems. A prototype data layout assistant tool based on our framework has been implemented as part of the D system currently under development at Rice University. The article reports preliminary experimental results. The results indicate that the framework is efficient and allows the generation of data layouts of high quality.

For many Fortran90 and HPF programs performing dense matrix computations, the main computational portion of the program belongs to a class of kernels known as stencils. Stencil computations are commonly used in solving partial differential equations, image processing, and geometric modeling. The efficient handling of such stencils is critical for achieving high performance on distributed-memory machines. Compiling stencils into efficient code is viewed as so important that some companies have built special-purpose compilers for handling them and others have added stencil-recognizers to existing compilers.In this paper we present a general compilation strategy for stencils written using Fortran90 array constructs. Our strategy is capable of optimizing single or multi-statement stencils and is applicable to stencils specified with shift intrinsics or with array-syntax all equally well. The strategy eliminates the need for pattern-recognition algorithms by orchestrating a set of optimizations that address the overhead of both intraprocessor and interprocessor data movement that results from the translation of Fortran90 array constructs. Our experimental results show that code produced by this strategy beats or matches the best code produced by the special-purpose compilers or pattern-recognition schemes that are known to us. In addition, our strategy produces highly optimized code in situations where the others fail, producing several orders of magnitude performance improvement, and thus provides a stencil compilation strategy that is more robust than its predecessors.

The enormous popularity of the Internet has made an instant star of the Java programming language. Java's portability, reusability, security and clean design has made it the language of choice for Web-based applications and a popular alternative to C++ for object-oriented programming. Unfortunately, the performance of the standard Java implementation, even with just-in-time compilation technology, is far behind the most popular languages today. The need for an aggressive optimizing compiler for Java is clear. Building on preliminary experience with the JavaSoft bytecode optimizer, this paper explores some of the issues that arise in building efficient implementations of Java. A number of interesting problems are presented by the Java language design, making classical optimization strategies much harder to implement. On the other hand, Java presents the opportunity for some new optimizations, unique for this language. © 1997 John Wiley & Sons, Ltd.

Communication placement analysis is an important step in the compilation of data-parallel programs for multiprocessor systems. This paper presents a communication placement framework that minimizes frequency of communication, eliminates redundant communication, and maximizes communication latency hiding. The paper shows how data dependence information can be combined with data-flow analysis to devise simpler and cleaner data-flow problems. It shows how to develop equations for balanced communication placement using a set of uni-directional analyses with an independent equation system for each placement criterion. This structure allows the framework to support vector message pipelining-an important optimization for programs with loop-carried dependences-but, that was not supported by any previous data-flow framework. The paper also describes how other optimizations, such as partially redundant communication elimination and message coalescing, are supported by the framework. Finally, the paper presents experimental results to prove the efficacy of our placement analysis.

Composite grid problems arise in important application areas, e.g. reactor simulation. Related physical phenomena are inherently parallel and their simulations are computationally intensive. Unfortunately, parallel languages, such as High Performance Fortran, provide little support for these problems. We illustrate topological connections via a coupling statement, develop a programming style and transformation system to support composite grid code development, and develop an algorithm that automatically determines distributions for composite grid problems with small meshes. A mesh is classified as small if the amount of computational work associated with the mesh is less than the amount of work to be assigned to a single processor. Precompiler transformations, such as cloning for alignment specification, are described. Excerpts from a High Performance Fortran program before and after transformation illustrate user programming style and transformation issues. Our distribution algorithm's alignment and distribution specifications are input to the transformed High Performance Fortran programs which applies the mapping for execution of the simulation code. Some advantages of this approach are: transformations are applied before compilation and allow communication optimization; data distribution may be determined for any number of problems without recompilation; user determined distribution for parallelization is unnecessary; portability is improved. We validate the topology-based data distribution algorithm using a number of reactor configurations. Two random distribution algorithms provide a basis of comparison with measures of load balance and communication cost. Experiments show that the topology-based distribution algorithm almost always obtains load balance at least as good as, and often significantly better than, random algorithms while reducing the total communication per iteration from 50% to as much as a factor of ten.

One of the challenging tasks in code generation for embedded systems is register assignment. When more live variables than registers exist, some variables will necessarily be accessed from data memory. Because loops are typically executed many times and are often time-critical, good register assignment in loops is exceedingly important as accessing data memory can degrade performance. The issue of finding an optimal register assignment to loops has been open for some time. In this article, we present a technique for optimal (i.e., spill minimizing) register assignment to loops. First we present a technique for register assignment to architecture styles that are characterized by a consolidated register file. Then we extend the technique to include architecture styles that are characterized by distributed memories and/or a combination of general- and special-purpose registers. Experimental results demonstrate that although the optimal algorithm may be computationally prohibitive, heuristic versions obtain results with performance better than that of an existing graph coloring approach.

Data-parallel languages, such as High Performance Fortran, are designed to make programming of distributed-memory machines easier, and resulting programs more portable and efficient. Advanced features of these languages require new methods in both compilers and run-time systems. We present efficient techniques for generating local memory addresses, in the exact order as specified by the original program, for computations involving references to arrays with cyclic(k) distribution, the most general regular data distribution provided in data-parallel languages. Our method exploits the repetitive pattern of memory accesses to handle arbitrary affine subscripts, while minimizing the space and time overhead. Extensive experimental results indicate the efficiency of our approach in practice. 1 Introduction Distributed-memory machines are widely regarded as the most promising means for high performance computing. However, the message-passing programming model, typically associated with these ...

It is widely acknowledged in high-performance computing circles that parallel input/output needs substantial improvement in order to make scalable computers truly usable. We present a data storage model that allows processors independent access to their own data and a corresponding compilation strategy that integrates data-parallel computation with data distribution for out-of-core problems. Our results compare several communication methods and I/O optimizations using two out-of-core problems, Jacobi iteration and LU factorization.

Data-parallel languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. Novel features of these languages call for the development of new techniques in both compilers and run-time systems. In this paper, we present an improved algorithm for finding the local memory access sequence in computations involving regular sections of arrays with cyclic(k) distributions. After establishing the fact that regular section indices correspond to elements of an integer lattice, we show how to find a lattice basis that allows for simple and fast enumeration of memory accesses. The complexity of our algorithm is shown to be lower than that of the previous solution for the same problem. In addition, the experimental results demonstrate the efficiency of our method in practice.

Supporting source-level performance analysis of programs written in data-parallel languages requires a unique degree of integration between compilers and performance analysis tools. Compilers for languages such as High Performance Fortran infer parallelism and communication from data distribution directives, thus, performance tools cannot meaningfully relate measurements about these key aspects of execution performance to source-level constructs without substantial compiler support. This paper describes an integrated system for performance analysis of data-parallel programs based on the Rice Fortran 77D compiler and the Illinois Pablo performance analysis toolkit. During code generation, the Fortran D compiler records mapping information and semantic analysis results describing the relationship between performance instrumentation and the original source program. An integrated performance analysis system based on the Pablo toolkit uses this information to correlate the program's dynamic behavior with the data parallel source code. The integrated system provides detailed source-level performance feedback to programmers via a pair of graphical interfaces. Our strategy serves as a model for integration of data-parallel compilers and performance tools.

This paper presents techniques for compiling loops with complex, indirect array accesses into loops whose array references have at most one level of indirection. The transformation allows prefetching of array indices for more efficient structuring of communication on distributed-memory machines. It can also improve performance on other architectures by enabling prefetching of data between levels of the memory hierarchy or exploitation of hardware support for vectorized gather/scatter. Our techniques are implemented in a compiler for Fortran D and execution speed improvements are given for multiprocessor and vector machines.

High Performance Fortran (HPF) is rapidly gaining acceptance as a language for parallel programming. The goal of HPF is to provide a simple yet efficient machine independent parallel programming model. Besides the algorithm selection, the data layout choice is the key intellectual step in writing an efficient HPF program. The developers of HPF did not believe that data layouts can be determined automatically in all cases, Therefore HPF requires the user to specify the data layout. It is the task of the HPF compiler to generate efficient code for the user supplied data layout. The choice of a good data layout depends on the HPF compiler used, the target architecture, the problem size, and the number of available processors. Allowing remapping of arrays at specific points in the program makes the selection of an efficient data layout even harder. Although finding an efficient data layout fully automatically may not be possible in all cases. HPF users will need support during the data layout selection process. In particular, this support is necessary if the user is not familiar with the characteristics of the target HPF compiler and target architecture, or even with HPF itself. Therefore, tools for automatic data layout and performance estimation will be crucial if the HPF is to find general acceptance in the scientific community. This paper discusses a framework for automatic data layout for use in a data layout assistant tool for a data-parallel language such as HPF. The envisioned tool can be used to generate a first data layout for a sequential Fortran program without data layout statements, or to extend a partially specified data layout in a HPF program to a totally specified data layout. Since the data layout assistant is not embedded in a compiler and will run only a few times during the tuning process of an application program, the framework can use techniques that may be too computationally expensive to be included in a compiler. A prototype data layout assistant tool based on our framework has been implemented as part of the D system currently under development at Rice University. The paper reports preliminary experimental results. The results indicate that the framework is efficient and generates data layouts of high quality.

We present a new method to determine whether a convex region contains any integer points. The method is designed for array subscript analysis in parallel programs. The general problem is whether a system of linear equalities and inequalities has an integer solution. A set of known techniques is used to transform the problem to that of finding whether a convex region contains any integer points. The main result of the paper is a set of new search procedures that identify an integer solution in a convex region, or prove that no integer solutions exist. They are based on the geometrical properties of convex regions that are not empty, but also do not contain any integer points. The results contribute to exact and efficient dependence and synchronization analysis of parallel programs.>

Parallel computing has not lived up to its promise. After nearly a decade of research, parallel systems are found primarily in research labs and only a few corporations have adopted it for their mainline computing problems. Significantly, very few independent software vendors have ported their codes to parallel machines. Now high-performance workstations are rapidly gaining on high-end supercomputing systems and we are undergoing a shakeout among the vendors of parallel computer systems.

Parallel processing has been a subject of extensive research for over 20 years, especially in the last 10 years, with many commercial parallel machines becoming available, from small scale parallel machines to massively parallel machines. At one time, it was claimed that parallel machines will become the mainstream computers. However, more recently, some parallel computer vendors have gone out of business and some others are struggling. Some pessimists even claimed that this is a dying field. So, what’s wrong? Five distinguished panelists are invited to share their views on this issue. The panelists are also expected to address what could be done and could be done in order to make parallel computers truly mainstream computers. Panelists

Compilers for data-parallel languages such as Fortran D and High-Performance Fortran use data alignment and distribution specifications as the basis for translating programs for execution on MIMD distributed-memory machines. This paper describes techniques for generating efficient code for programs that use block-cyclic distributions. These techniques can be applied to programs with symbolic loop bounds, symbolic array dimensions, and loops with non-unit strides. We present algorithms for computing the data elements that need to be communicated among processors both for loops with unit and non-unit strides, a linear-time algorithm for computing the memory access sequence for loops with non-unit strides, and experimental results for a hand-compiled test case using block-cyclic distributions

GIVE-N-TAKE is a code placement framework which uses a general producer-consumer concept. An advantage of GIVE-N-TAKE over existing partial redundancy elimination techniques is its concept of production regions, instead of single locations, which can be beneficial for general latency hiding. GIVE-N-TAKE guaranteed balanced production, that is, each production will be started and stopped once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. GIVE-N-TAKE can place production either before or after consumption, and it also provides the option to hoist code out of potentially zero-trip loop (nest) constructs. GIVE-N-TAKE uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases.

Fortran D and High Performance Fortran are languages designed to support efficient data-parallel programming on a variety of parallel architectures. The goal of the D Editor is to provide a tool that allows scientists to use these languages efficiently. The D Editor combines analyses for shared memory machines and compiler optimizations for distributed memory machines. By cooperating with the underlying compiler, it can provide novel information on partitioning, parallelism, and communication based on compile time analysis at the level of the original Fortran program. The D Editor uses color coding and a collection of graphical displays to help the user to zoom in on portions of the program containing sequentialized code or expensive communication. The prototype implementation is useful for interactively displaying the results of compile time analysis; however, it has a number of shortcomings that must be addressed. Future enhancements will provide additional advice and transformation capabilities. We believe the D Editor is representative of a new generation of tools that will be needed to assist scientists to fully exploit languages such as High Performance Fortran.>

Abstract Most conventional compilers fail to allocate array elements to registers because standard data‐flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating‐point registers, which are most often used as temporary repositories for subscripted variables. This paper presents a source‐to‐source transformation, called scalar replacement, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The scalar replaced variables are more likely to be assigned to registers by the coloring‐based register allocators found in most compilers than are their unreplaced counterparts. The algorithm presented here extends previous techniques for scalar replacement by allowing the presence of forward conditional control flow within loop bodies through the mapping of partial redundancy elimination to scalar replacement. Finally, experimental results show that scalar replacement is extremely effective. On kernels, integer‐factor improvements over code generated by a good optimizing compiler of conventional design are possible.

Over the past decade, microprocessor design strategies have focused on increasing the computational power on a single chip. Because computations often require more data from cache per floating-point operation than a machine can deliver and because operations are pipelined, idle computational cycles are common when scientific applications are executed. To overcome these bottlenecks, programmers have learned to use a coding style that ensures a better balance between memory references and floating-point operations. In our view, this is a step in the wrong direction because it makes programs more machine-specific. A programmer should not be required to write a new program version for each new machine; instead, the task of specializing a program to a target machine should be left to the compiler. But is our view practical? Can a sophisticated optimizing compiler obviate the need for the myriad of programming tricks that have found their way into practice to improve the performance of the memory hierarchy? In this paper we attempt to answer that question. To do so, we develop and evaluate techniques that automatically restructure program loops to achieve high performance on specific target architectures. These methods attempt to balance computation and memory accesses and seek to eliminate or reduce pipeline interlock. To do this, they estimate statically the balance between memory operations and floating-point operations for each loop in a particular program and use these estimates to determine whether to apply various loop transformations. Experiments with our automatic techniques show that integer-factor speedups are possible on kernels. Additionally, the estimate of the balance between memory operations and computation, and the application of the estimate are very accurate—experiments reveal little difference between the balance achieved by our automatic system that is made possible by hand optimization.

The ParaScope Editor is an interactive parallel programming tool that assists knowledgeable users in developing scientific Fortran programs. It displays the results of sophisticated program analyses, provides a set of powerful interactive transformations, and supports program editing. This paper summarizes experiences of scientific programmers and tool designers using the ParaScope Editor. We evaluate existing features and describe enhancements in three key areas: user interface, analysis, and transformation. many existing features prove crucial to successful program parallelization. They include interprocedural array side-effect analysis and program and dependence view filtering. Desirable functionality includes improved program navigation based on performance estimation, incorporating user assertions in analysis and more guidance in selecting transformations. These results offer insights for the authors of a variety of programming tools and parallelizing compilers.

Typically, commercially available shared memory machines have addressed the cache coherence problem with hardware strategies based on global inter-cache communication.However, global communication limits scalabihly and eficiency."Local knowledge' 'coherences trategies, which avoid global communication at run-time, ofler better scalability, at the cost of some additional cache misses.The most eflective Iocalknowledge strategies described in the literature are those based on generation timestamps (TS).We propose a new strategy, TS1, that requires less extra storage than TS, only one extra bit per cache line, and can produce more cache hits by exploiting sophisticated compiler analysis.TS1 handles common synchronization paradigms including DCMLL, I) CIACFtCISS, and critical sections.Early results show TS1 is, worst case, slightly slower than TS.Best case, TS1's flexibility allows for significant improvements.

No abstract available.

Procedure cloning is an interprocedural transformation where the compiler creates specialized copies of procedure bodies. The compiler divides incoming calls between the original procedure and its copies. By carefully partitioning the calls, the compiler ensures that each clone inherits an environment that allows for better code optimization. This paper presents a three-phase algorithm for deciding when to clone a procedure. The algorithm seeks to avoid unnecessary code growth by considering how the information exposed by cloning will be used during optimization. We present a set of assumptions that bound both the algorithm's running time and code expansion.

Abstract The ParaScope Editor is a new kind of interactive parallel programming tool for developing scientific Fortran programs. It assists the knowledgeable user by displaying the results of sophisticated program analyses and by providing editing and a set of powerful interactive transformations. After an edit or parallelism‐enhancing transformation, the ParaScope Editor incrementally updates both the analyses and source quickly. This paper describes the underlying implementation of the ParaScope Editor, paying particular attention to the analysis and representation of dependence information and its reconstruction after changes to the program.

The ParaScope parallel programming environment, developed to support scientific programming of shared-memory multiprocessors, is described. It includes a collection of tools that use global program analysis to help users develop and debug parallel programs. The focus is on ParaScope's compilation system. The compilation system extends the traditional single-procedure compiler by providing a mechanism for managing the compilation of complete programs. The ParaScope editor brings both compiler analysis and user expertise to bear on program parallelization. The debugging system detects and reports timing-dependent errors, called data races, in execution of parallel programs. A project aimed at extending ParaScope to support programming in FORTRAN D, a machine-independent parallel programming language for use with both distributed-memory and shared-memory parallel computers, is described.>

Access latency in large-scale shared-memory multiprocessors is a concern since most (if not all) memory is one or more hops away through an interconnection network. Providing processors with one or more levels of cache is an accepted way to reduce the average access latency; however, in a multiprocessor, cached values must be kept coherent for the multiprocessor to support the abstraction of a shared global memory. There is no generally accepted hardware solution to provde cache coherence for large-scale shared-memory multiprocessors. Software coherence strategies offer scalability with current hardware. In this paper we examine a compiler-based software strategy for maintaining cache coherence that relies on dependence analysis and a vectorization algorithm to insert cache control directives. Experiments on the BBN TC2000 for a pair of numerical problems show that the run-time cost of coherence using our strategy is less than that for previously proposed compiler-based software methods and suggest that it should compare favorably with proposed hardware schemes.

The Fortran D compiler uses data decomposition specifications to automatically translate Fortran programs for execution on MIMD distributed-memory machines. This paper introduces and classifies a number of advanced optimizations needed to achieve acceptable performance; they are analyzed and empirically evaluated for stencil computations. Profitability formulas are derived for each optimization. Results show that exploiting parallelism for pipelined computations, reductions, and scans is vital. Message vectorization, collective communication, and efficient coarsegrain pipelining also significantly affect performance. 1 Introduction Parallel computing represents the only plausible way to continue to increase the computational power available to computational scientists and engineers. However, parallel computers are not likely to be widely successful until they are also easy to program. MIMD distributed-memory machines such as the Intel iPSC/860 present the most difficult programming m...

Previous research has used program transformation to introduce parallelism and to exploit data locality. Unfortunately, these two objectives have usually been considered independently. This work explores the trade-offs between effectively utilizing parallelism and memory hierarchy on shared-memory multiprocessors. We present a simple, but surprisingly accurate, memory model to determine cache line reuse from both multiple accesses to the same memory location and from consecutive memory access. The model is used in memory optimizing and loop parallelization algorithms that effectively exploit data locality and parallelism in concert. We demonstrate the efficacy of this approach with very encouraging experimental results.

Many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. When running this kind of loop nest on a SIMD machine, the SIMD-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable MIMD implementations. This problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow.

An attempt was made to determine whether a compiler can automatically restructure computations well enough to avoid the need for hand blocking. To that end, programs in LAPACK were studied for which it was possible to examine both the block version and the corresponding point algorithm. For each of these programs, it was determined whether a plausible compiler technology could succeed in obtaining the block version from the point algorithm. The results are encouraging: one can block triangular and trapezoidal loops, and many of the problems introduced by complex dependence patterns can be overcome by the use of the transformation known as index-set splitting. In addition, it was shown that knowledge about which operations commute can enable a compiler to succeed in blocking codes that could not be blocked by any compiler based strictly on dependence analysis.>

Algorithms exist for compiling Fortran D for MIMD (multiple-instruction multiple-data) distributed-memory machines, but they are significantly restricted in the presence of procedure calls. The authors present interprocedural analysis, optimization, and code generation algorithms for Fortran D that limit compilation to only one pass over each procedure. This is accomplished by collecting summary information after edits, and then compiling procedures in reverse topological order to propagate necessary information. Delaying instantiation of the computation partition, communication, and dynamic data decomposition is key to enabling interprocedural optimization. Recompilation analysis preserves the benefits of separate compilation. Empirical results show that interprocedural optimization is crucial in achieving acceptable performance for a common application.>

The problem of allocating vector registers on supercomputers is addressed in the context of compiling vector languages. Two subproblems must be solved to achieve good vector register allocation. First, the vector operations in the source program must be subdivided into sections that fit the hardware of the target machine. Second, the locality of reference of the vector operations must be improved via aggressive program transformations. Solutions to both of these problems, based on the use of novel aspects of data dependence, are presented. The techniques described extend naturally to scalar machines by observing that a scalar register is simply a vector register of length one.>

Article Software prefetching Share on Authors: David Callahan View Profile , Ken Kennedy View Profile , Allan Porterfield View Profile Authors Info & Claims ASPLOS IV: Proceedings of the fourth international conference on Architectural support for programming languages and operating systemsApril 1991 Pages 40–52https://doi.org/10.1145/106972.106979Online:01 April 1991Publication History 394citation1,868DownloadsMetricsTotal Citations394Total Downloads1,868Last 12 Months79Last 6 weeks7 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 SiteGet Access

The ParaScope Editor is a new kind of interactive parallel programming tool for developing scientific Fortran programs. It assists the knowledgeable user by displaying the results of sophisticated program analyses and by providing editing and a set of powerful interactive transformations. After an edit or parallelism-enhancing transformation, the ParaScope Editor incrementally updates both the analyses and source quickly. This paper describes the underlying implementation of the ParaScope Editor, paying particular attention to the analysis and representation of dependence information and its reconstruction after changes to the program. 1 Introduction The ParaScope Editor is a tool designed to help skilled users interactively transform a sequential Fortran 77 program into a parallel program with explicit parallel constructs, such as those in PCF Fortran [40]. In a language like PCF Fortran, the principal mechanism for the introduction of parallelism is the parallel loop, which specif...

Precise and efficient dependence tests are essential to theeffectivermss ofaparallelizing compiler. This paper proposes a dependence testing scheme based on classi-fyingpairs ofsubscripted variable references. Exact yet fast dependence tests are presented for certain classes ofarray references, as well as empirical results showing that these references dominate scientific Fortran codes. These dependence tests are being implemented at Rice University in both PFC, aparallelizing compiler, and ParaScope, a parallel programming environment, 1

The choice of the data domain partitioning scheme is an important factor in determining the available parallelism and hence the performance of an application on a distributed memory multiprocessor.In this paper, we present a performance estimator for statically evaluating the relative efficiency of different data partitioning schemes for any given program on any given distributed memory multiprocessor.Our methlod is not based on a theoretical machine model, but ixnstead uses a set of kernel routinea to "train" the estimator for each target machine.We also describe a prototype implementation of this technique and discuss an experimental evaluation of its accuracy.

We present a new approach that enables compiler optimization of procedure calls and loop nests containing procedure calls. We introduce two interprocedural transformations that move loops across procedure boundaries, exposing them to traditional optimizations on loop nests. These transformations are incorporated into a code generation algorithm for a shared-memory multiprocessor. The code generator relies on a machine model to estimate the expected benefits of loop parallelization and parallelism-enhancing transformations. Several transformation strategies are explored and one that minimizes total execution time is selected. Efficient support of this strategy is provided by an existing interprocedural compilation system. We demonstrate the potential of these techniques by applying this code generation strategy to two scientific applications programs. 1 Introduction Modern computer architectures, such as pipelined, superscalar, VLIW and multiprocessor machines, demand sophisticated co...

Massivelyparallel MIMD distributed-memory machines can provide enormous computation power.

Regular section analysis, which summarizes interprocedural side effects on subarrays in a form useful to dependence analysis, while avoiding the complexity of prior solutions, is shown to be a practical addition to a production compiler. Optimizing compilers should produce efficient code even in the presence of high-level language constructs. However, current programming support systems are significantly lacking in their ability to analyze procedure calls. This deficiency complicates parallel programming, because loops with calls can be a significant source of parallelism. The performance of regular section analysis is compared to two benchmarks: the LINPACK library of linear algebra subroutines and the Rice Compiler Evaluation Program Suite (RiCEPS), a set of complete application codes from a variety of scientific disciplines. The experimental results demonstrate that regular section analysis is an effective means of discovering parallelism, given programs written in an appropriately modular programming style.>

The ParaScope Editor, an intelligent interactive editor for parallel Fortran programs, which is the centerpiece of the ParaScope project, an integrated collection of tools to help scientific programmers implement correct and efficient parallel programs, is discussed. ParaScope Editor reveals to users potential hazards of a proposed parallelization in a program. It provides a variety of powerful interactive program transformations that have been shown useful in converting programs to parallel form. ParaScope Editor supports general user editing through a hybrid text and structure editing facility that incrementally analyzes the modified program for potential hazards. It is shown that ParaScope Editor supports an exploratory programming style in which users get immediate feedback on their various strategies for parallelization.>

Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.

Understanding synchronization is important for a parallel programming tool that uses dependence analysis as the basis for advising programmers on the correctness of parallel constructs. This paper discusses static analysis methods that can be applied to parallel programs with event variable synchronization. The objective is to be able to predict potential data races in a parallel program. The focus is on how dependencies and synchronization statements inside loops can be used to analyze complete programs with parallel loop and parallel case style parallelism.

The authors describe an implementation of regular section analysis in the Rice Parallel Fortran Converter (PFC), an automatic parallelization system. The overriding concern in the implementation is that it be efficient enough to be incorporated in a practical compilation system. This implementation of regular section analysis describes interprocedural side effects on subarrays in a form useful to dependence analysis while avoiding the complexity of prior solutions. The authors also examine the performance of regular section analysis on two benchmarks: the LINPACK library of linear algebra subroutines and the Rice Compiler Evaluation Program Suite, a set of complete application codes from a variety of scientific disciplines. It is demonstrated that regular section analysis is an effective means of discovering parallelism, given programs written in an appropriately modular programming style.>

An approach for parallel debugging that coordinates static analysis with efficient on-the-fly access anomaly detection is described. On-the-fly instrumentation mechanisms are being developed for the structured synchronization primitives of Parallel Computing Forum (PCF) Fortran, the emerging standard for parallel Fortran. The proposed instrumentation techniques guarantee that one can isolate schedule-dependent behavior in a schedule-independent fashion. The result is that a single-instrumented execution will either report sources of schedule-dependent behavior, or it will validate that all executions of the program on the same data compute the same result. When an instrumented execution is being used solely to find sources of schedule-dependent behavior, its cost can be reduced by slicing out computations that do not contribute to race conditions. Ongoing efforts to incorporate the proposed debugging approach in the ParaScope environment are described.>

A general and optimal algorithm for loop distribution when control flow is present is proposed. The algorithm can be used to enhance the effectiveness of vectorizers, parallelizers, and programming environments. The method performs loop distribution in the presence of control flow based on control dependencies. This algorithm is optimal in that it generates the minimum number of new arrays and tests possible. A code generation algorithm that produces code for the resulting program without replicating statements or conditions is also presented.>

An algorithm for constructing a precise call multigraph for languages that permit procedure parameters, extending the method of B. Ryder (see ibid., vol.5, no.3, p.216-225 (1979)) for handling recursion, is presented. If it is assumed that there is a constant upper bound on the number of procedure parameters to any procedure in the program, then the algorithm is polynomial in the total number of procedures in the program.>

Article Compile-time detection of race conditions in a parallel program Share on Authors: Vasanth Balasundaram Dept. of Computer Science, Rice University, P.O. Box 1892, Houston, TX Dept. of Computer Science, Rice University, P.O. Box 1892, Houston, TXView Profile , Ken Kennedy Dept. of Computer Science, Rice University, P.O. Box 1892, Houston, TX Dept. of Computer Science, Rice University, P.O. Box 1892, Houston, TXView Profile Authors Info & Claims ICS '89: Proceedings of the 3rd international conference on SupercomputingJune 1989 Pages 175–185https://doi.org/10.1145/318789.318809Online:01 June 1989Publication History 36citation382DownloadsMetricsTotal Citations36Total Downloads382Last 12 Months8Last 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 SiteGet Access

article A technique for summarizing data access and its use in parallelism enhancing transformations Share on Authors: V. Balasundaram Dept. of Computer Science, Rice University Dept. of Computer Science, Rice UniversityView Profile , K. Kennedy Dept. of Computer Science, Rice University Dept. of Computer Science, Rice UniversityView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 24Issue 7July 1989 pp 41–53https://doi.org/10.1145/74818.74822Published:21 June 1989 104citation512DownloadsMetricsTotal Citations104Total Downloads512Last 12 Months15Last 6 weeks0 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 SiteGet Access

We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.

We present a new algorithm for computing interprocedural aliases due to passing parameters by reference. This algorithm runs in O(N2+NE) time and, when combined with algorithms for alias-free, flow-insensitive data-flow problems, yields algorithms for solution of the general flow-insensitive problems that also run in O(N2+NE) time.

The ParaScope project is building an integrated collection of tools to help scientific programmers develop correct and efficient parallel programs. The centerpiece of this collection is the ParaScope Editor, an intelligent interactive editor for parallel FORTRAN programs. The ParaScope Editor displays data dependencies, which correspond to potential data races among the iterations of a parallel loop, to assist the user in determining the correctness of a proposed parallelization. In addition, it uses dependencies to support a variety of program transformations selectable by the programmer.

We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the binding multi-graph, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.

An algorithm for transforming sequential programs into equivalent parallel programs is presented. The method concentrates on finding loops whose separate iterations can be run in parallel without syn-chronization. Although a simple version of the method can be shown to be optimal, the problem of generating optimal code when loop interchange is employed is shown to be intractable. These methods are implemented in an experimental translation system developed at Rice University. 1.

The recent success of vector computers such as the Cray-1 and array processors such as those manufactured by Floating Point Systems has increased interest in making vector operations available to the FORTRAN programmer. The FORTRAN standards committee is currently considering a successor to FORTRAN 77, usually called FORTRAN 8x, that will permit the programmer to explicitly specify vector and array operations. Although FORTRAN 8x will make it convenient to specify explicit vector operations in new programs, it does little for existing code. In order to benefit from the power of vector hardware, existing programs will need to be rewritten in some language (presumably FORTRAN 8x) that permits the explicit specification of vector operations. One way to avoid a massive manual recoding effort is to provide a translator that discovers the parallelism implicit in a FORTRAN program and automatically rewrites that program in FORTRAN 8x. Such a translation from FORTRAN to FORTRAN 8x is not straightforward because FORTRAN DO loops are not always semantically equivalent to the corresponding FORTRAN 8x parallel operation. The semantic difference between these two constructs is precisely captured by the concept of dependence . A translation from FORTRAN to FORTRAN 8x preserves the semantics of the original program if it preserves the dependences in that program. The theoretical background is developed here for employing data dependence to convert FORTRAN programs to parallel form. Dependence is defined and characterized in terms of the conditions that give rise to it; accurate tests to determine dependence are presented; and transformations that use dependence to uncover additional parallelism are discussed.

In spite of substantial progress in the theory of interprocedural data flow analysis, few practical compiling systems can afford to apply it to produce more efficient object programs. To perform interprocedural analysis, a compiler needs not only the source code of the module being compiled, but also information about the side effects of every procedure in the program containing that module, even separately compiled procedures. In a conventional batch compiler system, the increase in compilation time required to gather this information would make the whole process impractical. In an integrated programming environment, however, other tools can cooperate with the compiler to compute the necessary interprocedural information incrementally . as the program is being developed, decreasing both the overall cost of the analysis and the cost of individual compilations. A central goal of the R n project at Rice University is to construct a prototype software development environment that is designed to build whole programs, rather than just individual modules. It employs interprocedural analysis and optimization to produce high-quality machine code for whole programs. This paper presents an overview of the methods used by the environment to accomplish this task and discusses the impact of these methods on the various environment components. The responsibilities of each component of the environment for the preparation and use of interprocedural information are presented in detail.

Program analysis methods, especially those which support automatic vectorization, are based on the concept of interstatement dependence where a dependence holds between two statements when one of the statements computes values needed by the other. Powerful program transformation systems that convert sequential programs to a form more suitable for vector or parallel machines have been developed using this concept [AllK 82, KKLW 80].The dependence analysis in these systems is based on data dependence. In the presence of complex control flow, data dependence is not sufficient to transform programs because of the introduction of control dependences. A control dependence exists between two statements when the execution of one statement can prevent the execution of the other. Control dependences do not fit conveniently into dependence-based program translators.One solution is to convert all control dependences to data dependences by eliminating goto statements and introducing logical variables to control the execution of statements in the program. In this scheme, action statements are converted to IF statements. The variables in the conditional expression of an IF statement can be viewed as inputs to the statement being controlled. The result is that control dependences between statements become explicit data dependences expressed through the definitions and uses of the controlling logical variables.This paper presents a method for systematically converting control dependences to data dependences in this fashion. The algorithms presented here have been implemented in PFC, an experimental vectorizer written at Rice University.

The problem of semantic evaluation in a compiler-generating system can be addressed by specifying language semantics in an attribute grammar [19], a context-free grammar augmented with “attributes” for the nonterminals and “semantic functions” to compute the attributes. A deterministic method for evaluating all attributes in a “semantic” parse tree is derived and shown to have time and space complexities which are essentially linear in the size of the tree. In a prepass through the parse tree, the method determines an evaluation sequence for the attributes; thus it is somewhat analogous to dynamic programming. The constructor-evaluator system described should be suitable for inclusion in a general translator-writing system.

A standard approach to the analysis of program structure for the purpose of code optimization is to construct the "control flow graph" which models the possible execution paths through the program. Various graph algorithms can be applied to the control flow graph to produce data flow information, possible optimizations, etc. [A1,A2,AC,AU2,AU3,CS,HU1,HU2.HU3,Ke1,Ke2,Ke3,Ke4,Sc,U]. Studies of the form of typical control flow graphs indicate that such graphs tend to fall into a restricted subclass of general graphs. For example, empirical investigations have shown that the vast majority of program graphs have no multiple-entry loops [AC,HU2,HU3,Kn1].The recent work on "structured programming" has suggested that "good" programs fall into an even more restricted subclass. In fact, purists recommend that all programs be synthesized from three basic control structures: sequential statements, if-then-else statements, and single-entry single-exit loops [Di,Wi].Formal language theory [HoU] has given us a practical way to specify the set of strings which comprise a given language: via a grammar. It is then a natural idea to extend grammars from the strings to graphs in hopes of getting the same power of expression. Several researchers have used this approach [FKZ,J2,Ro].In this paper we study the applicability of a grammatical approach to describing the set of control flow graphs which arise from "good" programs in the sense proposed by many programming practitioners. The resulting flow graph language contains all those programs constructed according to the purists' rules and also admits programs with multiple-exit loops if such loops are constructed sensibly. The grammar we use is the "semi-structured flow graph" grammar GSSFG which was studied originally in [FKZ]. There are several appealing properties of this grammar; perhaps the most important, from the point-of-view of a compiler-writer, is the existence of a linear-time parsing algorithm which leads directly to a linear-time data flow analysis method [FKZ].In the present work we summarize the results from [FKZ] and address several new questions. First, how often do programs written by people with no knowledge of the SSFG rules fall into the language defined by GSSFG? In other words, is the language a natural one for programming? Second, once a program has been parsed according to GSSFG do benefits other than fast data flow analysis accrue?The paper is organized into three main sections. Section II introduces GSSFG and the parsing algorithm from [FKZ]. Section III is devoted to an empirical study conducted by the authors in an attempt to answer the question of naturalness, described above. Section IV discusses several applications of the graph parse in a "graph attribute grammar" framework. The summary at the end of the paper includes suggestions for further investigation.

Program structure is defined in terms of a simple graph grammar, the "semi-structured flow graph grammar," which admits many of the control structure extensions suggested for "structured programming." The grammar defines a set of graph reductions which are shown to have the "Finite Church-Rosser (FCR)" property; i.e., when applied in any order to a graph, the limit (when no further reductions are possible) is unique. In particular, if a given graph is generated by the grammar, repeated application of the reductions will result in a single node regardless of the order in which they are applied. This property gives rise to an algorithm that parses a given program flow graph in time linear in the size of the graph. The resulting parse is used in a global data flow analysis algorithm which requires a number of bit-vector steps which is also linear in the size of the given graph.

The translation process may be divided into a syntactic phase and a semantic phase. Context-free grammars can be used to describe the set of syntactically correct source texts in a formal yet intuitively appealing way, and many techniques are now known for automatically constructing parsers from given CF grammars. Knuth's attribute grammars offer the prospect of similarly automating the implementation of the semantic phase.

The problem of determining the points in a program at which variables are “live” (will be used again) is introduced and discussed. Two solutions, one which uses a simple iterative algorithm and one which uses an algorithm based on “Cocke–Allen interval” analysis, are presented and analyzed. These algorithms are compared on “self replicating“ families of reducible program flow graphs. The results are inconclusive in that the interval method requires fewer bit-vector steps on some graphs and more on others. If n is the number of nodes in a program flow graph and the number of edges is linearly proportional to n, then both algorithms require $O(n^2 )$ steps in the worst case.

A new approach to global program data flow analysis which constructs a for the control flow graph is discussed and a simple algorithm which uses a node listing to determine the live variables in a program is presented. This algorithm combined with a fast node listing constructor due to Aho and Ullman has produced an 0(n log n) algorithm for live analysis. The utility of the node-listing method is demonstrated by an examination of the class of graphs for which short listings exist. This class is quite similar to the class of graphs for understandable programs.