Summary With the increase in size and complexity of high‐performance computing systems, the probability of failures, and the cost of recovery grow. Parallel applications running on these systems should be able to continue running in spite of node failures at arbitrary times. Collective operations are essential for many parallel MPI applications, and are often the first to detect such failures. This work presents tree‐based fault‐tolerant collective operations, which combine fault detection and recovery as an integral part each operation. We do this by extending existing tree‐based algorithms, to allow for a collective operation to succeed despite failing nodes before or during its run. This differs from other approaches, where recovery takes place after a failure of such operations have failed. The article includes a comparison between the performance of the proposed algorithm and other approaches, as well as a simulator‐based analysis of performance at scale.

Driven by ever increasing performance demands of compute-intensive applications, supercomputing systems comprise more and more nodes. This growth is a significant burden for fast group communication primitives and also makes those systems more susceptible to failures of individual nodes. In this paper we present a two-phase fault-tolerant scheme for group communication. Using broadcast as an example, we provide a full-spectrum discussion of our approach --- from a formal analysis to LogP-based simulations to a message-passing-based implementation running on a large cluster. Ultimately, we are able to reduce the complex problem of reliable and fault-tolerant collective group communication to a graph theoretical renumbering problem. Both, simulations and measurements, show our solution to achieve a latency reduction of 50% with up to six times fewer messages sent in comparison to existing schemes.

Connected component identification is a fundamental problem in graph analytics, serving as a basis for subsequent computations in a wide range of applications. To determine connectivity, several parallel algorithms, whose complexity is proportional to the number of edges or graph diameter, have been proposed. However, an optimal algorithm may extract graph components by working proportionally to the number of vertices, which can be orders of magnitude lower than the number of edges. We propose Afforest: an extension of the Shiloach-Vishkin connected components algorithm that approaches optimal work efficiency by processing subgraphs in each iteration. We prove the convergence of the algorithm, analyze its work efficiency characteristics, and provide further techniques to speed up processing graphs containing a huge component. Designed with modern parallel architectures in mind, we show that the algorithm exhibits higher memory locality than existing methods. Using both synthetic and real-world graphs, we demonstrate that Afforest achieves speedups of up to 67x over the state-of-the-art on multi-core CPUs (Broadwell, POWER8) and up to 23x on GPUs (Pascal).

Large-scale parallel programming environments and algorithms require efficient group-communication on computing systems with failing nodes. Existing reliable broadcast algorithms either cannot guarantee that all nodes are reached or are very expensive in terms of the number of messages and latency. This paper proposes Corrected-Gossip, a method that combines Monte Carlo style gossiping with a deterministic correction phase, to construct a Las Vegas style reliable broadcast that guarantees reaching all the nodes at low cost. We analyze the performance of this method both analytically and by simulations and show how it reduces the latency and network load compared to existing algorithms. Our method improves the latency by 20% and the network load by 53% compared to the fastest known algorithm on 4,096 nodes. We believe that the principle of corrected-gossip opens an avenue for many other reliable group communication operations.

With the increased popularity of multi-GPU nodes in modern HPC clusters, it is imperative to develop matching programming paradigms for their efficient utilization. In order to take advantage of the local GPUs and the low-latency high-throughput interconnects that link them, programmers need to meticulously adapt parallel applications with respect to load balancing, boundary conditions and device synchronization. This paper presents MAPS-Multi, an automatic multi-GPU partitioning framework that distributes the workload based on the underlying memory access patterns. The framework consists of host- and device-level APIs that allow programs to efficiently run on a variety of GPU and multi-GPU architectures. The framework implements several layers of code optimization, device abstraction, and automatic inference of inter-GPU memory exchanges. The paper demonstrates that the performance of MAPS-Multi achieves near-linear scaling on fundamental computational operations, as well as real-world applications in deep learning and multivariate analysis.

Summary Management of forthcoming exascale clusters requires frequent collection of run‐time information about the nodes and the running applications. This paper presents a new paradigm for providing online information to the management system of scalable clusters, consisting of a large number of nodes and one or more masters that manage these nodes. We describe the details of resilient gossip algorithms for sharing local information within subsets of nodes and for sending global information to a master, which holds information on all the nodes. The presented algorithms are decentralized, scalable and resilient, working well even when some nodes fail, without needing any recovery protocol. The paper gives formal expressions for approximating the average ages of the local information at each node and the information collected by the master. It then shows that these results closely match the results of simulations and measurements on a real cluster. The paper also investigates the resilience of the algorithms and the impact on the average age when nodes or masters fail. The main outcome of this paper is that partitioning of large clusters can improve the quality of information available to the management system without increasing the number of messages per node. Copyright © 2015 John Wiley & Sons, Ltd.

GPUs play an increasingly important role in high-performance computing. While developing naive code is straightforward, optimizing massively parallel applications requires deep understanding of the underlying architecture. The developer must struggle with complex index calculations and manual memory transfers. This article classifies memory access patterns used in most parallel algorithms, based on Berkeley’s Parallel “Dwarfs.” It then proposes the MAPS framework, a device-level memory abstraction that facilitates memory access on GPUs, alleviating complex indexing using on-device containers and iterators. This article presents an implementation of MAPS and shows that its performance is comparable to carefully optimized implementations of real-world applications.

Markets of computing resources typically consist of a cluster (or a multi-cluster) and jobs that arrive over time and request computing resources in exchange for payment. In this paper we study a real system that is capable of preemptive process migration (i.e. moving jobs across nodes) and that uses a market-based resource allocation mechanism for job allocation. Specifically, we formalize our system into a market model and employ simulation-based analysis (performed on real data) to study the effects of users' behavior on performance and utility. Typically online settings are characterized by a large amount of uncertainty, therefore it is reasonable to assume that users will consider simple strategies to game the system. We thus suggest a novel approach to modeling users' behavior called the Small Risk-aggressive Group model. We show that under this model untruthful users experience degraded performance. The main result and the contribution of this paper is that using the k-th price payment scheme, which is a natural adaptation of the classical second-price scheme, discourages these users from attempting to game the market. The preemptive capability makes it possible not only to use the k-th price scheme, but also makes our scheduling algorithm superior to other non-preemptive algorithms. Finally, we design a simple one-shot game to model the interaction between the provider and the consumers. We then show (using the same simulation-based analysis) that market stability in the form of (symmetric) Nash-equilibrium is likely to be achieved in several cases.

Abstract Scalable computer systems, including clusters and multi‐cluster grids, require routine exchange of information about the state of system‐wide resources among their nodes. Gossip‐based algorithms are popular for providing such information services due to their simplicity, fault tolerance and low communication overhead. This paper presents a randomized gossip algorithm for maintaining a distributed bulletin board among the nodes of a scalable computer system. In this algorithm each node routinely disseminates its most recently acquired information while maintaining a snapshot of the other nodes' states. The paper provides analytical approximations for the expected average age, the age distribution and the expected maximal age for the acquired information at each node. We confirm our results by measurements of the performance of the algorithm on a multi‐cluster campus grid with 256 nodes and by simulations of configurations with up to 2048 nodes. The paper then presents practical enhancements of the algorithm, which makes it more suitable for a real system. Such enhancements include using fixed‐size messages, reducing the number of messages sent to inactive nodes and supporting urgent information. The enhanced algorithm guarantees the age properties of the information at each node in the configurations with an arbitrary number of inactive nodes. It is being used in our campus grid for resource discovery, for dynamic assignment of processes to the best available nodes, for load‐balancing and for on‐line monitoring. Copyright © 2009 John Wiley & Sons, Ltd.

The renewed interest in virtualization gives rise to new opportunities for running high performance computing (HPC) applications on clusters and grids. These include the ability to create a uniform (virtual) run-time environment on top of a multitude of hardware and software platforms, and the possibility for dynamic resource allocation towards the improvement of process performance, e.g., by virtual machine (VM) migration as a means for load-balancing. This paper deals with issues related to running HPC applications on multi-clusters and grids using VMware, a virtualization package running on Windows, Linux and OS X. The paper presents the ldquoJobrunrdquo system for transparent, on-demand VM launching upon job submission, and its integration with the MOSIX cluster and grid management system. We present a novel approach to job migration, combining VM migration with process migration using Jobrun, by which it is possible to migrate groups of processes and parallel jobs among different clusters in a multi-cluster or in a grid. We use four real HPC applications to evaluate the overheads of VMware (both on Linux and Windows), the MOSIX cluster extensions and their combination, and present detailed measurements of the performance of Jobrun.

Proportional (fair) share schedulers are designed to provide applications with predefined portions of system resources. Single node operating systems use context-switch (preemption) to dynamically allocate the CPU(s) to running processes. This paper presents an online algorithm for proportional share allocations of nodes in a cluster, in a fashion that resembles a single-node system. The algorithm relies on preemptive process migrations for dynamic allocations of nodes to users. The paper presents the algorithm and its performance on a MOSIX organizational Grid with 60 nodes. We show that proportional share allocations can be achieved in a relatively short time (minutes).

Economy-based admission control of jobs in a grid, or migration of guest jobs from a disconnecting cluster in a grid, as well as checkpointing parallel jobs in a cluster to a central repository are demanding tasks that can exhaust essential resources such as the communication networks, due to the requirement to quickly move large amounts of data from many nodes. Compressing memory images might make these operations more efficient provided that the overall throughput is increased. Existing serial compression algorithms are not suitable for such purposes because they do not exploit inter-file redundancy. This paper presents decentralized algorithms for parallel compression of correlated memory images of a job in a cluster or in a grid. The algorithms use block suppression to eliminate inter-file redundancy. They take advantage of the multiple processor environment to simultaneously map memory blocks to hash values in order to detect redundancies. It is shown that exploiting inter-file redundancy of correlated files can increase the overall transfer throughput of parallel jobs. It is also shown that combining serial compression with our algorithms further increases this throughput. The paper presents the algorithms and their performance.

MOSIX is a cluster management system that uses process migration to allow a Linux cluster to perform like a parallel computer. Recently it has been extended with new features that could make a grid of Linux clusters run as a cooperative system of federated clusters. On one hand, it supports automatic workload distribution among connected clusters that belong to different owners, while still preserving the autonomy of each owner to disconnect its cluster from the grid at any time, without sacrificing migrated processes from other clusters. Other new features of MOSIX include grid-wide automatic resource discovery; a precedence scheme for local processes and among guest processes (from other clusters); flood control; a secure run-time environment (sandbox) which prevents guest processes from accessing local resources in a hosting system, and support of cluster partitions. The resulting grid management system is suitable to create an intra-organizational high-performance computational grid, e.g., in an enterprise or in a campus. The paper presents enhanced and new features of MOSIX and their performance.

Computing clusters (CC) consisting of several connected machines, could provide a high-performance, multiuser, timesharing environment for executing parallel and sequential jobs. In order to achieve good performance in such an environment, it is necessary to assign processes to machines in a manner that ensures efficient allocation of resources among the jobs. The paper presents opportunity cost algorithms for online assignment of jobs to machines in a CC. These algorithms are designed to improve the overall CPU utilization of the cluster and to reduce the I/O and the interprocess communication (IPC) overhead. Our approach is based on known theoretical results on competitive algorithms. The main contribution of the paper is how to adapt this theory into working algorithms that can assign jobs to machines in a manner that guarantees near-optimal utilization of the CPU resource for jobs that perform I/O and IPC operations. The developed algorithms are easy to implement. We tested the algorithms by means of simulations and executions in a real system and show that they outperform existing methods for process allocation that are based on ad hoc heuristics.

One of the main methods for achieving fault tolerance in distributed systems is recovery of the state of failed components. Though generic recovery methods like checkpointing and message logging exist, in many cases the recovery has to be application specific. In this paper we propose a general model for a node state reconstruction after crash failures. In our model the reconstruction operation is defined only by the requirements it fulfills, without referring to the specific application dependent way it is performed. The model provides a framework for formal treatment of algorithm-specific and system-specific recovery procedures. It is used to specify node state reconstruction procedures for several widely used distributed algorithms and systems, as well as to prove their correctness.

Most implementations of a computing cluster (CC) use greedy-based heuristics to perform load balancing. In some cases, this is in contrast to theoretical results about the performance of online load balancing algorithms. We define the home model in order to better reflect the architecture of a CC. In this new theoretical model, we assume a realistic cluster structure in which every job has a "home" machine which it prefers to be executed on, e.g. due to I/O considerations or because it was created there. We develop several online algorithms for load balancing in this model. We first provide a theoretical worst-case analysis, showing that our algorithms achieve better competitive ratios and perform less reassignments than algorithms for the unrelated machines model, which is the best existing theoretical model to describe such clusters. We then present an empirical average-case performance analysis by means of simulations. We show that the performance of our algorithms is consistently better than that of several existing load balancing methods, e.g. the greedy and the opportunity cost methods, especially in a dynamic and changing CC environment.

A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and shown to be useful in practice. This "opportunity cost" method converts the usage of several heterogeneous resources in a machine to a single homogeneous "cost." Assignment and reassignment are then performed based on that cost. This is in contrast to traditional, ad hoc methods for job assignment and reassignment. These treated each resource as an independent entity with its own constraints, as there was no clean way to balance one resource against another. Our method has been tested by simulations, as well as real executions, and was found to perform well.

This paper describes a framework for parallel computing in a locally confined, scalable computing cluster (SCC) using Java agents. The framework consists of a programming model with agents and asynchronous invocations, and a scheme for adaptive placement of multiple agents in an SCC. Our scheme is geared to improve the overall performance by a dynamic match between the available cluster resources and the execution requirements of the agents. This is accomplished by agent migrations among the nodes using on-line algorithms for load leveling and reduction of the interagent communication overhead. Simulations of several examples show that our scheme outperforms a static agent placement scheme by as much as 40% for the test cases. © 1998 John Wiley & Sons, Ltd.

Execution of functional programs on distributed-memory multiprocessors gives rise to the problem of evaluating expressions that are shared between several Processing Elements (PEs). One of the main difficulties of solving this problem is that, for a given shared expression, it is not known in advance whether realizing the sharing is more cost effective than duplicating its evaluation. Realizing the sharing requires coordination between the sharing PEs to ensure that the shared expression is evaluated only once. This coordination involves relatively high communication costs, and is therefore only worthwhile when the shared expressions require much computation time to evaluate. In contrast, when the shared expression is not computation intensive, it is more cost effective to duplicate the evaluation, and thus avoid the communication overhead costs. This dilemma of deciding whether to duplicate the work or to realize the sharing stems from the unknown computation time that is required to evaluate a shared expression. This computation time is difficult to estimate due to unknown run-time evolution of loops and recursion that may be part of the expression. This paper presents an on-line (run-time) algorithm that decides which of the expressions that are shared between several PEs should be evaluated only once, and which expressions should be evaluated locally by each sharing PE. By applying competitive considerations, the algorithm manages to exploit sharing of computation-intensive expressions, while it duplicates the evaluation of expressions that require little time to compute. The algorithm accomplishes this goal even though it has no a priori knowledge of the amount of computation that is required to evaluate the shared expression. We show that this algorithm is competitive with a hypothetical optimal off-line algorithm, which does have such knowledge, and we prove that the algorithm is deadlock free. Furthermore, this algorithm does not require any programmer intervention, it has low overhead, and it is designed to run on a wide variety of distributed systems.

The paper presents novel embeddings of various classical topologies into the OPAM multicomputer. OPAM consists of a large number of processors that are connected by a two level, crossbar based interconnection network. The network combines a large, optical circuit-switched crossbar (reconfigurable network), with many small, packet-switching crossbars. The necessary embedding is very different than classical approaches. The goal in our case is to minimize routing decisions, so that communication requests can be satisfied by passing through two small crossbars. We show how to map parallel programs to this architecture using graph contraction notations. The family of parallel programs that we consider consists of multiple processes and communication links that are represented by connected, regular graphs such as rings, trees, two dimensional grids, cube connected cycles and hypercubes. In each case we show how to partition the vertex set of the program's graph to subsets, and how to assign each subset a cluster of processors in order to realize the topology of the given problem. In some of the cases we also prove that our partition and assignment algorithms are optimal.

Abstract This paper presents a toolkit for supporting the execution of coarse‐grain, parallel (distributed) applications under the MOSIX multicomputer operating system. These tools use standard UNIX System V process control and message‐passing facilities, as well as the dynamic process migration mechanisms of MOSIX. The MPE tools can be used to modify sequential applications that were originally written for execution in a uniprocessor environment, to run efficiently in a distributed environment, consisting of several loosely coupled independent computers that communicate by messages. After presenting the MPE tools, the paper gives examples of several sequential algorithms that have been modified for execution in such a distributed multicomputer, as well as the resulting execution speed‐ups that were obtained.

Abstract We present an on-line (run-time) algorithm that manages the granularity of parallel functional programs. The algorithm exploits useful parallelism when it exists, and ignores ineffective parallelism in programs that produce many small tasks. The idea is to balance the amount of local work with the cost of distributing the work. This is achieved by ensuring that for every parallel task spawned, an amount of work that equals the cost of the spawn is performed locally. We analyse several cases and compare the algorithm to the optimal execution. In most cases the algorithm competes well with the optimal algorithm, even though the optimal algorithm has information about the future evolution of the computation that is not available to the on-line algorithm. This is quite remarkable considering we have chosen extreme cases that have contradicting optimal executions. Moreover, we show that no other on-line algorithm can be consistently better than it. We also present experimental results that demonstrate the effectiveness of the algorithm.

Abstract LetGbe a simple connected undirected graph. A contraction φ ofGis a mapping fromG=G(V, E)toG'=G'(V', E'), whereG'is also a simple connected undirected graph, such that ifu, vφV(G)are connected by an edge (adjacent) inG, then either φ(u)= φ(v) orφ(u)and φ(v)are adjacent inG'. Consider a family of contractions, called bounded contractions, in which ∀v'∈V', the degree ofv'inG', DegG'(v'), satisfiesDegG'(v')≤ |φ−1(v')|, where φ−1(v')denotes the set of vertices inGmapped tov'under φ. These types of contractions are useful in the assignment (mapping) of parallel programs to a network of interconnected processors, where the number of communication channels of each processor is small. In this paper, we are concerned with bounded contractions of two‐dimensional grids such as mesh, hexagonal, and triangular arrays. For each of these graphs, we give contraction schemes that yield mappings of the minimal possible degree, such that the topology of the resulting graphs is identical to that of the desired target graph. We also prove that some contractions are not possible, regardless of their degree.

Abstract In this article we develop probabilistic algorithms for estimating the number of active nodes in a multicomputer system which consists of independent computers that are interconnected by a communication network. The algorithms are based on routine exchange of messages among the nodes of the multicomputer, using random routing. We show that each active node can find an ϵ‐estimate of the fraction λ of active nodes in the system in time that depends only on ϵ and λ. The underlying approach can be used for finding various global properties of distributed systems with decentralized control.

Abstract This paper describes the goals and the internal structure of MOS, a Multicomputer distributed Operating System. MOS is a general‐purpose time‐sharing operating system which makes a cluster of loosely connected independent homogeneous computers behave as a single‐machine UNIX system. The main goals of the system include network transparency, decentralized control, site autonomy and dynamic process migration. The main objective in the design of the system was to reduce the complexity of the system, while maintaining good performance. The internal structure of the system can be characterized by modularity, a high degree of information hiding, hierarchical organization and remote procedure calls.

Abstract This paper deals with the organization of a distributed load‐balancing policy for a multicomputer system which consists of a cluster of independent computers that are interconnected by a local area communication network. We introduce three algorithms necessary to maintain load balancing in this system: the local load algorithm, used by each processor to monitor its own load; the exchange algorithm, for exchanging load information between the processors, and the process migration algorithm that uses this information to dynamically migrate processes from overloaded to underloaded processors. The policy that we present is distributed, i.e. each processor uses the same policy. It is both dynamic, responding to load changes without using an a priori knowledge of the resources that each process requires; and stable, unnecessary overloading of a processor is minimized. We give the essential details of the implementation of the policy and initial results on its performance. Our results confirm the feasibility of building distributed systems that are based on network communication for uniform access, resource sharing and improved reliability, as well as the use of workstations without a secondary storage device.

Consider an m-processor distributed system having both local node and network traffic. Because users have incomplete information about the state of the queues at remote nodes, they can be tempted to shorten the expected completion time of a job by running multiple incarnations of each task in parallel on all m processors. To assess the temptation of such a “user countermeasure,” a job consisting of a sequence of n tasks to be performed sequentially is considered. Under simple assumptions about execution and network times, users can cut their expected job completion time by a factor of the square root of m. The implications of such user countermeasures on system design are discussed.

Abstract The steps necessary to extend the UNIX UNIX is a trademark of Bell Laboratories. time sharing system to a network which includes a central processor and a set of satellite processors is described. Software interfaces permit a program in the satellite processor to behave as if it were running in the central processor. Tasks are executed in parallel in several processors resulting in improved reliability and response time. The economics of such systems becomes more feasible with the reduction of the cost of CPUs and memories and the increasing demand for dedicated local computers.

Abstract The instruction mix of a CDC CYBER/74 computer in a university environment was monitored, and in this paper frequencies of execution for the most commonly used instructions are given. From these measurements we make a number of observations about several aspects of computing patterns. One observation is the fact that if we exclude the idle loop of the operating system, the percentage of occurrences for each type of instruction over various time intervals is constant. This fact is used to define a machine‐level software profile (MLSP) for the type of machine operations in the given computing environment. It is shown that the MLSP could be used to find machine utilization and the extent to which software takes advantage of machine architecture, and as a consistent method to improve the performance of a machine configuration.

This correspondence describes three algorithms of multiplicative type for ternary (base three) arithmetic using binary logic. The algorithms that are developed are multiplication, division, and natural logarithms. The method used is a normalization process of an operand to a specific constant.

In this paper we presentt family of techniques for the design of combinational networks whose objective is the reduction of the number of levels, subject to a constraint on the fan-in of the logic gates. We show that a Boolean expression with n literals and involving the connectivest AND and OR can be restructured so that the resulting network of AND and OR gates has depth at most Cllog2n + δ, where alis 1.81, 1.38, 1.18, and 1 for maximum fan-in l of 2,3,4, and 5, respectively. If we additionally require that the amount of equipment of the resulting network be bounded by a linear function of n, it is possible to bound the depth by 2 log2n with a fan-in of at most 3.

In this paper we construct algorithms and investigate the time required for the parallel evaluation of rational expressions using small numbers of processors. We define algorithms which compute a polynomial with n operations in 3n/(2p + 1) + Q(p2) time units with p processors and a general rational expression with n operations in 5n/(2p + 3) + 0(p2) time units. These algorithms are suitable for implementation on computers with restricted data access.

A bound for the number of steps that are required to evaluate Boolean expressions is obtained. It is shown that any Boolean expression of n distinct variables may be evaluated in $2\log _2 n - 1$ steps if sufficiently many processors are available.

The purpose of this paper is to develop a method for evaluation of certain elementary functions on a digital computer by the use of continued fractions. The time required for this evaluation is drastically reduced by using "short" operations like shift and add, instead of multiplications. Functional consistency is the most important factor that aliows the expansion of a function into a continued fraction. Several cases are discussed; in particular the solution of the quadratic equation is discussed in more detail to demonstrate the convergence of the method.

A method for the approximation of all the real roots of an n-order polynomial equation is developed. It is assumed that intervals containing the solutions are known. Bilinear transformations are used to approximate the solution. Convergence is achieved.