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

2015 IEEE 35th International Conference on Distributed computing Systems

作者： Wang, Hao Chen, Li Chen, Kai Li, Ziyang Zhang, Yiming Guan, Haibing Qi, Zhengwei Li, Dongsheng Geng, Yanhui SJTU Shanghai Peoples R China HKUST Hong Kong Hong Kong Peoples R China NUDT Changsha Hunan Peoples R China Huawei Shenzhen Peoples R China

ISBN: (纸本)9781467372145

data-parallel computing frameworks (DCF) such as MapReduce, Spark, and Dryad etc. have tremendous applications in big data and cloud computing, and throw tons of flows into data center networks. In this paper, we design and implement FLOWPROPHET, a general framework to predict traffic flows for DCFs. To this end, we analyze and summarize the common features of popular DCFs, and gain a key insight: since application logic in DCFs is naturally expressed by directed acyclic graphs (DAG), DAG contains necessary time and data dependencies for accurate flow prediction. Based on the insight, FLOWPROPHET extracts DAGs from user applications, and uses the time and data dependencies to calculate flow information 4-tuple, (source, destination, flow_size, establish_time), ahead-oftime for all flows. We also provide generic programming interface to FLOWPROPHET, so that current and future DCFs can deploy FLOWPROPHET readily. We implement FLOWPROPHET on both Spark and Hadoop, and perform extensive evaluations on a testbed with 37 physical servers. Our implementation and experiments demonstrate that, with time in advance and minimal cost, FLOWPROPHET can achieve almost 100% accuracy in source, destination, and flow size predictions. With accurate prediction from FLOWPROPHET, the job completion time of a Hadoop TeraSort benchmark is reduced by 12.52% on our cluster with a simple network scheduler.

关键词： data Center Network data-parallel computing Group Communication

来源：评论

学校读者我要写书评

暂无评论

Scheduling parallel-Task Jobs Subject to Packing and Placement Constraints

引用

OPERATIONS RESEARCH 2022年第6期70卷 3403-3419页

作者： Shafiee, Mehrnoosh Ghaderi, Javad Columbia Univ Dept Elect Engn New York NY 10027 USA

Motivated bymodern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel;however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process (pack) multiple tasks at the same time;however, the cumulative resource requirement of the tasks should not exceed the machine's capacity. Our objective is to minimize the weighted average of the jobs' completion times. The problem, subject to synchronization, packing, and placement constraints, is NP-hard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placement-feasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of (6 + epsilon). In the special case that only one machine can process each task, we design an algorithm with an improved approximation ratio of four. Finally, in the case that migrations (and preemptions) are not allowed, we design an algorithm with an approximation ratio of 24. Our algorithms use a combination of linear program relaxation and greedy packing techniques. We present extensive simulation results, using a real traffic trace, that demonstrate that our algorithms yield significant gains over the prior approaches.

关键词： scheduling algorithms approximation algorithms data-parallel computing datacenters

来源：评论

学校读者我要写书评

暂无评论

DGST: Efficient and scalable suffix tree construction on distributed data-parallel platforms

引用

parallel computing 2019年 87卷 87-102页

作者： Zhu, Guanghui Guo, Chen Lu, Le Huang, Zhi Yuan, Chunfeng Gu, Rong Huang, Yihua Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China

The suffix tree is a fundamental data structure for string processing. It is widely used in many important scenarios such as text processing, information retrieval, and bioinformatics. With the rapid growth of data volume, constructing the suffix tree for large-scale datasets is very time-consuming. To solve this problem, a number of MPI-based parallel algorithms were proposed, but they have limitations in fault tolerance and scalability for large-scale datasets. Recently, there are ever-increasing application demands on efficient algorithms for constructing the suffix tree for large-scale datasets on distributed data-parallel platforms, such as Hadoop and Spark. In this paper, we present DGST, which is an efficient and scalable algorithm for generalized suffix tree construction on distributed data-parallel platforms. DGST consists of two major stages: parallel sub-tree partitioning and parallel sub-tree construction. We first design a novel data partitioning strategy for both two stages in the data-parallel paradigm. Then, we propose an efficient sub-tree partitioning algorithm based on parallel frequency counting. To improve the load balance and amortize the disk I/O costs, we propose an efficient Bin-Packing and Number-Partitioning based task allocation strategy for the sub-tree construction. At the sub-tree construction stage, we further propose a novel data structure LCP-Range and a multi-way LCP-Merge sorting algorithm for parallel LCP array construction. The experimental results on Apache Spark reveal that DGST outperforms the state-of-the-art ERa algorithm with approximately 3 times speedup on both the DNA and English text datasets. Furthermore, DGST achieves near-linear data and node scalability. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Suffix tree Generalized suffix tree Distributed computing data-parallel computing Apache Spark

来源：评论

学校读者我要写书评

暂无评论

Index-Based Search Techniques for Visualization and data Analysis Algorithms on Many-Core Systems

Index-Based Search Techniques for Visualization and Data Ana...

引用

作者： Lessley, Brenton University of Oregon

学位级别：博士

Sorting and hashing are canonical index-based methods to perform searching, and are often sub-routines in many visualization and analysis algorithms. With the emergence of many-core architectures, these algorithms must be rethought to exploit the increased available thread-level parallelism and data-parallelism. data-parallel primitives (DPP) provide an efficient way to design an algorithm for scalable, platform-portable parallelism. This dissertation considers the following question: What are the best index-based search techniques for visualization and analysis algorithms on diverse many-core systems? To answer this question, we develop new DPP-based techniques, and evaluate their performance against existing techniques for data-intensive visualization and analysis algorithms across different many-core platforms. Then, we synthesize our findings into a collection of best practices and recommended usage. As a result of these efforts, we were able to conclude that our techniques demonstrate viability and leading platform-portable performance for several different search-based use cases. This dissertation is a culmination of previously-published co-authored material.

关键词： data-parallel computing data structures Hashing Platform-portable computing Scientific visualization Sorting

来源：评论

学校读者我要写书评

暂无评论

parallelizing Machine Learning Optimization Algorithms on Distributed data-parallel Platforms with Parameter Server 24

Parallelizing Machine Learning Optimization Algorithms on Di...

引用

24th IEEE International Conference on parallel and Distributed Systems (ICPADS)

作者： Gu, Rong Fan, Shiqing Hu, Qiu Yuan, Chunfeng Huang, Yihua Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China

ISBN: (纸本)9781538673089

In the big data era, machine learning optimization algorithms usually need to be designed and implemented on widely-used distributed computing platforms, such as Apache Hadoop, Spark, and Flink However, these general distributed computing platforms themselves do not focus on parallelizing machine learning optimization algorithms. In this paper, we present a parallel optimization algorithm framework for scalable machine learning, and empirically evaluate the synchronous Elastic Averaging SGD (EASGD) and other distributed SGD-based optimization algorithms. First, we design a distributed machine learning optimization algorithm framework based on Apache Spark by adopting the parameter server. Then, we design and implement the widely-used distributed synchronous EASGD and several other popular SGD-based optimization algorithms, such as Adadelta and Adam, on top of the framework. In addition, we evaluate the performance of synchronous distributed EASGD compared with other distributed optimization algorithms based on the same framework. Finally, to explore the optimal settings of mini-batch size in large-scale distributed optimization, we further analyze the empirical linear scaling rule originally proposed in the single-node environment. Experimental results show that our parallel optimization algorithm framework achieves good flexibility and scalability. And, the distributed synchronous EASGD runs over the proposed framework gains a competitive convergence performance and is about 5.7% faster than other distributed SGD-based optimization algorithms. Experimental results also verified that the empirical linear scaling rule only holds well before the mini-batch size exceeds certain threshold on large-scale benchmarks in the distributed environment.

关键词： Machine learning optimization algorithm Apache Spark Parameter server data-parallel computing SGD

来源：评论

学校读者我要写书评

暂无评论

A parallel IRRWBF LDPC Decoder Based on Stream-Based Processor

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2012年第12期23卷 2198-2204页

作者： Tiwari, Honey Durga Huynh Ngoc Bao Cho, Yong Beom Konkuk Univ Dept Elect Engn VLSI Design Lab Seoul 143701 South Korea

Low-density parity check (LDPC) codes have gained much attention due to their use of various belief-propagation (BP) decoding algorithms to impart excellent error-correcting capability. The BP decoders are quite simple;however, their computation-intensive and repetitive process prohibits their use in energy-sensitive applications such as sensor networks. Bit flipping-based decoding algorithms, especially implementation-efficient, reliability ratio-based, weighted bit-flipping (IRRWBF) decoding;have shown an excellent tradeoff between error-correction performance and implementation cost. In this paper, we show that with IRRWBF, iterative re-computation can be replaced by iterative selective updating. When compared with the original algorithm, simulation results show that, decoding speed can be increased by 200 to 600 percent, as the number of decoding iterations is increased from 5 to 1,000. The decoding steps are broken down into various stages such that the update operations are mostly of the single-instruction, multiple-data (SIMD) type. In this paper, we show that by using Intel Wireless MMX 2 accelerating technology in the proposed algorithm, the speed increased by 500 to 1,500 percent. The results of implementing the proposed scheme using an Intel/Marvell PXA320 (806 MHz) CPU are presented. The proposed scheme can be used effectively in real-time LDPC codes for energy-sensitive mobile devices.

关键词： data-parallel computing error correcting code low-density parity-check (LDPC) code SIMD processors

来源：评论

学校读者我要写书评

暂无评论

Massively LDPC Decoding on Multicore Architectures

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2011年第2期22卷 309-322页

作者： Falcao, Gabriel Sousa, Leonel Silva, Vitor Univ Coimbra Inst Telecomunicacoes P-3030290 Coimbra Portugal Univ Coimbra Dept Elect & Comp Engn P-3030290 Coimbra Portugal Univ Tecn Lisboa Dept Elect & Comp Engn Inst Super Tecn P-1000029 Lisbon Portugal INESC ID P-1000029 Lisbon Portugal

Unlike usual VLSI approaches necessary for the computation of intensive Low-Density Parity-Check (LDPC) code decoders, this paper presents flexible software-based LDPC decoders. Algorithms and data structures suitable for parallel computing are proposed in this paper to perform LDPC decoding on multicore architectures. To evaluate the efficiency of the proposed parallel algorithms, LDPC decoders were developed on recent multicores, such as off-the-shelf general-purpose x86 processors, Graphics Processing Units (GPUs), and the CELL Broadband Engine (CELL/B.E.). Challenging restrictions, such as memory access conflicts, latency, coalescence, or unknown behavior of thread and block schedulers, were unraveled and worked out. Experimental results for different code lengths show throughputs in the order of 1 similar to 2 Mbps on the general-purpose multicores, and ranging from 40 Mbps on the GPU to nearly 70 Mbps on the CELL/B.E. The analysis of the obtained results allows to conclude that the CELL/B.E. performs better for short to medium length codes, while the GPU achieves superior throughputs with larger codes. They achieve throughputs that in some cases approach very well those obtained with VLSI decoders. From the analysis of the results, we can predict a throughput increase with the rise of the number of cores.

关键词： LDPC data-parallel computing multicore graphics processing units GPU CUDA CELL OpenMP

来源：评论

学校读者我要写书评

暂无评论

parallel LDPC Decoding on GPUs Using a Stream-Based computing Approach

引用

Journal of Computer Science & Technology 2009年第5期24卷 913-924页

作者： Gabriel Falcao Student Member Shinichi Yamagiwa Vitor Silva Leonel Sousa Senior Member Department of Electrical and Computer Engineering University of Coimbra Instituto de Telecomunicacoes PoloⅡUniversidade de Coimbra 3030-290 Coimbra Portugal INESC-ID Technical University of Lisbon Rua Alves Redol n.9 1000-029 Lisboa Portugal Department of Electrical and Computer Engineering IST Technical University of Lisbon Rua Alves Redol n.9 1000-029 Lisboa Portugal

Low-Density Parity-Check （LDPC） codes are powerful error correcting codes adopted by recent communication standards. LDPC decoders are based on belief propagation algorithms, which make use of a Tanner graph and very intensive message-passing computation, and usually require hardware-based dedicated solutions. With the exponential increase of the computational power of commodity graphics processing units （GPUs）, new opportunities have arisen to develop general purpose processing on GPUs. This paper proposes the use of GPUs for implementing flexible and programmable LDPC decoders. A new stream-based approach is proposed, based on compact data structures to represent the Tanner graph. It is shown that such a challenging application for stream-based computing, because of irregular memory access patterns, memory bandwidth and recursive flow control constraints, can be efficiently implemented on GPUs. The proposal was experimentally evaluated by programming LDPC decoders on GPUs using the Caravela platform, a generic interface tool for managing the kernels＇ execution regardless of the GPU manufacturer and operating system. Moreover, to relatively assess the obtained results, we have also implemented LDPC decoders on general purpose processors with Streaming Single Instruction Multiple data （SIMD） Extensions. Experimental results show that the solution proposed here efficiently decodes several codewords simultaneously, reducing the processing time by one order of magnitude.

关键词： data-parallel computing graphics processing unit （GPU） Caravela low-density parity-check （LDPC） code error correcting code

来源：评论

学校读者我要写书评

暂无评论

Fine-grained parallelization of lattice QCD kernel routine on GPUs

引用

JOURNAL OF parallel AND DISTRIBUTED computing 2008年第10期68卷 1350-1359页

作者： Ibrahim, Khaled Z. Bodin, Francois Pene, Olivier INRIA IRISA F-35042 Rennes France Univ Paris 11 CNRS LPT F-91405 Orsay France

Simulation time for the classical problem of Lattice Quantum Chromodynamics (Lattice QCD) is dominated by one kernel routine responsible for computing the actions of a Dirac operator. This paper describes an experience in parallelizing this kernel routine. We explore parallelization granularities for this kernel routine on Graphical Processing Units (GPUs). We show that fine-grained parallelism can outperform coarse-grained parallelization, given that control-flow and communication effects are minimized. We propose two techniques for transforming control-flow-based code to control-free code. We also show how to reduce the communication effect by optimizing for commonly used sequences of calls to this routine. In our implementation on NVIDIA 8800 GTX, we were able to achieve an 8.3x speedup over an SSE2 optimized version on 2.8 GHz Intel Xeon CPU. (c) 2008 Elsevier Inc. All rights reserved.

关键词： Lattice QCD calculations Graphic processing unit (GPU) General-purpose computing on graphics hardware SIMD computer architecture data-parallel computing High-performance computing Domain specific systems

来源：评论

学校读者我要写书评

暂无评论

A survey of general-purpose computation on graphics hardware

引用

COMPUTER GRAPHICS FORUM 2007年第1期26卷 80-113页

作者： Owens, John D. Luebke, David Govindaraju, Naga Harris, Mark Krueger, Jens Lefohn, Aaron E. Purcell, Timothy J. Univ Calif Davis Davis CA 95616 USA Microsoft Corp Many Core Technol Incubat Grp Redmond WA 98052 USA Tech Univ Munich D-8000 Munich Germany

The rapid increase in the performance of graphics hardware, coupled with recent improvements in its programmability, have made graphics hardware a compelling platform for computationally demanding tasks in a wide variety of application domains. In this report, we describe, summarize, and analyze the latest research in mapping general-purpose computation to graphics hardware. We begin with the technical motivations that underlie general-purpose computation on graphics processors (GPGPU) and describe the hardware and software developments that have led to the recent interest in this field. We then aim the main body of this report at two separate audiences. First, we describe the techniques used in mapping general-purpose computation to graphics hardware. We believe these techniques will be generally useful for researchers who plan to develop the next generation of GPGPU algorithms and techniques. Second, we survey and categorize the latest developments in general-purpose application development on graphics hardware.

关键词： GPGPU general-purpose computing on graphics hardware parallel computing GPU graphics hardware SIMD stream processing stream computing data-parallel computing high-performance computing HPC

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：