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

20th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2015

作者： Tang, Yuan You, Ronghui Kan, Haibin Tithi, Jesmin Jahan Ganapathi, Pramod Chowdhury, Rezaul A. Software School School of Computer Science Fudan University Shanghai Key Laboratory of Intelligent Information Processing Shanghai China Department of Computer Science Stony Brook University Stony BrookNY11790 United States

ISBN: (纸本)9781450332057

State-of-the-art cache-oblivious parallel algorithms for dynamic programming (DP) problems usually guarantee asymptotically optimal cache performance without any tuning of cache parameters, but they often fail to exploit the theoretically best parallelism at the same time. While these algorithms achieve cache-optimality through the use of a recursive divide-and-conquer (DAC) strategy, scheduling tasks at the granularity of task dependency introduces artificial dependencies in addition to those arising from the defining recurrence equations. We removed the artificial dependency by scheduling tasks ready for execution as soon as all its real dependency constraints are satisfied, while preserving the cache-optimality by inheriting the DAC strategy. We applied our approach to a set of widely known dynamic programming problems, such as Floyd-Warshall's All-Pairs Shortest Paths, Stencil, and LCS. theoretical analyses show that our techniques improve the span of 2-way DAC-based Floyd Warshall's algorithm on an n node graph from Θ(nlog2 n) to Θ(n), stencil computations on a d-dimensional hypercubic grid of width w for h time steps from Θ ((d2h) wlog(d+2)-1) to Θ(h), and LCS on two sequences of length n each from Θ (nlog23) to Θ(n). In each case, the total work and cache complexity remain asymptotically optimal. Experimental measurements exhibit a 3-5 times improvement in absolute running time, 10-20 times improvement in burdened span by Cilkview, and approximately the same L1/L2 cache misses by PAPI. Copyright 2015 acm.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

CUDA-NP: Realizing nested thread-level parallelism in GPGPU applications 14

CUDA-NP: Realizing nested thread-level parallelism in GPGPU ...

引用

2014 19th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2014

作者： Yang, Yi Zhou, Huiyang Department of Computing Systems Architecture NEC Laboratories America Inc. United States Department of Electrical and Computer Engineering North Carolina State University United States

ISBN: (纸本)9781450326568

parallel programs consist of series of code sections with different thread-level parallelism (TLP). As a result, it is rather common that a thread in a parallel program, such as a GPU kernel in CUDA programs, still contains both sequential code and parallel loops. In order to leverage such parallel loops, the latest Nvidia Kepler architecture introduces dynamic parallelism, which allows a GPU thread to start another GPU kernel, thereby reducing the overhead of launching kernels from a CPU. However, with dynamic parallelism, a parent thread can only communicate with its child threads through global memory and the overhead of launching GPU kernels is non-trivial even within GPUs. In this paper, we first study a set of GPGPU benchmarks that contain parallel loops, and highlight that these benchmarks do not have a very high loop count or high degrees of TLP. Consequently, the benefits of leveraging such parallel loops using dynamic parallelism are too limited to offset its overhead. We then present our proposed solution to exploit nested parallelism in CUDA, referred to as CUDA-NP. With CUDA-NP, we initially enable a high number of threads when a GPU program starts, and use control flow to activate different numbers of threads for different code sections. We implemented our proposed CUDA-NP framework using a directive-based compiler approach. For a GPU kernel, an application developer only needs to add OpenMP-like pragmas for parallelizable code sections. then, our CUDA-NP compiler automatically generates the optimized GPU kernels. It supports both the reduction and the scan primitives, explores different ways to distribute parallel loop iterations into threads, and efficiently manages on-chip resource. Our experiments show that for a set of GPGPU benchmarks, which have already been optimized and contain nested parallelism, our proposed CUDA-NP framework further improves the performance by up to 6.69 times and 2.18 times on average. Copyright © 2014 acm.

关键词： Application programming interfaces (API)

来源：评论

学校读者我要写书评

暂无评论

Compiling CHR to parallel hardware 12

Compiling CHR to parallel hardware

引用

14th symposium on principles and practice of Declarative programming, PPDP 2012

作者： Triossi, Andrea Orlando, Salvatore Raffaetà, Alessandra Frühwirth, thom DAIS Università Ca'Foscari Venezia Italy Inst. for Software Engineering and Compiler Construction Ulm University Germany

ISBN: (纸本)9781450315227

this paper investigates the compilation of a committed-choice rulebased language, Constraint Handling Rules (CHR), to specialized hardware circuits. the developed hardware is able to turn the intrinsic concurrency of the language into parallelism. Rules are applied by a custom executor that handles constraints according to the best degree of parallelism the implemented CHR specification can offer. Our framework deploys the target digital circuits through the Field Programmable Gate Array (FPGA) technology, by first compiling the CHR code fragment into a low level hardware description language. We also discuss the realization of a hybrid CHR interpreter, consisting of a software component running on a general purpose processor, coupled with a hardware accelerator. the latter unburdens the processor by executing in parallel the most computational intensive CHR rules directly compiled in hardware. Finally the performance of a prototype system is evaluated by time efficiency measures. Copyright © 2012 acm.

关键词： Field programmable gate arrays (FPGA)

来源：评论

学校读者我要写书评

暂无评论

Effective garbage collection strategy for parallel programming languages on large scale distributed-memory machines

Effective garbage collection strategy for parallel programmi...

引用

Proceedings of the 1997 6th acm sigplan symposium on principles and practice of parallel programming

作者： Taura, Kenjiro Yonezawa, Akinori Univ of Tokyo Tokyo Japan

this paper describes the design and implementation of a garbage collection scheme on large-scale distributed-memory computers and reports various experimental results. the collector is based on the conservative GC library by Boehm & Weiser. Each processor traces local pointers using the GC library while traversing remote pointers by exchanging 'mark messages' between processors. It exhibits a promising performance - in the most space-intensive settings we tested, the total collection overhead ranges from 5% up to 15% of the application running time (excluding idle time). We not only examine basic performance figures such as the total overhead or latency of a global collection, but also demonstrate how local collection scheduling strategies affect application performance. In our collector, a local collection is scheduled either independently or synchronously. Experimental results show that the benefit of independent local collections has been overstated in the literature. Independent local collections slowed down application performance to 40%, by increasing the average communication latency. Synchronized local collections exhibit much more robust performance characteristics than independent local collections and the overhead for global synchronization is not significant. Furthermore, we show that an adaptive collection scheduler can select the appropriate local collection strategy based on the application's behavior. the collector has been used in a concurrent object-oriented language ABCL/f and the performance is measured on a large-scale parallel computer (256 processors) using four non-trivial applications written in ABCL/f.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

VAPRO: Performance Variance Detection and Diagnosis for Production-Run parallel Applications 22

VAPRO: Performance Variance Detection and Diagnosis for Prod...

引用

27th acm sigplan symposium on principles and practice of parallel programming (PPoPP)

作者： Zheng, Liyan Zhai, Jidong Tang, Xiongchao Wang, Haojie Yu, Teng Jin, Yuyang Song, Shuaiwen Leon Chen, Wenguang Tsinghua Univ Beijing Peoples R China Sangfor Technol Inc Shenzhen Guangdong Peoples R China Univ Sydney Sydney NSW Australia BNRist Beijing Peoples R China

ISBN: (纸本)9781450392044

Performance variance is a serious problem for parallel applications, which can cause performance degradation and make applications' behavior hard to understand. therefore, detecting and diagnosing performance variance are of crucial importance for users and application developers. However, previous detection approaches either bring too large overhead and hurt applications' performance, or rely on nontrivial source code analysis that is impractical for production-run parallel applications. In this work, we propose VAPRO, a performance variance detection and diagnosis framework for production-run parallel applications. Our approach is based on an important observation that most parallel applications contain code snippets that are repeatedly executed with fixed workload, which can be used for performance variance detection. To effectively identify these snippets at runtime even without program source code, we introduce State Transition Graph (STG) to track program execution and then conduct lightweight workload analysis on STG to locate variance. To diagnose the detected variance, VAPRO leverages a progressive diagnosis method based on a hybrid model leveraging variance breakdown and statistical analysis. Results show that the performance overhead of VAPRO is only 1.38% on average. VAPRO can detect the variance in real applications caused by hardware bugs, memory, and IQ After fixing the detected variance, the standard deviation of the execution time is reduced by up to 73.5%. Compared with the state-of-the-art variance detection tool based on source code analysis, VAPRO achieves 30.0% higher detection coverage.

关键词： Performance Variance Anomaly Detection System Noise

来源：评论

学校读者我要写书评

暂无评论

Computation migration: Enhancing locality for distributed-memory parallel systems 93

Computation migration: Enhancing locality for distributed-me...

引用

4th acm sigplan symposium on principles and practice of parallel programming, PPOPP 1993

作者： Hsieh, Wilson C. Wang, Paul Weihl, William E. MIT Laboratory for Computer Science 545 Technology Square CambridgeMA02139 United States

ISBN: (纸本)0897915895

We describe computation migration, a new technique that is based on compile-time program transformations, for accessing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. the access is performed at the remote processor, and the migrated thread portion continues to run on that same processor;this makes subsequent accesses in the thread portion local. We describe an implementation of computation migra^ tion that consists of two parts: an implementation that migrates single activation frames, and a high-level language annotation that allows a programmer to express when migration is desired. We performed experiments using two applications;these experiments demonstrate that computation migration is a valuable alternative to RPC and data migration.

关键词： High level languages

来源：评论

学校读者我要写书评

暂无评论

SCCMulti: An improved parallel strongly connected components algorithm 14

SCCMulti: An improved parallel strongly connected components...

引用

2014 19th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2014

作者： Tomkins, Daniel Smith, Timmie Amato, Nancy M. Rauchwerger, Lawrence Parasol Laboratory Department of Computer Science and Engineering Texas A and M University United States

ISBN: (纸本)9781450326568

Tarjan's famous linear time, sequential algorithm for finding the strongly connected components (SCCs) of a graph relies on depth first search, which is inherently sequential. Deterministic parallel algorithms solve this problem in logarithmic time using matrix multiplication techniques, but matrix multiplication requires a large amount of total work. Randomized algorithms based on reachability - the ability to get from one vertex to another along a directed path - greatly improve the work bound in the average case. However, these algorithms do not always perform well;for instance, Divide-and-Conquer Strong Components (DCSC), a scalable, divide-and-conquer algorithm, has good expected theoretical limits, but can perform very poorly on graphs for which the maximum reachability of any vertex is small. A related algorithm, MultiPivot, gives very high probability guarantees on the total amount of work for all graphs, but this improvement introduces an overhead that increases the average running time. this work introduces SCCMulti, a multi-pivot improvement of DCSC that offers the same consistency as MultiPivot without the time overhead. We provide experimental results demonstrating SCCMulti's scalability;these results also show that SCCMulti is more consistent than DCSC and is always faster than MultiPivot.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

An Internalist Approach to Correct-by-Construction Compilers 18

An Internalist Approach to Correct-by-Construction Compilers

引用

20th International symposium on principles and practice of Declarative programming (PPDP)

作者： Pardo, Alberto Gunther, Emmanuel Pagano, Miguel Viera, Marcos Univ Republica Montevideo Uruguay UNC FAMAF Cordoba Spain Consejo Nacl Invest Cient & Tecn Cordoba Spain

ISBN: (纸本)9781450364416

In this paper we present a methodology to organize the construction of a correct compiler, taking advantage of the power of full dependently type systems. the basic idea consists in decorating the abstract syntax of languages with their semantics, allowing to express the correctness of the compiler at type level. We show our methodology in a first small example and then explore how it can be promoted to more realistic languages, realizing that our internalistic approach is feasible for defining a correct-by-construction compiler from an imperative language with conditional iteration to a stack based intermediate language. We also show how this methodology can be combined with the externalist approach, compiling from the intermediate language to an assembly-like low level code and separately proving its correctness.

关键词： compiler design dependent types dependently-typed programming indexed families correct-by-construction ornaments

来源：评论

学校读者我要写书评

暂无评论

RaftLib: A C plus plus template library for high performance stream parallel processing

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2017年第5期31卷 391-404页

作者： Beard, Jonathan C. Li, Peng Chamberlain, Roger D. ARM Res 5707 Southwest Pkwy Suite 100 Austin Austin TX 78735 USA Amazon Inc Seattle WA USA Washington Univ Dept Comp Sci & Engn St Louis MO 63130 USA

Stream processing is a compute paradigm that has been around for decades, yet until recently has failed to garner the same attention as other mainstream languages and libraries (e.g. C++, OpenMP, MPI). Stream processing has great promise: the ability to safely exploit extreme levels of parallelism to process huge volumes of streaming data. there have been many implementations, both libraries and full languages. the full languages implicitly assume that the streaming paradigm cannot be fully exploited in legacy languages, while library approaches are often preferred for being integrable with the vast expanse of extant legacy code. Libraries, however are often criticized for yielding to the shape of their respective languages. RaftLib aims to fully exploit the stream processing paradigm, enabling a full spectrum of streaming graph optimizations, while providing a platform for the exploration of integrability with legacy C/C++ code. RaftLib is built as a C++ template library, enabling programmers to utilize the robust C++ standard library, and other legacy code, along with RaftLib's parallelization framework. RaftLib supports several online optimization techniques: dynamic queue optimization, automatic parallelization, and real-time low overhead performance monitoring.

关键词： Stream processing big-data C plus plus template library high performance computing RaftLib performance monitoring parallel processing

来源：评论

学校读者我要写书评

暂无评论

Lifeline-based Global Load Balancing 11

Lifeline-based Global Load Balancing

引用

16th acm symposium on principles and practice of parallel programming

作者： Saraswat, Vijay Kambadur, Prabhanjan Kodali, Sreedhar Grove, David Krishnamoorthy, Sriram Pacific NW Natl Lab Richland WA 99352 USA

ISBN: (纸本)9781450301190

On shared-memory systems, Cilk-style work-stealing [5] has been used to effectively parallelize irregular task-graph based applications such as Unbalanced Tree Search (UTS) [24, 28]. there are two main difficulties in extending this approach to distributed memory. In the shared memory approach, thieves (nodes without work) constantly attempt to asynchronously steal work from randomly chosen victims until they find work. In distributed memory, thieves cannot autonomously steal work from a victim without disrupting its execution. When work is sparse, this results in performance degradation. In essence, a direct extension of traditional work-stealing to distributed memory violates the work-first principle underlying work-stealing. Further, thieves spend useless CPU cycles attacking victims that have no work, resulting in system inefficiencies in multi-programmed contexts. Second, it is non-trivial to detect active distributed termination (detect that programs at all nodes are looking for work, hence there is no work). this problem is well-studied and requires careful design for good performance. Unfortunately, in most existing languages/frameworks, application developers are forced to implement their own distributed termination detection. In this paper, we develop a simple set of ideas that allow work-stealing to be efficiently extended to distributed memory. First, we introduce lifeline graphs: low-degree, low-diameter, fully-connected directed graphs. Such graphs can be constructed from k-dimensional hypercubes. When a node is unable to find work after w unsuccessful steals, it quiesces after informing the outgoing edges in its lifeline graph. Quiescent nodes do not disturb other nodes. A quiesced node is reactivated when work arrives from a lifeline, and itself shares this work with those of its incoming lifelines that are activated. Termination occurs precisely when computation at all nodes has quiesced. In a language such as X10, such passive distributed terminati

关键词： UTS global load balancing distributed computing X10 work-stealing parallel programming Algorithms Design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：