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

18th acm sigplan symposium on principles and practice of parallel programming

作者： Park, Changhee Steele, Guy L., Jr. Tristan, Jean-Baptiste Korea Adv Inst Sci & Technol Taejon South Korea

In the sciences, it is common to use the so-called "big operator" notation to express the iteration of a binary operator (the reducer) over a collection of values. Such a notation typically assumes that the reducer is associative and abstracts the iteration process. Consequently, from a programming point-of-view, we can organize the reducer operations to minimize the depth of the overall reduction, allowing a potentially parallel evaluation of a big operator expression. We believe that the big operator notation is indeed an effective construct to express parallel computations in the Generate/Map/Reduce programming model, and our goal is to introduce it in programming languages to support parallel programming. the effective definition of such a big operator expression requires a simple way to generate elements, and a simple way to declare algebraic properties of the reducer (such as its identity, or its commutativity). In this poster, we want to present an extension of Scala with support for big operator expressions. We show how big operator expressions are defined and how the API is organized to support the simple definition of reducers with their algebraic properties.

关键词： parallelism Mathematical notation Scala

来源：评论

学校读者我要写书评

暂无评论

Interaction of parallel programming constructs and coherence protocols

Interaction of parallel programming constructs and coherence...

引用

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

作者： Bianchini, Ricardo Carrera, Enrique V. Kontothanassis, Leonidas Federal Univ of Rio de Janeiro Rio de Janeiro Brazil

Some of the most common parallel programming idioms include locks, barriers, and reduction operations. the interaction of these programming idioms with the multiprocessor's coherence protocol has a significant impact on performance. In addition, the advent of machines that support multiple coherence protocols prompts the question of how to best implement such parallel constructs, i.e. what combination of implementation and coherence protocol yields the best performance. In this paper we study the running time and communication behavior of (1) centralized (ticket) and MCS spin locks, (2) centralized, dissemination, and tree-based barriers, and (3) parallel and sequential reductions, under pure and competitive update coherence protocols;results for write-invalidate protocol are presented mostly for comparison purposes. Our experiments indicate that parallel programming techniques that are well-established for write invalidate protocols, such as MCS locks and parallel reductions, are often inappropriate for update-based protocols. In contrast, techniques such as dissemination and tree barriers achieve superior performance under update-based protocols. Our results also show that the implementation of parallel programming idioms must take the coherence protocol into account, since update-based protocols often lead to different design decisions than write invalidate protocols. Our main conclusion is that protocol-conscious implementation of parallel programming structures can significantly improve application performance;for multiprocessors that can support more than one coherence protocol both the protocol and implementation should be taken into account when exploiting parallel constructs.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

SEP-Graph: Finding Shortest Execution Paths for Graph Processing under a Hybrid Framework on GPU 19

SEP-Graph: Finding Shortest Execution Paths for Graph Proces...

引用

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

作者： Wang, Hao Geng, Liang Lee, Rubao Hou, Kaixi Zhang, Yanfeng Zhang, Xiaodong Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Northeastern Univ Dept Comp Sci & Engn Shenyang Peoples R China United Parallel Comp Corp Atlanta DE USA Virginia Tech Dept Comp Sci Blacksburg VA USA

ISBN: (纸本)9781450362252

In general, the performance of parallel graph processing is determined by three pairs of critical parameters, namely synchronous or asynchronous execution mode (Sync or Async), Push or Pull communication mechanism (Push or Pull), and Data-driven or Topology-driven traversing scheme (DD or TD), which increases the complexity and sophistication of programming and system implementation of GPU. Existing graph-processing frameworks mainly use a single combination in the entire execution for a given application, but we have observed their variable and suboptimal performance. In this paper, we present SEP-Graph, a highly efficient software framework for graph-processing on GPU. the hybrid execution mode is automatically switched among three pairs of parameters, with an objective to achieve the shortest execution time in each iteration. We also apply a set of optimizations to SEP-Graph, considering the characteristics of graph algorithms and underlying GPU architectures. We show the effectiveness of SEP-Graph based on our intensive and comparative performance evaluation on NVIDIA 1080, P100, and V100 GPUs. Compared with existing and representative GPU graph-processing framework Groute and Gunrock, SEP-Graph can reduce execution time up to 45.8 times and 39.4 times.

关键词： Graph Algorithms GPU Hybrid

来源：评论

学校读者我要写书评

暂无评论

A Type theoretic Specification of Partial Evaluation 14

A Type Theoretic Specification of Partial Evaluation

引用

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

作者： Asai, Kenichi Fennell, Luminous thiemann, Peter Zhang, Yang Ochanomizu Univ Tokyo Japan Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450329477

We develop a type theoretic specification of offline partial evaluation for the simply-typed lambda calculus in the dependently-typed programming language Agda. We establish the correctness of the specification by proving termination, typing preservation, and semantics preservation using logical relations. Typing preservation is achieved by relying on a typed syntax representation based on De Bruijn indices for the source and the target language. the full calculus contains primitive recursion on natural numbers and higherorder lifting for function, product, and sum types.

关键词： partial evaluation dependently-typed programming typed metaprogramming

来源：评论

学校读者我要写书评

暂无评论

parallel 'go with the winners' algorithms in distributed memory models

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2003年第9期63卷 801-814页

作者： Peinado, M Lengauer, T Microsoft Corp Redmond WA 98052 USA Max Planck Inst Comp Sci D-66123 Saarbrucken Germany

We parallelize the 'go with the winners' algorithm of Aldous and Vazirani (in: Proceedings of the 35th IEEE symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring., MD, 1994, pp. 492-501) and analyze the resulting parallel algorithm in the LogP-model (in: Proceedings of the Fourth acm sigplan symposium on principles & practice of parallel programming, 1993, pp. 1-12). the main issues in the analysis are load imbalances and communication delays. the result of the analysis is a practical algorithm which, under reasonable assumptions, achieves linear speedup. Finally, we analyze our algorithm for a concrete application: generating models of amorphous chemical structures. (C) 2003 Elsevier Inc. All rights reserved.

关键词： parallel algorithms go with the winners LogP model second moment method load balancing amorphous solids self-avoiding walks

来源：评论

学校读者我要写书评

暂无评论

POSTER: Stream-K:Work-centric parallel Decomposition for Dense Matrix-Matrix Multiplication on the GPU 28

POSTER: Stream-K:Work-centric Parallel Decomposition for Den...

引用

28th acm sigplan Annual symposium on principles and practice of parallel programming, PPoPP 2023

作者： Osama, Muhammad Merrill, Duane Cecka, Cris Garland, Michael Owens, John D. University of California Davis United States NVIDIA Corporation

ISBN: (纸本)9798400700156

We introduce Stream-K, a work-centric parallelization of matrix multiplication (GEMM) and related computations in dense linear algebra. Whereas contemporary decompositions are primarily tile-based, our method operates by partitioning an even share of the aggregate inner loop iterations among physical processing elements. this provides a near-perfect utilization of computing resources, regardless of how efficiently the output tiling for any given problem quantizes across the underlying processing elements. © 2023 Owner/Author.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Deterministic parallel Random-Number Generation for Dynamic-Multithreading Platforms 12

Deterministic Parallel Random-Number Generation for Dynamic-...

引用

17th acm sigplan symposium on principles and practice of parallel programming

作者： Leiserson, Charles E. Schardl, Tao B. Sukha, Jim MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)9781450311601

Existing concurrency platforms for dynamic multithreading do not provide repeatable parallel random-number generators. this paper proposes that a mechanism called pedigrees be built into the runtime system to enable efficient deterministic parallel random-number generation. Experiments with the open-source MIT Cilk runtime system show that the overhead for maintaining pedigrees is negligible. Specifically, on a suite of 10 benchmarks, the relative overhead of Cilk with pedigrees to the original Cilk has a geometric mean of less than 1%. We persuaded Intel to modify its commercial C/C++ compiler, which provides the Cilk Plus concurrency platform, to include pedigrees, and we built a library implementation of a deterministic parallel random-number generator called DOTMIX that compresses the pedigree and then "RC6-mixes" the result. the statistical quality of DOTMIX is comparable to that of the popular Mersenne twister, but somewhat slower than a nondeterministic parallel version of this efficient and high-quality serial random-number generator. the cost of calling DOTMIX depends on the "spawn depth" of the invocation. For a naive Fibonacci calculation with n = 40 that calls DOTMIX in every node of the computation, this "price of determinism" is about a factor of 2.3 in running time over the nondeterministic Mersenne twister, but for more realistic applications with less intense use of random numbers - such as a maximal-independent-set algorithm, a practical samplesort program, and a Monte Carlo discrete-hedging application from QuantLib - the observed "price" was at most 2 1%, and sometimes much less. Moreover, even if overheads were several times greater, applications using DOTMIX should be amply fast for debugging purposes, which is a major reason for desiring repeatability.

关键词： Algorithms Performance theory Cilk determinism dynamic multithreading nondeterminism parallel computing pedigree random-number generator

来源：评论

学校读者我要写书评

暂无评论

One-and-a-halfth-order logic 06

One-and-a-halfth-order logic

引用

PPDP'06 - 8th acm sigplan symposium on principles and practice of Declarative programming

作者： Gabbay, Murdoch J. Mathijssen, Aad Dept. of Computer Science Heriot-Watt University Riccarton Edinburgh EH14 4AS United Kingdom P.O. Box 513 5600 MB Eindhoven Netherlands

ISBN: (纸本)1595933883

the practice of first-order logic is replete with meta-level concepts. Most notably there are the meta-variables themselves (ranging over predicates, variables, and terms), assumptions about freshness of variables with respect to these meta-variables, alpha-equivalence and capture-avoiding substitution. We present one-and-a-halfth-order logic, in which these concepts are made explicit. We exhibit both algebraic and sequent specifications of one-and-a-halfth-order logic derivability, show them equivalent, show that the derivations satisfy cut-elimination, and prove correctness of an interpretation of first-order logic within it. We discuss the technicalities in a wider context as a case-study for nominal algebra, as a logic in its own right, as an algebraisation of logic, as an example of how other systems might be treated, and also as a theoretical foundation for future implementation. Copyright © 2006 acm.

关键词： Logic programming

来源：评论

学校读者我要写书评

暂无评论

ParlayANN: Scalable and Deterministic parallel Graph-Based Approximate Nearest Neighbor Search Algorithms 24

ParlayANN: Scalable and Deterministic Parallel Graph-Based A...

引用

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

作者： Manohar, Magdalen Dobson Shen, Zheqi Blelloch, Guy E. Dhulipala, Laxman Gu, Yan Simhadri, Harsha Vardhan Sun, Yihan Carnegie Mellon Univ Pittsburgh PA 15213 USA UC Riverside Riverside CA USA Univ Maryland Baltimore MD USA Microsoft Res Redmond WA USA

ISBN: (纸本)9798400704352

Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector space representations (i.e., embeddings) of data. Among various ANNS algorithms, graph-based algorithms are known to achieve the best throughput-recall tradeoffs. Despite the large scale of modern ANNS datasets, existing parallel graphbased implementations suffer from significant challenges to scale to large datasets due to heavy use of locks and other sequential bottlenecks, which 1) prevents them from efficiently scaling to a large number of processors, and 2) results in nondeterminism that is undesirable in certain applications. In this paper, we introduce ParlayANN, a library of deterministic and parallel graph-based approximate nearest neighbor search algorithms, along with a set of useful tools for developing such algorithms. In this library, we develop novel parallel implementations for four state-of-the-art graph-based ANNS algorithms that scale to billion-scale datasets. Our algorithms are deterministic and achieve high scalability across a diverse set of challenging datasets. In addition to the new algorithmic ideas, we also conduct a detailed experimental study of our new algorithms as well as two existing non-graph approaches. Our experimental results both validate the effectiveness of our new techniques, and lead to a comprehensive comparison among ANNS algorithms on large scale datasets with a list of interesting findings.

关键词： nearest neighbor search vector search parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Race Detection with Futures 19

Efficient Race Detection with Futures

引用

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

作者： Utterback, Robert Agrawal, Kunal Fineman, Jeremy Lee, I-Ting Angelina Monmouth Coll Monmouth IL 61462 USA Washington Univ St Louis MO 14263 USA Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450362252

this paper addresses the problem of provably efficient and practically good on-the-fly determinacy race detection in task parallel programs that use futures. Prior works on determinacy race detection have mostly focused on either task parallel programs that follow a series-parallel dependence structure or ones with unrestricted use of futures that generate arbitrary dependences. In this work, we consider a restricted use of futures and show that we can detect races more efficiently than with general use of futures. Specifically, we present two algorithms: MultiBags and MultiBags+. MultiBags targets programs that use futures in a restricted fashion and runs in time O(T-1 alpha(m, n)), where T-1 is the sequential running time of the program, a is the inverse Ackermann's function, m is the total number of memory accesses, n is the dynamic count of places at which parallelism is created. Since a is a very slowly growing function (upper bounded by 4 for all practical purposes), it can be treated as a close-to-constant overhead. MultiBags+ is an extension of MultiBags that target programs with general use of futures. It runs in time O((T-1 + k(2))alpha(m, n)) where T-1, alpha, m and n are defined as before, and k is the number of future operations in the computation. We implemented both algorithms and empirically demonstrate their efficiency.

关键词： dynamic program analysis determinacy race race detection series-parallel maintenance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：