检索结果-内蒙古大学图书馆

Joint direct and transposed sparse matrix-vector multiplication for multithreaded CPUs

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2021年第13期33卷 e6236-e6236页

作者： Kozicky, Claudio Simecek, Ivan Czech Tech Univ Fac Informat Technol Dept Comp Syst Thakurova 9 Prague 16000 6 Czech Republic

Repeatedly performing sparse matrix-vector multiplication (SpMV) followed by transposed sparse matrix-vector multiplication (SpM(T)V) with the same matrix is a part of several algorithms, for example, the Lanczos biorthogonalization algorithm and the biconjugate gradient method. Such algorithms can benefit from combining parallel SpMV and SpM(T)V into a single operation we call joint direct and transposed sparse matrix-vector multiplication (SpMM(T)V). In this article, we present a parallel SpMM(T)V algorithm for shared-memory CPUs. The algorithm uses a sparse matrix format that divides the stored matrix into sparse matrix blocks and compresses the row and column indices of the matrix. This sparse matrix format can be also used for SpMV, SpM(T)V, and similar sparse matrix-vector operations. We expand upon existing research by suggesting new variants of the parallel SpMM(T)V algorithm and by extending the algorithm to efficiently support symmetric matrices. We compare the performance of the presented parallel SpMM(T)V algorithm with alternative approaches, which use state-of-the-art sparse matrix formats and libraries, using sparse matrices from real-world applications. The performance results indicate that the median performance of our proposed parallel SpMM(T)V algorithm is up to 45% higher than of the alternative approaches.

关键词： high‐ performance computing multithreaded execution numerical linear algebra shared‐ memory parallel algorithm SpMV storage format

来源：评论

学校读者我要写书评

暂无评论

Space-Efficient k-d Tree-Based Storage Format for Sparse Tensors 20

Space-Efficient k-d Tree-Based Storage Format for Sparse Ten...

引用

29th International Conference on High-Performance Parallel and Distributed Computing (HPDC)

作者： Simecek, Ivan Kozicky, Claudio Langr, Daniel Tvrdik, Pavel Czech Tech Univ Fac Informat Technol Dept Comp Syst Prague Czech Republic

ISBN: (纸本)9781450370523

Computations with tensors are widespread in many scientific areas. Usually, the used tensors are very large but sparse, i.e., the vast majority of their elements are zero. The space complexity of sparse tensor storage formats varies significantly. For overall efficiency, it is important to reduce the execution time and additional space requirements of the initial preprocessing (i.e., converting tensors from common storage formats to the given internal format). The main contributions of this paper are threefold. Firstly, we present a new storage format for sparse tensors, which we call the succinct k-d tree-based tensor (SKTB) format. We compare the space complexity of common tensor storage formats and of the SKTB format and demonstrate the viability of using a tree as a data structure for sparse tensors. Secondly, we present a parallel space-efficient algorithm for converting tensors to the SKTB format. Thirdly, we demonstrate the computational efficiency of the proposed format in sparse tensor-vector multiplication.

关键词： Data structures sparse tensor multithreaded execution storage complexity k-d tree OpenMP

来源：评论

学校读者我要写书评

暂无评论

Multilayer Approach for Joint Direct and Transposed Sparse Matrix Vector Multiplication for multithreaded CPUs 12th

Multilayer Approach for Joint Direct and Transposed Sparse M...

引用

12th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Simecek, Ivan Langr, Daniel Kotenkov, Ivan Czech Tech Univ Fac Informat Technol Dept Comp Syst Prague Czech Republic

ISBN: (纸本)9783319780245;9783319780238

One of the most common operations executed on modern high-performance computing systems is multiplication of a sparse matrix by a dense vector within a shared-memory computational node. Strongly related but far less studied problem is joint direct and transposed sparse matrix-vector multiplication, which is widely needed by certain types of iterative solvers. We propose a multilayer approach for joint sparse multiplication that balances the workload of threads. Measurements prove that our algorithm is scalable and achieve high computational performance for multiple benchmark matrices that arise from various scientific and engineering disciplines.

关键词： Sparse matrix-vector multiplication multithreaded execution OpenMP Joint direct and transposed multiplication Scalability

来源：评论

学校读者我要写书评

暂无评论

Nonuniform Memory Affinity Strategy in multithreaded Sparse Matrix Computations

Nonuniform Memory Affinity Strategy in Multithreaded Sparse ...

引用

High Performance Computing Symposium (HPC 2012)

作者： Srinivasa, Avinash Sosonkina, Masha Iowa State Univ Ames Lab Ames IA 50011 USA

ISBN: (纸本)9781618397881

As the core counts on modern multiprocessor systems increase, so does the memory contention with all the processes/threads trying to access the main memory simultaneously. This is typical of UMA (Uniform Memory Access) architectures with a single physical memory bank leading to poor scalability in multithreaded applications. To alleviate this problem, modern systems are moving increasingly towards Nonuniform Memory Access (NUMA) architectures, in which the physical memory is split into several (typically two or four) banks. Each memory bank is associated with a set of cores enabling threads to operate from their own physical memory banks while retaining the concept of a shared virtual address space. However, accessing shared data structures from the remote memory banks may become increasingly slow. This paper proposes a way to determine and pin certain parts of the shared data to specific memory banks, thus minimizing remote accesses. To achieve this, the existing application code may be supplied with the proposed interface to set up and distribute shared data appropriately among memory banks. Experiments with the NAS CG benchmark as well as with a realistic large-scale application calculating ab initio nuclear structure have been performed. Speedups of up to 3.5 times were observed with the proposed approach compared with the default memory placement policy.

关键词： Memory affinity Nonuniform Memory Access (NUMA) node multithreaded execution Shared array Sparse matrix-vector multiply

来源：评论

学校读者我要写书评

暂无评论

Effcient Shared-array Accesses in Ab Initio Nuclear Structure Calculations on Multicore Architectures

引用

Procedia Computer Science 2012年 9卷 256-265页

作者： Avinash Srinivasa Masha Sosonkina Pieter Maris James P. Vary U.S. DOE Ames Laboratory Iowa State University Ames IA 50011 USA Department of Physics and Astronomy Iowa State University Ames IA 50011 USA

With the increase in the processing core counts on modern computing platforms, the main memory accesses present a considerable execution bottleneck, leading to poor scalability in multithreaded applications. Even when the memory is physically divided into separate banks, each associated with a set of cores, i.e., exhibiting the so called nonuniform memory access (NUMA) architecture, the access time to the shared data structures may be detrimental to the scalability. Hence, it is imperative to carefully map large shared arrays to speciﬁc memory banks based on the nature of the computation and the multithreaded parallelism characteristics. This paper describes memory-pinning strategies pertinent to sparse matrix-vector multiplication and vector orthogonalization phases of an ab initio nuclear structure computation performed by the MFDn package. Several nuclei and nuclear interactions were considered in the large-scale test cases with the dimensions of the sparse symmetric matrices ranging from 32 million to 320 million. Performance gains of up to 25% were observed with the proposed strategies as compared to the default memory placement policy.

关键词： Nonuniform memory access (NUMA) node multithreaded execution Memory affnity Sparse matrix-vector multiply Vector orthogonalization Ab initio nuclear structure calculation

来源：评论

学校读者我要写书评

暂无评论

Automatic Formal Verification of multithreaded Pipelined Microprocessors

Automatic Formal Verification of Multithreaded Pipelined Mic...

引用

IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

作者： Velev, Miroslav N. Gao, Ping Aries Design Automat LLC Chicago IL 60618 USA

ISBN: (纸本)9781457713989

We present highly automatic techniques for formal verification of pipelined microprocessors with hardware support for multithreading. The processors are modeled at a high level of abstraction, using a subset of Verilog, in a way that allows us to exploit the property of Positive Equality that results in significant simplifications of the solution space, and orders of magnitude speedup relative to previous methods. We propose abstraction techniques that produce at least 3 orders of magnitude speedup, which is increasing with the number of threads implemented in a pipelined processor. To the best of our knowledge, this is the first work on automatic formal verification of pipelined processors with hardware support for multithreading.

关键词： abstraction Correspondence Checking decision procedures formal verification Logic of Equality with Uninterpreted Functions and Memories (EUFM) multithreaded execution pipelined processors Positive Equality SAT SMT

来源：评论

学校读者我要写书评

暂无评论

A HYBRID SHARED MEMORY execution MODEL FOR A DATA PARALLEL LANGUAGE WITH I/O

引用

PARALLEL PROCESSING LETTERS 2008年第1期18卷 23-37页

作者： Grelck, Clemens Kuthe, Steffen Scholz, Sven-Bodo Univ Lubeck Inst Software Technol & Programming Languages Ratzeburger Allee 160 D-23538 Lubeck Germany Univ Hertfordshire Dept Comp Sci Hatfield AL10 9AB Herts England

We propose a novel execution model for the implicitly parallel execution of data parallel programs in the presence of general I/O operations. This model is called hybrid because it combines the advantages of the standard execution models fork/join and SPMD. Based on program analysis the hybrid model adapts itself to one or the other on the granularity of individual instructions. We outline compilation techniques that systematically derive the organization of parallel code from data flow characteristics aiming at the reduction of execution mode switches in general and synchronization/communication requirements in particular. Experiments based on a prototype implementation show the effectiveness of the hybrid execution model for reducing parallel overhead.

关键词： multithreaded execution execution models implicit parallelisation Single Assignment C declarative array programming data parallel programming

来源：评论

学校读者我要写书评

暂无评论

Performance of shared caches on multithreaded architectures

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 1998年第2期14卷 499-514页

作者： Chen, YY Peir, JK King, CT Ind Technol Res Inst Comp & Commun Res Lab ATC Hsinchu 310 Taiwan Univ Florida Dept Comp & Informat Sci Gainesville FL 32611 USA Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan

A multithreaded computer maintains multiple program counters and register files to support concurrent or overlapping execution of multiple threads of context, and to provide fast context switching for tolerance of memory latency. In this paper, we apply trace-driven simulation to study the performance impact of a multithreaded architecture on the storage hierarchy. In particalar, we examined the effects of different multithread scheduling techniques on cache performance. Using several program traces representing a typical server/workstation workload mix, we find that cache performance can be improved over that of the traditional round-robin scheduling method when the thread with the MRU hit is given a higher priority. With a direct-mapped cache, the absolute hit ratio can be improved by more than 7%. We also study the performance effects of the multithreading degree, i.e., the number of threads coexisting in the processor at the same time, an cache memory. The results show that both cache size and set associativity need to increase according to the multithreading degree in order to maintain comparable cache performance.

关键词： computer architecture multithreaded execution cache system performance evaluation scheduling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：