| 1. |
- Ho, Ching-Tien, et al.
(författare)
-
Embedding Meshes in Boolean Cubes by Graph Decomposition
- 1990
-
Ingår i: Parallel Computing. - : Elsevier BV. - 0167-8191 .- 1872-7336. ; 8:4, s. 325-339
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 2. |
- Ho, Ching-Tien, et al.
(författare)
-
Embedding Meshes into Small Boolean Cubes
- 1990
-
Konferensbidrag (refereegranskat)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.
|
|
| 3. |
- Ho, Ching-Tien, et al.
(författare)
-
Embedding Three–Dimensional Meshes in Boolean Cubes by Graph Decomposition
- 1990
-
Konferensbidrag (refereegranskat)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.
|
|
| 4. |
|
|
| 5. |
- Ho, Ching-Tien, et al.
(författare)
-
Optimizing Tridiagonal Solvers for the Alternating Direction Method on Boolean Cube Multiprocessors
- 1990
-
Ingår i: SIAM Journal on Scientific Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 1064-8275 .- 1095-7197. ; 11:3, s. 563-592
-
Tidskriftsartikel (refereegranskat)abstract
- Sets of tridiagonal systems occur in many applications. Fast Poisson solvers and Alternate Direction Methods make use of tridiagonal system solvers. Network-based multiprocessors provide a cost-effective alternative to traditional supercomputer architectures. The complexity of concurrent algorithms for the solution of multiple tridiagonal systems on Boolean-cube-configured multiprocessors with distributed memory are investigated. Variations of odd-even cyclic reduction, parallel cyclic reduction, and algorithms making use of data transposition with or without substructuring and local elimination, or pipelined elimination, are considered. A simple performance model is used for algorithm comparison, and the validity of the model is verified on an Intel iPSC/ 1. For many combinations of machine and system parameters, pipelined elimination, or equation transposition with or without substructuring is optimum. Hybrid algorithms that at any stage choose the best algorithm among the considered ones for the remainder of the problem are presented. It is shown that the optimum partitioning of a set of independent tridiagonal systems among a set of processors yields the embarrassingly parallel case. If the systems originate from a lattice and solutions are computed in alternating directions, then to first order the aspect ratio of a computational lattice shall be the same as that of the lattice forming the base for the equations. The experiments presented here demonstrate the importance of combining in the communication system for architectures with a relatively high communications start-up time.
|
|
| 6. |
- Ho, Cieng-Tien, et al.
(författare)
-
The Complexity of Reshaping Arrays on Boolean Cubes
- 1990
-
Konferensbidrag (refereegranskat)abstract
- Reshaping ofarrays is a convenient programming primitive. For arrays encoded in a binary-reflected Gray code reshaping implies code change. We show that an axis splitting, or combining of two axes, requires communica tion in exactly one dimension, and that for multiple axes split tings the exchanges in the different dimensions can be ordered arbitrarily. The nnmber of element transfers in sequence is independent of the number of dimensions requiring coniniunication for large local data sets, and concurrent conuiiunication. The lowerboundfor the number of element transfers in sequence is $with K elements perprocessor. We present algorithius that is of this complexity for some cases, and of complexity K in the worstcase. Conversion between binary code and binary-reflected Gray code is a special case of reshaping.
|
|
| 7. |
- Johnsson, Lennart, et al.
(författare)
-
Data Structures and Algorithms for the Finite Element Method on a Data Parallel Supercomputer
- 1990
-
Ingår i: International Journal for Numerical Methods in Engineering. - : Wiley. - 0029-5981 .- 1097-0207. ; 29:4, s. 881-908
-
Tidskriftsartikel (refereegranskat)abstract
- This article describes a formulation of the finite element method and its implementation on a data parallel computing system. The Connection Machine® system, CM-2, has been used as the model architecture. Data structures, storage requirements, communication and parallel arithmetic complexity are analysed in detail for the cases when a processor represents an unassembled finite element and when a processor is assigned to an unassembled nodal point. Data parallel algorithms for the grid generation, the evaluation of the elemental stiffness matrices and for the iterative solution of the linear system are presented. The algorithm for evaluating the elemental stiffness matrices computes the matrix elements concurrently without communication. This concurrency is in addition to the inherent parallelism present among different finite elements. A conjugate gradient solver with diagonal pre-conditioner is used for the solution of the resulting linear system. Results from an implementation of the three-dimensional finite element method based on Lagrange elements are reported. For single-precision floating-point operations, the measured peak performance is approximately 2·4 G flops s−1 for evaluating the elemental stiffness matrices and approximately 850 M flops s−1 for the conjugate gradient solver. On a Connection Machine system with 16K physical processors, the time per conjugate gradient iteration for an application with 400 000 degrees of freedom is approximately 0·13 s for double-precision floating-point operations.
|
|
| 8. |
|
|
| 9. |
- Johnsson, Lennart
(författare)
-
Supercomputers: Past and Future
- 1990
-
Ingår i: Kosmos. - : Almqvist & Wiksell. ; , s. 31-44
-
Bokkapitel (refereegranskat)abstract
- Abstract: "Progress in many fields of science and in engineering design is rapidly becomming [sic] critically dependent upon supercomputers. The management of very large data sets, including fast update and retrieval of information, is also becomming [sic] a very important function in many non-manufacturing businesses, such as the transportation, the securities, and financial industries, and in various parts of the government. The goal for the designers of the next generation
|
|
| 10. |
- Mathur, Kapil K, et al.
(författare)
-
Data Parallel Algorithms for the Finite Element Method
- 1990
-
Konferensbidrag (refereegranskat)abstract
- A data paralell implementation of the finite element method is described. The focus of the presentation is on data mapping and data motion. The essential ideas of the dataparallel implementation are developed for discretizations of regular domains by Lagrange elements ofarbitrary order in two and three dimensions, A generalization to irregular domains is also presented.Implementations of the data mappings for both regular and irregular domains have been made onthe Connection Machine®system model CM-2. Peak performances Well in excess of 2 Gñops have bee measured for the evaluation of the elemental stiffness matrices. The performance of the iterative solver is in the range of 600 850 Mñops s'1.
|
|
