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

proceedings of the acm sigplan symposium on principles and practice of parallel programming, PPOPP 1999年 84-95页

作者： Moon, Sungdo Hall, Mary W. Univ of Southern California Marina del Rey United States

this paper presents an evaluation of a new analysis for parallelizing compilers called predicated array data-flow analysis. this analysis extends array data-flow analysis for parallelization and privatization to associate predicates with data-flow values. these predicates can be used to derive conditions under which dependences can be eliminated or privatization is possible. these conditions can be used both to enhance compile-time analysis and to introduce run-time tests that guard safe execution of a parallelized version of a computation. As compared to previous work that combines predicates with array data-flow analysis, our approach is distinguished by two features: (1) it derives low-cost, run-time parallelization tests;and, (2) it incorporates predicate embedding and predicate extraction, which translate between the domain of predicates and data-flow values to derive more precise analysis results. We present extensive experimental results across three benchmark suites and one additional program, demonstrating that predicated array data-flow analysis parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler and that it yields improved speedups for 5 programs.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

High-Performance GPU-to-CPU Transpilation and Optimization via High-Level parallel Constructs 23

High-Performance GPU-to-CPU Transpilation and Optimization v...

引用

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

来源：评论

学校读者我要写书评

暂无评论

parallel Evaluation of Recursive Rule Queries 5

Parallel Evaluation of Recursive Rule Queries

引用

5th acm SIGACT-SIGMOD symposium on principles of Database Systems, PODS 1986

作者： Cosmadakis, Stavros S. Kanellakis, Paris C. IBM Thomas J. Watson Research Center NY United States Brown University RI United States

We investigate the parallel computational complexity of recursive rule queries. these queries are a subset of first-order relational queries augmented with recursion. they form an important part of the PROLOG language and can be evaluated in PTIME. In [32] Sagiv has shown that it is decidable whether a typed recursive rule query is equivalent to a first-order relational query. We present an alternative proof of this fact We demonstrate a "gap" theorem for these queries. We provide two classes of queries, which can be evaluated in NC, using a logarithmic number of iterations of a first-order query. Finally, we give various, syntactically tight, queries which are logspace-complete in PTIME and cannot be evaluated in this fashion. © 1999 Association for Computing Machinery. All rights reserved.

关键词： Logic programming

来源：评论

学校读者我要写书评

暂无评论

Predictive analysis of a wavefront application using LogGP

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年 141-150页

作者： Sundaram-Stukel, David Vernon, Mary K. Epic Systems Corp Madison WI United States

this paper develops a highly accurate LogGP model of a complex wavefront application that uses MPI communication on the IBM SP/2. Key features of the model include: (1) elucidation of the principal wavefront synchronization structure, and (2) explicit high-fidelity models of the MPI-send and MPI-receive primitives. the MPI-send/receive models are used to derive L, o, and G from simple two-node micro-benchmarks. Other model parameters are obtained by measuring small application problem sizes on four SP nodes. Results show that the LogGP model predicts, in seconds and with a high degree of accuracy, measured application execution time for large problems running on 128 nodes. Detailed performance projections are provided for very large future processor configurations that are expected to be available to the application developers. these results indicate that scaling beyond one or two thousand nodes yields greatly diminished in execution time, and that synchronization delays are a principal factor limiting the scalability of the application.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Automatic parallelization of divide and conquer algorithms

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年 72-83页

作者： Rugina, Radu Rinard, Martin Massachusetts Inst of Technology Cambridge United States

Divide and conquer algorithms are a good match for modern parallel machines: they tend to have large amounts of inherent parallelism and they work well with caches and deep memory hierarchies. But these algorithms pose challenging problems for parallelizing compilers. they are usually coded as recursive procedures and often use pointers into dynamically allocated memory blocks and pointer arithmetic. All of these features are incompatible with the analysis algorithms in traditional parallelizing compilers. this paper presents the design and implementation of a compiler that is designed to parallelize divide and conquer algorithms whose subproblems access disjoint regions of dynamically allocated arrays. the foundation of the compiler is a flow-sensitive, context-sensitive, and interprocedural pointer analysis algorithm. A range of symbolic analysis algorithms build on the pointer analysis information to extract symbolic bounds for the memory regions accessed by (potentially recursive) procedures that use pointers and pointer arithmetic. the symbolic bounds information allows the compiler to find procedure calls that can execute in parallel without violating the data dependences. the compiler generates code that executes these calls in parallel. We have used the compiler to parallelize several programs that use divide and conquer algorithms. Our results show that the programs perform well and exhibit good speedup.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

SUIF Explorer: An interactive and interprocedural parallelizer

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年 37-48页

作者： Liao, Shih-Wei Diwan, Amer Bosch Jr., Robert P. Ghuloum, Anwar Lam, Monica S. Stanford Univ United States

the SUIF Explorer is an interactive parallelization tool that is more effective than previous systems in minimizing the number of lines of code that require programmer assistance. First, the interprocedural analyses in the SUIF system is successful in parallelizing many coarse-grain loops, thus minimizing the number of spurious dependences requiting attention. Second, the system uses dynamic execution analyzers to identify those important loops that are likely to be parallelizable. third, the SUIF Explorer is the first to apply program slicing to aid programmers in interactive parallelization. the system guides the programmers in the parallelization process using a set of sophisticated visualization technique. this paper demonstrates the effectiveness of the SUIF Explorer with three case studies. the programmer was able to speed up all three programs by examining only a small fraction of the program and privatizing a few variables.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Stackthreads/MP: Integrating futures into calling standards

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年 60-71页

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

An implementation scheme of fine-grain multithreading that needs no changes to current calling standards for sequential languages and modest extensions to sequential compilers is described. Like previous similar systems, it performs an asynchronous call as if it were an ordinary procedure call, and detaches the callee from the caller when the callee suspends or either of them migrates to another processor. Unlike previous similar systems, it detaches and connects arbitrary frames generated by off-the-shelf sequential compilers obeying calling standards. As a consequence, it requires neither a frontend preprocessor nor a native code generator that has a builtin notion of parallelism. the system practically works with unmodified GNU C compiler (GCC). Desirable extensions to sequential compilers for guaranteeing portability and correctness of the scheme are clarified and claimed modest. Experiments indicate that sequential performance is not sacrificed for practical applications and both sequential and parallel performance are comparable to Cilk, whose current implementation requires a fairly sophisticated preprocessor to C. these results show that efficient asynchronous calls (a.k.a. future calls) can be integrated into current calling standard with a very small impact both on sequential performance and compiler engineering.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Automatic node selection for high performance applications on networks

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年 163-172页

作者： Subhlok, Jaspal Lieu, Peter Lowekamp, Bruce Univ of Houston Houston United States

A central problem in executing performance critical parallel and distributed applications on shared networks is the selection of computation nodes and communication paths for execution. Automatic selection of nodes is complex as the best choice depends on the application structure as well as the expected availability of computation and communication resources. this paper presents a solution to this problem for realistic application and network scenarios. A new algorithm to jointly analyze computation and communication resources for different application demands is introduced and a framework for automatic node selection is developed on top of Remos, which is a query interface to network information. the paper reports results from a set of applications, including Airshed pollution modeling and magnetic resonance imaging, executing on a high speed network testbed. the results demonstrate that node selection is effective in enhancing application performance in the presence of computation load as well as network traffic. Under the network conditions used for experiments, the increase in execution time due to compute loads and network congestion was reduced by half with node selection. the node selection algorithms developed in this research are also applicable to dynamic migration of long running jobs.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：