Search NASA⌕ Search

SEARCH · Search NASA

Results for “hypercube”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Hypercluster - Parallel processing for computational mechanics

An account is given of the development status, performance capabilities and implications for further development of NASA-Lewis' testbed 'hypercluster' parallel computer network, in which multiple processors communicate through a shared memory. Processors have local as well as shared memory; the hypercluster is expanded in the same manner as the hypercube, with processor clusters replacing the normal single processor node. The NASA-Lewis machine has three nodes with a vector personality and one node with a scalar personality. Each of the vector nodes uses four board-level vector processors, while the scalar node uses four general-purpose microcomputer boards.

Blech, Richard A.↗
NASA NTRS1988

Design and implementation of parallel multigrid algorithms

Techniques for mapping multigrid algorithms to solve elliptic PDEs on hypercube parallel computers are described and demonstrated. The need for proper data mapping to minimize communication distances is stressed, and an execution-time model is developed to show how algorithm efficiency is affected by changes in the machine and algorithm parameters. Particular attention is then given to the case of coarse computational grids, which can lead to idle processors, load imbalances, and inefficient performance. It is shown that convergence can be improved by using idle processors to solve a new problem concurrently on the fine grid defined by a splitting.

Chan, Tony F.↗
NASA NTRS1988

On multigrid methods for the Navier-Stokes Computer

The overall architecture of the multipurpose parallel-processing Navier-Stokes Computer (NSC) being developed by Princeton and NASA Langley (Nosenchuck et al., 1986) is described and illustrated with extensive diagrams, and the NSC implementation of an elementary multigrid algorithm for simulating isotropic turbulence (based on solution of the incompressible time-dependent Navier-Stokes equations with constant viscosity) is characterized in detail. The present NSC design concept calls for 64 nodes, each with the performance of a class VI supercomputer, linked together by a fiber-optic hypercube network and joined to a front-end computer by a global bus. In this configuration, the NSC would have a storage capacity of over 32 Gword and a peak speed of over 40 Gflops. The multigrid Navier-Stokes code discussed would give sustained operation rates of about 25 Gflops.

Nosenchuck, D. M.↗
NASA NTRS1987

Solving finite element equations on concurrent computers

This paper discusses the development of a concurrent algorithm for the solution of systems of equations arising in finite element applications. The approach is based on a hybrid of direct elimination method and preconditioned conjugate iteration. Two different preconditioners are used; diagonal scaling and a concurrent implementation of incomplete LU factorization. First, an automatic procedure is used to partition the finite element mesh into sub-structures. The particular mesh partition is chosen to minimize an estimate of the cost for evaluating the solution using this algorithm on a concurrent computer. These procedures are implemented in a finite element program on the JPL/CalTech MARK III hypercube computer. An overview of the structure of this program is presented. The performance of the solution method is demonstrated with the aid of a number of numerical test runs, and its advantages for concurrent implementations are discussed. Efficiency and speed-up factors over sequential machines for the numerical examples are highlighted.

Nour-Omid, B.↗
NASA NTRS1987

Optimal mapping of irregular finite element domains to parallel processors

Mapping the solution domain of n-finite elements into N-subdomains that may be processed in parallel by N-processors is an optimal one if the subdomain decomposition results in a well-balanced workload distribution among the processors. The problem is discussed in the context of irregular finite element domains as an important aspect of the efficient utilization of the capabilities of emerging multiprocessor computers. Finding the optimal mapping is an intractable combinatorial optimization problem, for which a satisfactory approximate solution is obtained here by analogy to a method used in statistical mechanics for simulating the annealing process in solids. The simulated annealing analogy and algorithm are described, and numerical results are given for mapping an irregular two-dimensional finite element domain containing a singularity onto the Hypercube computer.

Flower, J.↗
NASA NTRS1987

A parallelized elliptic solver for reacting flows

A modified Newton algorithm for the solution of nonlinear elliptic boundary value problems via finite discretization methods is presented. A serial implementation of this algorithm which has recently been applied successfully to the computation of an axisymmetric over-ventilated subsonic laminar methane-air jet diffusion flame is described. Parallel implementation issues and a complexity theory are presented. Included as well are actual performance data for model systems obtained on the Intel Hypercube and a discussion of its implications for modeling realistic systems.

Keyes, David E.↗
NASA NTRS1988

TRAPEDS: Producing traces for multicomputers via execution-driven simulation

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces for these simulations is a difficult problem for single processors and particularly for multicomputers. Even when existing trace methods can be used on multicomputers, the amount of collected data typically grows with the number of processors, so I/O and trace storage costs increase. A new technique is presented which modifies the executable code to dynamically collect the address trace from the user code and analyzes this trace during the execution of the program. This method helps resolve the I/O and storage problems and facilitates parallel analysis of the address trace. If a trace stored on disk is desired, the generated trace information can also be written to files during execution, with a resultant drop in program execution speed. An initial implementation on the Intel iPSC/2 hypercube multicomputer is detailed, and sample simulation results are presented. The effect of this trace collection method on execution time is illustrated.

Stunkel, Craig B.↗
NASA NTRS1989

A message passing kernel for the hypercluster parallel processing test bed

A Message-Passing Kernel (MPK) for the Hypercluster parallel-processing test bed is described. The Hypercluster is being developed at the NASA Lewis Research Center to support investigations of parallel algorithms and architectures for computational fluid and structural mechanics applications. The Hypercluster resembles the hypercube architecture except that each node consists of multiple processors communicating through shared memory. The MPK efficiently routes information through the Hypercluster, using a message-passing protocol when necessary and faster shared-memory communication whenever possible. The MPK also interfaces all of the processors with the Hypercluster operating system (HYCLOPS), which runs on a Front-End Processor (FEP). This approach distributes many of the I/O tasks to the Hypercluster processors and eliminates the need for a separate I/O support program on the FEP.

Blech, Richard A.↗
NASA NTRS1988

Totally parallel multilevel algorithms

Four totally parallel algorithms for the solution of a sparse linear system have common characteristics which become quite apparent when they are implemented on a highly parallel hypercube such as the CM2. These four algorithms are Parallel Superconvergent Multigrid (PSMG) of Frederickson and McBryan, Robust Multigrid (RMG) of Hackbusch, the FFT based Spectral Algorithm, and Parallel Cyclic Reduction. In fact, all four can be formulated as particular cases of the same totally parallel multilevel algorithm, which are referred to as TPMA. In certain cases the spectral radius of TPMA is zero, and it is recognized to be a direct algorithm. In many other cases the spectral radius, although not zero, is small enough that a single iteration per timestep keeps the local error within the required tolerance.

Frederickson, Paul O.↗
NASA NTRS1988

Speeding up parallel processing

In 1967 Amdahl expressed doubts about the ultimate utility of multiprocessors. The formulation, now called Amdahl's law, became part of the computing folklore and has inspired much skepticism about the ability of the current generation of massively parallel processors to efficiently deliver all their computing power to programs. The widely publicized recent results of a group at Sandia National Laboratory, which showed speedup on a 1024 node hypercube of over 500 for three fixed size problems and over 1000 for three scalable problems, have convincingly challenged this bit of folklore and have given new impetus to parallel scientific computing.

Denning, Peter J.↗
NASA NTRS1989

Concurrent algorithms for transient FE analysis

Information on concurrent algorithms for transient finite element analysis is given in viewgraph form. Information is given on concurrent dynamic algorithms, interprocessor communication, the performance of the BAR problem on the 32 Processor Hypercube, computational efficiency and accuracy analysis.

Ortiz, M.↗
NASA NTRS1988

Advanced flight computers for planetary exploration

Research concerning flight computers for use on interplanetary probes is reviewed. The history of these computers from the Viking mission to the present is outlined. The differences between ground commercial computers and computers for planetary exploration are listed. The development of a computer for the Mariner Mark II comet rendezvous asteroid flyby mission is described. Various aspects of recently developed computer systems are examined, including the Max real time, embedded computer, a hypercube distributed supercomputer, a SAR data processor, a processor for the High Resolution IR Imaging Spectrometer, and a robotic vision multiresolution pyramid machine for processsing images obtained by a Mars Rover.

Stephenson, R. Rhoads↗
NASA NTRS1989

Parallel multilevel adaptive methods

The progress of a project for the design and analysis of a multilevel adaptive algorithm (AFAC/HM/) targeted for the Navier Stokes Computer is discussed. The results of initial timing tests of AFAC, coupled with multigrid and an efficient load balancer, on a 16-node Intel iPSC/2 hypercube are included. The results of timing tests are presented.

Dowell, B.↗
NASA NTRS1989

A polynomial time algorithm for checking the robust stability of a polytope of polynomials

An efficient algorithm to check the robust stability of a polytope of polynomials is proposed. This problem is equivalent to a zero-exclusion condition at each frequency. It is shown that such a condition has to be checked at only a finite number of frequencies. This problem is formulated as a parametric linear program, which can be solved by the simplex procedure with additional computations between steps, consisting of polynomial evaluations and calculation of positive polynomial roots. The algorithm requires a finite number of steps (corresponding to frequency checks), and, in the important case of the polytope of parameters being a hypercube, this number is at most O(m3n), where n is the degree of the polynomials in the family and m is the number of parameters.

Sideris, Athanasios↗
NASA NTRS1990

Assignment Of Finite Elements To Parallel Processors

Elements assigned approximately optimally to subdomains. Mapping algorithm based on simulated-annealing concept used to minimize approximate time required to perform finite-element computation on hypercube computer or other network of parallel data processors. Mapping algorithm needed when shape of domain complicated or otherwise not obvious what allocation of elements to subdomains minimizes cost of computation.

Salama, Moktar A.↗
NASA NTRS1990

Computer-Access-Code Matrices

Authorized users respond to changing challenges with changing passwords. Scheme for controlling access to computers defeats eavesdroppers and "hackers". Based on password system of challenge and password or sign, challenge, and countersign correlated with random alphanumeric codes in matrices of two or more dimensions. Codes stored on floppy disk or plug-in card and changed frequently. For even higher security, matrices of four or more dimensions used, just as cubes compounded into hypercubes in concurrent processing.

Collins, Earl R., Jr.↗
NASA NTRS1989

Efficient diagnosis of multiprocessor systems under probabilistic models

The problem of fault diagnosis in multiprocessor systems is considered under a probabilistic fault model. The focus is on minimizing the number of tests that must be conducted in order to correctly diagnose the state of every processor in the system with high probability. A diagnosis algorithm that can correctly diagnose the state of every processor with probability approaching one in a class of systems performing slightly greater than a linear number of tests is presented. A nearly matching lower bound on the number of tests required to achieve correct diagnosis in arbitrary systems is also proven. Lower and upper bounds on the number of tests required for regular systems are also presented. A class of regular systems which includes hypercubes is shown to be correctly diagnosable with high probability. In all cases, the number of tests required under this probabilistic model is shown to be significantly less than under a bounded-size fault set model. Because the number of tests that must be conducted is a measure of the diagnosis overhead, these results represent a dramatic improvement in the performance of system-level diagnosis techniques.

Blough, Douglas M.↗
NASA NTRS1989

Parallel implementation and evaluation of motion estimation system algorithms on a distributed memory multiprocessor using knowledge based mappings

Several techniques to perform static and dynamic load balancing techniques for vision systems are presented. These techniques are novel in the sense that they capture the computational requirements of a task by examining the data when it is produced. Furthermore, they can be applied to many vision systems because many algorithms in different systems are either the same, or have similar computational characteristics. These techniques are evaluated by applying them on a parallel implementation of the algorithms in a motion estimation system on a hypercube multiprocessor system. The motion estimation system consists of the following steps: (1) extraction of features; (2) stereo match of images in one time instant; (3) time match of images from different time instants; (4) stereo match to compute final unambiguous points; and (5) computation of motion parameters. It is shown that the performance gains when these data decomposition and load balancing techniques are used are significant and the overhead of using these techniques is minimal.

Choudhary, Alok Nidhi↗