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

35th ACM International Conference on Supercomputing (ICS)

作者： Demirci, Gunduz Vehbi Ferhatosmanoglu, Hakan Univ Warwick Coventry W Midlands England

ISBN: (纸本)9781450383356

The state-of-the-art deep neural networks (DNNs) have significant computational and data management requirements. The size of both training data and models continue to increase. Sparsification and pruning methods are shown to be effective in removing a large fraction of connections in DNNs. The resulting sparse networks present unique challenges to further improve the computational efficiency of training and inference in deep learning. Both the feed-forward (inference) and backpropagation steps in stochastic gradient descent (SGD) algorithm for training sparse DNNs involve consecutive sparse matrix-vector multiplications (SpMVs). We first introduce a distributed-memory parallel SpMV-based solution for the SGD algorithm to improve its scalability. The parallelization approach is based on row-wise partitioning of weight matrices that represent neuron connections between consecutive layers. We then propose a novel hypergraph model for partitioning weight matrices to reduce the total communication volume and ensure computational load-balance among processors. Experiments performed on sparse DNNs demonstrate that the proposed solution is highly efficient and scalable. By utilizing the proposed matrix partitioning scheme, the performance of our solution is further improved significantly.

关键词： Scalable Deep Learning sparse Deep Neural Networks Distributed Stochastic Gradient Descent Hypergraph Partitioning sparse matrix vector multiplication

来源：评论

学校读者我要写书评

暂无评论

Fast Spectral Graph Layout on Multicore Platforms 20

Fast Spectral Graph Layout on Multicore Platforms

引用

49th International Conference on Parallel Processing (ICPP)

作者： Mishra, Ashirbad Kirmani, Shad Madduri, Kamesh Penn State Univ University Pk PA 16802 USA eBay Inc San Jose CA USA

ISBN: (纸本)9781450388160

We present ParHDE, a shared-memory parallelization of the High-Dimensional Embedding (HDE) graph algorithm. Originally proposed as a graph drawing algorithm, HDE characterizes the global structure of a graph and is closely related to spectral graph computations such as computing the eigenvectors of the graph Laplacian. We identify compute- and memory-intensive steps in HDE and parallelize these steps for efficient execution on shared-memory multicore platforms. ParHDE can process graphs with billions of edges in minutes, is up to 18x faster than a prior parallel implementation of HDE, and achieves up to a 24x relative speedup on a 28-core system. We also implement several extensions of ParHDE and demonstrate its utility in diverse graph computation-related applications.

关键词： graph layout graph embedding breadth-first search sparse matrix vector multiplication orthogonalization

来源：评论

学校读者我要写书评

暂无评论

CSCC: Convolution Split Compression Calculation Algorithm for Deep Neural Network

引用

IEEE ACCESS 2019年 7卷 71607-71615页

作者： Fan, Shengyu Yu, Hui Lu, Dianjie Jiao, Shuai Xu, Weizhi Liu, Fangai Liu, Zhiyong Shandong Normal Univ Sch Informat Sci & Engn Jinan 250358 Shandong Peoples R China Shandong Normal Univ Sch Business Jinan 250358 Shandong Peoples R China Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China

Convolutional Neural Networks (CNNs) have become one of the most successful machine learning techniques for image and video processing. The most computationally intensive part of the CNN is the convolutional layers, which have the multi-channel image and multiple kernels. However, due to the network pruning operation and the application of RELU activation function operation in the training process, numerous zero values are generated in the network. This paper proposes the convolution split compression calculation (CSCC) algorithm, which improves the performance of the convolution layer by utilizing the sparse characteristic of the feature map. In the CSCC algorithm, first, the feature map is directly converted into a sparse matrix of compressed sparse row (CSR) format, which avoids expanding feature map to an intermediate matrix and reduces the memory space consumption. Second, the convolution kernel is converted into a vector. Finally, the convolution result is obtained by the sparse matrix vector multiplication (SpMV). The experimental results show that the CSCC algorithm has a good advantage in computation speed and memory consumption compared with the other convolution algorithms.

关键词： Convolutional neural network sparse matrix vector multiplication neural networks convolution sparse matrices

来源：评论

学校读者我要写书评

暂无评论

Evaluate Metadata of sparse matrix for SpMV on Shared Memory Architecture

引用

INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS 2019年第11期10卷 614-623页

作者： Maruf, Nazmul Ahasan Ahmed, Waseem King Abdulaziz Univ Fac Comp & Informat Technol Jeddah Saudi Arabia

sparse matrix operations are frequently used operations in scientific, engineering and high-performance computing (HPC) applications. Among them, sparse matrix-vector multiplication (SpMV) is a popular kernel and considered an important numerical method for science, engineering and in scientific computing. However, SpMV is a computationally expensive operation. To obtain better performance, SpMV depends on certain factors;choosing the right storage format for the sparse matrix is one of them. Other things like data access pattern, the sparsity of the matrix data set, load balancing, sharing of the memory hierarchy, etc. are other factors that affect performance. Metadata, that describes the substructure of the sparse matrix, like shape, density, sparsity, etc. of the sparse matrix also affects performance efficiency for any sparse matrix operation. Various approaches presented in literature over the last few decades given good results for certain types of matrix structures and don't perform as well with others. Developers thus are faced with a difficulty in choosing the most appropriate format. In this research, an approach is presented that evaluates metadata of a given sparse matrix and suggest to the developers the most suitable storage format to use for SpMV.

关键词： sparse matrix vector multiplication sparse matrix metadata sparse matrix vector multiplication parallelization shared memory architecture sparse matrix storage formats high performance computing

来源：评论

学校读者我要写书评

暂无评论

Exploiting dense substructures for fast sparse matrix vector multiplication

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2011年第3期25卷 328-341页

作者： Shantharam, Manu Chatterjee, Anirban Raghavan, Padma Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Penn State Univ Inst CyberSci University Pk PA 16802 USA

The execution time of many scientific computing applications is dominated by the time spent in performing sparse matrix vector multiplication (SMV;y <- A . x). We consider improving the performance of SMV on multicores by exploiting the dense substructures that are inherently present in many sparse matrices derived from partial differential equation models. First, we identify indistinguishable vertices, i.e., vertices with the same adjacency structure, in a graph representation of the sparse matrix (A) and group them into a supernode. Next, we identify effectively dense blocks within the matrix by grouping rows and columns in each supernode. Finally, by using a suitable data structure for this representation of the matrix, we reduce the number of load operations during SMV while exactly preserving the original sparsity structure of A. In addition, we use ordering techniques to enhance locality in accesses to the vector, x, to yield an SMV kernel that exploits the effectively dense substructures in the matrix. We evaluate our scheme on Intel Nehalem and AMD Shanghai processors. We observe that for larger matrices on the Intel Nehalem processor, our method improves performance on average by 37.35% compared with the traditional compressed sparse row scheme (a blocked compressed form improves performance on average by 30.27%). Benefits of our new format are similar for the AMD processor. More importantly, if we pick for each matrix the best among our method and the blocked compressed scheme, the average performance improvements increase to 40.85%. Additional results indicate that the best performing scheme varies depending on the matrix and the system. We therefore propose an effective density measure that could be used for method selection, thus adding to the variety of options for an auto-tuned optimized SMV kernel that can exploit sparse matrix properties and hardware attributes for high performance.

关键词： compressed storage formats envelope ordering performance sparse matrix vector multiplication supernodes

来源：评论

学校读者我要写书评

暂无评论

Exploiting dense substructures for fast sparse matrix vector multiplication

Exploiting dense substructures for fast sparse matrix vector...

引用

Workshop on Clusters, Clouds and Grids for Scientific Computing (CCGSC)

作者： Shantharam, Manu Chatterjee, Anirban Raghavan, Padma Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Penn State Univ Inst CyberSci University Pk PA 16802 USA

关键词： compressed storage formats envelope ordering performance sparse matrix vector multiplication supernodes

来源：评论

学校读者我要写书评

暂无评论

Cascaded DMA Controller for Speedup of Indirect Memory Access in Irregular Applications 9

Cascaded DMA Controller for Speedup of Indirect Memory Acces...

引用

9th IEEE/ACM Workshop on Irregular Applications - Architectures and Algorithms (IA3)

作者： Kashimata, Tomoya Kitamura, Toshiaki Kimura, Keiji Kasahara, Hironori Waseda Univ Tokyo Japan

ISBN: (纸本)9781728159874

Indirect memory accesses caused by sparse linear algebra calculations are widely used in important real applications. However, they also cause serious inefficient memory accesses and pipeline stalls resulting in low execution efficiency even with high memory bandwidth and much computational resource. One of the important issues of indirect memory accesses, such as accessing A[B[i]], is it requires two successive memory accesses: the index loads (B[i]) and the following data element accesses (A[B[i]]). To overcome this situation, we propose the Cascaded-DMAC (CDMAC). This CDMAC is intended to be attached in each core of a multicore chip in addition to a CPU core, a vector accelerator, and a local data memory. It performs data transfers between an off-chip main memory and an in-core local data memory, which provides data to the accelerator. The key idea of the CDMAC is cascading two DMACs so that the first one loads indices, then the second one accesses data elements by using these indices. Thus, this organization realizes the autonomous indirect memory accesses by giving an index array and an element array, and obtains the efficient SIMD computations by lining up the sparse data into the local data memory. We implemented a multicore processor having the proposed CDMAC on an FPGA board. The evaluation result of sparse matrix-vector multiplications on the FPGA shows that the CDMAC achieves a maximum speedup of 17x compared with the CPU data transfer.

关键词： Cascaded DMA Controller CDMAC DMAC DMA indirect memory access sparse matrix vector multiplication SpMV SMVM

来源：评论

学校读者我要写书评

暂无评论

Design and Implementation of Adaptive SpMV Library for Multicore and Many-Core Architecture

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2018年第4期44卷 1–25页

作者： Tan, Guangming Liu, Junhong Li, Jiajia Univ Chinese Acad Sci Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing Peoples R China Georgia Inst Technol Computat Sci & Engn Atlanta GA 30332 USA Chinese Acad Sci Inst Comp Technol Beijing Peoples R China

sparse matrix vector multiplication (SpMV) is an important computational kernel in traditional highperformance computing and emerging data-intensive applications. Previous SpMV libraries are optimized by either application-specific or architecture-specific approaches but present difficulties for use in real applications. In this work, we develop an auto-tuning system (SMATER) to bridge the gap between specific optimizations and general-purpose use. SMATER provides programmers a unified interface based on the compressed sparse row (CSR) sparse matrix format by implicitly choosing the best format and fastest implementation for any input sparse matrix during runtime. SMATER leverages a machine-learning model and retargetable back-end library to quickly predict the optimal combination. Performance parameters are extracted from 2,386 matrices in the Suitesparse matrix collection. The experiments show that SMATER achieves good performance (up to 10 times that of the Intel Math Kernel Library (MKL) on Intel E5-2680 v3) while being portable on state-of-the-art x86 multicore processors, NVIDIA GPUs, and Intel Xeon Phi accelerators. Compared with the Intel MKL library, SMATER runs faster by more than 2.5 times on average. We further demonstrate its adaptivity in an algebraic multigrid solver from the Hypre library and report greater than 20% performance improvement.

关键词： sparse matrix vector multiplication auto-tuning multicore machine learning

来源：评论

学校读者我要写书评

暂无评论

A Recursive Hypergraph Bipartitioning Framework for Reducing Bandwidth and Latency Costs Simultaneously

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第2期28卷 345-358页

作者： Selvitopi, Oguz Acer, Seher Aykanat, Cevdet Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey

Intelligent partitioning models are commonly used for efficient parallelization of irregular applications on distributed systems. These models usually aim to minimize a single communication cost metric, which is either related to communication volume or message count. However, both volume-and message-related metrics should be taken into account during partitioning for a more efficient parallelization. There are only a few works that consider both of them and they usually address each in separate phases of a two-phase approach. In thiswork, we propose a recursive hypergraph bipartitioning framework that reduces the total volume and total message count in a single phase. In this framework, the standard hypergraph models, nets of which already capture the bandwidth cost, are augmented with message nets. The message nets encode the message count so that minimizing conventional cutsize captures the minimization of bandwidth and latency costs together. Our model provides a more accurate representation of the overall communication cost by incorporating both the bandwidth and the latency components into the partitioning objective. The use of the widely-adopted successful recursive bipartitioning framework provides the flexibility of using any existing hypergraph partitioner. The experiments on instances from different domains show that our model on the average achieves up to 52 percent reduction in total message count and hence results in 29 percent reduction in parallel running time compared to the model that considers only the total volume.

关键词： Communication cost bandwidth latency partitioning hypergraph recursive bipartitioning load balancing sparse matrix vector multiplication combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds in the Asymmetric External Memory Model 17

Lower Bounds in the Asymmetric External Memory Model

引用

29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Jacob, Riko Sitchinava, Nodari IT Univ Copenhagen Rued Langgaards Vej 7 DK-2300 Copenhagen S Denmark Univ Hawaii Manoa Informat & Comp Sci 1680 East West RdPOST 317 Honolulu HI 96822 USA

ISBN: (纸本)9781450345934

Motivated by the asymmetric read and write costs of emerging non-volatile memory technologies, we study lower bounds for the problems of sorting, permuting and multiplying a sparse matrix by a dense vector in the asymmetric external memory model (AEM). Given an AEM with internal (symmetric) memory of size M, transfers between symmetric and asymmetric memory in blocks of size B and the ratio omega between write and read costs, we show Omega(min{N;omega N/B log omega M/B N/B}) lower bound for the cost of permuting N input elements. O is lower bound also applies to the problem of sorting N elements. O is proves that the existing sorting algorithms in the AEM model are optimal to within a constant factor for reasonable ranges of parameters N, M, B, and omega. We also show a lower bound of Omega(min (H;omega H/B log(omega M/B) N/max{delta, M}}) for the cost of multiplying an N x N matrix with at most H = delta N non-empty entries by a vector with N elements.

关键词： Asymmetric external memory AEM asymmetric read-write NVMs sorting permuting lower bounds sparse matrix vector multiplication SpMxV

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：