Molecular dynamics (MD) simulation, a computationally intensive method that provides invaluable insights into the behavior of biomolecules, typically requires large-scale parallelization. Implementation of fast parallel MD simulation demands both high bandwidth and low latency for inter-node communication, but in current semiconductor technology, neither of these properties is scaling as quickly as intra-node computational capacity. This disparity in scaling necessitates architectural innovations to maximize the utilization of computational units. For Anton 3, the latest in a family of highly successful special-purpose supercomputers designed for MD simulations, we thus designed and built a completely new specialized network as part of our ASIC. Tightly integrating this network with specialized computation pipelines enables Anton 3 to perform simulations orders of magnitude faster than any general-purpose supercomputer, and to outperform its predecessor, Anton 2 (the state of the art prior to Anton 3), by an order of magnitude. In this paper, we present the three key features of the network that contribute to the high performance of Anton 3. First, through architectural optimizations, the network achieves very low end-to-end inter-node communication latency for fine-grained messages, allowing for better overlap of computation and communication. Second, novel application-specific compression techniques reduce the size of most messages sent between nodes, thereby increasing effective inter-node bandwidth. Lastly, a new hardware synchronization primitive, called a network fence, supports fast fine-grained synchronization tailored to the data flow within a parallel MD application. These application-driven specializations to the network are critical for Anton 3’s MD simulation performance advantage over all other machines.

Protein-protein interactions (PPIs) are ubiquitous biomolecular processes that are central to virtually all aspects of cellular function. Identifying small molecules that modulate specific disease-related PPIs is a strategy with enormous promise for drug discovery. The design of drugs to disrupt PPIs is challenging, however, because many potential drug-binding sites at PPI interfaces are "cryptic": When unoccupied by a ligand, cryptic sites are often flat and featureless, and thus not readily recognizable in crystal structures, with the geometric and chemical characteristics of typical small-molecule binding sites only emerging upon ligand binding. The rational design of small molecules to inhibit specific PPIs would benefit from a better understanding of how such molecules bind at PPI interfaces. To this end, we have conducted unbiased, all-atom MD simulations of the binding of four small-molecule inhibitors (SP4206 and three SP4206 analogs) to interleukin 2 (IL2)-which performs its function by forming a PPI with its receptor-without incorporating any prior structural information about the ligands' binding. In multiple binding events, a small molecule settled into a stable binding pose at the PPI interface of IL2, resulting in a protein-small-molecule binding site and pose virtually identical to that observed in an existing crystal structure of the IL2-SP4206 complex. Binding of the small molecule stabilized the IL2 binding groove, which when the small molecule was not bound emerged only transiently and incompletely. Moreover, free energy perturbation (FEP) calculations successfully distinguished between the native and non-native IL2-small-molecule binding poses found in the simulations, suggesting that binding simulations in combination with FEP may provide an effective tool for identifying cryptic binding sites and determining the binding poses of small molecules designed to disrupt PPI interfaces by binding to such sites.

• Understand biomolecular systems through their motions •Numerical integration of Newton's laws of motion — Model atoms as point masses — Compute forces on every atom based on current positions — Update atom velocities and positions in discrete time steps of a few femtoseconds • Force computation described by a model: the force field

Anton 3 is the newest member in a family of supercomputers specially designed for atomic-level simulation of molecules relevant to biology (e.g., DNA, proteins, and drug molecules). Anton 3 achieves order-of-magnitude improvements in time-to-solution over its predecessor, Anton 2 (the current state of the art), and is over 100-fold faster than any other currently available supercomputer, thereby enabling broad new avenues of research on critical questions in biology and drug discovery. This speedup means that a 512-node Anton 3 simulates a million atoms at over 100 microseconds per day. Furthermore, Anton 3 attains this performance while consuming an order of magnitude less energy per simulated microsecond than any other machine. Like its predecessors, Anton 3 was designed from the ground up around a new custom chip to best exploit the capabilities offered by new technologies. We present here the main architectural and algorithmic developments that were necessary to achieve such significant advances.

Parallel implementations of molecular dynamics (MD) simulation require significant inter-node communication, but off-chip communication bandwidth is not scaling as quickly as on-chip logic density. We present three network features targeting this problem that have been implemented in Anton 2, a massively parallel special-purpose supercomputer for MD simulations. The first is a mechanism to dynamically identify packets that do not need to be delivered to all endpoints within a multicast tree, these packets are filtered to conserve network bandwidth. The second is hardware for in-network reductions that supports over a thousand concurrent neighbourhood reductions per node and fast all-to-all global reductions. The third is a log-weight synchronization mechanism for multicast-reduce communication patterns that can be used to efficiently detect the completion of reduction operations when the number of summands is difficult to predict. We use the combination of packet filtering, in-network reductions and log-weight synchronization to decrease the communication requirements of MD simulations by as much as 51% on Anton 2, yielding application-level performance improvements of up to 14%.

The design of network architectures has become increasingly complex as the chips connected by inter-node networks have emerged as distributed systems in their own right, complete with their own on-chip networks. In Anton 2, a massively parallel special-purpose supercomputer for molecular dynamics simulations, we managed this complexity by reusing the on-chip network as a switch for inter-node traffic. This unified network approach introduces several design challenges. Maintaining fairness within the inter-node network is difficult, as each hop becomes a sequence of many on-chip routing decisions. We addressed this problem with an inverse-weighted arbiter that ensures fairness with low implementation costs. Balancing the load of inter-node traffic across the on-chip network is also critical, and we adopted an optimization approach to design an appropriate routing algorithm. Finally, the on-chip routers carry inter-node traffic, so they must implement inter-node virtual channels to avoid deadlock. In order to keep the routers small and fast, we developed a deadlock-free routing algorithm that reduces the number of virtual channels by one-third relative to previous approaches. The resulting Anton 2 network implementation efficiently utilizes its inter-node channels and provides low messaging latency, while occupying a modest amount of silicon area.

Anton 2 is a second-generation special-purpose supercomputer for molecular dynamics simulations that achieves significant gains in performance, programmability, and capacity compared to its predecessor, Anton 1. The architecture of Anton 2 is tailored for fine-grained event-driven operation, which improves performance by increasing the overlap of computation with communication, and also allows a wider range of algorithms to run efficiently, enabling many new software-based optimizations. A 512-node Anton 2 machine, currently in operation, is up to ten times faster than Anton 1 with the same number of nodes, greatly expanding the reach of all-atom bio molecular simulations. Anton 2 is the first platform to achieve simulation rates of multiple microseconds of physical time per day for systems with millions of atoms. Demonstrating strong scaling, the machine simulates a standard 23,558-atom benchmark system at a rate of 85 μs/day -- 180 times faster than any commodity hardware platform or general-purpose supercomputer.

The epidermal growth factor receptor (EGFR) plays a key role in regulating cell proliferation, migration, and differentiation, and aberrant EGFR signaling is implicated in a variety of cancers. EGFR signaling is triggered by extracellular ligand binding, which promotes EGFR dimerization and activation. Ligand-binding measurements are consistent with a negatively cooperative model in which the ligand-binding affinity at either binding site in an EGFR dimer is weaker when the other site is occupied by a ligand. This cooperativity is widely believed to be central to the effects of ligand concentration on EGFR-mediated intracellular signaling. Although the extracellular portion of the human EGFR dimer has been resolved crystallographically, the crystal structures do not reveal the structural origin of this negative cooperativity, which has remained unclear. Here we report the results of molecular dynamics simulations suggesting that asymmetrical interactions of the two binding sites with the membrane may be responsible (perhaps along with other factors) for this negative cooperativity. In particular, in our simulations the extracellular domains of an EGFR dimer spontaneously lay down on the membrane in an orientation in which favorable membrane contacts were made with one of the bound ligands, but could not be made with the other. Similar interactions were observed when EGFR was glycosylated, as it is in vivo.

Exploiting parallelism to accelerate a computation typically involves dividing it into many small tasks that can be assigned to different processing elements. An efficient execution schedule for these tasks can be difficult or impossible to determine in advance, however, if there is uncertainty as to when each task's input data will be available. Ideally, each task would run in direct response to the arrival of its input data, thus allowing the computation to proceed in a fine-grained event-driven manner. Realizing this ideal is difficult in practice, and typically requires sacrificing flexibility for performance.

Cascade is a cycle-based C++ simulation infrastructure used in the design and verification of two successive versions of Anton, a specialized machine designed for high-speed molecular dynamics computation. Cascade was engineered to address the size and speed challenges inherent in simulating massively parallel special-purpose machines. It provides a lightweight programming interface, rich debugging support, tight Verilog integration, fast multithreaded execution, and low memory overhead. Here, we describe the core features of Cascade that proved most valuable for our simulation efforts.

Special-purpose computing hardware can provide significantly better performance and power efficiency for certain applications than general-purpose processors. Even within a single application area, however, a special-purpose machine can be far more valuable if it is capable of efficiently supporting a number of different computational methods that, taken together, expand the machine's functionality and range of applicability. We have previously described a massively parallel special-purpose supercomputer, called Anton, and have shown that it executes traditional molecular dynamics simulations orders of magnitude faster than the previous state of the art. Here, we describe how we extended Anton's software to support a more diverse set of methods, allowing scientists to simulate a broader class of biological phenomena at extremely high speeds. Key elements of our approach, which exploits Anton's tightly integrated hardwired pipelines and programmable cores, are applicable to the hardware and software design of various other specialized or heterogeneous parallel computing platforms.

Network-on-Chips (NoCs) are becoming integral parts of modern microprocessors as the number of cores and modules integrated on a single chip continues to increase. Research and development of future NoC technology relies on accurate modeling and simulations to evaluate the performance impact and analyze the cost of novel NoC architectures. In this work, we present BookSim, a cycle-accurate simulator for NoCs. The simulator is designed for simulation flexibility and accurate modeling of network components. It features a modular design and offers a large set of configurable network parameters in terms of topology, routing algorithm, flow control, and router microarchitecture, including buffer management and allocation schemes. BookSim furthermore emphasizes detailed implementations of network components that accurately model the behavior of actual hardware. We have validated the accuracy of the simulator against RTL implementations of NoC routers.

We describe a high-performance digit-recurrence algorithm for computing exactly rounded reciprocals, square roots, and reciprocal square roots in hardware at a rate of three result bits - one radix-8 digit - per recurrence iteration. To achieve a single-cycle recurrence at a short cycle time, we adapted the digit-by-rounding algorithm, which is normally applied at much higher radices, for efficient operation at radix 8. Using this approach avoids in the recurrence step the lookup table required by SRT - the usual algorithm used for hardware digit recurrences. The increasing access latency of this table, the size of which grows super linearly in the radix, limits high-frequency SRT implementations to radix 4 or lower. We also developed a series of novel optimizations focused on further reducing the critical path through the recurrence. We propose, for example, decreasing data path widths to a point where erroneous results sometimes occur and then correcting these errors off the critical path. We present a specific implementation that computes any of these functions to 31 bits of precision in 13 cycles. Our implementation achieves a cycle time only 11% longer than the best reported SRT design for the same functions, yet delivers results in five fewer cycles. Finally, we show that even at lower radices, a digit-by-rounding design is likely to have a shorter critical path than one using SRT at the same radix.

Digit-by-rounding algorithms enable efficient hardware implementations of algebraic functions such as the reciprocal, square root, or reciprocal square root, but certifying the correctness of such algorithms is a nontrivial endeavor. Traditionally, sufficient conditions for correctness are derived as closed-form formulae relating key design parameters. These sufficient conditions, however, often prove stricter than necessary, excluding correct and efficient designs. In this paper, we present a rigorous, computer-aided method for correctness certification that better approximates the necessary conditions, lowering the risk of rejecting correct designs. We also present two specific applications of this method. First, when applied to a conventional digit-by-rounding reciprocal square root design, our method enabled a fourfold reduction in lookup table size relative to the minimum dictated by a standard sufficient condition. Second, our method certified the correctness of a novel reciprocal square root design that we developed to parallelize two computational steps whose sequential execution lies on the critical path of conventional designs. The difficulty in deriving closed-form sufficient conditions to ascertain this design's correctness provided the original motivation for development of the new certification method.

Most pseudorandom number generators (PRNGs) scale poorly to massively parallel high-performance computation because they are designed as sequentially dependent state transformations. We demonstrate that independent, keyed transformations of counters produce a large alternative class of PRNGs with excellent statistical properties (long period, no discernable structure or correlation). These counter-based PRNGs are ideally suited to modern multi-core CPUs, GPUs, clusters, and special-purpose hardware because they vectorize and parallelize well, and require little or no memory for state. We introduce several counter-based PRNGs: some based on cryptographic standards (AES, Threefish) and some completely new (Philox). All our PRNGs pass rigorous statistical tests (including TestU01's BigCrush) and produce at least 264 unique parallel streams of random numbers, each with period 2128 or more. In addition to essentially unlimited parallel scalability, our PRNGs offer excellent single-chip performance: Philox is faster than the CURAND library on a single NVIDIA GPU.

Strong scaling of scientific applications on parallel architectures is increasingly limited by communication latency. This paper describes the techniques used to mitigate latency in Anton, a massively parallel special-purpose machine that accelerates molecular dynamics (MD) simulations by orders of magnitude compared with the previous state of the art. Achieving this speedup required a combination of hardware mechanisms and software constructs to reduce network latency, sender and receiver overhead, and synchronization costs. Key elements of Anton's approach, in addition to tightly integrated communication hardware, include formulating data transfer in terms of counted remote writes, leveraging fine-grained communication, and establishing fixed, optimized communication patterns. Anton delivers software-to-software inter-node latency significantly lower than any other large-scale parallel machine, and the total critical-path communication time for an Anton MD simulation is less than 4% that of the next fastest MD platform.

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macromolecules could in principle lead to important scientific advances and provide a powerful new tool for drug discovery. A wide range of biologically important processes, however, occur over time scales on the order of a millisecond ~ several orders of magnitude beyond the duration of the longest previous MD simulations. Our research group has completed a specialized, massively parallel machine called Anton, which is capable of calculating millisecond-scale molecular trajectories at an atomic level of detail. The machine has greatly extended the power of simulation as a tool for understanding the structure and dynamics of proteins, and has already allowed us to observe and analyze important biological phenomena that have not previously been accessible to either computational or experimental study.

Anton is a recently completed special-purpose supercomputer designed for molecular dynamics (MD) simulations of biomolecular systems. The machine's specialized hardware dramatically increases the speed of MD calculations, making possible for the first time the simulation of biological molecules at an atomic level of detail for periods on the order of a millisecond---about two orders of magnitude beyond the previous state of the art. Anton is now running simulations on a timescale at which many critically important, but poorly understood phenomena are known to occur, allowing the observation of aspects of protein dynamics that were previously inaccessible to both computational and experimental study. Here, we report Anton's performance when executing actual MD simulations whose accuracy has been validated against both existing MD software and experimental observations. We also discuss the manner in which novel algorithms have been coordinated with Anton's co-designed, application-specific hardware to achieve these results.

Anton is a recently completed special-purpose supercomputer designed for molecular dynamics (MD) simulations of biomolecular systems. The machine's specialized hardware dramatically increases the speed of MD calculations, making possible for the first time the simulation of biological molecules at an atomic level of detail for periods on the order of a millisecond---about two orders of magnitude beyond the previous state of the art. Anton is now running simulations on a timescale at which many critically important, but poorly understood phenomena are known to occur, allowing the observation of aspects of protein dynamics that were previously inaccessible to both computational and experimental study. Here, we report Anton's performance when executing actual MD simulations whose accuracy has been validated against both existing MD software and experimental observations. We also discuss the manner in which novel algorithms have been coordinated with Anton's co-designed, application-specific hardware to achieve these results.

Anton, a massively parallel special-purpose machine for molecular dynamics simulations, performs a 32x32x32 FFT in 3.7 microseconds and a 64x64x64 FFT in 13.3 microseconds on a configuration with 512 nodes---an order of magnitude faster than all other FFT implementations of which we are aware. Achieving this FFT performance requires a coordinated combination of computation and communication techniques that leverage Anton's underlying hardware mechanisms. Most significantly, Anton's communication subsystem provides over 300 gigabits per second of bandwidth per node, message latency in the hundreds of nanoseconds, and support for word-level writes and single-ended communication. In addition, Anton's general-purpose computation system incorporates primitives that support the efficient parallelization of small 1D FFTs. Although Anton was designed specifically for molecular dynamics simulations, a number of the hardware primitives and software implementation techniques described in this paper may also be applicable to the acceleration of FFTs on general-purpose high-performance machines.

Design verification of complex digital circuits typically starts only after the register-transfer level (RTL) description is complete. This frequently makes verification more difficult than necessary because logic that is intrinsically hard to verify, such as memories, counters and deep first-in, first-out (FIFO) structures, becomes immutable in the design. This paper proposes a new approach that exploits formal verification of conditional coverage points with the goal of early identification of hard-to-verify logic. We use the difficulty of formal verification problems as an early estimator of the verification complexity of a design. While traditional verification methods consider conditional coverage only in the design verification phase, we describe an approach that uses conditional coverage at a much earlier stage---the design phase, during which changes to the RTL code are still possible. The method is illustrated using real examples from the verification of an ASIC designed for a specialized supercomputer.

An effective special-purpose supercomputer for molecular dynamics (MD) requires much more than high-performance acceleration of computational kernels: such accelerators must be balanced with general-purpose computation and communication resources. Achieving this balance was a significant challenge in the design of Anton, a parallel machine that will accelerate MD simulations by several orders of magnitude. Anton executes its most computationally demanding calculations on a highly specialized, enormously parallel, but largely non-programmable high-throughput interaction subsystem (HTIS). Other elements of the simulation have a less uniform algorithmic structure, and may also change in response to future advances in physical models and simulation techniques. Such calculations are executed on Antonpsilas flexible subsystem, which combines programmability with the computational power required to avoid ldquoAmdahlpsilas Lawrdquo bottlenecks arising from the extremely high throughput of the HTIS. Antonpsilas flexible subsystem is a heterogeneous multiprocessor with 12 cores, each organized around a 128-bit data path. This subsystem includes hardware support for synchronization, data transfer and certain types of particle interactions, along with specialized instructions for geometric operations. All aspects of the flexible subsystem were designed specifically to accelerate MD simulations, and although it relies primarily on what may be regarded as ldquogeneral-purposerdquo processors, even this subsystem contains more application-specific features than many recently proposed ldquospecializedrdquo architectures.

Anton is a massively parallel special-purpose supercomputer designed to accelerate molecular dynamics (MD) simulations by several orders of magnitude, making possible for the first time the atomic-level simulation of many biologically important phenomena that take place over microsecond to millisecond time scales. The majority of the computation required for MD simulations involves the calculation of pairwise interactions between particles and/or gridpoints separated by no more than some specified cutoff radius. In Anton, such range-limited interactions are handled by a high-throughput interaction subsystem (HTIS). The HTIS on each of Antonpsilas 512 ASICs includes 32 computational pipelines running at 800 MHz, each producing a result on every cycle that would require approximately 50 arithmetic operations to compute on a general-purpose processor. In order to feed these pipelines and collect their results at a speed sufficient to take advantage of this computational power, Anton uses two novel techniques to limit inter- and intra-chip communication. The first is a recently developed parallelization algorithm for the range-limited N-body problem that offers major advantages in both asymptotic and absolute terms by comparison with traditional methods. The second is an architectural feature that processes pairs of points chosen from two point sets in time proportional to the product of the sizes of those sets, but with input and output volume proportional only to their sum. Together, these features allow Anton to perform pairwise interactions with very high throughput and unusually low latency, enabling MD simulations on time scales inaccessible to other general- and special-purpose parallel systems.

One of the major design verification challenges in the development of Anton, a massively parallel special-purpose machine for molecular dynamics, was to provide evidence that computations spanning more than a quadrillion clock cycles will produce valid scientific results. Our verification methodology addressed this problem by using a hierarchy of RTL, architectural, and numerical simulations. Block- and chip-level RTL models were verified by means of extensive co-simulation with a detailed C++ architectural simulator, ensuring that the RTL models could perform the same molecular dynamics computations as the architectural simulator. The output of the architectural simulator was compared to a parallelized numerical simulator that produces bitwise identical results to Anton, and is fast enough to verify the long-term numerical stability of computations on Anton. These explicit couplings between adjacent levels of the simulation hierarchy created a continuous verification chain from molecular dynamics to individual logic gates.

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macromolecules could in principle lead to important scientific advances and provide a powerful new tool for drug discovery. A wide range of biologically interesting phenomena, however, occur over time scales on the order of a millisecond - several orders of magnitude beyond the duration of the longest current MD simulations. Our research group is currently building a specialized, massively parallel machine, called Anton, which should soon be capable of executing millisecond-scale MD simulations of proteins at an atomic level of detail. Antonpsilas highly accelerated execution of such simulations is attributable in large part to specialized logic for the high-speed calculation of pairwise interactions between particles and/or gridpoints separated by no more than some specified cutoff radius.In particular, each of Anton's 512 ASICs, which are implemented using 90-nm technology,includes a "high-throughput interaction subsystem" incorporating 32 highly specialized pipelines running at 800 MHz. During every cycle, each of these pipelines produces a pairwise-interaction result that would require approximately 50 arithmetic operations to calculate on a general-purpose processor. Novel algorithms and architectural features are used to greatly reduce the requirements for inter- and intra-chip communication, allowing Anton to feed these pipelines and collect their results at a speed sufficient to take advantage of the machine's computational power. The ASIC also includes a "flexible subsystem" based on eight programmable "geometry cores", each containing eight arithmetic pipelines. This talk will provide an overview of our work on parallel algorithms and machine architectures for high-speed MD simulation, with special attention to the respective roles of specialized vs. general-purpose hardware, and to the techniques used to minimize communication at various levels within the system.

As parallel algorithms and architectures drive the longest molecular dynamics (MD) simulations towards the millisecond scale, traditional sequential post-simulation data analysis methods are becoming increasingly untenable. Inspired by the programming interface of Google's MapReduce, we have built a new parallel analysis framework called HiMach, which allows users to write trajectory analysis programs sequentially, and carries out the parallel execution of the programs automatically. We introduce (1) a new MD trajectory data analysis model that is amenable to parallel processing, (2) a new interface for defining trajectories to be analyzed, (3) a novel method to make use of an existing sequential analysis tool called VMD, and (4) an extension to the original MapReduce model to support multiple rounds of analysis. Performance evaluations on up to 512 cores demonstrate the efficiency and scalability of the HiMach framework on a Linux cluster.

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macro-molecules could in principle provide answers to some of the most important currently outstanding questions in the fields of biology, chemistry and medicine. A wide range of biologically interesting phenomena, however, occur over time scales on the order of a millisecond--about three orders of magnitude beyond the duration of the longest current MD simulations.

Although molecular dynamics (MD) simulations of biomolecular systems often run for days to months, many events of great scientific interest and pharmaceutical relevance occur on long time scales that remain beyond reach. We present several new algorithms and implementation techniques that significantly accelerate parallel MD simulations compared with current state-of-the-art codes. These include a novel parallel decomposition method and message-passing techniques that reduce communication requirements, as well as novel communication primitives that further reduce communication time. We have also developed numerical techniques that maintain high accuracy while using single precision computation in order to exploit processor-level vector instructions. These methods are embodied in a newly developed MD code called Desmond that achieves unprecedented simulation throughput and parallel scalability on commodity clusters. Our results suggest that Desmond's parallel performance substantially surpasses that of any previously described code. For example, on a standard benchmark, Desmond's performance on a conventional Opteron cluster with 2K processors slightly exceeded the reported performance of IBM's Blue Gene/L machine with 32K processors running its Blue Matter MD code.

Considerable interest has recently been expressed in the construction of parallel machines capable of significant performance and cost/performance improvements in various artificial intelligence applications. In this paper, we consider the capabilities of a particular massively parallel machine called NON-VON, an initial prototype of which is currently operational at Columbia University, for the efficient execution of a rather wide range of AI tasks. The paper provides a brief overview of the general NON-VON architecture, and summarizes certain performance projections, derived through detailed analysis and simulation, in the areas of rule-based inferencing, computer vision, and knowledge-base management. In particular, summaries are presented of projections derived for the execution of OPS5 production systems, the performance of a number of low- and intermediate-level image understanding tasks, and the execution of certain “difficult” relational algebraic operations having relevance to the manipulation of knowledge bases. The results summarized in this paper, most of which are based on benchmarks proposed by other researchers, suggest that NON-VON could provide a performance improvement of as much as several orders of magnitude on such tasks by comparison with a conventional sequential machine of comparable hardware cost.

Abstract This paper examines the applicability of fine-grained tree-structured SIMD machines, which are amenable to highly efficient VLSI implementation, to several low-level image understanding tasks. Algorithms are presented for histogramming, thresholding, image correlation, connected component labeling, and computing Euler number. A particular massively parallel machine called NON-VON is used for purposes of explication and performance evaluation. Only NON-VON tree-structured communication capabilities and its SIMD mode of execution are considered in this paper. Novel algorithmic techniques are described, such as vertical pipelining, subproblem partitioning, associative matching, and data duplication, that effectively exploit the massive parallelism available in fine-grained SIMD tree machines while avoiding communication bottlenecks. Simulation results are presented and compared with results obtained or forecast for other highly parallel machines. The relative advantages and limitations of the class of machines under consideration are outlined; except for some types of image correlation, the fine-grained SIMD tree is exceptionally fast.

In this paper, we examine the implementation of two middle-level image understanding tasks on fine-grained tree-structured SIMD machines, which have highly efficient VLSI implementations. We first present one such massively parallel machine called NON-VON, and summarize the cost/performance trade-offs of such machines for vision taks. We follow with a more detailed description of the NON-VON architecture (a prototype of which has been operational since January 1985), and of the high-level parallel language in which our algorithms have been written and simulated. The heart of the paper consists of the description and analysis of algorithms for a representative Hough transform, and of an algorithm for the interpretation of moving light displays. Novel algorithmic techniques are motivated and described, and simulation timings are presented and discussed. We conclude that it is possible to exploit the available massive parallelism while avoiding many of the communication bottlenecks common at this level of image understanding, by carefully and inexpensively duplicating data and/or control information, and by delaying or avoiding the reporting of intermediate results.

In recent years, the development of expert systems implemented by rule-based production systems has emerged as one of the dominant paradigms in the field of artificial intelligence. While production systems offer important advantages in large-scale AI applications, their use in such applications is typically very costly in execution time. In this paper, we describe an algorithm for executing production systems expressed in the OPS5 language on a massively parallel multiple-SIMD machine called NON-VON, portions of which are currently under construction at Columbia University. The algorithm, a parallel adaptation of Forgy's Rete Match, has been implemented and tested on an instruction-level simulator. We present a detailed performance analysis, based on the implemented code, for the averaged characteristics of six production systems having an average of 910 inference rules each. The analysis predicts an execution rate of more than 850 production firings per second using hardware comparable in cost to a VAX 11/780. By way of comparison, a LISP-based OPS5 interpreter running on a VAX 11/780 typically fires 1 to 5 rules per second, while a Bliss-based interpreter executes 5 to 12 rules per second.

In a paper by Hawthorn and DeWitt, the projected performance of several proposed database machines was examined for three relational database queries. The present paper investigates the performance of a massively parallel machine called NON-VON for the same queries under comparable assumptions. In the case of simple queries, a NON-VON machine of comparable size to those considered by Hawthorn and DeWitt is found to be somewhat faster than the fastest machines examined in their study; for a more complex database operation, NON-VON is shown to be five to ten times faster than the fastest of these machines.