In this paper, we present a new framework for selecting, duplicating and sequencing instructions so as to decrease register pressure. The motivation for this work is to target current and future high-performance processors where reductions in register pressure in the compiled programs can lead to improved performance.

Article Anticipatory instruction scheduling Share on Authors: Vivek Sarkar Application Development Technology Institute, IBM Software Solutions Division, 555 Bailey Avenue, San Jose, California Application Development Technology Institute, IBM Software Solutions Division, 555 Bailey Avenue, San Jose, CaliforniaView Profile , Barbara Simons Application Development Technology Institute, IBM Software Solutions Division, 555 Bailey Avenue, San Jose, California Application Development Technology Institute, IBM Software Solutions Division, 555 Bailey Avenue, San Jose, CaliforniaView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 119–130https://doi.org/10.1145/237502.237515Online:24 June 1996Publication History 3citation192DownloadsMetricsTotal Citations3Total Downloads192Last 12 Months2Last 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

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication protocol, the algorithms tolerate both link and processor failures of any type. The algorithm for maintaining synchronization works for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as those of Lamport and Melliar Smith and Welch and Lynch, although, unlike them, it does require an authentication protocol to handle Byzantine faults. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement that is provably necessary.

We present a polynomial time algorithm for constructing a minimum completion time schedule of instructions from a basic block on RISC machines such as the Sun SPARC, the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. Our algorithm can be used as a heuristic for RISC processors with longer pipelines, for which there is no known optimal algorithm. Our algorithm can also handle time-critical instructions, which are instructions that have to be completed by a specific time. Time-critical instructions occur in some real-time computations, and can also be used to make shared resources such as registers quickly available for reuse. We also prove that in the absence of time-critical constraints, a greedy scheduling algorithm always produces a schedule for a target machine with multiple identical pipelines that has a length less than twice that of an optimal schedule. The behavior of the heuristic is of interest because, as we show, the instruction scheduling problem becomes NP-hard for arbitrary length pipelines, even when the basic block of code being input consists of only several independent streams of straightline code, and there are no time-critical constraints. Finally, we prove that the problem becomes NP-hard even for small pipelines, no time-critical constraints, and input of several independent streams of straightline code if either there is only a single register or if no two instructions are allowed to complete simultaneously because of some shared resource such as a bus.

We present an algorithm for analyzing deadlock and for constructing sequentializations of a class of communicating sequential processes. The algorithm may be used for deadlock detection in parallel and distributed programs at compile time, or for debugging purposes at run time. The algorithm generates a data structure we call the flow graph, which contains all you need to know about the communications between the processes. If the algorithm is used only for debugging, it is not necessary to retain a copy of the flow graph. Both static deadlock analysis and trace generation are linear in the size of the (minimum) flow graph we construct.

We present a polynomial time algorithm for constructing a minimum completion time schedule of instructions from a basic block on RISC machines such as the Sun SPARC, the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. Our algorithm can be used as a heuristic for RISC processors with longer pipelines, for which there is no known optimal algorithm. Our algorithm can also handle time-critical instructions, which are instructions that have to be completed by a specific time. Time-critical instructions occur in some real-time computations, and can also be used to make shared resources such as registers quickly available for reuse. We also prove that in the absence of time-critical constraints, a greedy scheduling algorithm always produces a schedule for a target machine with multiple identical pipelines that has a length less than twice that of an optimal schedule. The behavior of the heuristic is of interest because, as we show, the instruction scheduling problem becomes NP-hard for arbitrary length pipelines, even when the basic block of code being input consists of only several independent streams of straightline code, and there are no time-critical constraints, Finally, we prove that the problem becomes NP-hard even for small pipelines, no time-critical constraints, and input of several independent streams of straightline code if either there is only a single register or if no two instructions are allowed to complete simultaneously because of some shared resource such as a bus

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

Automatic parallelization of code written in a sequential language such as FORTRAN is of great importance for compilers for parallel computers. First, the problem of automatically parallelizing iterative loops on multiprocessors is discussed, and then a scheduling problem involving precedence constraints that models a technique for the automatic parallelization is derived. Polynomial time algorithms are presented for some special cases of this scheduling problem together with an upper bound on a naive algorithm for the general case. Using one of the polynomial time algorithms, a heuristic for the original compiler problem is obtained. Finally, test results obtained by applying our heuristic to EISPACK, a well-known umerical analysis FORTRAN package, are presented. In these tests the amount of parallelism obtained always equals and frequently surpasses that obtained by the best known techniques in the literature. This approach represents one of the first attempts at understanding the complexity theoretic aspects of loop parallelization.

An efficient polynomial time algorithm for the problem of scheduling n unit length jobs with rational release times and deadlines on m identical parallel machines is presented. By using preprocessing, a running time of $O(mn^2 )$ is obtained that is an improvement over the previous best running time of $O(n^3 \log \log n)$. The authors also present new NP-completeness results for two closely related problems.

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.

We construct fault tolerant routings for several families of graphs, including all graphs of maximal degree less than cnl/3 for some c > 0. With these routings, the diameter of the survival graph is bounded by a constant (e.g., 4 or 6), so long as the number of faults is less than the connectivity of the graph.This result partially confirms a conjecture of Dolev et.al. [DHSS].

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. The algorithms tolerate both link and node failures of any type. The algorithm for maintaining synchronization will work for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as [LM1,LM2,LL1]. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement which is provably necessary.

We analyze the problem of constructing a network which will have a fixed routing and which will be highly fault tolerant. A construction is presented which forms a “product route graph” from two or more constituent “route graphs.” The analysis involves the surviving route graph, which consists of all non-faulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph, that is, the maximum distance between any pair of nodes, is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a “padding theorem” which allows one to add nodes to a graph and to extend a previous routing.

Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,ρ)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if ρ is a minimal length routing, then the diameter of R(G,ρ)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G,ρ)/F≤3 for any minimal length routing ρ and any set of faults F with |F|

We present a polynomial time algorithm for constructing an optimal schedule, if a feasible schedule exists, for tthe following multimachine scheduling problem. There are n unit-time jobs, with arbitrary release times and deadlines, and m identical parallel machines. A feasible schedule is one in which no job is started before it is released, each job is completed by its deadline, and no job is interrupted once it begins to run.

The basic problem considered is that of scheduling n unit-time tasks, with arbitrary release times and deadlines, so as to minimize the maximum task completion time. Previous work has shown that this problem can be solved rather easily when all release times are integers. We are concerned with the general case in which noninteger release times are allowed, a generalization that considerably increases the difficulty of the problem even for only a single processor. Our results are for the one-processor case, where we provide an $O(n\log n)$ algorithm based on the concept of “forbidden regions”.