Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “multithreading”

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.

203 records · Page 12
All sourcesNASA NTRSDOE OSTI
DOE OSTI2016

Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdös-Rényi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.

2.5D algorithms↗
DOE OSTI2016

Efficient Synthesis of Graph Methods: a Dynamically Scheduled Architecture

RDF databases naturally map to a graph representation and employ languages, such as SPARQL, that implements queries as graph pattern matching routines. Graph methods exhibit an irregular behavior: they present unpredictable, fine-grained data accesses, and are synchronization inten- sive. Graph data structures expose large amounts of dy- namic parallelism, but are difficult to partition without gen- erating load unbalance. In this paper, we present a novel ar- chitecture to improve the synthesis of graph methods. Our design addresses the issues of these algorithms with two com- ponents: a Dynamic Task Scheduler (DTS), which reduces load unbalance and maximize resource utilization, and a Hi- erarchical Memory Interface controller (HMI), which pro- vides support for concurrent memory operations on multi- ported/multi-banked shared memories. We evaluate our ap- proach by generating the accelerators for a set of SPARQL queries from the Lehigh University Benchmark (LUBM). We first analyze the load unbalance of these queries, showing that execution time among tasks can differ even of order of magnitudes. We then synthesize the queries and com- pare the performance of the resulting accelerators against the current state of the art. Experimental results show that our solution provides a speedup over the serial implementa- tion close to the theoretical maximum and a speedup up to 3.45 over a baseline parallel implementation. We conclude our study by exploring the design space to achieve maximum memory channels utilization. The best design used at least three of the four memory channels for more than 90% of the execution time.

architecture↗
DOE OSTI2016

Fast Uncovering of Graph Communities on a Chip: Toward Scalable Community Detection on Multicore and Manycore Platforms

Graph representations are pervasive in scientific and social computing. They serve as vital tools to model the interplay among different interacting entities. In this paper, we visit the problem of community detection, which is one of the most widely used graph operations toward scientific discovery. Community detection refers to the process of identifying tightly-knit subgroups of vertices in a large graph. These sub-groups (or communities) represent vertices that are tied together through common structure or function. Identification of communities could help in understanding the modular organization of complex networks. However, owing to large data sizes and high computational costs, performing community detection at scale has become increasingly challenging. Here, we present a detailed review and analysis of some of the leading computational methods and implementations developed for executing community detection on modern day multicore and manycore architectures. Our goals are to: a) define the problem of community detection and highlight its scientific significance; b) relate to challenges in parallelizing the operation on modern day architectures; c) provide a detailed report and taxonomical classification of the approaches that have been designed for various architectures; and d) finally, provide insights into the strengths and suitability of different architectures for community detection, and a preview into the future trends of the area. It is our hope that this detailed treatment of community detection on parallel architectures can serve as an exemplar study for extending the application of modern day multicore and manycore architectures to other complex graph applications.

community detection, multithreaded platforms↗
DOE OSTI2014

Final Report: Performance Engineering Research Institute

This document is a final report about the work performed for cooperative agreement DE-FC02-06ER25764, the Rice University effort of Performance Engineering Research Institute (PERI). PERI was an Enabling Technologies Institute of the Scientific Discovery through Advanced Computing (SciDAC-2) program supported by the Department of Energy's Office of Science Advanced Scientific Computing Research (ASCR) program. The PERI effort at Rice University focused on (1) research and development of tools for measurement and analysis of application program performance, and (2) engagement with SciDAC-2 application teams.

97 MATHEMATICS AND COMPUTING↗