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

Empirical performance model-driven data layout optimization selection for tensor contraction expressions

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第3期72卷 338-352页

作者： Lu, Qingda Gao, Xiaoyang Krishnamoorthy, Sriram Baumgartner, Gerald Ramanujam, J. Sadayappan, P. Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Louisiana State Univ Dept Elect & Comp Engn Baton Rouge LA 70803 USA

Empirical optimizers like ATLAS have been very effective in optimizing computational kernels in libraries. The best choice of parameters such as tile size and degree of loop unrolling is determined in ATLAS by executing different versions of the computation. In contrast, optimizing compilers use a model-driven approach to program transformation. While the model-driven approach of optimizing compilers is generally orders of magnitude faster than ATLAS-like library generators, its effectiveness can be limited by the accuracy of the performance models used. In this paper, we describe an approach where a class of computations is modeled in terms of constituent operations that are empirically measured, thereby allowing modeling of the overall execution time. The performance model with empirically determined cost components is used to select library calls and choose data layout transformations in the context of the Tensor Contraction Engine, a compiler for a high-level domain-specific language for expressing computational models in quantum chemistry. The effectiveness of the approach is demonstrated through experimental measurements on representative computations from quantum chemistry. (C) 2011 Elsevier Inc. All rights reserved.

关键词： data layout optimization Library call selection Compiler optimization Tensor contractions

来源：评论

学校读者我要写书评

暂无评论

The automatic improvement of locality in storage systems

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 2005年第4期23卷 424-473页

作者： Hsu, WW Smith, AJ Young, HC IBM Corp Almaden Res Ctr Comp Sci Storage Syst Dept San Jose CA 95120 USA Univ Calif Berkeley Dept EECS Div Comp Sci Berkeley CA 94720 USA

Disk I/O is increasingly the performance bottleneck in computer systems despite rapidly increasing disk data transfer rates. In this article, we propose Automatic Locality-Improving Storage (ALIS), an introspective storage system that automatically reorganizes selected disk blocks based on the dynamic reference stream to increase effective storage performance. ALIS is based on the observations that sequential data fetch is far more efficient than random access, that improving seek distances produces only marginal performance improvements, and that the increasingly powerful processors and large memories in storage systems have ample capacity to reorganize the data layout and redirect the accesses so as to take advantage of rapid sequential data transfer. Using trace-driven simulation with a large set of real workloads, we demonstrate that ALIS considerably outperforms prior techniques, improving the average read performance by up to 50% for server workloads and by about 15% for personal computer workloads. We also show that the performance improvement persists as disk technology evolves. Since disk performance in practice is increasing by only about 8% per year, the benefit of ALIS may correspond to as much as several years of technological progress.

关键词： algorithms design performance management measurement data layout optimization block layout data reorganization data restructuring locality improvement prefetching disk technology trends defragmentation

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for parallelizing Monte Carlo simulations for 2D Ising spin models

引用

JOURNAL OF SUPERCOMPUTING 2008年第3期44卷 274-290页

作者： Santos, Eunice E. Rickman, Jeffrey M. Muthukrishnan, Gayathri Feng, Shuangtong Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Lehigh Univ Dept Mat Sci & Engn Bethlehem PA 18015 USA

In this paper, we design and implement a variety of parallel algorithms for both sweep spin selection and random spin selection. We analyze our parallel algorithms on LogP, a portable and general parallel machine model. We then obtain rigorous theoretical runtime results on LogP for all the parallel algorithms. Moreover, a guiding equation is derived for choosing data layouts (blocked vs. stripped) for sweep spin selection. In regard to random spin selection, we are able to develop parallel algorithms with efficient communication schemes. We introduce two novel schemes, namely the FML scheme and the alpha-scheme. We analyze randomness of our schemes using statistical methods and provide comparisons between the different schemes.

关键词： Ising model LogP model parallel computing algorithm design and analysis computational science performance prediction parallel models data layout optimization

来源：评论

学校读者我要写书评

暂无评论

Wide Table layout optimization based on Column Ordering and Duplication 17

Wide Table Layout Optimization based on Column Ordering and ...

引用

ACM International Conference on Management of data

作者： Bian, Haoqiong Yan, Ying Tao, Wenbo Chen, Liang Jeff Chen, Yueguo Du, Xiaoyong Moscibroda, Thomas Renmin Univ China DEKE Key Lab MOE Beijing Peoples R China Microsoft Res Redmond WA 98052 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450341974

Modern data analytical tasks often witness very wide tables, from a few hundred columns to a few thousand. While it is commonly agreed that column stores are an appropriate data format for wide tables and analytical workloads, the physical order of columns has not been investigated. Column ordering plays a critical role in I/O performance, because in wide tables accessing the columns in a single horizontal partition may involve multiple disk seeks. An optimal column ordering will incur minimal cumulative disk seek costs for the set of queries applied to the data. In this paper, we aim to find such an optimal column layout to maximize I/O performance. Specifically, we study two problems for column stores on HDFS: column ordering and column duplication. Column ordering seeks an approximately optimal order of columns;column duplication complements column ordering in that some columns may be duplicated multiple times to reduce contention among the queries' diverse requirements on the column order. We consider an actual fine-grained cost model for column accesses and propose algorithms that take a query workload as input and output a column ordering strategy with or without storage redundancy that significantly improves the overall I/O performance. Experimental results over real-life data and production query workloads confirm the effectiveness of the proposed algorithms in diverse settings.

关键词： disk-based storage system hdfs colum store wide table data analytics data layout optimization

来源：评论

学校读者我要写书评

暂无评论

A Server-Level Adaptive data layout Strategy for Parallel File Systems

A Server-Level Adaptive Data Layout Strategy for Parallel Fi...

引用

26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) / Workshop on High Performance data Intensive Computing

作者： Song, Huaiming Jin, Hui He, Jun Sun, Xian-He Thakur, Rajeev Dawning Informat Ind Ctr Res & Dev Beijing 100193 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA Argonne Natl Lab Math & Comp Sci Div 9700 S Cass Ave Argonne IL 60439 USA

ISBN: (纸本)9780769546766

Parallel file systems are widely used for providing a high degree of I/O parallelism to mask the gap between I/O and memory speed. However, peak I/O performance is rarely attained due to complex data access patterns of applications. Based on the observation that the I/O performance of small requests is often limited by the request service rate, and the performance of large requests is limited by I/O bandwidth, we take into consideration both factors and propose a server-level adaptive data layout strategy. The proposed strategy adopts different stripe sizes for different file servers according to the data access characteristics on each individual server. We let the file servers that can fully utilize bandwidth hold more data, and the file servers that are limited with request service rate hold less data. As a result, heavy-load servers can offload some data accesses to light-load servers for potential improvement of I/O performance. We present a method to measure access cost for each data block and then utilize an equal-depth histogram approach to distributed data blocks across multiple servers adaptively, so as to balance data accesses on all file servers. Analytical and experimental results demonstrate that the proposed server-level adaptive layout strategy can improve I/O performance by as much as 80.3% and is more appropriate for applications with complex data access patterns.

关键词： Server-level adaptive data layout variable stripe size equal-depth histogram data layout optimization parallel file system

来源：评论

学校读者我要写书评

暂无评论

p-OFTL: An Object-based Semantic-aware Parallel Flash Translation Layer 14

p-OFTL: An Object-based Semantic-aware Parallel Flash Transl...

引用

Design, Automation and Test in Europe Conference and Exhibition (DATE)

作者： Wang, Wei Lu, Youyou Shu, Jiwu Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Tsinghua Natl Lab Informat Sci & Technol Beijing Peoples R China

ISBN: (纸本)9783981537024

With increased density and decreased price, flash memory has been widely used in storage systems for its low latency and low power features. However, traditional storage systems are designed and excessively optimized for magnetic disks, and the potential of flash memory is not brought into full play in the form of Solid State Drives (SSDs). In this paper, we propose p-OFTL, an object-based semantic-aware parallel flash translation layer (FTL). p-OFTL removes the mapping table in the FTL and directly manages the flash memory in file objects, which enables optimization of data layout in the flash using object semantics. While the removing of the mapping table improves system performance, a challenge remains to exploit the internal parallelism when maintaining the continuity of logical addresses in each object, which is essential for efficient garbage collection. To address this challenge, p-OFTL statically remaps the addresses by shifting the bits in the addresses, which spreads writes to different internal parallel units without another mapping table. Also, p-OFTL employs a semantic-aware data grouping algorithm to group data pages by trading off the hot-cold clustering for the continuity of logical addresses, so as to reduce the page movement in garbage collection. Experiments show that p-OFTL improves system performance by 4.0% similar to 10.3% and reduces garbage collection overhead by 15.1% similar to 32.5% in semantic-aware data grouping compared to those in semantic-unaware data grouping algorithms.

关键词： flash memories magnetic disc storage parallel processing storage management SSDs data layout optimization data pages flash memory garbage collection hot-cold clustering internal parallel units logical addresses magnetic disks mapping table object-based semantic-aware parallel flash translation layer p-OFTL semantic-aware data grouping algorithm semantic-unaware data grouping algorithms solid state drives storage systems Ash History layout optimization Parallel processing Semantics Time-frequency analysis

来源：评论

学校读者我要写书评

暂无评论

Memory-Efficient Storing of Timestamps for Spatio-Temporal data Management in Columnar In-Memory databases 26th

Memory-Efficient Storing of Timestamps for Spatio-Temporal D...

引用

26th International Conference on database Systems for Advanced Applications (DASFAA)

作者： Richly, Keven Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9783030731939;9783030731946

Vast amounts of spatio-temporal data are continuously accumulated through the wide distribution of location-acquisition technologies. Concerning the increased performance requirements of spatio-temporal data mining applications, in-memory database systems are used to store and process the data. As DRAM capacities are limited and expensive, the efficient utilization of the available resources is necessary. In contrast to storing the positions of moving objects, there is less focus on optimized storage concepts for the temporal component. However, it has a significant impact on the memory footprint and the overall system performance. Especially for columnar databases, the memory-efficient storing of timestamps is challenging as numerous compression approaches are optimized for contradicting data characteristics (e.g., low number of distinct values, sequences of equal values). In this paper, we present and compare different data layouts for columnar in-memory databases to store timestamps. Additionally, we propose an optimized approach for range queries with standard access ranges that uses multiple columns. We evaluate the memory consumption and performance of different compression techniques for specific access patterns. Based on the results, we introduce a workload-aware heuristic approach for the selection of performance and cost balancing data layouts. Further, we demonstrate that workload-driven optimizations for timestamps can significantly reduce the data footprint and increase the performance of spatio-temporal data management.

关键词： In-memory databases data layout optimization Spatio-temporal data

来源：评论

学校读者我要写书评

暂无评论

data layout Transformation for Enhancing data Locality on NUCA Chip Multiprocessors 09

Data Layout Transformation for Enhancing Data Locality on NU...

引用

18th International Conference on Parallel Architectures and Compilation Techniques

作者： Lu, Qingda Alias, Christophe Bondhugula, Uday Henretty, Thomas Krishnamoorthy, Sriram Ramanujam, J. Rountev, Atanas Sadayappan, P. Chen, Yongjian Lin, Haibo Ngai, Tin-Fook Ohio State Univ Columbus OH 43210 USA ENS INRIA Lyon France Pacific NorthWest Natl Lab Richland WA 99352 USA Louisiana State Univ Baton Rouge LA 70803 USA Intel Corp Santa Clara CA 95051 USA IBM Corp China Res Lab Beijing Peoples R China

ISBN: (纸本)9780769537719

With increasing numbers of cores, future CMPs (Chip Multi-Processors) are likely to have a tiled architecture with a portion of shared L2 cache on each the and a bank-interleaved distribution of the address space. Although such an organization is effective for avoiding access hot-spots, it can cause a significant number of non-local L2 accesses for many commonly occurring regular data access patterns. In this paper we develop a compile-time framework For data locality optimization via data layout transformation. Using a polyhedral model, the program's localizability is determined by analysis of its index set and array reference functions, followed by non-canonical data layout transformation to reduce non-local accesses for localizable computations. Simulation-based results on a 16-core 2D tiled CMP demonstrate the effectiveness of the approach. The developed program transformation technique is also useful in several other data layout transformation contexts.

关键词： data layout optimization Polyhedral Model NUCA Cache

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallelization of 2D Ising Spin Systems

Efficient Parallelization of 2D Ising Spin Systems

引用

作者： Feng, Shuangtong Virginia Tech | University

The problem of efficient parallelization of 2D Ising spin systems requires realistic algorithmic design and implementation based on an understanding of issues from computer science and statistical physics. In this work, we not only consider fundamental parallel computing issues but also ensure that the major constraints and criteria of 2D Ising spin systems are incorporated into our study. This realism in both parallel computation and statistical physics has rarely been reflected in previous research for this problem.

In this thesis,we designed and implemented a variety of parallel algorithms for both sweep spin selection and random spin selection. We analyzed our parallel algorithms on a portable and general parallel machine model, namely the LogP model. We were able to obtain rigorous theoretical run-times on LogP for all the parallel algorithms. Moreover, a guiding equation was derived for choosing data layouts (blocked vs. stripped) for sweep spin selection. In regards to random spin selection, we were able to develop parallel algorithms with efficient communication schemes. We analyzed randomness of our schemes using statistical methods and provided comparisons between the different schemes. Furthermore, algorithms were implemented and performance data gathered and analyzed in order to determine further design issues and validate theoretical analysis.

关键词： spin selection schemes data layout optimization computational science Ising model LogP parallel model performance prediction parallel and distributed processing Thesis

来源：评论

学校读者我要写书评

暂无评论

Optimizing Memory Access Efficiency in CUDA Kernel via data layout Technique

引用

Journal of Computer and Communications 2024年第5期12卷 124-139页

作者： Neda Seifi Abdullah Al-Mamun Department of Computer & Cyber Sciences&#8212 SCCS Augusta University Augusta Georgia USA

Over the past decade, Graphics Processing Units (GPUs) have revolutionized high-performance computing, playing pivotal roles in advancing fields like IoT, autonomous vehicles, and exascale computing. Despite these advancements, efficiently programming GPUs remains a daunting challenge, often relying on trial-and-error optimization methods. This paper introduces an optimization technique for CUDA programs through a novel data layout strategy, aimed at restructuring memory data arrangement to significantly enhance data access locality. Focusing on the dynamic programming algorithm for chained matrix multiplication—a critical operation across various domains including artificial intelligence (AI), high-performance computing (HPC), and the Internet of Things (IoT)—this technique facilitates more localized access. We specifically illustrate the importance of efficient matrix multiplication in these areas, underscoring the technique’s broader applicability and its potential to address some of the most pressing computational challenges in GPU-accelerated applications. Our findings reveal a remarkable reduction in memory consumption and a substantial 50% decrease in execution time for CUDA programs utilizing this technique, thereby setting a new benchmark for optimization in GPU computing.

关键词： data layout optimization CUDA Performance optimization GPU Memory optimization Dynamic Programming Matrix Multiplication Memory Access Pattern optimization in CUDA

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：