Engineering topics

Chu, Eleanor

Publications and source records attributed to Chu, Eleanor.

4 records

NASA NTRS1993

Dynamic programming on a shared-memory multiprocessor

Three new algorithms for solving dynamic programming problems on a shared-memory parallel computer are described. All three algorithms attempt to balance work load, while keeping synchronization cost low. In particular, for a multiprocessor having p processors, an analysis of the best algorithm shows that the arithmetic cost is O(n-cubed/6p) and that the synchronization cost is O(absolute value of log sub C n) if p much less than n, where C = (2p-1)/(2p + 1) and n is the size of the problem. The low synchronization cost is important for machines where synchronization is expensive. Analysis and experiments show that the best algorithm is effective in balancing the work load and producing high efficiency.

Edmonds, Phil↗

NASA NTRS1992

A balanced submatrix merging algorithm for multiprocessor architectures

In this article, a parallel algorithm which applies Givens rotations to selectively annihilate k(k + 1)/2 nonzero elements from two k x n(k not more than n) upper trapezoidal submatrices is described. The new algorithm is suitable for implementation on either a pair of directly connected local-memory processors or two clusters of multiple tightly-coupled processors. Analyses show that in both cases the proposed algorithms achieve optimal speed-up by balancing the work load distribution and masking interprocessor or intercluster communication by computation if k is much small than n. In the context of solving large scale least squares problems, this submatrix merging step is repetitively needed during the entire computation and, furthermore, there are usually many pairs of such submatrices to be merged with each submatrix stored in the memory of a processor or a cluster of processors. The proposed algorithm can be applied to each pair of submatrices concurrently, and thus parallelizes an important step in solving the least squares problems.

Chu, Eleanor↗

NASA NTRS1989

Sparse matrix methods research using the CSM testbed software system

Research is described on sparse matrix techniques for the Computational Structural Mechanics (CSM) Testbed. The primary objective was to compare the performance of state-of-the-art techniques for solving sparse systems with those that are currently available in the CSM Testbed. Thus, one of the first tasks was to become familiar with the structure of the testbed, and to install some or all of the SPARSPAK package in the testbed. A suite of subroutines to extract from the data base the relevant structural and numerical information about the matrix equations was written, and all the demonstration problems distributed with the testbed were successfully solved. These codes were documented, and performance studies comparing the SPARSPAK technology to the methods currently in the testbed were completed. In addition, some preliminary studies were done comparing some recently developed out-of-core techniques with the performance of the testbed processor INV.

Chu, Eleanor↗

NASA NTRS1988

Algorithms and software for solving finite element equations on serial and parallel architectures

The primary objective was to compare the performance of state-of-the-art techniques for solving sparse systems with those that are currently available in the Computational Structural Mechanics (MSC) testbed. One of the first tasks was to become familiar with the structure of the testbed, and to install some or all of the SPARSPAK package in the testbed. A brief overview of the CSM Testbed software and its usage is presented. An overview of the sparse matrix research for the Testbed currently employed in the CSM Testbed is given. An interface which was designed and implemented as a research tool for installing and appraising new matrix processors in the CSM Testbed is described. The results of numerical experiments performed in solving a set of testbed demonstration problems using the processor SPK and other experimental processors are contained.

Chu, Eleanor↗