PICO. A prefix, a name, and an HP Labs project that began in 1995. PICO stood for “Program In, Chip Out”.

Molecular dynamics (MD) simulations have transformed our understanding of the nanoscale, driving breakthroughs in materials science, computational chemistry, and several other fields, including biophysics and drug design. Even on exascale supercomputers, however, runtimes are excessive for systems and timescales of scientific interest. Here, we demonstrate strong scaling of MD simulations on the Cerebras Wafer-Scale Engine. By dedicating a processor core for each simulated atom, we demonstrate a 457-fold improvement in timesteps per second versus the Frontier GPU-based Exascale platform, along with a large improvement in timesteps per unit energy. Reducing every year of runtime to less than a day unlocks currently inaccessible timescales of slow microstructure transformation processes that are critical for understanding material behavior and function.Our dataflow algorithm runs Embedded Atom Method (EAM) simulations at rates over 699k timesteps per second for problems with up to 800k atoms. This demonstrated performance is unprecedented for general-purpose processing cores.

The performance of CPU-based and GPU-based systems is often low for PDE codes, where large, sparse, and often structured systems of linear equations must be solved. Iterative solvers are limited by data movement, both between caches and memory and between nodes. Here we describe the solution of such systems of equations on the Cerebras Systems CS-1, a wafer-scale processor that has the memory bandwidth and communication latency to perform well. We achieve 0.86 PFLOPS on a single wafer-scale system for the solution by BiCGStab of a linear system arising from a 7-point finite difference stencil on a 600 × 595 × 1536 mesh, achieving about one third of the machine's peak performance. We explain the system, its architecture and programming, and its performance on this problem and related problems. We discuss issues of memory capacity and floating point precision. We outline plans to extend this work towards full applications.

Future systems dealing with big-data workloads will be severely constrained by the high performance and energy penalty imposed by data movement. This penalty can be reduced by storing datasets in DRAM or NVM main memory in compressed formats. Prior compressed memory systems have required significant changes to the operating system, thus limiting commercial viability. The first contribution of this paper is to integrate compression metadata with ECC metadata so that the compressed memory system can be implemented entirely in hardware with no OS involvement. We show that in such a system, read operations are unable to exploit the benefits of compression because the compressibility of the block is not known beforehand. To address this problem, we introduce a compressibility predictor that yields an accuracy of 97%. We also introduce a new data mapping policy that is able to maximize read/write parallelism and NVM endurance, when dealing with compressed blocks. Combined, our proposals are able to eliminate OS involvement and improve performance by 7% (DRAM) and 8% (NVM), and system energy by 12% (DRAM) and 14% (NVM), relative to an uncompressed memory system.

Summary form only given, as follows. The 25th year of IPDPS gives us the opportunity to look back and (to attempt) to assess what has gone wrong, what has gone well, and what came as a surprise, in the field of parallel and distributed processing. The panel members will give a few examples of striking events that took place in their area (covering Algorithms/ Applications/ Architectures/ Software). They will also give a short statement on how they would summarize the evolution of the field as a whole over the last 25 years.

For large-scale networks, high-radix switches reduce hop and switch count, which decreases latency and power. The ITRS projections for signal-pin count and per-pin bandwidth are nearly flat over the next decade, so increased radix in electronic switches will come at the cost of less per-port bandwidth. Silicon nanophotonic technology provides a long-term solution to this problem. We first compare the use of photonic I/O against an all-electrical, Cray YARC inspired baseline. We compare the power and performance of switches of radix 64, 100, and 144 in the 45, 32, and 22 nm technology steps. In addition with the greater off-chip bandwidth enabled by photonics, the high power of electrical components inside the switch becomes a problem beyond radix 64.

By providing high bandwidth chip-wide communication at low latency and low power, on-chip optics can improve many-core performance dramatically. Optical channels that connect many nodes and allow for single cycle cache-line transmissions will require fast, high bandwidth arbitration.

We expect that many-core microprocessors will push performance per chip from the 10 gigaflop to the 10 teraflop range in the coming decade. To support this increased performance, memory and inter-core bandwidths will also have to scale by orders of magnitude. Pin limitations, the energy cost of electrical signaling, and the non-scalability of chip-length global wires are significant bandwidth impediments. Recent developments in silicon nanophotonic technology have the potential to meet these off- and on-stack bandwidth requirements at acceptable power levels. Corona is a 3 D many-core architecture that uses nanophotonic communication for both inter-core communication and off-stack communication to memory or I/O devices. Its peak floating-point performance is 10 teraflops. Dense wavelength division multiplexed optically connected memory modules provide 10 terabyte per second memory bandwidth. A photonic crossbar fully interconnects its 256 low-power multithreaded cores at 20 terabyte per second bandwidth. We have simulated a 1024 thread Corona system running synthetic benchmarks and scaled versions of the SPLASH-2 benchmark suite. We believe that in comparison with an electrically-connected many-core alternative that uses the same on-stack interconnect power, Corona can provide 2 to 6 times more performance on many memory intensive workloads, while simultaneously reducing power.

We describe several new bottom-up approaches to problems in role engineering for Role-Based Access Control (RBAC). The salient problems are all NP-complete, even to approximate, yet we find that in instances that arise in practice these problems can be solved in minutes. We first consider role minimization, the process of finding a smallest collection of roles that can be used to implement a pre-existing user-to-permission relation. We introduce fast graph reductions that allow recovery of the solution from the solution to a problem on a smaller input graph. For our test cases, these reductions either solve the problem, or reduce the problem enough that we find the optimum solution with a (worst-case) exponential method. We introduce lower bounds that are sharp for seven of nine test cases and are within 3.4% on the other two. We introduce and test a new polynomial-time approximation that on average yields 2% more roles than the optimum. We next consider the related problem of minimizing the number of connections between roles and users or permissions, and we develop effective heuristic methods for this problem as well. Finally, we propose methods for several related problems.

In this paper, we present a measure associated with detection and inference of statistically anomalous clusters of a graph based on the likelihood test of observed and expected edges in a subgraph.This measure is adapted from spatial scan statistics for point sets and provides quantitative assessment for clusters.We discuss some important properties of this statistic and its relation to modularity and Bregman divergences.We apply a simple clustering algorithm to find clusters with large values of this measure in a variety of real-world data sets, and we illustrate its ability to identify statistically significant clusters of selected granularity.

We want to perform compile-time analysis of an SPMD program and place barriers in it to synchronize it correctly, minimizing the runtime cost of the synchronization. This is the barrier minimization problem. No full solution to the problem has been given previously.Here we model the problem with a new combinatorial structure, a nested family of sets of circular intervals. We show that barrier minimization is equivalent to finding a hierarchy of minimum cardinality point sets that cut all intervals. For a single loop, modeled as a simple family of circular intervals, a linear-time algorithm is known. We extend this result, finding a linear-time solution for nested circular interval families. This result solves the barrier minimization problem for general nested loops.

We investigate the problem of memory reuse in order to reduce the memory needed to store an array variable. We develop techniques that can lead to smaller memory requirements in the synthesis of dedicated processors or to more effective use by compiled code of software-controlled scratchpad memory. Memory reuse is well-understood for allocating registers to hold scalar variables. Its extension to arrays has been studied recently for multimedia applications, for loop parallelization, and for circuit synthesis from recurrence equations. In all such studies, the introduction of modulo operations to an otherwise affine mapping (of loop or array indices to memory locations) achieves the desired reuse. We develop here a new mathematical framework, based on critical lattices, that subsumes the previous approaches and provides new insight. We first consider the set of indices that conflict, those that cannot be mapped to the same memory cell. Next, we construct the set of differences of conflicting indices. We establish a correspondence between a valid modular mapping and a strictly-admissible integer lattice-one having no nonzero element in common with the set of conflicting index differences. The memory required by an optimal modular mapping is equal to the determinant of the corresponding lattice. The memory reuse problem is thus reduced to the (still interesting and nontrivial) problem of finding a strictly admissible integer lattice-of least determinant. We then propose and analyze several practical strategies for finding strictly admissible integer lattices, either optimal or optimal up to a multiplicative factor, and, hence, memory-saving modular mappings. We explain and analyze previous approaches in terms of our new framework.

We investigate the problem of memory reuse, for reducing the necessary memory size, in the context of compilation of dedicated processors. Memory reuse is a well-known concept when allocating registers (i.e., scalar variables). Its (recent) extension to arrays was studied mainly by Lefebvre and Feautrier (for loop parallelization) and by Quillere and Rajopadhye (for circuit synthesis based on recurrence equations). Both consider affine mappings of indices to data, with modulo expressions in the first and (mainly) projections in the second. We develop a mathematical framework based on (integral) critical lattices that subsumes all previous approaches and gives new insights into the problem. Our technique consists first in building an abstract representation of conflicting indices (equivalent in a multi-dimensional space to the interference graph for register allocation), then in defining an integral lattice, admissible for the set of differences of conflicting indices, used to build a valid modular allocation. We also show the link with critical lattices, successive minima, and basis reduction, and we analyze various strategies for lattice-based memory allocation.

We present two new results of importance in code generation for and synthesis of synchronously scheduled parallel processor arrays and multicluster VLIWs. The first is a new practical method for constructing a linear schedule for the iterations of a loop nest that schedules precisely one iteration per cycle on each of a prescribed set of processors. While this problem goes back to the era in which systolic computation was in vogue, it has defied practical solution until now. We provide a closed form solution that enables the enumeration of all such schedules. The second result is a new technique that reduces the cost of code or hardware whose function is to control the flow of data and predicate operations, and to generate memory addresses. The key idea is that by using the mathematical structure of any of the conflict-free schedules we construct, a very shallow recurrence can be developed to inexpensively update these quantities.

Program-in chip-out (PICO) is a system for automatically synthesizing embedded hardware accelerators from loop nests specified in the C programming language. A key issue confronted when designing such accelerators is the optimization of hardware by exploiting information that is known about the varying number of bits required to represent and process operands. In this paper, we describe the handling and exploitation of integer bitwidth in PICO. A bitwidth analysis procedure is used to determine bitwidth requirements for all integer variables and operations in a C application. Given known bitwidths for all variables, complex problems arise when determining a program schedule that specifies on which function unit (FU) and at what time each operation executes. If operations are assigned to FUs with no knowledge of bitwidth, bitwidth-related cost benefit is lost when each unit is built to accommodate the widest operation assigned. By carefully placing operations of similar width on the same unit, hardware costs are decreased. This problem is addressed using a preliminary clustering of operations that is based jointly on width and implementation cost. These clusters are then honored during resource allocation and operation scheduling to create an efficient width-conscious design. Experimental results show that exploiting integer bitwidth substantially reduces the gate count of PICO-synthesized hardware accelerators across a range of applications.

The PICO-N system automatically synthesizes embedded nonprogrammable accelerators to be used as co-processors for functions expressed as loop nests in C. The output is synthesizable VHDL that defines the accelerator at the register transfer level (RTL). The system generates a synchronous array of customized VLIW (very-long instruction word) processors, their controller local memory, and interfaces. The system also modifies the user's application software to make use of the generated accelerator. The user indicates the throughput to be achieved by specifying the number of processors and their initiation interval. In experimental comparisons, PICO-N designs are slightly more costly than hand-designed accelerators with the same performance.

We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of processor array synthesis. First, we provide a closed form solution that enables the enumeration of all conflict-free schedules. Then, we discuss the reduction of the cost of hardware whose function is to control the flow of data, enable or disable functional units, and generate memory addresses. We present a new technique for controlling the complexity of these housekeeping functions in a processor array. Both of these techniques have been incorporated into a software system for the automatic synthesis of hardware accelerators developed by HP Labs.

We investigate the problem of evaluating Fortran 90-style array expressions on massively parallel distributed-memory machines. On such a machine, an elementwise operation can be performed in constant time for arrays whose corresponding elements are in the same processor. If the arrays are not aligned in this manner, the cost of aligning them is part of the cost of evaluating the expression tree. The choice of where to perform the operation then affects this cost. We describe the communication cost of the parallel machine theoretically as a metric space; we model the alignment problem as that of finding a minimum-cost embedding of the expression tree into this space. We present algorithms based on dynamic programming that solve the embedding problem optimally for several communication cost metrics: multidimensional grids and rings, hypercubes, fat-trees, and the discrete metric. We also extend our approach to handle operations that change the shape of the arrays.

Compared to the customary column oriented approaches, block oriented, distributed memory sparse Cholesky factorization benefits from an asymptotic reduction in interprocessor communication volume and an asymptotic increase in the amount of concurrency that is exposed in the problem. Unfortunately, block oriented approaches (specifically, the block fan out method) have suffered from poor balance of the computational load. As a result, achieved performance can be quite low. The paper investigates the reasons for this load imbalance and proposes simple block mapping heuristics that dramatically improve it. The result is a roughly 20% increase in realized parallel factorization performance, as demonstrated by performance results from an Intel Paragon system. We have achieved performance of nearly 3.2 billion floating point operations per second with this technique on a 196 node Paragon system.>

Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distributed-memory parallel machine by requiring nonlocal data accesses. Determining array alignments that reduce communication is therefore a key issue in compiling such languages.

Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution, and a computation involving the regular section A(l:h:s), the local memory access sequence for any processor is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.

When a data-parallel language like FORTRAN 90 is compiled for a distributed-memory machine, aggregate data objects (such as arrays) are distributed across the processor memories. The mapping determines the amount of residual communication needed to bring operands of parallel operations into alignment with each other. A common approach is to break the mapping into two stages: first, an alignment that maps all the objects to an abstract template, and then a distribution that maps the template to the processors. We solve two facets of the problem of finding alignments that reduce residual communication: we determine alignments that vary in loops, and objects that should have replicated alignments. We show that loop-dependent mobile alignment is sometimes necessary for optimum performance, and we provide algorithms with which a compiler can determine good mobile alignments for objects within do loops. We also identify situations in which replicated alignment is either required by the program itself (via spread operations) or can be used to improve performance. We propose an algorithm based on network flow that determines which objects to replicate so as to minimize the total amount of broadcast communication in replication. This work on mobile and replicated alignment extends our earlier work on determining static alignment.

Article Free Access Share on The NAS parallel benchmarks—summary and preliminary results Authors: D. H. Bailey Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , E. Barszcz Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , J. T. Barton Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , D. S. Browning Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , R. L. Carter Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , L. Dagum Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , R. A. Fatoohi Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , P. O. Frederickson Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , T. A. Lasinski Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , R. S. Schreiber Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , H. D. Simon Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , V. Venkatakrishnan Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile , S. K. Weeratunga Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CA Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, Mail Stop T045-1, Moffett Field, CAView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 158–165https://doi.org/10.1145/125826.125925Published:01 August 1991Publication History 405citation1,162DownloadsMetricsTotal Citations405Total Downloads1,162Last 12 Months161Last 6 weeks25 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

An lmplementat]on of sparse LDL T and LU factorlzatlon and back substitution, based on a new scheme for storing sparse matrmes, is presented.The new method appears to be as efficmnt m terms of work and storage as existing schemes It is more amenable to efficmnt implementation on fast plpehned scmntlfic computers Categories and Subject Descriptors: G.