Search NASA⌕ Search

SEARCH · Search NASA

Results for “MULTIPROCESSORS”

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 307 records · Page 17

Shared Memory Parallelization of an Implicit ADI-type CFD Code

A parallelization study designed for ADI-type algorithms is presented using the OpenMP specification for shared-memory multiprocessor programming. Details of optimizations specifically addressed to cache-based computer architectures are described and performance measurements for the single and multiprocessor implementation are summarized. The paper demonstrates that optimization of memory access on a cache-based computer architecture controls the performance of the computational algorithm. A hybrid MPI/OpenMP approach is proposed for clusters of shared memory machines to further enhance the parallel performance. The method is applied to develop a new LES/DNS code, named LESTool. A preliminary DNS calculation of a fully developed channel flow at a Reynolds number of 180, Re(sub tau) = 180, has shown good agreement with existing data.

Hauser, Th.↗

By Hand or Not By-Hand: A Case Study of Alternative Approaches to Parallelize CFD Applications

While parallel processing promises to speed up applications by several orders of magnitude, the performance achieved still depends upon several factors, including the multiprocessor architecture, system software, data distribution and alignment, as well as the methods used for partitioning the application and mapping its components onto the architecture. The existence of the Gorden Bell Prize given out at Supercomputing every year suggests that while good performance can be attained for real applications on general purpose multiprocessors, the large investment in man-power and time still has to be repeated for each application-machine combination. As applications and machine architectures become more complex, the cost and time-delays for obtaining performance by hand will become prohibitive. Computer users today can turn to three possible avenues for help: parallel libraries, parallel languages and compilers, interactive parallelization tools. The success of these methodologies, in turn, depends on proper application of data dependency analysis, program structure recognition and transformation, performance prediction as well as exploitation of user supplied knowledge. NASA has been developing multidisciplinary applications on highly parallel architectures under the High Performance Computing and Communications Program. Over the past six years, the transition of underlying hardware and system software have forced the scientists to spend a large effort to migrate and recede their applications. Various attempts to exploit software tools to automate the parallelization process have not produced favorable results. In this paper, we report our most recent experience with CAPTOOL, a package developed at Greenwich University. We have chosen CAPTOOL for three reasons: 1. CAPTOOL accepts a FORTRAN 77 program as input. This suggests its potential applicability to a large collection of legacy codes currently in use. 2. CAPTOOL employs domain decomposition to obtain parallelism. Although the fact that not all kinds of parallelism are handled may seem unappealing, many NASA applications in computational aerosciences as well as earth and space sciences are amenable to domain decomposition. 3. CAPTOOL generates code for a large variety of environments employed across NASA centers: MPI/PVM on network of workstations to the IBS/SP2 and CRAY/T3D.

Yan, Jerry C.↗

The Design and Evaluation of "CAPTools"--A Computer Aided Parallelization Toolkit

Writing applications for high performance computers is a challenging task. Although writing code by hand still offers the best performance, it is extremely costly and often not very portable. The Computer Aided Parallelization Tools (CAPTools) are a toolkit designed to help automate the mapping of sequential FORTRAN scientific applications onto multiprocessors. CAPTools consists of the following major components: an inter-procedural dependence analysis module that incorporates user knowledge; a 'self-propagating' data partitioning module driven via user guidance; an execution control mask generation and optimization module for the user to fine tune parallel processing of individual partitions; a program transformation/restructuring facility for source code clean up and optimization; a set of browsers through which the user interacts with CAPTools at each stage of the parallelization process; and a code generator supporting multiple programming paradigms on various multiprocessors. Besides describing the rationale behind the architecture of CAPTools, the parallelization process is illustrated via case studies involving structured and unstructured meshes. The programming process and the performance of the generated parallel programs are compared against other programming alternatives based on the NAS Parallel Benchmarks, ARC3D and other scientific applications. Based on these results, a discussion on the feasibility of constructing architectural independent parallel applications is presented.

Yan, Jerry↗

Mobile Thread Task Manager

The Mobile Thread Task Manager (MTTM) is being applied to parallelizing existing flight software to understand the benefits and to develop new techniques and architectural concepts for adapting software to multicore architectures. It allocates and load-balances tasks for a group of threads that migrate across processors to improve cache performance. In order to balance-load across threads, the MTTM augments a basic map-reduce strategy to draw jobs from a global queue. In a multicore processor, memory may be "homed" to the cache of a specific processor and must be accessed from that processor. The MTTB architecture wraps access to data with thread management to move threads to the home processor for that data so that the computation follows the data in an attempt to avoid L2 cache misses. Cache homing is also handled by a memory manager that translates identifiers to processor IDs where the data will be homed (according to rules defined by the user). The user can also specify the number of threads and processors separately, which is important for tuning performance for different patterns of computation and memory access. MTTM efficiently processes tasks in parallel on a multiprocessor computer. It also provides an interface to make it easier to adapt existing software to a multiprocessor environment.

Clement, Bradley J.↗

Singular value decomposition utilizing parallel algorithms on graphical processors

One of the current challenges in underwater acoustic array signal processing is the detection of quiet targets in the presence of noise. In order to enable robust detection, one of the key processing steps requires data and replica whitening. This, in turn, involves the eigen-decomposition of the sample spectral matrix, Cx = 1/K xKX(k)XH(k) where X(k) denotes a single frequency snapshot with an element for each element of the array. By employing the singular value decomposition (SVD) method, the eigenvectors and eigenvalues can be determined directly from the data without computing the sample covariance matrix, reducing the computational requirements for a given level of accuracy (van Trees, Optimum Array Processing). (Recall that the SVD of a complex matrix A involves determining V, , and U such that A = U VH where U and V are orthonormal and is a positive, real, diagonal matrix containing the singular values of A. U and V are the eigenvectors of AAH and AHA, respectively, while the singular values are the square roots of the eigenvalues of AAH.) Because it is desirable to be able to compute these quantities in real time, an efficient technique for computing the SVD is vital. In addition, emerging multicore processors like graphical processing units (GPUs) are bringing parallel processing capabilities to an ever increasing number of users. Since the computational tasks involved in array signal processing are well suited for parallelization, it is expected that these computations will be implemented using GPUs as soon as users have the necessary computational tools available to them. Thus, it is important to have an SVD algorithm that is suitable for these processors. This work explores the effectiveness of two different parallel SVD implementations on an NVIDIA Tesla C2050 GPU (14 multiprocessors, 32 cores per multiprocessor, 1.15 GHz clock - peed). The first algorithm is based on a two-step algorithm which bidiagonalizes the matrix using Householder transformations, and then diagonalizes the intermediate bidiagonal matrix through implicit QR shifts. This is similar to that implemented for real matrices by Lahabar and Narayanan ("Singular Value Decomposition on GPU using CUDA", IEEE International Parallel Distributed Processing Symposium 2009). The implementation is done in a hybrid manner, with the bidiagonalization stage done using the GPU while the diagonalization stage is done using the CPU, with the GPU used to update the U and V matrices. The second algorithm is based on a one-sided Jacobi scheme utilizing a sequence of pair-wise column orthogonalizations such that A is replaced by AV until the resulting matrix is sufficiently orthogonal (that is, equal to U ). V is obtained from the sequence of orthogonalizations, while can be found from the square root of the diagonal elements of AH A and, once is known, U can be found from column scaling the resulting matrix. These implementations utilize CUDA Fortran and NVIDIA's CUB LAS library. The primary goal of this study is to quantify the comparative performance of these two techniques against themselves and other standard implementations (for example, MATLAB). Considering that there is significant overhead associated with transferring data to the GPU and with synchronization between the GPU and the host CPU, it is also important to understand when it is worthwhile to use the GPU in terms of the matrix size and number of concurrent SVDs to be calculated.

99 GENERAL AND MISCELLANEOUS↗

CUDA Computation of the Feynman Distribution

In 2006, NVIDIA Corporation introduced the Computer Unified Device Architecture (CUDA) for C, C++, and Fortran programming languages. The CUDA parallel computing platform uses the Graphics Processing Unit (GPU) of NVIDIA graphics card, and it is designed for parallel computations. In these computations, the same algorithms are executed on the data in parallel. The GPU contains many Streaming Multiprocessors (SM) that can independently execute blocks of threads. A thread is a sequence of serial programmed instructions. The SM executes threads in groups of 32 and a group of 32 threads is called warp. The threads within a block can be synchronized and have access to a shared memory that is visible only to them. Conversely, blocks of threads cannot be synchronized and have access only to the global memory of the graphics card. This memory is called device memory and is independent of the host memory controlled by the Central Processing Unit (CPU). A single thread has access to a local memory (register) that is not visible to any other thread. The part of the program that is executed on the graphics card is called kernel. Each thread of the kernel has a unique identification index that is accessible by the in-built variable threadIdx; the latter is a 3-component vector. A threads block can contain up to 1024 threads. Blocks of threads have a unique identification index that is accessible by the in-built variable blockIdx; the latter is a 3-component vector. The in-built variable blockDim contains the number of threads per block; this variable is a 3-component vector. Threads and blocks represent different levels of parallelism; a kernel is executed as a grid of blocks of threads. Figure 1 illustrates a grid of thread blocks for a GPU with 2 SM. A SM can execute multiple blocks of threads in parallel; a block of threads is executed on a single SM. A GPU can execute multiple kernels concurrently. This work has used the Quadro M5000 graphics card with the following technical specifications: - 2048 cores with 861 MHz frequency, - 16 streaming multiprocessors, - 5.2 trillion transistors, - 8.2 Gb device memory, - 64 kb register memory (per thread), - 48 kb shared memory (per block) - 211.6 GB/s memory bandwidth, and - 3.5 GFLOPS floating point performance.

97 MATHEMATICS AND COMPUTING↗

NASA's New Millennium Program : The Space Technology 8 (ST8) Mission

This viewgraph presentation reviews the planning for the mission of Space Technology 8 (ST8). ST8 is a low-cost mission that will demonstrate 4 technology experiments: the SAILMAST, Ultraflex 175, Thermal Loop and a Dependable Multiprocessor. These technologies are described. The development and demonstration of these technologies will enable future missions.

Ultaflex 175↗

Neutronics Calculation of Fast Reactor Using Modern Computing Systems

The possibility of using the LUCKY-A three-dimensional multiprocessor transport code as a neutronics module for the COREMELT integrated non-stationary code for performing safety analysis, which is used for fast sodium reactor safety validation, is discussed. In this application, more stringent requirements are imposed on the computing speed of the LUCKY-A code. To test LUCKY-A possibilities, a typical computational problem is examined in a formulation characteristic for the proposed use of the code. The possibilities of the code for parallelized calculations are shown, and a comparison is made with calculations performed with the MMKKENO and TRIGEX codes. The efficacy of a parallel computational process is investigated as a function of the number of computing kernels used.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Real-Time Considerations for Rugged Embedded Systems

This chapter introduces the characterizing aspects of embedded systems, and discusses the specific features that a designer should address to an embedded system “rugged”, i.e., able to operate reliably in harsh environments. The chapter addresses both the hardware and the less obvious software aspect. After presenting a current list of certifications for ruggedization, the chapters present a case study that focuses on the interaction of the hardware and software layers in reactive real-time system. In particular, it shows how the use of fast FPGA prototyping could provide insights on unexpected factors that influence the performance and thus responsiveness to events of a scheduling algorithm for multiprocessor systems that manages both periodic, hard real-time task, and aperiodic tasks. The main lesson is that to make the system “rugged”, a designer should consider these issues by, for example, overprovisioning resources and/or computation capabilities.

FPGA↗

SYNTHETIC SPECTRA OF RADIO, MILLIMETER, SUB-MILLIMETER, AND INFRARED REGIMES WITH NON-LOCAL THERMODYNAMIC EQUILIBRIUM APPROXIMATION

We use a numerical code called PAKALMPI to compute synthetic spectra of the solar emission in quiet conditions at millimeter, sub-millimeter, and infrared wavelengths. PAKALMPI solves the radiative transfer equation, with non-local thermodynamic equilibrium (NLTE), in a three-dimensional geometry using a multiprocessor environment. The code is able to use three opacity functions: classical bremsstrahlung, H{sup -}, and inverse bremsstrahlung. In this work, we have computed and compared two synthetic spectra, one in the common way: using bremsstrahlung opacity function and considering a fully ionized atmosphere; and a new one considering bremsstrahlung, inverse bremsstrahlung, and H{sup -} opacity functions in NLTE. We analyzed in detail the local behavior of the low atmospheric emission at 17, 212, and 405 GHz (frequencies used by the Nobeyama Radio Heliograph and the Solar Submillimeter Telescope). We found that the H{sup -} is the major emission mechanism at low altitudes (below 500 km) and that at higher altitudes the classical bremsstrahlung becomes the major mechanism of emission. However, the brightness temperature remains unalterable. Finally, we found that the inverse bremsstrahlung process is not important for radio emission at these heights.

79 ASTRONOMY AND ASTROPHYSICS↗

SHELXT – Integrated space-group and crystal-structure determination

SHELXT automates routine small-molecule structure determination starting from single-crystal reflection data, the Laue group and a reasonable guess as to which elements might be present. The new computer program SHELXT employs a novel dual-space algorithm to solve the phase problem for single-crystal reflection data expanded to the space group P1. Missing data are taken into account and the resolution extended if necessary. All space groups in the specified Laue group are tested to find which are consistent with the P1 phases. After applying the resulting origin shifts and space-group symmetry, the solutions are subject to further dual-space recycling followed by a peak search and summation of the electron density around each peak. Elements are assigned to give the best fit to the integrated peak densities and if necessary additional elements are considered. An isotropic refinement is followed for non-centrosymmetric space groups by the calculation of a Flack parameter and, if appropriate, inversion of the structure. The structure is assembled to maximize its connectivity and centred optimally in the unit cell. SHELXT has already solved many thousand structures with a high success rate, and is optimized for multiprocessor computers. It is, however, unsuitable for severely disordered and twinned structures because it is based on the assumption that the structure consists of atoms.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

GPU-Centric Communication on NVIDIA GPU Clusters with InfiniBand: A Case Study with OpenSHMEM

GPUs have become an essential component for building compute clusters with high compute density and high performance per watt. As such clusters scale to have 1000s of GPUs, efficiently moving data between the GPUs becomes imperative to get maximum performance. NVSHMEM is an implementation of the OpenSHMEM standard for NVIDIA GPU clusters which allows communication to be issued from inside GPU kernels. In earlier work, we have shown how NVSHMEM can be used to achieve better application performance on GPUs connected through PCIe or NVLink. As part of this effort, we implement IB verbs for Mellanox InfiniBand adapters in CUDA. We evaluate different design alternatives, taking into consideration the relaxed memory model, automatic memory access coalescing and thread hierarchy on the GPU. We also consider correctness issues that arise in these designs. We take advantage of these designs transparently or through API extensions in NVSHMEM. With micro-benchmarks, we show that a Nvidia Pascal P100 GPU is able saturate the network bandwidth using only one or two of its 56 available streaming multiprocessors (SM). On a single GPU using a single IB EDR adapter, we achieve a throughput of around 90 million messages per second. In addition, we implement a 2dstencil application kernel using NVSHMEM and compare its performance with a CUDA-aware MPI-based implementation that uses GPUDirect RDMA. Speedups in the range of 23% to 42% are seen for input sizes large enough to fill the occupancy of Nvidia Pascal P100 GPUs on 2 to 4 nodes indicating that there are gains to be had by eliminating the CPU from the communication path when all computation runs on the GPU.

Potluri, Sreeram↗

Performance Assessment of Emerging Memories Through FPGA Emulation

Emerging memory technologies offer the prospect of large capacity, high bandwidth, and a range of access latencies ranging from DRAM-like to SSD-like. In this paper, we evaluate the performance of parallel applications on CPUs whose main memories sweep a wide range of latencies within a bandwidth cap. We use an FPGA emulator, the logic in memory emulator (LiME) to accelerate evaluation. The LiME framework uses a multiprocessor system on chip (MPSoC) combining multicore CPU, integrated memory controller, and FPGA fabric, and enables emulation orders of magnitude faster than software simulation. This work highlights the performance impact of higher latency on concurrent applications and identifies conditions under which future high latency memories can effectively be used as main memory.

97 MATHEMATICS AND COMPUTING↗

Composing Data Parallel Code for a SPARQL Graph Engine

Big data analytics process large amount of data to extract knowledge from them. Semantic databases are big data applications that adopt the Resource Description Framework (RDF) to structure metadata through a graph-based representation. The graph based representation provides several benefits, such as the possibility to perform in memory processing with large amounts of parallelism. SPARQL is a language used to perform queries on RDF-structured data through graph matching. In this paper we present a tool that automatically translates SPARQL queries to parallel graph crawling and graph matching operations. The tool also supports complex SPARQL constructs, which requires more than basic graph matching for their implementation. The tool generates parallel code annotated with OpenMP pragmas for x86 Shared-memory Multiprocessors (SMPs). With respect to commercial database systems such as Virtuoso, our approach reduces memory occupation due to join operations and provides higher performance. We show the scaling of the automatically generated graph-matching code on a 48-core SMP.

Big data↗

Select Advances in Computational Accelerator Physics

Computational accelerator physics has changed and broadened over the last decade or so. Part of the change is due to the advent of multiple ways of parallel computing. Another part comes from algorithmic developments. The multiple ways of parallel computing include distributed memory parallelism and on-chip parallelism, with the latter coming from architectures (CPU and GPU) having multiple processing elements (cores or streaming multiprocessors) and wide vector (SIMD) instruction units. The basics of these new architectures and their application to computational accelerator physics are briefly reviewed. Algorithmic advances in the select areas of spin tracking, cavity calculations, plasma acceleration, and electron cooling are also reviewed. In some cases the algorithms provide increased fidelity improving the overall accuracy, while in other cases, such as controlled dispersion, the algorithms provide increased fidelity by better modeling the essential physical interaction. Finally, the use of computational frameworks, which provide the basic computational infrastructure, while allowing the capability developer to concentrate on the math and physics, is reviewed in the context of the Vorpal application, which has found use across accelerator physics and many other fields.

Engineering↗

Fast and Accurate Simulation of the Cray XMT Multithreaded Supercomputer

Irregular applications, such as data mining and analysis or graph-based computations, show unpredictable memory/network access patterns and control structures. Highly multithreaded architectures with large processor counts, like the Cray MTA-1, MTA-2 and XMT, appear to address their requirements better than commodity clusters. However, the research on highly multithreaded systems is currently limited by the lack of adequate architectural simulation infrastructures due to issues such as size of the machines, memory footprint, simulation speed, accuracy and customization. At the same time, Shared-memory MultiProcessors (SMPs) with multi-core processors have become an attractive platform to simulate large scale machines. In this paper, we introduce a cycle-level simulator of the highly multithreaded Cray XMT supercomputer. The simulator runs unmodified XMT applications. We discuss how we tackled the challenges posed by its development, detailing the techniques introduced to make the simulation as fast as possible while maintaining a high accuracy. By mapping XMT processors (ThreadStorm with 128 hardware threads) to host computing cores, the simulation speed remains constant as the number of simulated processors increases, up to the number of available host cores. The simulator supports zero-overhead switching among different accuracy levels at run-time and includes a network model that takes into account contention. On a modern 48-core SMP host, our infrastructure simulates a large set of irregular applications 500 to 2000 times slower than real time when compared to a 128-processor XMT, while remaining within 10\% of accuracy. Emulation is only from 25 to 200 times slower than real time.

Cray XMT↗

A lock-free priority queue design based on multi-dimensional linked lists

The throughput of concurrent priority queues is pivotal to multiprocessor applications such as discrete event simulation, best-first search and task scheduling. Existing lock-free priority queues are mostly based on skiplists, which probabilistically create shortcuts in an ordered list for fast insertion of elements. The use of skiplists eliminates the need of global rebalancing in balanced search trees and ensures logarithmic sequential search time on average, but the worst-case performance is linear with respect to the input size. In this paper, we propose a quiescently consistent lock-free priority queue based on a multi-dimensional list that guarantees worst-case search time of O(logN) for key universe of size N. The novel multi-dimensional list (MDList) is composed of nodes that contain multiple links to child nodes arranged by their dimensionality. The insertion operation works by first injectively mapping the scalar key to a high-dimensional vector, then uniquely locating the target position by using the vector as coordinates. Nodes in MDList are ordered by their coordinate prefixes and the ordering property of the data structure is readily maintained during insertion without rebalancing nor randomization. Furthermore, in our experimental evaluation using a micro-benchmark, our priority queue achieves an average of 50% speedup over the state of the art approaches under high concurrency.

97 MATHEMATICS AND COMPUTING↗

Computing Maximum Cardinality Matchings in Parallel on Bipartite Graphs via Tree-Grafting

It is difficult to obtain high performance when computing matchings on parallel processors because matching algorithms explicitly or implicitly search for paths in the graph, and when these paths become long, there is little concurrency. In spite of this limitation, we present a new algorithm and its shared-memory parallelization that achieves good performance and scalability in computing maximum cardinality matchings in bipartite graphs. This algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favorably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. Here, we provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor and to 240 threads on an Intel Knights Corner coprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.

97 MATHEMATICS AND COMPUTING↗