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

ACM/IEEE International Conference for High Performance computing, Networking, Storage, and Analysis

作者： Nadathur Satish Changkyu Kim Jatin Chhugani Pradeep Dubey Parallel Computing Lab Intel Corporation

ISBN: (纸本)9781467308052

Graph traversal is a widely used algorithm in a variety of fields, including social networks, business analytics, and high-performance computing among others. There has been a push for HPC machines to be rated not just in Petaflops, but also in "GigaTEPS" (billions of traversed edges per second), and the Graph500 benchmark has been established for this purpose. Graph traversal on single nodes has been well studied and optimized on modern CPU architectures. However, current cluster implementations suffer from high latency data communication with large volumes of transfers across nodes, leading to inefficiency in performance and energy consumption. In this work, we show that we can overcome these constraints using a combination of efficient low-overhead data compression techniques to reduce transfer volumes along with latency-hiding techniques. Using an optimized single node graph traversal algorithm [1], our novel cluster optimizations result in over 6.6X performance improvements over state-of-the-art data transfer techniques, and almost an order of magnitude in energy savings. Our resulting implementation of the Graph500 benchmark achieves 115 GigaTEPS on a 320-node/5120 core intel~? Endeavor cluster with intel~? Xeon~? processors E5-2670, which matches the second ranked result in the recent November 2011 Graph500 list [2] with about 5.6X fewer nodes~(12). Our cluster optimizations only have a 1.8X overhead in overall performance from the performance of the optimized single-node implementation, and allows for near-linear scaling with number of nodes. Our algorithm on 1024 nodes on intel~? Xeon~? processor X5670-based systems (with lower per-node performance) for a large multi-Terabyte graph attained 195 GigaTEPS in performance, proving the high scalability of our algorithm. Our per-node performance is the highest in the top 10 of the Nov 2011 Graph500 list.

关键词： HPC high-performance computing among others our algorithm High Performance computing Ganglia Line graph Clusters pushing

来源：评论

学校读者我要写书评

暂无评论

CloudRAMSort: Fast and efficient large-scale distributed RAM sort on shared-nothing cluster 12

CloudRAMSort: Fast and efficient large-scale distributed RAM...

引用

2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12

作者： Kim, Changkyu Park, Jongsoo Satish, Nadathur Lee, Hongrae Dubey, Pradeep Chhugani, Jatin Parallel Computing Lab. Intel Labs. Santa Clara CA United States Structured Data Group Google Research Mountain View United States

ISBN: (纸本)9781450312479

Sorting is a fundamental kernel used in many database operations. The total memory available across cloud computers is now sufficient to store even hundreds of terabytes of data in-memory. Applications requiring high-speed data analysis typically use in-memory sorting. The two most important factors in designing a high-speed in-memory sorting system are the single-node sorting performance and inter-node communication. In this paper, we present CloudRAMSort, a fast and efficient system for large-scale distributed sorting on shared-nothing clusters. CloudRAMSort performs multi-node optimizations by carefully overlapping computation with inter-node communication. The system uses a dynamic multi-stage random sampling approach for improved load-balancing between nodes. CloudRAMSort maximizes per-node efficiency by exploiting modern architectural features such as multiple cores and SIMD (Single-Instruction Multiple Data) units. This holistic combination results in the highest performing sorting performance on distributed shared-nothing platforms. CloudRAMSort sorts 1 Terabyte (TB) of data in 4.6 seconds on a 256-node Xeon X5680 cluster called the intel Endeavor system. CloudRAMSort also performs well on heavily skewed input distributions, sorting 1 TB of data generated using Zipf distribution in less than 5 seconds. We also provide a detailed analytical model that accurately projects (within avg. 7%) the performance of CloudRAMSort with varying tuple sizes and interconnect bandwidths. Our analytical model serves as a useful tool to analyze performance bottlenecks on current systems and project performance with future architectural advances. With architectural trends of increasing number of cores, bandwidth, SIMD width, cache-sizes, and interconnect bandwidth, we believe CloudRAMSort would be the system of choice for distributed sorting of large-scale in-memory data of current and future systems. © 2012 ACM.

关键词： Sorting

来源：评论

学校读者我要写书评

暂无评论

Billion-Particle SIMD-Friendly Two-Point Correlation on Large-Scale HPC Cluster Systems 12

Billion-Particle SIMD-Friendly Two-Point Correlation on Larg...

引用

ACM/IEEE International Conference for High Performance computing, Networking, Storage, and Analysis

作者： Jatin Chhugani Changkyu Kim Hemant Shukla Jongsoo Park Pradeep Dubey John Shalf Horst D. Simon Parallel Computing Lab Intel Corporation Lawrence Berkeley National Laboratory

ISBN: (纸本)9781467308052

Two-point Correlation Function (TPCF) is widely used in astronomy to characterize the distribution of matter/energy in the Universe, and help derive the physics that can trace back to the creation of the universe. However, it is prohibitively slow for current sized datasets, and would continue to be a critical bottleneck with the trend of increasing dataset sizes to billions of particles and more, which makes TPCF a compelling benchmark application for future exa-scale architectures. State-of-the-art TPCF implementations do not map well to the underlying SIMD hardware, and also suffer from load-imbalance for large core counts. In this paper, we present a novel SIMD-friendly histogram update algorithm that exploits the spatial locality of histogram updates to achieve near-linear SIMD scaling. We also present a load-balancing scheme that combines domain-specific initial static division of work and dynamic task migration across nodes to effectively balance computation across nodes. Using Zin supercomputer at Lawrence Livermore National laboratory (25,600 cores of intel? Xeon? E5-2670, each with 256-bit SIMD), we achieve 90% parallel efficiency and 96% SIMD efficiency, and perform TPCF computation on a 1.7 billion particle dataset in 5.3 hours (at least 35×faster than previous approaches). In terms of cost per performance (measured in flops/$), we achieve at least an order-of-magnitude (11.1 ×) higher flops/$ as compared to the best known results [1]. Consequently, we now have line-of-sight to achieving the processing power for correlation computation to process billion+ particles telescopic data.

关键词： TPCF universe trend of increasing dataset sizes Universe single instruction multiple datastream histograms spatial locality Ganglia Lawrence Livermore National laboratory Dataset ASTRONOMY particles arithmetic High Performance computing

来源：评论

学校读者我要写书评

暂无评论

High Performance Non-uniform FFT on Modern X86-based Multi-core Systems

High Performance Non-uniform FFT on Modern X86-based Multi-c...

引用

International Symposium on parallel and Distributed Processing (IPDPS)

作者： Dhiraj D. Kalamkar Joshua D. Trzaskoz Srinivas Sridharan Mikhail Smelyanskiy Daehyun Kim Armando Manduca Yunhong Shu Matt A. Bernstein Bharat Kaul Pradeep Dubey Parallel Computing Lab Intel Labs Bangalore KA India Mayo Clinic Minnesota Rochester MN US Parallel Computing Laboratory INTEL Research Laboratory Santa Clara CA USA Department of Physiology and Biomedical Engineering Mayo Clinic Rochester MN USA Parallel Computing Lab Intel Labs Santa Clara CA USA Department of Radiology Mayo Clinic Rochester MN USA

The Non-Uniform Fast Fourier Transform (NUFFT) is a generalization of FFT to non-equidistant samples. It has many applications which vary from medical imaging to radio astronomy to the numerical solution of partial differential equations. Despite recent advances in speeding up NUFFT on various platforms, its practical applications are still limited, due to its high computational cost, which is significantly dominated by the convolution of a signal between a non-uniform and uniform grids. The computational cost of the NUFFT is particularly detrimental in cases which require fast reconstruction times, such as iterative 3D non-Cartesian MRI reconstruction. We propose novel and highly scalable parallel algorithm for performing NUFFT on x86-based multi-core CPUs. The high performance of our algorithm relies on good SIMD utilization and high parallel efficiency. On convolution, we demonstrate on average 90% SIMD efficiency using SSE, as well up to linear scalability using a quad-socket 40-core intel(R) Xeon(R) E7-4870 Processors based system. As a result, on dual socket intel(R) Xeon(R) X5670 based server, our NUFFT implementation is more than 4x faster compared to the best available NUFFT3D implementation, when run on the same hardware. On intel(R) Xeon(R) E5-2670 processor based server, our NUFFT implementation is 1.5X faster than any published NUFFT implementation today. Such speed improvement opens new usages for NUFFT. For example, iterative multi channel reconstruction of a 240×240×240 image could execute in just over 3 minutes, which is on the same order as contemporary non-iterative (and thus less-accurate) 3D NUFFT-based MRI reconstructions.

关键词： Convolution Kernel Interpolation Magnetic resonance imaging Image reconstruction Hardware Transforms

来源：评论

学校读者我要写书评

暂无评论

Miss-Correlation Folding: Encoding Per-Block Miss Correlations in Compressed DRAM for Data Prefetching

Miss-Correlation Folding: Encoding Per-Block Miss Correlatio...

引用

IEEE International parallel & Distributed Processing Symposium

作者： Gang Liu Jih-Kwon Peir Victor Lee Department of Computer & Information Science & Eng University of Florida Gainesville FL USA Parallel Computing Lab Intel Labs Intel Corporation Santa Clara CA USA

ISBN: (纸本)9781467309752

Cache misses frequently exhibit repeated streaming behavior, i.e. a sequence of cache misses has a high tendency of being repeated. Correlation-based prefetchers record the missing streams in a history table for accurate prefetching. Saving a large miss history in off-chip DRAM is a practical implementation, but incurs access latency and consumes memory bandwidth which leads to performance degradation. In this paper, we investigate a new data prefetching mechanism based on per-block miss correlation where a miss is correlated with an earlier miss when the two misses are closely encountered both in time and space. The miss correlations are captured dynamically and saved along with the content of the data block using a simple data compression technique. As a result of this novel combination, our scheme provides unbounded correlation history and its prefetch metadata can be fetched together with demand data without incurring additional latency nor consuming any memory bandwidth. Performance evaluations using data-parallel applications demonstrate that prefetchers based on per-block miss correlations can improve IPC by 42-139% with an average of 88% compared to the IPC without prefetching. In comparison with regular stream prefetcher, sampled temporal streaming prefetcher and spatial-temporal memory streaming prefetcher, up to 115%, 99% and 98% IPC improvement can be obtained with an average about 36%, 26% and 27% respectively.

关键词： prefetch data parallel miss correlation compress cache temporal spatial

来源：评论

学校读者我要写书评

暂无评论

PALM: parallel architecture friendly latchfree modifications to B+ trees on manycore processors 37

PALM: Parallel architecture friendly latchfree modifications...

引用

37th International Conference on Very Large Data Bases, VLDB 2011

作者： Sewall, Jason Chhugani, Jatin Kim, Changkyu Satish, Nadathur Dubey, Pradeep Parallel Computing Lab Intel Corporation United States

Concurrency control on B+ trees is primarily achieved with latches, but serialization and contention can hinder scalability. As core counts on current processors increase, it is imperative to develop scalable latch-free techniques for concurrency control. We present PALM, a novel technique for performing multiple concurrent queries on in-memory B+ trees. PALM is based on the Bulk Synchronous parallel model, which guarantees freedom from deadlocks and race conditions. Input queries are grouped and processed in atomic batches, and work proceeds in stages that preclude contention. Transitions between stages are accomplished with scalable point-to-point communication. PALM exploits dataand thread-level parallelism on modern many-core architectures, and performs 40M1 updates/second on trees with 128M keys, and 128M updates/second on trees with 512K keys on the latest CPU architectures. Our throughput is 2.3X-19X that of state-of-theart concurrent update algorithms on in-memory B+ trees. PALM obtains close to peak throughput at very low response times of less than 350μs, even for large trees. We also evaluate PALM on the intel® Many Integrated Core (intel® MIC) architecture, and demonstrate a speedup of 1.5-2.1X for out-of-cache tree sizes on an intel® Knights Ferry over a pair of intel® Xeon® processors DP X5680 (Westmere-EP) in a dual-socket configuration. © 2011 VLDB Endowment.

关键词： Concurrency control

来源：评论

学校读者我要写书评

暂无评论

Designing fast architecture-sensitive tree search on modern multicore/many-core processors

Designing fast architecture-sensitive tree search on modern ...

引用

作者： Kim, Changkyu Chhugani, Jatin Satish, Nadathur Sedlar, Eric Nguyen, Anthony D. Kaldewey, Tim Lee, Victor W. Brandt, Scott A. Dubey, Pradeep Intel Corporation Parallel Computing Lab United States Oracle Corporation United States University of California Santa Cruz United States

In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendous computing power by integrating multiple cores, each with wide vector units. There has been much work to exploit modern processor architectures for database primitives like scan, sort, join, and aggregation. However, unlike other primitives, tree search presents significant challenges due to irregular and unpredictable data accesses in tree traversal. In this article, we present FAST, an extremely fast architecturesensitive layout of the index tree. FAST is a binary tree logically organized to optimize for architecture features like page size, cache line size, and Single Instruction Multiple Data (SIMD) width of the underlying hardware. FAST eliminates the impact of memory latency, and exploits thread-level and data-level parallelism on both CPUs and GPUs to achieve 50 million (CPU) and 85 million (GPU) queries per second forlarge trees of 64M elements, with even better results on smaller trees. These are 5X (CPU) and 1.7X (GPU) faster than the best previously reported performance on the same architectures. We also evaluated FAST on the intel® Many Integrated Core architecture (intelR MIC), showing a speedup of 2.4X-3X over CPU and 1.8X-4.4X over GPU. FAST supports efficient bulk updates by rebuilding index trees in less than 0.1 seconds for datasets as large as 64M keys and naturally integrates compression techniques, overcoming the memory bandwidth bottleneck and achieving a 6X performance improvement over uncompressed index search for large keys on CPUs. © 2011 ACM.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Emerging applications for multi/many-core processors

Emerging applications for multi/many-core processors

引用

IEEE International Symposium on Circuits and Systems (ISCAS)

作者： Victor W. Lee Yen-Kuang Chen J. Chhugani C. Kim D. Kim C.J. Hughes N. Rajagopalan Satish M. Smelyanskiy P. Dubey Parallel Computing Lab Intel Labs Intel Corporation Santa Clara California USA Parallel Computing Lab Intel Labs Intel Corporation Santa Clara California USA

There has always been a strong relationship between computer applications and computer architectures. Advances in computer architecture enable new usage models; new usage models challenge new architectures. For many decades, the interplays between applications and architectures have resulted in significant progress in the computer technologies. Recently, the computer industry adopts the multi/many-core architecture for better performance, energy efficiency and reliability. This industry-wide movement towards multi/many-core architectures opens up many opportunities for developing new classes of applications. This paper uses a few emerging applications as examples to illustrate the interplay between applications and architecture. It further discusses the key characteristics of emerging applications and how multi/many-core architecture addresses the needs of the new applications. The paper closes with recommendations for new application developers to allow better utilization of new multi/many-core processors.

关键词： Computer architecture Synchronization Data models Computers parallel processing Bandwidth Program processors

来源：评论

学校读者我要写书评

暂无评论

Journal of Information Science and Engineering: Editorial notice

引用

Journal of Information Science and Engineering 2005年第5期21卷 i-ii页

作者： Lee, Der-Tsai Amato, Nancy M. Chang, Shih-Fu Chen, Homer H. Chen, Tsuhan Hsu, Tsan-Sheng Hwang, Jenq-Neng Kuo, Sy-Yen Kuo, Tei-Wei Li, Chung-Sheng Tokuyama, Takeshi Wing, Jeannette Wu, Tzong-Chen Yen, John Computer Science at Texas A and M University United States Parasol Laboratory United States IEEE Transactions on Parallel and Distributed Systems Computing Research Association's Committee on the Status of Women in Computing Research CRA-W's Distributed Mentor Program United States Department of Electrical Engineering Columbia University United States Lab. United States College of Electrical Engineering and Computer Science National Taiwan University Taiwan IEEE Transactions on Circuits and Systems for Video Technology IEEE Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh PA United States ACM ACM SIGACT IEEE Computer Society IICM Austria Research and Development of the Department Multimedia Signal Processing Technical Committee IEEE Signal Processing Society United States IEEE Transactions on Circuits and systems for Video Technology College of Electrical Engineering and Computer Science National Taiwan Ocean University Keelung Taiwan Department of Electrical Engineering National Taiwan University Taiwan Department of Computer Science and Information Engineering National Taiwan University Taipei Taiwan IEEE Technical Committee on Real-Time Systems Computer Science Division IBM T.J. Watson Research Center United States IBM Research Division Graduate School of Information Sciences Tohoku University Japan ACM IPSJ Mathematical Society of Japan Japan Department of Computer Science Computer Science Department Carnegie Mellon University United States National Academies of Science's Computer Science and Telecommunications Board United States Microsoft's Trustworthy Academic Advisory Board Intel Research Pittsburgh's Advisory Board United States Dartmouth's Institute for Security Technology Studies Advisory Committee Canada Sloan Research Fellowships Program Committee United States ACM Taiwan China Information Sciences and Technology Pennsylvania State University United States Laboratory for Intelligent Agents Penn State's School of Info

No abstract available

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：