This is the best of times for high-performance computing. Our simulations continue to grow in complexity and sophistication, and they drive progress in the physical sciences and engineering, improving the world in myriad ways. Around the globe multiple plans are underway to achieve exascale performance by the early 2020's. Although considerable challenges remain, it seems that we can get to the exascale with familiar technologies and programming models. But while the immediate future looks bright, significant problems lie ahead. With Dennard scaling long-dead, device technologies won't save us from crippling power requirements for a 10 exaflop machine. And with Moore's Law sputtering towards end-of-life, performance is not improving much with each new generation of chips. There has been considerable excitement about the promise of quantum computing, reversible computing and other exotic concepts. But it seems likely that these will not become general-purpose approaches to computing for many years, if ever.

Despite decades of activity, parallel computing remains immature. Like much of computer science, advances in the field are driven by a mixture of theoretical insights and technological advances. But in parallel computing, the gap between theory and practice remains disconcertingly wide.Key theoretical concepts in parallel computing were developed in the seventies including P-completeness, PRAMs, boolean circuits, and more. A rich set of algorithms and complexity classes was built on top of these models, and these ideas influenced early thinking about parallel machines. But applied parallel computing today is little influenced by these concepts.In the past twenty years computational scientists and engineers have embraced parallelism as an essential computational tool for solving ever larger and more complex problems. By the mid-nineties, the computational science community had settled on a computing paradigm involving distributed memory machines programmed with explicit message passing. Although not elegant, this approach allows for portability and the use of inexpensive commodity hardware. This hardware is sufficiently different from the abstract models proposed in the seventies that insights from the theory community have had minimal impact on mainstream parallel computing practice.A variety of alternative theoretical models have been proposed in the interim that are more reflective of hardware realities than their counterparts from the seventies. These include the Bulk Synchronous Processing and LogP complexity models as well as computational abstractions like Active Messages partitioned global address space languages. But these concepts and tools have been consigned to niche roles within the larger MPI-dominated parallel computing world.However, several forces are rearranging the parallel computing landscape and will raise the importance of ideas and techniques from the theory community. The most familiar change is the rise of multi-core processors. The need for node-based parallelism will broaden the parallel computing community, and will also require significant modifications to existing parallel computing practice. But multicore processors are only an artifact of a more fundamental change that Moore's Law is bringing. Silicon is now essentially free, and this will allow for architectural innovation and potentially disruptive new processor designs. The decade of homogeneity in parallel architectures is coming to an end, and the implications for the parallel computing community could be profound.Simultaneous with this architectural revolution is an upheaval in the demands of applications. The computational physics and engineering applications that have dominated parallel computing are comparatively easy to parallelize. They have abundant coarse-grained parallelism that can be expressed in a bulk synchronous style, and they exhibit a high degree of spatial and temporal locality. But unstructured and adaptive grids, and the complexity of multiphysics simulations are already greatly taxing existing machines and programming models. Some newly emerging applications look to be incompatible with current mainstream approaches to parallel computing. As just one example, the analysis of very large social or communication networks has become important in the social sciences, but it is entirely unclear how to perform some of these computations using existing approaches. These new more data-centric and highly unstructured applications will require new ways of expressing and exploiting parallelism.As with the end of the Cretaceous period, these disruptive externalities will reshape the parallel computing ecosystem. New architectures and applications will require fresh thinking from both the applied and theoretical communities. The enormous challenges ahead will provide great opportunities for closer ties between theory and practice, to the betterment of all.

Despite decades of activity, parallel computing remains immature. Like much of computer science, advances in the field are driven by a mixture of theoretical insights and technological advances. But in parallel computing, the gap between theory and practice remains disconcertingly wide.

Search-based graph queries, such as finding short paths and isomorphic subgraphs, are dominated by memory latency. If input graphs can be partitioned appropriately, large cluster-based computing platforms can run these queries. However, the lack of compute-bound processing at each vertex of the input graph and the constant need to retrieve neighbors implies low processor utilization. Furthermore, graph classes such as scale-free social networks lack the locality to make partitioning clearly effective. Massive multithreading is an alternative architectural paradigm, in which a large shared memory is combined with processors that have extra hardware to support many thread contexts. The processor speed is typically slower than normal, and there is no data cache. Rather than mitigating memory latency, multithreaded machines tolerate it. This paradigm is well aligned with the problem of graph search, as the high ratio of memory requests to computation can be tolerated via multithreading. In this paper, we introduce the multithreaded graph library (MTGL), generic graph query software for processing semantic graphs on multithreaded computers. This library currently runs on serial machines and the Cray MTA-2, but Sandia is developing a run-time system that will make it possible to run MTGL-based code on symmetric multiprocessors. We also introduce a multithreaded algorithm for connected components and a new heuristic for inexact subgraph isomorphism We explore the performance of these and other basic graph algorithms on large scale-free graphs. We conclude with a performance comparison between the Cray MTA-2 and Blue Gene/Light for s-t connectivity.

The Cray MTA-2 system provides exceptional performance on a variety of sparse graph algorithms. Unfortunately, it was an extremely expensive platform. Cray is preparing an Eldorado platform that leverages the Cray XT3 network and system infrastructure while integrating a new revision of the MTA-2 processors that is pin compatible with the AMD Opteron socket. Unlike the MTA-2, this platform will have a more constrained network bisection bandwidth and will pay a high penalty for random memory accesses. This work assesses the hardware level scalability of the Eldorado platform on several graph algorithms.

A new trend in processor design is increased on-chip support for multithreading in the form of both chip multiprocessors and simultaneous multithreading. Recent research in database systems has begun to explore increased thread-level parallelism made possible by these new multicore and multithreaded processors. The question of how best to use this new technology remains open, particularly as the number of cores per chip and threads per core increase. In this paper we use an existing massively multithreaded architecture, the Cray MTA-2, to explore the implications that a larger degree of on-chip multithreading may have for parallelism in database operations. We find that parallelism in database operations is easy to achieve on the MTA-2 and that, with little effort, parallelism can be made to scale linearly with the number of available processor cores.

Many emerging large-scale data science applications require searching large graphs distributed across multiple memories and processors. This paper presents a distributed breadth- first search (BFS) scheme that scales for random graphs with up to three billion vertices and 30 billion edges. Scalability was tested on IBM BlueGene/L with 32,768 nodes at the Lawrence Livermore National Laboratory. Scalability was obtained through a series of optimizations, in particular, those that ensure scalable use of memory. We use 2D (edge) partitioning of the graph instead of conventional 1D (vertex) partitioning to reduce communication overhead. For Poisson random graphs, we show that the expected size of the messages is scalable for both 2D and 1D partitionings. Finally, we have developed efficient collective communication functions for the 3D torus architecture of BlueGene/L that also take advantage of the structure in the problem. The performance and characteristics of the algorithm are measured and reported.

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But, there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log W/sub T/ and |P| probe calls, where W/sub T/ and |P|, respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem and formulate it as a linearly constrained optimization problem, i.e., min /spl par/Ax/spl par//spl infin/, s.t. Bx=d. To avoid solving an intractable /spl infin/-norm optimization problem, we show that, in this case, minimizing the 2-norm is sufficient to minimize the /spl infin/-norm, which reduces the problem to the well-studied linearly constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization. Our experiments with molecular dynamics and overlapped domain decomposition applications proved the effectiveness of our methods with significant improvements in load balance. We also discuss how our techniques can be extended to heterogeneous parallel computers.

Many parallel applications require periodic redistribution of workloads and associated data. In a distributed memory computer, this redistribution can be difficult if limited memory is available for receiving messages. We propose a model for optimizing the exchange of messages under such circumstances which we call the minimum phase remapping problem. We first show that the problem is NP-complete, and then analyze several methodologies for addressing it. First, we show how the problem can be phrased as an instance of multicommodity flow. Next, we study a continuous approximation to the problem. We show that this continuous approximation has a solution which requires at most two more phases than the optimal discrete solution, but the question of how to consistently obtain a good discrete solution from the continuous problem remains open. We also devise a simple and practical approximation algorithm for the problem with a bound of 1.5 times the optimal number of phases. We also present an empirical study of variations of our algorithms which indicate that our approaches are quite practical.

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with $\log W_T$ and $|P|$ probe calls, where $W_T$ and $|P|$, respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem, and formulate it as a linearly constrained optimization problem, i.e., $ \min \|Ax\|_\∞,\; \rm s.t.\; Bx=d$. To avoid solving an intractable ∞-norm optimization problem, we show that in this case minimizing the 2-norm is sufficient to minimize the ∞-norm, which reduces the problem to the well-studied linearly-constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization.

Graph partitioning is an important tool for dividing work amongst processors of a parallel machine, but it is unsuitable for some important applications. Specifically, graph partitioning requires the work per processor to be a simple sum of vertex weights. For many applications, this assumption is not true — the work (or memory) is a complex function of the partition. In this paper we describe a general framework for addressing such partitioning problems and investigate its utility on two applications — partitioning so that overlapped subdomains are balanced and partitioning to minimize the sum of computation plus communication time.

Discrete ordinates methods are commonly used to simulate radiation transport for fire or weapons modeling. The computation proceeds by sweeping the flux across a grid. A particular cell cannot be computed until all the cells immediately upwind of it are finished. If the directed dependence graph for the grid cells contains a cycle then sweeping methods will deadlock. This can happen in unstructured grids and time stepped problems where the grid is allowed to deform. In this paper we present a parallel algorithm to detect cycles in the dependence graphs present in these grids as well as an implementation and experimental results on shared and distributed memory machines.

The design of general-purpose dynamic load-balancing tools for parallel applications is more challenging than the design of static partitioning tools. Both algorithmic and software engineering issues arise. We have addressed many of these issues in the design of the Zoltan dynamic load-balancing library. Zoltan has an object-oriented interface that makes it easy to use and provides separation between the application and the load-balancing algorithms. It contains a suite of dynamic load-balancing algorithms, including both geometric and graph-based algorithms. Its design makes it valuable both as a partitioning tool for a variety of applications and as a research test-bed for new algorithmic development. In this paper, we describe Zoltan's design and demonstrate its use in an unstructured-mesh finite element application.

The method of discrete ordinates is commonly used to solve the Boltzmann radiation transport equation for applications ranging from simulations of fires to weapons effects. The equations are most efficiently solved by sweeping the radiation flux across the computational grid. For unstructured grids this poses several interesting challenges, particularly when implemented on distributed-memory parallel machines where the grid geometry is spread across processors. We describe a asynchronous, parallel, message-passing algorithm that performs sweeps simultaneously from many directions across unstructured grids. We identify key factors that limit the algorithm’s parallel scalability and discuss two enhancements we have made to the basic algorithm: one to prioritize the work within a processor’s subdomain and the other to better decompose the unstructured grid across processors. Performance results are give for the basic and enhanced algorithms implemented withi a radiation solver running on hundreds of processors of Sandia’s Intel Tflops machine and DEC-Alpha CPlant cluster.

Many parallel applications require periodic redistribution of workloads and associated data. In a distributed memory computer, this redistribution can be difficult if limited memory is available for receiving messages. We propose a model for optimizing the exchange of messages under such circumstances which we call the minimum phase remapping problem. We first show that the problem is NP-Complete, and then analyze several methodologies for addressing it. First, we show how the problem can be phrased as an instance of multi-commodity flow. Next, we study a continuous approximation to the problem. We show that this continuous approximation has a solution which requires at most two more phases than the optimal discrete solution, but the question of how to consistently obtain a good discrete solution from the continuous problem remains open. Finally, we devise a simple and practical approximation algorithm for the problem with a bound of 1.5 times the optimal number of phases.

A number of computational procedures employ multiple grids on which solutions are computed. For example, in multi-physics simulations a primary grid may be used to compute mechanical deformation of an object while a secondary grid is used for thermal conduction calculations. When modeling coupled thermo-mechanical effects, solution data must be interpolated back and forth between the grids each timestep. On a parallel machine, this grid transfer operation can be challenging if the two grids are decomposed to processors differently for reasons of computational efficiency. If the grids move or adapt separately, the complexity of the operation is compounded. In this paper we describe a grid transfer algorithm suitable for massively parallel codes which use multiple grids. It uses a rendezvous technique wherein a third decomposition is used to search for elements in one grid that contain nodal points of the other. This has the advantage of enabling the grid transfer to be load-balanced separately from the remainder of the computations. The algorithm has been implemented as an object-oriented tool for the multi-physics code SIERRA, currently under development at Sandia. Performance and scalability results for the grid transfer operation running on the Intel/Sandia TFLOPS supercomputer are presented.

The main cost of solving a linear programming problem using an interior point method is usually the cost of solving a series of sparse, symmetric linear systems of equations, AΘA T x = b. These systems are typically solved using a sparse direct method. The first step in such a method is a reordering of the rows and columns of the matrix to reduce fill in the factor and/or reduce the required work. This article evaluates several methods for performing fill-reducing ordering on a variety of large-scale linear programming problems. We find that a new method, based on the nested dissection heuristic, provides significantly better orderings than the most commonly used ordering method, minimum degree.

In applications ranging from DNA sequencing through archeological dating to sparse matrix reordering, a recurrent problem is the sequencing of elements in such a way that highly correlated pairs of elements are near each other. That is, given a correlation function f reflecting the desire for each pair of elements to be near each other, find all permutations $\pi$ with the property that if $\pi(i) < \pi(j) < \pi(k)$ then $f(i,j) \ge f(i,k)$ and $f(j,k) \ge f(i,k)$. This seriationproblem is a generalization of the well-studied consecutive ones problem. We present a spectral algorithm for this problem that has a number of interesting features. Whereas most previous applications of spectral techniques provide only bounds or heuristics, our result is an algorithm that correctly solves a nontrivial combinatorial problem. In addition, spectral methods are being successfully applied as heuristics to a variety of sequencing problems, and our result helps explain and justify these applications.

The graph partitioning problem is that of dividing the vertices of a graph into sets of specified sizes such that few edges cross between sets. This NP-complete problem arises in many important scientific and engineering problems. Prominent examples include the decomposition of data structures for parallel computation, the placement of circuit elements and the ordering of sparse matrix computations. We present a multilevel algorithm for graph partitioning in which the graph is approximated by a sequence of increasingly smaller graphs. The smallest graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs. A variant of the Kernighan-Lin algorithm is applied periodically to refine the partition. The entire algorithm can be implemented to execute in time proportional to the size of the original graph. Experiments indicate that, relative to other advanced methods, the multilevel algorithm produces high quality partitions at low cost.

Many scientific and engineering applications require a detailed analysis of complex systems with strongly coupled fluid flow, thermal energy transfer mass transfer and nonequilibrium chemical reactions. Here we describe the performance of a newly developed application code, SALSA, designed to simulate these complex flows on large-scale parallel machines such as the Intel Paragon. SALSA uses 3D unstructured finite element methods to model geometrically complex flow systems. Fully implicit time integration, multicomponent mass transport and general gas phase and surface species non-equilibrium chemical kinetics are employed. Using these techniques we have obtained over 65 Gflop/s on a 3D chemically reacting flow CVD problem for Silicon Carbide (SiC) deposition. This represents 46% of the peak performance of our 1904 node Intel Paragon, an outstanding computational rate in view of the required unstructured data communication.>

The graph realization problem is that of computing the relative locations of a set of vertices placed in Euclidean space, relying only upon some set of inter-vertex distance measurements. This paper is concerned with the closely related problem of determining whether or not a graph has a unique realization. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If one assumes the vertex locations are unrelated, then the uniqueness question can be approached from a purely graph theoretic angle that ignores edge lengths. This paper identifies three necessary graph theoretic conditions for a graph to have a unique realization in any dimension. Efficient sequential and NC algorithms are presented for each condition, although these algorithms have very different flavors in different dimensions.