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

Tapir: Embedding Recursive fork-join parallelism into LLVM's Intermediate Representation

ACM TRANSACTIONS ON PARALLEL COMPUTING 2019年第4期6卷 1–33页

作者： Schardl, Tao B. Moses, William S. Leiserson, Charles E. MIT Comp Sci & Artificial Intelligence Lab 32 Vassar St Cambridge MA 02139 USA

Tapir (pronounced TAY-per) is a compiler intermediate representation (IR) that embeds recursive fork-join parallelism, as supported by task-parallel programming platforms such as Cilk and OpenMP, into a mainstream compiler's IR. Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations on and across parallel control constructs. Remedying this situation has generally been thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir leverages the "serial-projection property," which is commonly satisfied by task-parallel programs, to handle the semantics of these programs without an extensive rework of the compiler. For recursive fork-join programs that satisfy the serial-projection property, Tapir enables effective compiler optimization of parallel programs with only minor changes to existing compiler analyses and code transformations. Tapir uses the serial-projection property to order logically parallel fine-grained tasks in the program's control-flow graph. This ordered representation of parallel tasks allows the compiler to optimize parallel codes effectively with only minor modifications. For example, to implement Tapir/LLVM, a prototype of Tapir in the LLVM compiler, we added or modified less than 3,000 lines of LLVM's half-millionline core middle-end functionality. These changes sufficed to enable LLVM's existing compiler optimizations for serial code including loop-invariant-code motion, common-subexpression elimination, and tail-recursion elimination-to work with parallel control constructs such as parallel loops and Cilk's cilk_spawn keyword. Tapir also supports parallel optimizations, such as loop scheduling, which restructure the parallel control flow of the program. By making use of existing LLVM optimizations and new parallel optimizations, Tapir/LLVM can opti

关键词： Cilk compiling control-flow graph fork-join parallelism LLVM multicore OpenMP optimization parallel computing serial-projection property Tapir

来源：评论

学校读者我要写书评

暂无评论

Tapir: Embedding fork-join parallelism into LLVM's Intermediate Representation 17

Tapir: Embedding Fork-Join Parallelism into LLVM's Intermedi...

引用

22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Schardl, Tao B. Moses, William S. Leiserson, Charles E. MIT Comp Sci & Artificial Intelligence Lab 32 Vassar St Cambridge MA 02139 USA

ISBN: (纸本)9781450344937

This paper explores how fork-join parallelism, as supported by concurrency platforms such as Cilk and OpenMP, can be embedded into a compiler's intermediate representation (IR). Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations across parallel control constructs. Remedying this situation is generally thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir is a compiler IR that represents logically parallel tasks asymmetrically in the program's control flow graph. Tapir allows the compiler to optimize across parallel control constructs with only minor changes to its existing analyses and code transformations. To prototype Tapir in the LLVM compiler, for example, we added or modified about 6000 lines of LLVM's 4-million-line codebase. Tapir enables LLVM's existing compiler optimizations for serial code - including loop-invariant-code motion, common-subexpression elimination, and tail-recursion elimination - to work with parallel control constructs such as spawning and parallel loops. Tapir also supports parallel optimizations such as loop scheduling.

关键词： Cilk compiling control-flow graph fork-join parallelism LLVM multicore OpenMP optimization parallel computing serial semantics Tapir

来源：评论

学校读者我要写书评

暂无评论

An approach for non-intrusively adding malleable fork/join parallelism into ordinary JavaBean compliant applications

引用

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2010年第3期36卷 288-315页

作者： Mateos, Cristian Zunino, Alejandro Campo, Marcelo UNICEN Univ ISISTAN Res Inst Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina

Motivated by the advent of powerful hardware such as SMP machines and execution environments such as Grids, research in parallel programming has gained much attention within the distributed computing community. There is a substantial body of efforts in the form of parallel libraries and frameworks that supply developers with programming tools to exploit parallelism in their applications. Still, many of these efforts prioritize performance over other important characteristics such as code invasiveness, ease of use and independence of the underlying executing hardware/environment. In this paper, we present EasyFJP, a new approach for semi-automatically injecting parallelism into sequential Java applications that offers a convenient balance to these four aspects. EasyFJP is based upon the popular fork/join parallel pattern, and combines implicit, application-level parallelism with explicit, non-invasive application tuning. Experiments performed with several classic CPU-intensive benchmarks and a real-world application confirm that EasyFJP effectively addresses these problems while delivers very competitive performance. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Parallel computing fork-join parallelism Implicit parallelism Non-invasive tuning Java

来源：评论

学校读者我要写书评

暂无评论

PERFORMANCE ANALYSIS AND SCHEDULING OF STOCHASTIC fork-join JOBS IN A MULTICOMPUTER SYSTEM

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第10期4卷 1147-1164页

作者： KUMAR, A SHOREY, R IEEE Department of Electrical Communication Engineering Indian Institute of Science

We model a parallel processing system comprising several homogeneous computers interconnected by a communication network. Jobs arriving to this system have a linear fork-join structure. Each fork of the job gives rise to a random number of tasks that can be processed independently on any of the computers. Since exact analysis of fork-join models is known to be intractable, we resort to obtaining analytical bounds to the mean job response time of the fork-join job. For jobs with a single fork-join and, probabilistic allocation of tasks of the job to the N processors, we obtain upper and lower bounds to the mean job response time. Upper bounds are obtained using the concept of associated random variables and are found to be a good approximation to the mean job response time. A simple lower bound is obtained by neglecting queueing delays. We also find two lower bounds that include queueing delays. For multiple fork-join jobs, we study an approximation based on associated random variables. Finally, two versions of the join-the-Shortest-Queue (JSQ) allocation policy (i.e., JSQ by batch and JSQ by task) are studied and compared, via simulations and diffusion limits.

关键词： fork-join parallelism LOWER UPPER BOUNDS PERFORMANCE EVALUATION QUEUING MODELS STOCHASTIC SCHEDULING TASK ALLOCATION POLICIES

来源：评论

学校读者我要写书评

暂无评论

Region and effect inference for safe parallelism

引用

AUTOMATED SOFTWARE ENGINEERING 2019年第2期26卷 463-509页

作者： Tzannes, Alexandros Heumann, Stephen T. Eloussi, Lamyaa Vakilian, Mohsen Adve, Vikram S. Han, Michael Univ Illinois Champaign IL 61820 USA Autodesk Inc San Rafael CA USA

In this paper, we present the first full regions-and-effects inference algorithm for explicitly parallel fork-join programs. We infer annotations equivalent to those in Deterministic Parallel Java (DPJ) for type-safe C++ programs. We chose the DPJ annotations because they give the strongest safety guarantees of any existing concurrency-checking approach we know of, static or dynamic, and it is also the most expressive static checking system we know of that gives strong safety guarantees. This expressiveness, however, makes manual annotation difficult and tedious, which motivates the need for automatic inference, but it also makes the inference problem very challenging: the code may use region polymorphism, imperative updates with complex aliasing, arbitrary recursion, hierarchical region specifications, and wildcard elements to describe potentially infinite sets of regions. We express the inference as a constraint satisfaction problem and develop, implement, and evaluate an algorithm for solving it. The region and effect annotations inferred by the algorithm constitute a checkable proof of safe parallelism, and it can be recorded both for documentation and for fast and modular safety checking.

关键词： Safe parallelism Annotation inference fork-join parallelism

来源：评论

学校读者我要写书评

暂无评论

Staccato: shared-memory work-stealing task scheduler with cache-aware memory management

引用

INTERNATIONAL JOURNAL OF WEB AND GRID SERVICES 2019年第4期15卷 394-407页

作者： Kuchumov, Ruslan Sokolov, Andrey Korkhov, Vladimir St Petersburg State Univ 7-9 Univ Skaya Nab St Petersburg 199034 Russia RAS Karelian Res Ctr Inst Appl Math Res Petrozavodsk Russia St Petersburg State Univ Fac Appl Math & Control Proc 7-9 Univ Skaya Nab St Petersburg 199034 Russia

Work-stealing is one of the popular ways to schedule near-optimal task distribution across multiple CPU cores with low overheads on time, memory and inter-thread synchronisations. In the work-stealing strategy, workers that run out of tasks for execution start claiming tasks from other workers' queues. Double ended queues (deques) based on circular arrays proved to be an effective solution for such scenario. In this paper we investigate ways to improve performance of work-stealing schedulers based on deques by enhancing internal data handling mechanisms. Traditionally, deques are designed with an assumption that task pointers are stored within these data structures, while task objects reside in the heap memory. By modifying task queues so that they can hold task objects instead of pointers we managed to increase the performance more than 2.5 times on CPU-bound applications and decrease last-level cache misses up to 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

关键词： work-stealing scheduler work-stealing deques lock-free data structures cache locality fork-join parallelism

来源：评论

学校读者我要写书评

暂无评论

Distributed Continuation Stealing is More Scalable than You Might Think

Distributed Continuation Stealing is More Scalable than You ...

引用

IEEE International Conference on Cluster Computing (CLUSTER)

作者： Shiina, Shumpei Taura, Kenjiro Univ Tokyo Tokyo Japan

ISBN: (数字)9781665498562

ISBN: (纸本)9781665498562

The need for load balancing in applications with irregular parallelism has motivated research on work stealing. An important choice in work-stealing schedulers is between child stealing or continuation stealing. In child stealing, a newly created task is made stealable by other processors, whereas in continuation stealing, the caller's continuation is made stealable by executing the newly created task first, which preserves the serial execution order. Although the benefits of continuation stealing have been demonstrated on shared memory by Cilk and other runtime systems, it is rarely employed on distributed memory, presumably because it has been thought to be difficult to implement and inefficient as it involves migration of call stacks across nodes. Akiyama and Taura recently introduced efficient RDMA-based continuation stealing, but the practicality of distributed continuation stealing is still unclear because a comparison of its performance with that of child stealing has not previously been performed. This paper presents the results of a comparative performance analysis of continuation stealing and child stealing on distributed memory. To clarify the full potential of continuation stealing, we first investigated various RDMA-based synchronization (task join) implementations, which had not previously been fully investigated. The results revealed that, when the task synchronization pattern was complicated, continuation stealing performed better than child stealing despite its relatively long steal latency due to stack migration. Notably, our runtime system achieved almost perfect scaling on 110,592 cores in an unbalanced tree search (UTS) benchmark. This scalability is comparable to oreven better than that of state-of-the-art bag-of-tasks counterparts.

关键词： work stealing fork-join parallelism futures work-first scheduling task-based runtime systems RDMA

来源：评论

学校读者我要写书评

暂无评论

Accurate fork-join Profiling on the Java Virtual Machine 28th

Accurate Fork-Join Profiling on the Java Virtual Machine

引用

28th International Conference on Parallel and Distributed Computing (Euro-Par)

作者： Basso, Matteo Rosales, Eduardo Schiavio, Filippo Rosa, Andrea Binder, Walter Univ Svizzera Italiana USI Fac Informat Lugano Switzerland

ISBN: (纸本)9783031125973;9783031125966

The fork-join model for parallel computing has become very popular and is included in the Java class library since Java 7. While understanding and optimizing the performance of fork-join computations is of paramount importance, accurately profiling them on the Java Virtual Machine (JVM) is challenging due to the complexity of the API. In this paper, we present a novel model for analyzing fork-join computations on the JVM, addressing the peculiarities of the Java fork-join framework, including features such as task unforking and task reuse. We implement our model in a profiler that detects every spawned fork-join task, capturing all task dependencies and aiming at collecting cycle-accurate task-granularity data. We evaluate our profiler against a dedicated fork-join profiler for the JVM, showing that our tool achieves higher profile accuracy and introduces less overhead.

关键词： fork-join parallelism Work Stealing Accurate Profiling Task Granularity Task Dependencies Java

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：