The Experts below are selected from a list of 183 Experts worldwide ranked by ideXlab platform
S. Lennart Johnsson - One of the best experts on this subject based on the ideXlab platform.
-
All-to-all communication on the Connection Machine CM-200
Scientific Programming, 1995Co-Authors: Kaph K. Mathur, S. Lennart JohnssonAbstract:Detailed algorithms for all-to-all broadcast and reduction are given for arrays mapped by binary or binary-reflected Gray code encoding to the processing nodes of binary cube networks. Algorithms are also given for the local computation of the array indices for the communicated data, thereby reducing the demand for the communications bandwidth. For the Connection Machine system CM-200, Hamiltonian cycle-based all-to-all communication algorithms yield a performance that is a factor of 2 to 10 higher than the performance offered by algorithms based on trees, butterfly networks, or the Connection Machine router. The peak data rate achieved for all-to-all broadcast on a 2,048-node Connection Machine system CM-200 is 5.4 Gbyte/s. The index order of the data in local memory depends on implementation details of the algorithms, but it is well defined. If a linear ordering is desired, then including the time for local data reordering reduces the effective peak data rate to 2.5 Gbyte/s.
-
POLYSHIFT communications software for the Connection Machine system CM-200
Scientific Programming, 1994Co-Authors: William George, R. G. Brickner, S. Lennart JohnssonAbstract:We describe the use and implementation of a polyshift function PSHIFT for circular shifts and end-offs shifts. Polyshift is useful in many scientific codes using regular grids, such as finite difference codes in several dimensions, and multigrid codes, molecular dynamics computations, and in lattice gauge physics computations, such as quantum chromodynamics (QCD) calculations. Our implementation of the PSHIFT function on the Connection Machine systems CM-2 and CM-200 offers a speedup of up to a factor of 3-4 compared with CSHIFT when the local data motion within a node is small. The PSHIFT routine is included in the Connection Machine Scientific Software Library (CMSSL).
-
Cooley-Tukey FFT on the Connection Machine
Parallel Computing, 1992Co-Authors: S. Lennart Johnsson, R. L. KrawitzAbstract:We describe an implementation of the Cooley-Tukey complex-to-complex FFT on the Connection Machine. The implementation is designed to make effective use of the communications bandwidth of the architecture, its memory bandwidth, and storage with precomputed twiddle factors. The peak data motion rate that is achieved for the interprocessor communication stages is in excess of 7 Gbytes/s for a Connection Machine system CM-200 with 2048 floating-point processors. The peak rate of FFT computations local to a processor is 12.9 Gflops/s in 32-bit precision, and 10.7 Gflops/s in 64-bit precision. The same FFT routine is used to perform both one- and multi-dimensional FFT without any explicit data rearrangement. The peak performance for a one-dimensional FFT on data distributed over all processors is 5.4 Gflops/s in 32-bit precision and 3.2 Gflops/s in 64-bit precision. The peak performance for square, two-dimensional transforms, is 3.1 Gflops/s in 32-bit precision, and for cubic, three dimensional transforms, the peak is 2.0 Gflops/s in 64-bit precision. Certain oblong shapes yield better performance. The number of twiddle factors stored in each processor is P/2N + log2 N for an FFT on P complex points uniformly distributed among N processors. To achieve this level of storage efficiency we show that a decimation-in-time FFT is required for normal order input, and a decimation-in-frequency FFT is required for bit-reversed input order.
-
All-To-All Broadcast and Applications On the Connection Machine
The International Journal of Supercomputing Applications, 1992Co-Authors: Jean-philippe Brunet, S. Lennart JohnssonAbstract:An all-to-all broadcast algorithm that exploits concur rent communication on all channels of the Connection Machine system CM-200 binary cube network is de scribed. Issues in integrating a physical all-to-all broad cast between processing nodes into a language envi ronment using a global address space are discussed. Timings for the physical broadcast between nodes and for the virtual broadcast are given. The peak data transfer rate for the physical broadcast on a CM-200 is 5.9 gigabytes/sec, and the peak rate for the virtual broadcast is 31 gigabytes/sec. Array reshaping is an effective performance optimization technique. An ex ample is given where reshaping improved perfor mance by a factor of 7 by reducing the amount of local data motion. We also show how to exploit symmetry for computation of an interaction matrix using the all- to-all broadcast function. Further optimizations are suggested for N-body-type calculations. Using the all- to-all broadcast function, a peak rate of 9.3 GFLOPS/ sec has been achieved for the N-body computations in 32-bit precision on a 2,048 node Connection Machine system CM-200.
-
The parallel multipole method on the Connection Machine
SIAM Journal on Scientific and Statistical Computing, 1991Co-Authors: Feng Zhao, S. Lennart JohnssonAbstract:This paper reports on a fast implementation of the three-dimensional nonadaptive Parallel Multipole Method (PMM) on the Connection Machine system model CM–2. The data interactions within the decomposition tree are modeled by a hierarchy of three-dimensional grids forming a pyramid in which parent nodes have degree eight. The base of the pyramid is embedded in the Connection Machine as a three-dimensional grid. The standard grid embedding feature is used. For 10 or more particles per processor the communication time is insignificant. The evaluation of the potential field for a system with 128k particles takes 5 seconds, and a system of a million particles about 3 minutes. The maximum number of particles that can be represented in 2G bytes of primary storage is $ \sim 50$ million. The execution rate of this implementation of the PMM is at about 1.7 Gflops/sec for a particle-processor-ratio of 10 or greater. A further speed improvement is possible by an improved use of the memory hierarchy associated with ea...
R. G. Brickner - One of the best experts on this subject based on the ideXlab platform.
-
POLYSHIFT communications software for the Connection Machine system CM-200
Scientific Programming, 1994Co-Authors: William George, R. G. Brickner, S. Lennart JohnssonAbstract:We describe the use and implementation of a polyshift function PSHIFT for circular shifts and end-offs shifts. Polyshift is useful in many scientific codes using regular grids, such as finite difference codes in several dimensions, and multigrid codes, molecular dynamics computations, and in lattice gauge physics computations, such as quantum chromodynamics (QCD) calculations. Our implementation of the PSHIFT function on the Connection Machine systems CM-2 and CM-200 offers a speedup of up to a factor of 3-4 compared with CSHIFT when the local data motion within a node is small. The PSHIFT routine is included in the Connection Machine Scientific Software Library (CMSSL).
-
QCD on the Connection Machine: beyond LISP
Computer Physics Communications, 1991Co-Authors: R. G. Brickner, Clive F. Baillie, S. Lennart JohnssonAbstract:We report on the status of code development for a simulation of quantum chromodynamics (QCD) with dynamical Wilson fermions on the Connection Machine model CM-2. Our original code, written in Lisp, gave performance in the near-GFLOPS range. We have rewritten the most time-consuming parts of the code in the low-level programming systems CMIS, including the matrix multiply and the communication. Current versions of the code run at approximately 3.6 GFLOPS for the fermion matrix inversion, and we expect the next version to reach or exceed 5 GFLOPS.
Michael A. Young - One of the best experts on this subject based on the ideXlab platform.
-
Connection Machine Software Conversion of the Navy TOPS Model
1994Co-Authors: Paul B. Anderson, Michael A. YoungAbstract:Abstract : The introduction of highly parallel Machines with peak performance significantly exceeding the Cray Machines has sparked interest in running scientific models on these new architectures. This report describes a software conversion, of the Navy model called TOPS, starting with a Cray Y-MP/8 version in Fortran 77 and ending with a Fortran 90 version for the Connection Machine CM-5. Data mapping, conversion planning, and performance points of view are considered. Connection Machine, Fortran 90, Ocean modeling.
-
Connection Machine Software Conversion of a Navy Oceans Model
1993Co-Authors: Paul B. Anderson, Michael A. YoungAbstract:Abstract : The instruction of highly parallel Machines with peak performance significantly exceeding the Cray Machines has sparked interest in running scientific models on these new architectures. This report describes a software conversion, of the Navy model called OCEANS, starting with a Cray Y-MP/8 version in Fortran 77 and ending with a Fortran 90 version for the Connection Machine CM-200. Data mapping, conversion planning, and performance points of view are considered. Connection Machine, Fortran 90, Ocean modeling.
-
NRL Connection Machine Fortran Library
1991Co-Authors: Michael A. YoungAbstract:Abstract : The NRL Connection Machine Fortran Library consists of numerous mathematical routines coded in CM Fortran along with lower level routines written in Paris which manipulate data, plot data, and perform operations unavailable in the context of the CM Fortran language. Users are able to remain entirely within the CM Fortran programming environment while making calls to these library routines. Interfaces to the Framebuffer, a high resolution graphics device, and the DataVault, a high speed I/O channel, are available. A summary and demonstration of each routine is provided.
T. Fontaine - One of the best experts on this subject based on the ideXlab platform.
-
Data-parallel training of spatiotemporal Connectionist networks on the Connection Machine
[Proceedings 1992] IJCNN International Joint Conference on Neural Networks, 1Co-Authors: T. FontaineAbstract:An algorithm for optimizing spatiotemporal Connectionist networks utilizing training set parallelism has been implemented on the Connection Machine (CM). The algorithm supports several optimization methods including backpropagation, conjugate gradient, and pseudo-Newtonian. By allocating one CM processor per training example, the computational complexity of the gradient derivation becomes independent of the number of training examples. The author has experimentally corroborated this independence, and reports the timing performance of the Connection Machine implementation on a series of spatiotemporal discrimination tasks. He also presents the timing performance of a serial implementation of the algorithm, running on an IBM RS/6000, to emphasize the efficacy of the data-parallel approach. >
Clive F. Baillie - One of the best experts on this subject based on the ideXlab platform.
-
QCD on the Connection Machine: beyond LISP
Computer Physics Communications, 1991Co-Authors: R. G. Brickner, Clive F. Baillie, S. Lennart JohnssonAbstract:We report on the status of code development for a simulation of quantum chromodynamics (QCD) with dynamical Wilson fermions on the Connection Machine model CM-2. Our original code, written in Lisp, gave performance in the near-GFLOPS range. We have rewritten the most time-consuming parts of the code in the low-level programming systems CMIS, including the matrix multiply and the communication. Current versions of the code run at approximately 3.6 GFLOPS for the fermion matrix inversion, and we expect the next version to reach or exceed 5 GFLOPS.