Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper, we consider the problem of scheduling applications to ensure fair and efficient execution on a distributed network of processors. We limit our study to the case where communication is restricted to a tree embedded in the network, and the applications consist of a large number of independent tasks (Bags of Tasks) that originate at the tree's root. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary for different applications. The goal of scheduling is to maximize the throughput of each application while ensuring a fair sharing of resources between applications. We can find the optimal asymptotic rates by solving a linear programming problem that expresses all necessary problem constraints, and we show how to construct a periodic schedule from any linear program solution. For single-level trees, the solution is characterized by processing tasks with larger communication-to-computation ratios at children with larger bandwidths. For multilevel trees, this approach requires global knowledge of all application and platform parameters. For large-scale platforms, such global coordination by a centralized scheduler may be unrealistic. Thus, we also investigate decentralized schedulers that use only local information at each participating resource. We assess their performance via simulation and compare to an optimal centralized solution obtained via linear programming. The best of our decentralized heuristics achieves the same performance on about 2/3 of our test cases but is far worse in a few cases. Although our results are based on simple assumptions and do not explore all parameters (such as the maximum number of tasks that can be held on a node), they provide insight into the important question of fairly and optimally scheduling heterogeneous applications on heterogeneous grids.

Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper, we consider the problem of scheduling applications to ensure fair and efficient execution on a distributed network of processors. We limit our study to the case where communication is restricted to a tree embedded in the network, and the applications consist of a large number of independent tasks that originate at the tree's root. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary for different applications. Each application is given a weight that quantifies its relative value. The goal of scheduling is to maximize throughput while executing tasks from each application in the same ratio as their weights. We can find the optimal asymptotic rates by solving a linear program that expresses all necessary problem constraints, and we show how to construct a periodic schedule. For single-level trees, the solution is characterized by processing tasks with larger communication-to-computation ratios at children with larger bandwidths. For multi-level trees, this approach requires global knowledge of all application and platform parameters. For large-scale platforms, such global coordination by a centralized scheduler may be unrealistic. Thus, we also investigate decentralized schedulers that use only local information at each participating resource. We assess their performance via simulation, and compare to a centralized solution obtained via linear programming. The best of our decentralized heuristics achieves the same performance on about two-thirds of our test cases, but is far worse in a few cases. While our results are based on simplistic assumptions and do not explore all parameters (such as buffer size), they provide insight into the important question of fairly and optimally co-scheduling heterogeneous applications on heterogeneous grids

Summary form only given. Overlapping communication with computation is a well-known technique to increase application performance. While it is commonly assumed that communication and computation can be overlapped at no cost, in reality, they do contend for resources and thus interfere with each other. Here we present an empirical quantification of the interference rate of communication on computation. We measure this rate on a single processor communicating with both local and remote processors via Java sockets. Among other results we find that the computation rate can suffer by as much as 50%, and that the reduction is approximately proportional to the communication rate. We conclude that interference deserves further study.

We consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous computing platform. We use a nonoriented graph to model the platform, where resources can have different speeds of computation and communication. Because the number of tasks is large, we focus on the question of determining the optimal steady state scheduling strategy for each processor (the fraction of time spent computing and the fraction of time spent communicating with each neighbor). In contrast to minimizing the total execution time, which is NP-hard in most formulations, we show that finding the optimal steady state can be solved using a linear programming approach and, thus, in polynomial time. Our result holds for a quite general framework, allowing for cycles and multiple paths in the interconnection graph, and allowing for several masters. We also consider the simpler case where the platform is a tree. While this case can also be solved via linear programming, we show how to derive a closed-form formula to compute the optimal steady state, which gives rise to a bandwidth-centric scheduling strategy. The advantage of this approach is that it can directly support autonomous task scheduling based only on information local to each node; no global information is needed. Finally, we provide a theoretical comparison of the computing power of tree-based versus arbitrary platforms.

Predicated execution can eliminate hard to predict branches and help to enable instruction level parallelism. Many current predication variants exist where the result update is conditional based upon the outcome of the guarding predicate. However conditional writing of a register creates a naming problem for an out-of-order processor and can stall the issuing of instructions. This problem arises from potential multiple predicated definitions reaching a use, which is unresolved until the prior predicate values are computed. We focus on a light-weight form of predication, phi-predication, where all predicated instructions write a result value to their register regardless of the predicate value (i.e. even if it is false). Therefore, the predicate does not guard the writing of the result register; it instead acts as a form of selection between two input registers. This eliminates the naming problem for an out-of-order processor. Our phi-predicated ISA is derived from the predicated features of the Multiflow ISA, with extensions to efficiently predicate complex control flow. Our compiler modifications also expand upon prior techniques to provide efficient code generation. We examine the use of phi-predication for an in-order and out-of-order architecture and compare its performance to using select-op and IA64 ISA predication.

Predicated execution can be used to alleviate the costs associated with frequently mispredicted branches. This is accomplished by trading the cost of a mispredicted branch for execution of both paths following the conditional branch. In this paper we examine two enhancements for branch prediction in the presence of predicated code. Both of the techniques use recently calculated predicate definitions to provide a more intelligent branch prediction. The first branch predictor, called the squash false path filter, recognizes fetched branches known to be guarded with a false predicate and predicts them as not-taken with 100% accuracy. The second technique, called the predicate global update branch predictor, improves prediction by incorporating recent predicate information into the branch predictor. We use these techniques to aid the prediction of region-based branches. A region-based branch is a branch that is left in a predicated region of code. A region-based branch may be correlated with predicate definitions in the region in addition to those that define the branch's guarding predicate.

Many program analysis techniques used by compilers are applicable only to programs whose control flow graphs are reducible. Node-splitting is a technique that can be used to convert any control flow graph to a reducible one. However, as has been observed for various node-splitting algorithms, there can be an exponential blowup in the size of the graph.We prove that exponential blowup is unavoidable. In particular, we show that any reducible graph that is equivalent to the complete graph on n nodes (or to related bounded-degree control flow graphs) must have at least 2n-1 nodes. While this result is not a surprise, it may be relevant to the quest for finding methods of obfuscation for software protection.

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops that have a regular stencil of data dependences. Tiling is a well-known compiler optimization that improves performance on such loops, particularly for computers with a multilevel hierarchy of parallelism and memory. Most previous work on tiling is limited in at least one of the following ways: they only handle nested loops of depth two, orthogonal tiling, or rectangular tiles. In our work, we tile loop nests of arbitrary depth using polyhedral tiles. We derive a prediction formula for the execution time of such tiled loops, which can be used by a compiler to automatically determine the tiling parameters that minimizes the execution time. We also explain the notion of rise, a measure of the relationship between the shape of the tiles and the shape of the iteration space generated by the loop nest. The rise is a powerful tool in predicting the execution time of a tiled loop. It allows us to reason about how the tiling affects the length of the longest path of dependent tiles, which is a measure of the execution time of a tiling. We use a model of the tiled iteration space that allows us to determine the length of the longest path of dependent tiles using linear programming. Using the rise, we derive a simple formula for the length of the longest path of dependent tiles in rectilinear iteration spaces, a subclass of the convex iteration spaces, and show how to choose the optimal tile shape.

By sharing processor resources among threads at a very fine granularity, a simultaneous multithreading processor (SMT) renders thread-level parallelism (TLP) and instruction-level parallelism (ILP) operationally equivalent.Under what circumstances are they performance equivalent?In this paper, we show that operational equivalence does not imply performance equivalence.Rather, for some codes they perform equally well, for others ILP outperforms TLP, and for yet others, the opposite is true.In this paper, we define the performance characteristics that divide codes into one of these three circumstances.We present evidence from three codes to support the factors involved in the model.

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops which have a regular stencil of data dependences.Tiling is a well-known optimization that improves performance on such loops, particularly for computers with a multi-levelled hierarchy of parallelism and memory.Most previous work on tiling restricts the tile shape to be rectangular.Our previous work and its extension by Desprez, Dongarra, Rastello and Robert showed that for doubly nested loops, using parallelograms can improve parallel execution time by decreasing the idle time, the time that a processor spends waiting for data or synchronization.In this paper, we extend that work to more deeply nested loops, as well as to more complex loop bounds.We introduce a model which allows us to demonstrate the equivalence in complexity of linear programming and determining the execution time of a tiling in the model.We then identify a sub-class of these loops that constitute rectilinear iteration spaces for which we derive a closed form formula for their execution time.This formula can be used by a compiler to predict the execution time of a loop nest.We then derive the tile shape that minimizes this formula.Using the duality property of linear programming, we also study how the longest path of dependent tiles within a rectilinear iteration space changes with the tile shape.Finally, we observe that the execution time of a rectilinear iteration space depends on the slope of only four of the facets defining the iteration space, independent of its dimensionality.

This paper studies the relationship between storage requirements and performance. Storage-related dependences inhibit optimizations for locality and parallelism. Techniques such as renaming and array expansion can eliminate all storage-related dependences, but do so at the expense of increased storage. This paper introduces the universal occupancy vector (UOV) for loops with a regular stencil of dependences. The UOV provides a schedule-independent storage reuse pattern that introduces no further dependences (other than those implied by true flow dependences). OV-mapped code requires less storage than full array expansion and only slightly more storage than schedule-dependent minimal storage.We show that determine if a vector is a UOV is NPcomplete. However, an easily constructed but possibly nonminimal UOV can be used. We also present a branch and bound algorithm which finds the minimal UOV, while still maintaining a legal UOV at all times.Our experimental results show that the use of OV-mapped storage, coupled with tiling for locality, achieves better performance than tiling after array expansion, and accommodates larger problem sizes than untilable, storage-optimized code. F'urthermore, storage mapping based on the UOV introduces negligible runtime overhead.

This paper investigates the idle time associated with a parallel computation, that is, the time that processors are idle because they are either waiting for data from other processors or waiting to synchronize with other processors. We study doubly-nested loops corresponding to parallelogram- or trapezoidal-shaped iteration spaces that have been parallelized by the well-known tiling transformation. We introduce the notion of rise r, which relates the shape of the iteration space to that of the tiles. For parallelogram- shaped iteration spaces, we show that when r < -2, the idle time is linear in P, the number of processors, but when r > -1, it is quadratic in P. In the context of hierarchical tiling, where multiple levels of tiling are used, a good choice of rise can lead to less idle time and better performance. While idle time is not the only cost that should be considered in evaluating a tiling strategy, current architectural trends (of deeper memory hierarchies and multiple levels of parallelism) suggest it has increasing importance.

Recently, Static Single-Assignment Form and Sparse Evaluation Graphs have been advanced for the efficient solution of program optimization problems. Each method is provided with an initial set of flow graph nodes that inherently affect a problem's solution. Other relevant nodes are those where potentially disparate solutions must combine. Previously, these so-called φ-nodes were found by computing the iterated dominance frontiers of the initial set of nodes, a process that could take worst-case quadratic time with respect to the input flow graph. In this article we present an almost-linear algorithm for determining exactly the same set of φ-nodes.

A static program slice is an extract of a program which can help our understanding of the behavior of the program; it has been proposed for use in debugging, optimization, parallelization, and integration of programs. This article considers two types of static slices: executable and nonexecutable. Efficient and well-founded methods have been developed to construct executable slices for programs without goto statements; it would be tempting to assume these methods would apply as well in programs with arbitrary goto statements. We show why previous methods do not work in this more general setting, and describe our solutions that correctly and efficiently compute executable slices for programs even with arbitrary goto statements. Our conclusion is that goto statements can be accommodated in generating executable static slices.

Recent advances in languages, software design methodologies, and architecture have prompted the development of improved compile-time methods for analyzing the effects of procedure calls, pointer references, and array accesses. Such sophistication, however, generally implies that compilers and programming environments will experience a corresponding increase in the volume of analysis information, which may be difficult to use efficiently. In this paper, we consider the practical accommodation of such information. Our results show how to engineer a compiler such that its optimization phase takes time proportional to the benefit, rather than the size, of such information.>

The ability to represent, manipulate and optimize data movement between devices such as processors in a distributed memory machine, or between global memory and processors in a shared memory machine, is crucial in generating efficient code for such machines. In this paper we describe a methodology for representing and manipulating data movement explicitly in a compiler. Our methodology, called Explicit Data Placement (XDP), consists of extensions to the compiler's intermediate program language, as well as run-time structures that allow certain operations to be performed efficiently. We also illustrate one of the unique features of the XDP methodology: the ability to manipulate the run-time transfer of data ownership between processors.

In this paper, we present an algorithm that con-structs sparse evaluation graphs for forward or backward monotone data flow problems. The sparse graph combines information as early as possible, yet directly connects nodes that generate and use information. This allows problems from the large, general class of monotone data flow problems to err joy the advantages of solutions based on Static Single Assignment (SSA) form. 1

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization.A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable.Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow propertiee of programs.Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimization.Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use.We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs.The algorithms use dominance frontiers, a new concept that may have other applications.We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program.This paper thus presents strong evidence that these structures can be of practical use in optimization.

article Free Access Share on Compact representations for control dependence Authors: Ron Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , Jeanne Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , V. Sarkar IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 6Jun. 1990 pp 337–351https://doi.org/10.1145/93548.93592Online:01 June 1990Publication History 33citation585DownloadsMetricsTotal Citations33Total Downloads585Last 12 Months14Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on A foundation for sequentializing parallel code Authors: B. Simons IBM Almaden Research Center, K53-802, 650 Harry Rd., San Jose, CA IBM Almaden Research Center, K53-802, 650 Harry Rd., San Jose, CAView Profile , D. Alpern MasPar Computer Corp., 749 N. Mary Ave., Sunnyvale, CA MasPar Computer Corp., 749 N. Mary Ave., Sunnyvale, CAView Profile , J. Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 350–359https://doi.org/10.1145/97444.97702Published:01 May 1990Publication History 10citation383DownloadsMetricsTotal Citations10Total Downloads383Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article An efficient method of computing static single assignment form Share on Authors: R. Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , J. Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , B. K. Rosen IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Computer Science Dept., Brown University, Providence, RI Computer Science Dept., Brown University, Providence, RIView Profile Authors Info & Claims POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1989 Pages 25–35https://doi.org/10.1145/75277.75280Online:03 January 1989Publication History 308citation1,950DownloadsMetricsTotal Citations308Total Downloads1,950Last 12 Months119Last 6 weeks14 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

An approach to finding and forming parallel processes for both sequential and parallel programs is presented. The approach is presented in a framework that can create useful parallelism for a variety of parallel architectures. The framework makes use of a control dependence graph to capture maximal parallelism, a process tree to expose useful parallelism, renaming and storage segregation to reduce data dependencies, and an architecture-specific cost analyzer to evaluate the effectiveness of the potential processes. The framework is currently being implemented.

We consider the problem of generating sequential code for parallel programs written in a language which contains a FORALL operator, predicates and statements. This problem can arise when compiling for a multiprocessor where each processor is sequential, and in the vectorization of sequential programs. We present a necessary and sufficient condition for determining if extra guard variables or duplicate code must be inserted when generating a correct sequential program from a given, well-structured parallel program. We also have an efficient method for checking whether this condition occurs in the parallel program. This method gives rise to an algorithm for generating sequential code from parallel code which inserts guard variables (or duplicate code) only when determined by our necessary and sufficient condition. Given the choice to insert duplicate code, an exponential blow-up in size may result. We suggest some simple heuristics to limit such blow-up. We also show that in a restricted case, the minimal size sequential code can be efficiently generated. However, we show that a problem closely related to finding the minimal size sequential code (or equivalently, the minimum number of guards to be inserted) in NP-Complete. We conjecture that this problem in the general case is indeed NP-Complete.

In this paper we present an intermediate program representation, called the program dependence graph ( PDG ), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the relevant data flow relationships of a program. Control dependences are introduced to analogously represent only the essential control flow relationships of a program. Control dependences are derived from the usual control flow graph. Many traditional optimizations operate more efficiently on the PDG. Since dependences in the PDG connect computationally related parts of the program, a single walk of these dependences is sufficient to perform many optimizations. The PDG allows transformations such as vectorization, that previously required special treatment of control dependence, to be performed in a manner that is uniform for both control and data dependences. Program transformations that require interaction of the two dependence types can also be easily handled with our representation. As an example, an incremental approach to modifying data dependences resulting from branch deletion or loop unrolling is introduced. The PDG supports incremental optimization, permitting transformations to be triggered by one another and applied only to affected dependences.

We consider the problem of generating sequential code for programs written in a language which contains a Multiple GOTO operator, predicates and statements. This problem arises when compiling a parallel intermediate form (such as the PDG [3,4]) to run on a sequential machine; in a source-to-source FORTRAN translator when vectorization of a loop has failed; and when compiling logic designs written in a parallel design language for simulation on a sequential machine. It is easy to generate sequential code for this sort of parallel program if one allows either duplication of code or the insertion of guard variables at merge points; in fact, it is in general impossible without this addition. However, for a large class of parallel programs (such as those originally arising from sequential programs, even after some optimizations have been applied) it is possible to generate sequential code without duplication or the addition of guard variables. In this paper we present an efficient algorithm which will generate sequential code from a parallel program without duplication or additional guard variables for a large class of parallel programs.

A new program representation is presented which permits certain optimizations to be performed at less expense than with other forms. This paper describes code motion, common subexpression elimination and induction variable detection. Scalar propagation and constant folding are sketched here, but detailed elsewhere. The powerful code motion strategy allows entire regions of the program to be moved. The representation described may be used as a compiler intermediate form or simply as a model for program analysis. It has great potential for use in translation for parallel machines.

Consider the first order theory of the real numbers with the function + (plus) and the predicate $ < $ (less than). Let S be the set of true sentences of this theory. We first present an elimination of quantifiers decision procedure for S, and then analyze it to show that it takes at most time $2^{2cn} $, where c is a constant, to decide sentences of length n. We next show that a given sentence does not change in truth value when each of the quantifiers is limited to range over an appropriately chosen finite set of rationals. This fact leads to a new decision procedure for S which uses at most space $2^{cn} $. We also remark that our methods lead to a decision procedure for Presburger arithmetic which operates within space $2^{2cn} $. These upper bounds should be compared with the results of Fischer and Rabin [2] that for some constant c, real addition requires time $2^{cn} $ and Presburger arithmetic requires time $2^{2cn} $.