The Connection Machine: PDE solution on 65 536 processors

The Connection Machine is a massively parallel architecture with 65 536 single-bit processors and 32 Mbytes of memory, organized as a high-dimensional hypercube. A sophisticated router system provides efficient communication between remote processors. A rich software environment, including a parallel extension of COMMON LISP, provides access to the processors and network. Virtual processor capability extends the degree of fine-grained parallelism beyond 1 000 000.We describe the hardware and the parallel programming environment. We then present implementations of SOR, Multigrid and Conjugate Gradient algorithms for solving Partial Differential Equations on the Connection Machine. Measurements of computational efficiency are provided as well as an analysis of opportunities for achieving better performance. Despite the lack of floating-point hardware, computation rates above 100 Mflops have been achieved in PDE solution. Virtual processors prove to be a real advantage, easing the effort of software development while improving system performance significantly.     

Massively parallel implementation of the Splitting Equilibration Algorithm

In this paper, we describe a massively parallel implementation of the Splitting Equilibration Algorithm using CM FORTRAN on the Thinking Machines CM-2 system. Numerical results using upwards of 32 768 (32 K) processors on the CM-2 system, the Connection Machine, are presented for both input/output and social accounting matrix estimation problems and compared with those obtained for the same problems on the IBM 3090. Our experiences with the relative ease/difficulty of the implementations on these fine-grain and coarse-grain parallel architectures are also presented and discussed.     

Parallel finite-element computation of 3D flows

The authors describe their work on the massively parallel finite-element computation of compressible and incompressible flows with the CM-200 and CM-5 Connection Machines. Their computations are based on implicit methods, and their parallel implementations are based on the assumption that the mesh is unstructured. Computations for flow problems involving moving boundaries and interfaces are achieved by using the deformable-spatial-domain/stabilized-space-time method. Using special mesh update schemes, the frequency of remeshing is minimized to reduce the projection errors involved and also to make parallelizing the computations easier. This method and its implementation on massively parallel supercomputers provide a capability for solving a large class of practical problems involving free surfaces, two-liquid interfaces, and fluid-structure interactions     

Efficient representation and transformation of image data on the connection machine system

We discuss the transformation of image data from one level of representation to another using the data parallel programming model of the Connection Machine System.¹ Emphasis is placed on maintaining locality of reference in order to take advantage of fast, local communications. Image pyramids illustrate the transformation of image-based representations. We review pointer jumping as a transformation from the image to a sequence-based representation, the primary representation of data outside of the image plane. Using communication primitives, especially segmented scans, we review utilities for representing and manipulating such sequences. We then compare several algorithms for matching and evidence accumulation. The techniques emphasize the use of sorting and sparse representations of space, in order to limit the computational requirements of high level vision. Connection Machine is a registered trademark of Thinking Machines Corporation. Address reprint requests to: Library, Thinking Machines Corporation, 245 First St., Cambridge, MA 02142, USA     

Plurals: A SIMD extension to EuLisp

There are now several versions of Lisp for massively parallel SIMD architectures like the Thinking Machines Connection Machine. We describe here the extensions made to EuLisp for data-parallel programming and their implementation on a specific platform, a MasPar MP-1. Plural EuLisp, in keeping with the rest of the language, presents a collection of simple orthogonal operators which capture the essence of data parallel processing. In support of this, we demonstrate how to implement a number of higher-level abstraction from other data-parallel languages.This work has been partially supported through the British Council ARC Programme, a Science and Engineering Research Council (SERC) Studentship, SERC grant GR/G31048, International Computers Limited (SERC CASE award)     

VPNAgent系统连接迁移机制

移动代理系统中连接的迁移机制可用来支持移动代理之间连续透明的通信。描述了一个可靠的连接迁移机制的设计与实现,它为所有在代理迁移期间传送的数据提供准确的一次性传输。在用于虚拟专用网安全机制的移动代理平台VPNAgent系统中实现了该机制,并将其命名为AgentSocket,这是一个纯中间件实现,不需要更改Java虚拟机。     

PARAMICS—Parallel microscopic simulation of road traffic

This paper describes work done on the original PARAMICS project, which was developed for the Edinburgh Parallel Computing Centre to examine parallel microscopic road traffic simulation. The simulator, constructed originally for a Thinking Machines Connection Machine (CM-200), uses a data-parallel approach to simulate approximately 200,000 vehicles on 20,000 miles of roadway. More recent work has focused on the use of a message-passing paradigm, with a 256-node CRAY T3D as the target machine. The message-passing version of PARAMICS, PARAMICS-MP, is inherently scalable and can model many smaller networks on a broad range of platforms.An earlier version of this paper was presented at Supercomputing '94.     

Extended muSIMP/muMATH for teaching and learning mathematics

muSIMP is described by its authors (David Stoutemyer and Albert Rich, of the Soft Warehouse, Honolulu. Hawaii) as a “surface language” for muLISP. The latter is one of their earlier products, a LISP interpreter and development system for microcomputers.muSIMP has a very different syntax from LISP, although in other respects it is effectively the same language. A “conventional mathematics” appearance is clearly helpful to users. muSIMP offers f (x, y, z) where LISP would require (f x y z), for example, and the assignment “A: B + C 1 D;” is obviously nearer to most mathematics students' experience than the LISP equivalent, “(SETQ A (PLUS B(TIMES C D)))”.muMATH is a large library of muSIMP function and variable definitions. It permits the user to carry out symbolic algebraic operations including algebraic simplification, logarithmic and trigonometric expansion, equation solving, vector and matrix manipulation, differentiation, integration, limits and summation. All of this software can be extended as required by the user, so that new rules for differentiating or integrating can be added, for example.muSIMP does not, as sold, possess graphics capability, XSIMP, the author's extended version of muSIMP, for the RML 380Z (CP/M system) includes all the Research Machines Level 2 graphics functions, retaining a correspondence of names and order of parameters. XSIMP also contains a full floating-point arithmetic package, with the four arithmetic operations complemented by exponential, logarithmic, trigonometric and square root functions. Functions have also been provided in XSIMP for making BDOS and BIOS calls to CP/M.     

Concurrent Query Processing for Logic Inference Using the Connection Graph

Some logic program may have to process a sequence of asynchronously arriving concurrent queries. We provide a tagging scheme for resolution in the Connection Graph that allows later queries to reuse the work done for earlier or concurrent queries. The scheme can be used either by a sequential or a parallel logic inference system that uses the Connection Graph proof procedure. Our scheme is justified in terms of multiplexing multiple virtual Connection Graphs on one physical data structure. The tagging scheme is presented as a set of rules which are proved to be correct. An important characteristic of the Connection Graph procedure is the ability to delete clauses containing pure literals. In the proposed scheme, it is necessary to weaken it. Given some information about the form of incoming queries, we can strengthen this capability. If earlier links are allowed to be reconstructed, then the ability can be regained fully, via a caching scheme.     

Perspectives on supercomputing: three decades of change

I am fortunate to have had access to supercomputers for the last 28 years. Over this time I have used them to simulate time-dependent fluid flows in the compressible regime. Strong shocks and unstable multifluid boundaries, along with the phenomenon of fluid turbulence, have provided the simulation complexity that demands supercomputer power. The supercomputers I have used-the CDC 6600, 7600, and Star-100, the Cray-1, Cray-XMP, Cray-2, and Cray C-90, the Connection Machines CM-2 and CM-5, the Cray T3D, and the Silicon Graphics Challenge Array and Power Challenge Array-span three revolutions in supercomputer design: the introduction of vector supercomputing, parallel supercomputing on multiple CPUs, and supercomputing on hierarchically organized clusters of microprocessors with cache memories. The last revolution is still in progress, so its outcome is somewhat uncertain. I view these design revolutions through the prism of my specialty and through applications of the supercomputers I have used. Also, because these supercomputer design changes have driven equally important changes in numerical algorithms and the programs that implement them, I describe the three revolutions from this perspective     

An Interleaving Transformation for Parallelizing Reductions for Distributed-Memory Parallel Machines

Reduction operations frequently appear in algorithms. Due to their mathematical invariance properties (assuming that round-off errorscan be tolerated), it is reasonable to ignore ordering constraints on the computation of reductions in order to take advantage of the computing power of parallel machines.One obvious and widely-used compilation approach for reductions is syntactic pattern recognition. Either the source language includes explicit reduction operators, or certain specific loops are recognized as equivalent to known reductions. Once such patterns are recognized, hand optimized code for the reductions are incorporated in the target program. The advantage of this approach is simplicity. However, it imposes restrictions on the reduction loops—no data dependence other than that caused by the reduction operation itself is allowed in the reduction loops.In this paper, we present a parallelizing technique, interleaving transformation, for distributed-memory parallel machines. This optimization exploits parallelism embodied in reduction loops through combination of data dependence analysis and region analysis. Data dependence analysis identifies the loop structures and the conditions that can trigger this optimization. Region analysis divides the iteration domain into a sequential region and an order-insensitive region. Parallelism is achieved by distributing the iterations in the order-insensitive region among multiple processors. We use a triangular solver as an example to illustrate the optimization. Experimental results on various distributed-memory parallel machines, including the Connection Machines CM-5, the nCUBE, the IBM SP-2, and a network of Sun Workstations are reported.     

Implementations of artificial neural networks on the Connection Machine

A review of five distinct artificial neural network implementations on the Connection Machine is presented along with a brief discussion of the more general issues surrounding the implementation of artificial neural network models in parallel. The implementation which proves to be fastest on the Connection Machine is parallel in the training patterns and runs at more than 1300 million interconnects per second.     

A portable lisp compiler

The programming language LISP is usually implemented via an interpreter, and a compiler is added later as a LISP program. However, all such production compilers known to the authors produce explicit instructions for the given computer being used. This paper describes the development of a portable LISP compiler in the sense that only Standard LISP functions are used in its definition and the output is a sequence of abstract machine codes, easily mapped to instruction sequences on current computers. The resulting code is quite efficient, demonstrating once again the maxim that most compiler optimization is largely machine independent.     

LISP语言的并行性研究

本文讨论了源串行LISP语言的并行性开发,包括任务的划分和表示、并行处理策略、任务的环境控制、任务的调度和通讯,并给出了提高任务并行度的特殊函数处理、伪结果控制、自定义函数任务提升策略等算法,上述思想已在实验系统MTASKLISP上初步实现.     

多核系统下并行节点复制垃圾收集算法

为了提高垃圾收集效率,减少用户程序等待时间,提出了一种在多核系统下基于LISP2算法的并行节点复制算法。该算法通过把LISP2算法的4个垃圾收集阶段分别并行化来实现并行垃圾收集。实验结果显示,该算法在多核系统下能有效提高垃圾收集效率。     

The Mc Carthy's recursion induction principle: «Oldy» but «Goody»

We present here a very fruitful tool for proving properties of LISP functions. We implement the ancient, but quite natural and elegant, Recursion Induction Principle stated by J. Mc Carthy by using the famous fold/unfold method elaborated by R. Burstall and J. Darlington. We thus obtain a very simple and flexible method for proving theorems about LISP functions; we call it the Mc Carthy method. Furthermore the method is machine oriented and we implement it in a conversational system. We do not make any comparison with the R. Boyer and J. Moore theorem-prover since our system is not automatic. But our system is implementable in a wide range of machines and we expect to implement our method in the R. Burstall and J. Darlington system. We then shall have a very powerful system which might perform program synthesis and proofs of program properties simultaneously (in a way parallel to that followed by Z. Manna and R. Waldinger). In this paper we apply our method (by hand) to give the proof of two properties: associativity of the append operation between lists and idempotence of the reverse operation.     

A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine

Region growing is a general technique for image segmentation, where image characteristics are used to group adjacent pixels together to form regions. This paper presents a parallel algorithm for solving the region growing problem based on the split-and-merge approach, and uses it to test and compare various parallel architectures and programming models. The implementations were done on the Connection Machine, models CM-2 and CM-5, in the data parallel and message passing programming models. Randomization was introduced in breaking ties during merging to increase the degree of parallelism, and only one- and two-dimensional arrays of data were used in the implementations.     

Integrating multiple parallel programming paradigms in a dataflow-based software environment

By viewing different parallel programming paradigms as essentially heterogeneous approaches in mapping ‘real-world’ problems to parallel systems, the authors discuss methodologies in integrating multiple programming models on a massively parallel system such as Connection Machine CM5. Using a dataflow based integration model built in a visualization software AVS, the authors describe a simple, effective and modular way to couple sequential, data-parallel and explicit message-passing modules into an integrated parallel programming environment on a CM5. A case study in the area of numerical advection modeling is given to demonstrate the integration of data-parallel and message-passing modules in the proposed multi-paradigm programming environment.     

PRA*: Massively Parallel Heuristic Search

In this paper we describe a variant of A* search designed to run on the massively parallel, SIMD Connection Machine (CM-2). The algorithm is designed to run in a limited memory by the use of a retraction technique which allows nodes with poor heuristic values to be removed from the open list until such time as they may need reexpansion, more promising paths having failed. Our algorithm, called PRA* (for Parallel Retraction A*), is designed to maximize use of the Connection Machine′s memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissible heuristic is used. Results comparing PRA* to Korf′s IDA* for the fifteen puzzle show significantly fewer node expansions for PRA*. In addition, empirical results show significant parallel speedups, indicative of the algorithm′s design for high processor utilization.