| 1. |
- Mathur, K, et al.
(author)
-
Massively Parallel Computing: Unstructured Finite Element Simulations
- 1993
-
In: NAFEMS. ; , s. 24-29
-
Conference paper (peer-reviewed)abstract
- Massively parallel computing holds the promise of extreme performance. Critical for achieving high performance is the ability to exploit locality of reference and effective management of the communication resources. This article describes two communication primitives and associated mapping strategies that have been used for several different unstructured, three-dimensional, finite element applications in computational fluid dynamics and structural mechanics.
|
|
| 2. |
- Brickner, R.G, et al.
(author)
-
QCD on the Connection Machine: Beyond-Lisp
- 1991
-
In: Computer Physics Communications. - 0010-4655 .- 1879-2944. ; 65, s. 39-51
-
Journal article (peer-reviewed)abstract
- 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 system 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.
|
|
| 3. |
- Brunet, Jean-Philippe, et al.
(author)
-
All–to–All Broadcast with Applications on the Connection Machine
- 1992
-
In: International Journal of Supercomputer Applications. ; 6:3, s. 241-256
-
Journal article (peer-reviewed)abstract
- 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.
|
|
| 4. |
- Edelman, Alan, et al.
(author)
-
Index Transformation Algorithms in a Linear Algebra Framework
- 1994
-
In: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 5:12, s. 1302-1309
-
Journal article (peer-reviewed)abstract
- We present a linear algebraic formulation for a class of index transformations such as Gray code encoding and decoding, matrix transpose, bit reversal, vector reversal, shuffles, and other index or dimension permutations. This formulation unifies, simplifies, and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.
|
|
| 5. |
- George, William, et al.
(author)
-
POLYSHIFT Communications Software for the Connection Machine System CM–200
- 1994
-
In: Scientific Programming. - 1058-9244 .- 1875-919X. ; 3:1, s. 83-99
-
Journal article (peer-reviewed)abstract
- 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).
|
|
| 6. |
- Ho, Ching-Tien, et al.
(author)
-
An Efficient Algorithm for Gray–to–Binary Permutation on Hypercubes
- 1994
-
In: Journal of Parallel and Distributed Computing. - 0743-7315 .- 1096-0848. ; 20:1, s. 114-120
-
Journal article (peer-reviewed)abstract
- Both Gray code and binary code are frequently used in mapping arrays into hypercube architectures. While the former is preferred when communication between adjacent array elements is needed, the latter is preferred for FFT-type communication. When different phases of computations have different types of communication patterns, the need arises to remap the data. We give a nearly optimal algorithm for permuting data from a Gray code mapping to a binary code mapping on a hypercube with communication restricted to one input and one output channel per node at a time. Our algorithm improves over the best previously known algorithm [6] by nearly a factor of two and is optimal to within a factor of n=(n Gamma 1) with respect to data transfer time on an n-cube. The expected speedup is confirmed by measurements on an Intel iPSC/2 hypercube
|
|
| 7. |
- Ho, Ching-Tien, et al.
(author)
-
Embedding Hyper–pyramids in Hypercubes
- 1994
-
In: IBM Journal of Research and Development. - : IBM. - 0018-8646 .- 2151-8556. ; 38:1, s. 31-45
-
Journal article (peer-reviewed)
|
|
| 8. |
- Ho, Ching-Tien, et al.
(author)
-
Embedding Meshes in Boolean Cubes by Graph Decomposition
- 1990
-
In: Parallel Computing. - : Elsevier BV. - 0167-8191 .- 1872-7336. ; 8:4, s. 325-339
-
Journal article (peer-reviewed)abstract
- This paper explores the embeddings of multidimensional meshes into minimal Boolean cubes by graph decomposition. The dilation and the congestion of the product graph (G1 × G2) → (H1 × H2) is the maximum of the dilation and congestion for the two embeddings G1 → H1 and G2 → H2. The graph decomposition technique can be used to improve the average dilation and average congestion. The graph decomposition technique combined with some particular two-dimensional embeddings allows for minimal-expansion, dilation-two, congestion-two embeddings of about 87% of all two-dimensional meshes, with a significantly lower average dilation and congestion than by modified line compression. For three-dimensional meshes we show that the graph decomposition technique, together with two three-dimensional mesh embeddings presented in this paper and modified line compression, yields dilation-two embeddings of more than 96% of all three-dimensional meshes contained in a 512 × 512 × 512 mesh. The graph decomposition technique is also used to generalize the embeddings to meshes with wrap-around. The dilation increases by at most one compared to a mesh without wraparound. The expansion is preserved for the majority of meshes, if a wraparound feature is added to the mesh.
|
|
| 9. |
- Ho, Ching-Tien, et al.
(author)
-
Embedding Meshes into Small Boolean Cubes
- 1990
-
Conference paper (peer-reviewed)abstract
- The embedding of arrays in Boolean cubes, when there are more array elements than nodes in the cube, can always be made with optimal load-factor by reshaping the array to a one-dimensional array. We show that the dilation for such an embedding is of an .to x .t1 x - + x &-I array in an n-cube.Dila tion one embeddings can be obtained by splitting each axis into segments and assigning segments to nodes in the cube by a Gray code. The load-factor is optimal if the axis lengths contain sufficiently many powers of two. The congestion is minimized, if the segment lengths along the different axes are as equal as possible, for the cube configured with at most as many axes as the array. A further decrease in the congestion is possible if the array is partitioned into subarrays, and corresponding axis of different subarrays make use of edge-disjoint Hamiltonian cycles within subcubes. The congestion can also be reduced by using multiple paths between pairs of cube nodes, i.e., by using “fat” edges.
|
|
| 10. |
- Ho, Ching-Tien, et al.
(author)
-
Embedding Three–Dimensional Meshes in Boolean Cubes by Graph Decomposition
- 1990
-
Conference paper (peer-reviewed)abstract
- This paper explores the embeddings of multidimensional meshes into minimal Boolean cubes by graph decomposition. The graph decomposition technique can be used to improve the average dilation and average congestion. The graph decomposition technique combined with some particular two-dimensional embeddings allows for minimal-expansion, dilation-two, congestion-two embeddings of about 87% of all two-dimensional meshes, with a significantly lower average dilation and congestion than by modified line compression. For three-dimensional meshes the authors show that the graph decomposition technique, together with two three-dimensional mesh embeddings presented in this paper and modified line compression, yields dilation-two embeddings of more than 96% of all three dimensional meshes contained in a 512 {times} 512 {times} 512 mesh.
|
|
