International Journal of High Speed Computing

The Neocognitron, a neural network model which has a multilayered structure, has been realized on a hypercube parallel computer, NCUBE. The structure of the Neocognition was analyzed and discussed from the point of view of parallel processing. An efficient node-assignment has been made with full consideration of the network structure of the Neocognitron and the properties of the hypercube machine. Eight Neocognitron systems, each of which can recognize a handwritten numeral, have been achieved on the NCUBE which has 512 nodes. Broadcast and gathering method, which realizes exhaustive connections among cells, was proposed and its performance discussed.

Given two sorted arrays, A (of size n) and B (of size m) where n≤m, it is required to determine for every element of A its position within B. A parallel algorithm is presented to solve this problem on the exclusive-read exclusive-write parallel random access machine (EREW PRAM). The algorithm uses p processors and runs in time. When and n≤m^α, with 0<α<1, the cost of the algorithm, i.e. its running time multiplied by the number of processors it uses, matches the running time of the fastest known sequential algorithm for this problem.

The Connection Machine CM-2 computer represents the state of the art in supercomputer performance at this time, with peak rates of over 20 Gflops in 32-bit precision. While theoretical peak rates are essentially never attained, remarkable performance is possible on real applications. We discuss a number of CM-2 applications including implicit and explicit PDE solvers as well as spectral methods. We demonstrate delivered performance over a gigaflop in each case, and ranging as high as 3.8 gigaflops in the case of conjugate gradient solution of elliptic PDE.

We describe 2D and 3D Fast Helmholtz and Poisson Direct Solvers for the CM-2 and provide performance data for them on grids with up to 4 million points and using 65,536 processors. Performance of 1.1 Gflops is attained in 2D, and over 850 Mflops in 3D. The solution of the Helmholtz equation on a 2048×2048 grid takes under half a second, and on a 128×128×256 3D grid it requires .54 seconds. We have iteratively solved more general elliptic PDE by conjugate gradient methods at 3.8 Gflops. The fast solver has been used to provide a pre-conditioner for the conjugate gradient solver, which is then limited in performance to 1.3 Gflops, but results in far fewer iterations.

We also describe several partial and complete applications ranging from oil reservoir simulation to oceanographic modeling. In the latter case we present the first results of spectral models running on the CM-2. We emphasize the issues involved in attaining these levels of performance and compare in most cases with CRAY-XMP performance for the same algorithm. All results are for algorithms written in a high-level language.

This paper presents a strategy for automatically decomposing a functional program into new combinators with an optimal grain and distributing them on a distributed-memory multicomputer. The program transformation method accepts a lambda expression and generates program-derived combinators which are fine-tuned to have a right granularity for a particular multiprocessor architecture. The right granularity is decided by analyzing the weight for each program-derived combinator during translation. We call a program-derived combinator at just the right level of granularity the hybrid combinator, which is composed of a fixed set of combinators suitable for spawning the parallel elements and partitioning them. The hybrid combinator provides an alternative method to the representation and synchronization of processes. This paper shows the parallel graph reduction process, where the hybrid combinators act as the controlling mechanisms by directing when and which subgraph is to be distributed.

This paper discusses the parallel implementation of a hypercube-based circuit partitioning scheme. The circuit partitioner is based on a simulated annealing algorithm and is designed to provide near optimal circuit partitions for simulating the circuits on a hypercube architecture. The circuit partitioning scheme optimizes multiple criteria such as tight coupling of nodes within a subcircuit, load balancing among processors and communication overheads. Design of a partitioner that obtains near optimal solutions satisfying such multiple criteria is difficult using any simple heuristic techniques other than simulated annealing.

This paper examines some of the aspects of an induction process that can have a significant decrease in total run time through the use of a vector processor and appropriate algorithms and code. The simplified induction algorithm assumes that all values are realistic, that a number of possible attributes could be used at every single node, and that possible partition points are given. The algorithm chooses the one-step optimal attribute, then builds a tree. Two slightly different variants of the algorithm are considered. For the first, the results include a comparison between the times taken for a scalar compilation, a compilation with the automatic vector code and some vector compiler directives. In the second variant calls to the vector library are used and other parts have the compiler directives.

Timings for building the tree on a learning sample, and passing a test sample down an existing tree are compared in each case. The gain in speed, even for relatively short vectors, is about a factor of two.