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

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

作者： Moses, William S. Ivanov, Ivan R. Domke, Jens Endo, Toshio Doerfert, Johannes Zinenko, Oleksandr MIT CSAIL United States Tokyo Tech Japan RIKEN Japan LLNL United States Google France

ISBN: (纸本)9798400700156

While parallelism remains the main source of performance, architectural implementations and programming models change with each new hardware generation, often leading to costly application re-engineering. Most tools for performance portability require manual and costly application porting to yet another programming model. We propose an alternative approach that automatically translates programs written in one programming model (CUDA), into another (CPU threads) based on Polygeist/MLIR. Our approach includes a representation of parallel constructs that allows conventional compiler transformations to apply transparently and without modification and enables parallelism-specific optimizations. We evaluate our framework by transpiling and optimizing the CUDA Rodinia benchmark suite for a multi-core CPU and achieve a 58% geomean speedup over handwritten OpenMP code. Further, we show how CUDA kernels from PyTorch can efficiently run and scale on the CPU-only Supercomputer Fugaku without user intervention. Our PyTorch compatibility layer making use of transpiled CUDA PyTorch kernels outperforms the PyTorch CPU native backend by 2.7×. © 2023 Owner/Author.

关键词： Supercomputers

来源：评论

学校读者我要写书评

暂无评论

Turbocharging Boosted Transactions or: How I Learnt to Stop Worrying and Love Longer Transactions

引用

acm sigplan NOTICES 2009年第4期44卷 307-308页

作者： Kulkarni, Chinmay Unsal, Osman Cristal, Adrian Ayguade, Eduard Valero, Mateo Birla Inst Technol & Sci Pilani Rajasthan India Tech Univ Catalunya Catalunya Spain

Boosted transactions offer an attractive method that enables programmers to create larger transactions that scale well and offer deadlock-free guarantees. However, as boosted transactions get larger, they become more susceptible to conflicts and aborts. We describe a linear-time algorithm to detect transactions that cannot make progress, which transactions need to be aborted, and when. the algorithm guarantees zero false positives with minimal aborts. Our proposals, as implemented in DSTM2, increase the transactional throughput of the system, often by more than 30%.

关键词： Algorithms Performance Concurrency parallel programming transactional memory deadlocks deadlock-detection

来源：评论

学校读者我要写书评

暂无评论

Performance prediction of large parallel applications using parallel simulations

Proceedings of the ACM SIGPLAN Symposium on Principles and P...

引用

Proceedings of the acm sigplan symposium on principles and practice of parallel programming, PPOPP 1999年 151-162页

作者： Bagrodia, Rajive Deelman, Ewa Docy, Steven Phan, thomas Univ of California Los Angeles Los Angeles United States

Accurate simulation of large parallel applications can be facilitated with the use of direct execution and parallel discrete event simulation. this paper describes the use of COMPASS, a direct execution-driven, parallel simulator for performance prediction of programs that include both communication and I/O intensive applications. the simulator has been used to predict the performance of such applications on both distributed memory machines like the IBM SP and shared-memory machines like the SGI Origin 2000. the paper illustrates the usefulness of COMPASS as a versatile performance prediction tool. We use both real-world applications and synthetic benchmarks to study application scalability, sensitivity to communication latency, and the interplay between factors like communication pattern and parallel file system caching on application performance. We also show that the simulator is accurate in its predictions and that it is also efficient in its ability to use parallel simulation to reduce its own execution time which, in some cases, has yielded a near-linear speedup.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

REASONING ABOUT PROBABILISTIC ALGORIthMS 90

REASONING ABOUT PROBABILISTIC ALGORITHMS

引用

9th ANNUAL SYMP OF thE ASSOC FOR COMPUTING MACHINERY : principles OF DISTRIBUTED COMPUTING

作者： RAO, JR Department of Computer Sciences The University of Texas at Austin Austin Texas

ISBN: (纸本)089791404X

the use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. this gain in simplicity, efficiency and solvability results in a tradeoff of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. the addition of the notion of parallelism to the already unintutive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper, we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability one. We present a proof methodology based on existing proof systems for probabilistic algorithms, the theory of the predicate transformer and the theory of UNITY. Although the proofs of probabilistic programs are slippery at best, we show that such programs can be derived with the same rigor and elegance that we have seen in the derivation of sequential and parallel programs. By applying this methodology to derive probabilistic programs, we hope to develop tools and techniques that would make randomization a useful paradigm in algorithm design.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Preliminary Results on NB-FEB, a Synchronization Primitive for parallel programming

引用

acm sigplan NOTICES 2009年第4期44卷 295-296页

作者： Ha, Phuong Hoai Tsigas, Philippas Anshus, Otto J. Univ Tromso N-9001 Tromso Norway Chalmers Univ Technol Gothenburg Sweden

We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).

关键词： Algorithms Reliability theory many-core architectures non-blocking synchronization full/empty bit universal primitives combinability

来源：评论

学校读者我要写书评

暂无评论

parallel k-Core Decomposition with Batched Updates and Asynchronous Reads 24

Parallel k-Core Decomposition with Batched Updates and Async...

引用

29th acm sigplan Annual symposium on principles and practice of parallel programming, PPoPP 2024

作者： Liu, Quanquan C. Shun, Julian Zablotchi, Igor Yale University United States MIT CSAIL United States Mysten Labs Switzerland

ISBN: (纸本)9798400704352

Maintaining a dynamic k-core decomposition is an important problem that identifies dense subgraphs in dynamically changing graphs. Recent work by Liu et al. [SPAA 2022] presents a parallel batch-dynamic algorithm for maintaining an approximate k-core decomposition. In their solution, both reads and updates need to be batched, and therefore each type of operation can incur high latency waiting for the other type to finish. To tackle most real-world workloads, which are dominated by reads, this paper presents a novel hybrid concurrent-parallel dynamic k-core data structure where asynchronous reads can proceed concurrently with batches of updates, leading to significantly lower read latencies. Our approach is based on tracking causal dependencies between updates, so that causally related groups of updates appear atomic to concurrent readers. Our data structure guarantees linearizability and liveness for both reads and updates, and maintains the same approximation guarantees as prior work. Our experimental evaluation on a 30-core machine shows that our approach reduces read latency by orders of magnitude compared to the batch-dynamic algorithm, up to a (4.05 · 105 ) -factor. Compared to an unsynchronized (non-linearizable) baseline, our read latency overhead is only up to a 3.21-factor greater, while improving accuracy of coreness estimates by up to a factor of 52.7. © 2024 Copyright held by the owner/author(s).

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

A Cooperative parallelization Approach for Property-Directed k-Induction 1

引用

21st International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI) part of the 47th acm sigplan symposium on principles of programming Languages (POPL)

作者： Blicha, Martin Hyvarinen, Antti E. J. Marescotti, Matteo Sharygina, Natasha Univ Svizzera Italiana USI Lugano Switzerland Charles Univ Prague Fac Math & Phys Prague Czech Republic

ISBN: (数字)9783030393229

ISBN: (纸本)9783030393229;9783030393212

Recently presented, IC3-inspired symbolic model checking algorithms strengthen the procedure for showing inductiveness of lemmas expressing reachability of states. these approaches show an impressive performance gain in comparison to previous state-of-the-art, but also present new challenges to portfolio-based, lemma sharing parallelization as the solvers now store lemmas that serve different purposes. In this work we formalize this recent algorithm class for lemma sharing parallel portfolios using two central engines, one for checking inductiveness and the other for checking bounded reachability, and show when the respective engines can share their information. In our implementation based on the PD-KIND algorithm, the approach provides a consistent speedup already in a multi-core environment, and surpasses in performance the winners of a recent solver competition by a comfortable margin.

关键词： parallel model checking Lemma sharing Property-directed k-induction IC3/PDR Craig interpolation

来源：评论

学校读者我要写书评

暂无评论

Serialization Sets: A Dynamic Dependence-Based parallel Execution Model

引用

acm sigplan NOTICES 2009年第4期44卷 85-95页

作者： Allen, Matthew D. Sridharan, Srinath Sohi, Gurindar S. Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

this paper proposes a new parallel execution model where programmers augment a sequential program with pieces of code called serializers that dynamically map computational operations into serialization sets of dependent operations. A runtime system executes operations in the same serialization set in program order, and may concurrently execute operations in different sets. Because serialization sets establish a logical ordering on all operations, the resulting parallel execution is predictable and deterministic. We describe the API and design of Prometheus, a C++ library that implements the serialization set abstraction through compile-time template instantiation and a runtime support library. We evaluate a set of parallel programs running on the x86_64 and SPARC-V9 instruction sets and study their performance on multi-core, symmetric multiprocessor, and ccNUMA parallel machines. By contrast with conventional parallel execution models, we find that Prometheus programs are significantly easier to write, test, and debug, and their parallel execution achieves comparable performance.

关键词： Languages Performance parallel computing runtime system serialization sets serializer

来源：评论

学校读者我要写书评

暂无评论

Application-Aware Management of parallel Simulation Collections

引用

acm sigplan NOTICES 2009年第4期44卷 35-44页

作者： Yau, Siu-Man Karamcheti, Vijay Damevski, Kostadin Parker, Steven G. Zorin, Denis NYU Courant Inst Math Sci New York NY 10003 USA Univ Utah Dept Comp Sci Salt Lake City UT 84112 USA

this paper presents a system deployed on parallel clusters to manage a collection of parallel simulations that make up a computational study. It explores how such a system can extend traditional parallel job scheduling and resource allocation techniques to incorporate knowledge specific to the study. Using a UINTAH-based helium gas simulation code (ARCHES) and the SimX system for multi-experiment computational studies, this paper demonstrates that, by using application-specific knowledge in resource allocation and scheduling decisions, one can reduce the run time of a computational study from over 20 hours to under 4.5 hours on a 32-processor cluster, and from almost 11 hours to just over 3.5 hours on a 64-processor cluster.

关键词： Design Performance parallel System High-throughput computing

来源：评论

学校读者我要写书评

暂无评论

Basic compiler algorithms for parallel programs

Proceedings of the ACM SIGPLAN Symposium on Principles and P...

引用

Proceedings of the acm sigplan symposium on principles and practice of parallel programming, PPOPP 1999年 1-12页

作者： Lee, Jaejin Padua, David A. Midkiff, Samuel P. Univ of Illinois Urbana United States

Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. this is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. these optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：