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

EITHOT: Efficient In-place Transposition of High Order Tensors on GPUs

ACM TRANSACTIONS ON PARALLEL COMPUTING 2025年第1期12卷 1-22页

作者： Wu, Cun-yu Tu, Chih-chieh Cheng, Kai-jung Lee, Che-rung Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

Tensor transposition is a fundamental operation in tensor calculations with various applications. However, a naive implementation that copies each element from the source tensor to the transposed position in the target tensor requires double space, making it unsuitable for large-scale tensors on memory-limited accelerators, like Graphic Processing Units (GPUs). In this article, we propose an algorithm and its implementation, called EITHOT, for In-place Transposition of High Order Tensors on GPUs, which requires only 5% additional memory at most for large high order tensors. To achieve this, EITHOT uses a newly proposed method, called permutation decomposition, to factorize a transposition of a high-order tensor into a sequence of low-order tensor transpositions. Then, based on the estimated extra memory requirements, EITHOT divides a large tensor into smaller tensors and transposes each smaller tensor separately. Finally, the transposed smaller tensors are combined to form the desired result. The GPU implementation optimizes memory access performance using the cooperative groups programming model. Our experiments demonstrate that EITHOT delivers competitive performance compared to the state-of-the-art out-of-place GPU implementations. Furthermore, EITHOT can handle nearly double the size of tensors compared to out-of-place methods, making it suitable for various transpositions of N-order tensors.

关键词： GPU tensor transposition in-place algorithm

来源：评论

学校读者我要写书评

暂无评论

PI-sqrt: novel parallel implementations of in-place sequence rotation on multicore systems

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2023年第1期26卷 539-557页

作者： Hashem, Mervat Li, Kenli Salah, Ahmad Hunan Univ Coll Informat Sci & Engn Changsha Peoples R China Zagazig Univ Fac Comp & Informat Zagazig Egypt Univ Technol & Appl Sci Dept Informat Technol CAS Ibri Muscat Oman

The huge data volumes and the emergence of new parallel architectures, e.g. multicore CPUs lead to revisiting classic computer science topics such as in-place sequence rotation. In-place sequence rotation is a basic step in several fundamental computing tasks. The sequential algorithms of the in-place sequence rotation effect are classic and well-studied, which are classified into three classes. Recently, Intel introduced the parallel standard template library (STL) implementation for multicore CPU systems;it has an in-place rotation function based on the rotation by copy, but its space complexity is O(n). In this work, we propose the blend rotation, which is a parallel-friendly and in-place algorithm that combines the merits of these three rotation algorithm classes. Besides, we propose a set of for Parallel In-place SeQuence RoTation (PI-sqrt) implementations. The performance of PI-sqrt is examined through several experiments. To the best of our knowledge, the obtained running times show that the implementations of blend and reversal rotations are by far the fastest parallel implementations;they are faster on average, through different experiments, by 7.85 x and 5.52x, respectively, compared to the parallel rotation function of Intel parallel STL.

关键词： Parallel algorithm in-place algorithm Sequence rotation Multicore CPU PI-sqrt

来源：评论

学校读者我要写书评

暂无评论

In-place initializable arrays

引用

THEORETICAL COMPUTER SCIENCE 2022年 916卷 62-69页

作者： Katoh, Takashi Goto, Keisuke Fujitsu Labs Ltd Kawasaki Japan

An initializable array is an array that supports the read and write operations for any element and the initialization of the entire array. This paper proposes a simple in-place algorithm to implement an initializable array of length N containing l is an element of O(w) bits entries in Nl+ 1 bits on the word RAM model with w bits word size, i.e., the proposed array requires only 1 extra bit on top of a normal array of length N containing l bits entries. Our algorithm supports the all three operations in constant worst-case time, that is, it runs in-place using at most constant number of words O(w) bits during each operation. The time and space complexities are optimal since it was already proven that there is no implementation of an initializable array with no extra bit supporting all the operations in constant worst-case time (Hagerup and Kammer, 2017 [12]). Our algorithm significantly improves upon the best algorithm presented in the earlier studies (Navarro, 2014 [5]) which uses N + o(N) extra bits to support all the operations in constant worst-case time. (c) 2022 Elsevier B.V. All rights reserved.

关键词： in-place algorithm Space efficient data structure Initializable array

来源：评论

学校读者我要写书评

暂无评论

Engineering In-place (Shared-memory) Sorting algorithms

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2022年第1期9卷 1–62页

作者： Axtmann, Michael Witt, Sascha Ferizovic, Daniel Sanders, Peter Karlsruhe Inst Technol Karlsruhe Germany

We present new sequential and parallel sorting algorithms that now represent the fastest known techniques for a wide range of input sizes, input distributions, data types, and machines. Somewhat surprisingly, part of the speed advantage is due to the additional feature of the algorithms to work in-place, i.e., they do not need a significant amount of space beyond the input array. Previously, the in-place feature often implied performance penalties. Our main algorithmic contribution is a blockwise approach to in-place data distribution that is provably cache-efficient. We also parallelize this approach taking dynamic load balancing and memory locality into account. Our new comparison-based algorithm In-place Parallel Super Scalar Samplesort (IPS(4)o), combines this technique with branchless decision trees. By taking cases with many equal elements into account and by adapting the distribution degree dynamically, we obtain a highly robust algorithm that outperforms the best previous in-place parallel comparison-based sorting algorithms by almost a factor of three. That algorithm also outperforms the best comparison-based competitors regardless of whether we consider in-place or not in-place, parallel or sequential settings. Another surprising result is that IPS(4)o even outperforms the best (in-place or not in-place) integer sorting algorithms in a wide range of situations. In many of the remaining cases (often involving near-uniform input distributions, small keys, or a sequential setting), our new In-place Parallel Super Scalar Radix Sort ((IPSRa)-Ra-2) turns out to be the best algorithm. Claims to have the - in some sense - "best" sorting algorithm can be found in many papers which cannot all be true. Therefore, we base our conclusions on an extensive experimental study involving a large part of the cross product of 21 state-of-the-art sorting codes, 6 data types, 10 input distributions, 4 machines, 4 memory allocation strategies, and input sizes varying over 7 orde

关键词： in-place algorithm branch prediction

来源：评论

学校读者我要写书评

暂无评论

A Class of In-place Linear Transformations Possessing the Cache-Oblivious Property

引用

IEEE ACCESS 2019年 7卷 23068-23075页

作者： Zhao, Zhe Lin, Sian-Jheng Yu, Nenghai Univ Sci & Technol China Sch Informat Sci & Technol CAS Key Lab Electromagnet Space Informat Hefei 230027 Anhui Peoples R China

In-place linear transformations allow input to be overwritten with the output of the transformation. This paper presents a family of in-place linear transformations based on block lower/upper (LU) decompositions, of which the known transformation via LU decomposition is a special case, and shows that the proposed family includes a class of transformations that possesses the cache-oblivious property. Furthermore, the number of cache misses and approaches for non-square matrices is discussed. The simulation shows that the proposed in-place linear transformation is faster than the existing transformation via LU decompositions.

关键词： Cache-oblivious linear transformation in-place algorithm block LU decomposition

来源：评论

学校读者我要写书评

暂无评论

Generic Reductions for In-place Polynomial Multiplication 19

Generic Reductions for In-place Polynomial Multiplication

引用

44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Giorgi, Pascal Grenet, Bruno Roche, Daniel S. Univ Montpellier LIRMM CNRS Montpellier France US Naval Acad Annapolis MD USA

ISBN: (纸本)9781450360845

The polynomial multiplication problem has attracted considerable attention since the early days of computer algebra, and several algorithms have been designed to achieve the best possible time complexity. More recently, efforts have been made to improve the space complexity, developing modified versions of a few specific algorithms to use no extra space while keeping the same asymptotic running time. In this work, we broaden the scope in two regards. First, we ask whether an arbitrary multiplication algorithm can be performed in-place generically. Second, we consider two important variants which produce only part of the result (and hence have less space to work with), the so-called middle and short products, and ask whether these operations can also be performed in-place. To answer both questions in (mostly) the affirmative, we provide a series of reductions starting with any linear-space multiplication algorithm. For full and short product algorithms these reductions yield in-place versions with the same asymptotic time complexity as the out-of-place version. For the middle product, the reduction incurs an extra logarithmic factor in the time complexity only when the algorithm is quasi-linear.

关键词： arithmetic polynomial multiplication in-place algorithm self reduction

来源：评论

学校读者我要写书评

暂无评论

Cache-Aware, In-place Rotation Method for Texture-Based Volume Rendering

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2017年第3期E100D卷 452-461页

作者： Misaki, Yuji Ino, Fumihiko Hagihara, Kenichi Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

We propose a cache-aware method to accelerate texturebased volume rendering on a graphics processing unit (GPU) that is compatible with the compute unified device architecture. The proposed method extends a previous method such that it can maximize the average rendering performance while rotating the viewing direction around a volume. To realize this, the proposed method performs in-place rotation of volume data, which rearranges the order of voxels to allow consecutive threads (warps) to refer to voxels with the minimum access strides. Experiments indicate that the proposed method replaces the worst texture cache (TC) hit rate of 42% with the best TC hit rate of 93% for a 1024(3)-voxel volume. Thus, the average frame rate increases by a factor of 1.6 in the proposed method compared with that in the previous method. Although the overhead of inplace rotation slightly decreases the frame rate from 2.0 frames per second (fps) to 1.9 fps, this slowdown occurs only with a few viewing directions.

关键词： cache optimization volume rendering in-place algorithm GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

Memory efficient algorithms for cactus graphs and block graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part2期216卷 393-407页

作者： Brimkov, Boris Hicks, Illya V. Rice Univ Computat & Appl Math Houston TX 77005 USA

We present constant-work-space polynomial time algorithms for solving the shortest path problem, finding the chromatic polynomial, clique number, number of components, circumference, and girth of cactus graphs and block graphs. For some of these problems we also present in-place algorithms, which perform faster than the corresponding constant work-space algorithms. The problems considered are fundamental to many areas of graph theory, computational geometry, and combinatorial optimization, and have a wide range of applications including transportation, robotics, and image processing. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Constant-work-space algorithm in-place algorithm Shortest path Cactus graph Block graph Chromatic polynomial

来源：评论

学校读者我要写书评

暂无评论

Reducing memory usage by the lifting-based discrete wavelet transform with a unified buffer on a GPU

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 93-94卷 44-55页

作者： Ikuzawa, Takuya Ino, Fumihiko Hagihara, Kenichi Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamada Oka Suita Osaka 5650871 Japan Toshiba Co Ltd Ind ICT Solut Co Saiwai Ku 72-34 Horikawa Cho Kawasaki Kanagawa 2120013 Japan

In this study, to improve the speed of the lifting-based discrete wavelet transform (DWT) for large-scale data, we propose a parallel method that achieves low memory usage and highly efficient memory access on a graphics processing unit (GPU). The proposed method reduces the memory usage by unifying the input buffer and output buffer but at the cost of a working memory region that is smaller than the data size it The method partitions the input data into small chunks, which are then rearranged into groups so different groups of chunks can be processed in parallel. This data rearrangement scheme classifies chunks in terms of data dependency but it also facilitates transformation via simultaneous access to contiguous memory regions, which can be handled efficiently by the GPU. In addition, this data rearrangement is interpreted as a product of circular permutations such that a sequence of seeds, which is an order of magnitude shorter than input data, allows the GPU threads to compute the complicated memory indexes needed for parallel rearrangement. Because the DWT is usually part of a processing pipeline in an application, we believe that the proposed method is useful for retaining the amount of memory for use by other pipeline stages. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Discrete wavelet transform Lifting scheme Memory-saving computation in-place algorithm GPU

来源：评论

学校读者我要写书评

暂无评论

An in-place min-max priority search tree

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2013年第3期46卷 310-327页

作者： De, Minati Maheshwari, Anil Nandy, Subhas C. Smid, Michiel Indian Stat Inst Kolkata India Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

One of the classic data structures for storing point sets in R-2 is the priority search tree, introduced by McCreight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry stores only one point of the point set and no entry is stored in more than one location of that array. It combines a binary search tree with a heap. We show that all the standard query operations can be performed within the same time bounds as for the original priority search tree, while using only O(1) extra space. We introduce the min-max priority search tree which is a combination of a binary search tree and a min-max heap. We show that all the standard queries which can be done in two separate versions of a priority search tree can be done with a single min-max priority search tree. As an application, we present an in-place algorithm to enumerate all maximal empty axis-parallel rectangles amongst points in a rectangular region R in R-2 in O(m log n) time with O(1) extra space, where m is the total number of maximal empty rectangles. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Min-max priority search tree in-place algorithm Three-sided orthogonal range query Maximum empty rectangle

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：