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

optimistic parallelization support for event stream processing systems

Optimistic parallelization support for event stream processi...

5th Middleware Doctoral Symposium, MDS'08, Co-located with ACM/IFIP/USENIX 9th International Middleware Conference, Middleware 2008

作者： Brito, Andrey Systems Engineering Group TU Dresden Germany

ISBN: (纸本)9781605583617

Event stream applications consist of an acyclic graph of components that are traversed by streams of events. Examples of operations in such components are filtering, aggregation, enrichment, and transformation of events and, commonly, applications include a mix of common-use library functions and user-defined functions. When the operation only depends on the current input events, the component can be trivially parallelized by replication. However, if the component keeps state that is used for the computation of the results, the trivial parallelization approach does not work. Parallel versions for common components have being designed, but complex or user-defined components are normally limited by single thread performance. In this work, we use optimistic parallelization approaches to harness the potential of multi-core processors to scale the performance of stateful operators in event stream applications. In addition, we investigate indulgent ways to allow the user to provide application knowledge that can improve the amount of useful speculative work. The current prototype shows considerable gain in throughput even though some speculative executions must be disregarded. Copyright 2008 ACM.

关键词： event stream processing optimistic parallelization software transactional memory

来源：评论

学校读者我要写书评

暂无评论

Processor Allocation for optimistic parallelization of Irregular Programs 1

引用

12th International Conference on Computational Science and Its Applications (ICCSA)

作者： Versaci, Francesco Pingali, Keshav Univ Padua TU Wien I-35100AOGJ Padua Italy Univ Texas Austin Austin TX USA

ISBN: (数字)9783642311253

ISBN: (纸本)9783642311246;9783642311253

optimistic parallelization is a promising approach for the parallelization of irregular algorithms: potentially interfering tasks are launched dynamically, and the runtime system detects conflicts between concurrent activities, aborting and rolling back conflicting tasks. However, parallelism in irregular algorithms is very complex. In a regular algorithm like dense matrix multiplication, the amount of parallelism can usually be expressed as a function of the problem size, so it is reasonably straightforward to determine how many processors should be allocated to execute a regular algorithm of a certain size (this is called the processor allocation problem). In contrast, parallelism in irregular algorithms can be a function of input parameters, and the amount of parallelism can vary dramatically during the execution of the irregular algorithm. Therefore, the processor allocation problem for irregular algorithms is very difficult. In this paper, we describe the first systematic strategy for addressing this problem. Our approach is based on a construct called the conflict graph, which (i) provides insight into the amount of parallelism that can be extracted from an irregular algorithm, and (ii) can be used to address the processor allocation problem for irregular algorithms. We show that this problem is related to a generalization of the unfriendly seating problem and, by extending Turan's theorem, we obtain a worst-case class of problems for optimistic parallelization, which we use to derive a lower bound on the exploitable parallelism. Finally, using some theoretically derived properties and some experimental facts, we design a quick and stable control strategy for solving the processor allocation problem heuristically.

关键词： Irregular algorithms optimistic parallelization Automatic parallelization Amorphous data-parallelism Processor allocation Unfriendly seating Turan's theorem

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Processor Allocation for optimistic parallelization of Irregular Programs 11

Brief Announcement: Processor Allocation for Optimistic Para...

引用

23rd Annual Symposium on Parallelism in Algorithms and Architectures

作者： Versaci, Francesco Pingali, Keshav Univ Padua Dept Informat Engn I-35100 Padua Italy

ISBN: (纸本)9781450307437

关键词： Irregular algorithms optimistic parallelization Amorphous data-parallelism Processor allocation Turan's theorem

来源：评论

学校读者我要写书评

暂无评论

Using the Xeon Phi Platform to Run Speculatively-Parallelized Codes

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2017年第2期45卷 225-241页

作者： Estebanez, Alvaro Llanos, Diego R. Gonzalez-Escribano, Arturo Univ Valladolid Dept Informat Campus M Delibes Valladolid 47011 Spain

Intel Xeon Phi accelerators are one of the newest devices used in the field of parallel computing. However, there are comparatively few studies concerning their performance when using most of the existing parallelization techniques. One of them is thread-level speculation, a technique that optimistically tries to extract parallelism of loops without the need of a compile-time analysis that guarantees that the loop can be executed in parallel. In this article we evaluate the performance delivered by an Intel Xeon Phi coprocessor when using a software, state-of-the-art thread-level speculative parallelization library in the execution of well-known benchmarks. We describe both the internal characteristics of the Xeon Phi platform and the particularities of the thread-level speculation library being used as benchmark. Our results show that, although the Xeon Phi delivers a relatively good speedup in comparison with a shared-memory architecture in terms of scalability, the relatively low computing power of its computational units when specific vectorization and SIMD instructions are not fully exploited makes this first generation of Xeon Phi architectures not competitive (in terms of absolute performance) with respect to conventional multicore systems for the execution of speculatively parallelized code.

关键词： Thread-level speculation Speculative parallelization optimistic parallelization Xeon Phi

来源：评论

学校读者我要写书评

暂无评论

An OpenMP Extension that Supports Thread-Level Speculation

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2016年第1期27卷 78-91页

作者： Aldea, Sergio Estebanez, Alvaro Llanos, Diego R. Gonzalez-Escribano, Arturo Univ Valladolid Dept Informat Campus Miguel Delibes E-47011 Valladolid Spain

OpenMP directives are the de-facto standard for shared-memory parallel programming. However, OpenMP does not guarantee the correctness of the parallel execution of a given loop if runtime data dependences arise. Consequently, many highly-parallel regions cannot be safely parallelized with OpenMP due to the possibility of a dependence violation. In this paper, we propose to augment OpenMP capabilities, by adding thread-level speculation (TLS) support. Our contribution is threefold. First, we have defined a new speculative clause for variables inside parallel loops. This clause ensures that all accesses to these variables will be carried out according to sequential semantics. Second, we have created a new, software-based TLS runtime library to ensure correctness in the parallel execution of OpenMP loops that include speculative variables. Third, we have developed a new GCC plugin, which seamlessly translates our OpenMP speculative clause into calls to our TLS runtime engine. The result is the ATLaS C Compiler framework, which takes advantage of TLS techniques to expand OpenMP functionalities, and guarantees the sequential semantics of any parallelized loop.

关键词： Parallelism and concurrency code generation thread-level speculation optimistic parallelization

来源：评论

学校读者我要写书评

暂无评论

Squashing Alternatives for Software-Based Speculative parallelization

引用

IEEE TRANSACTIONS ON COMPUTERS 2014年第7期63卷 1826-1839页

作者： Garcia Yagueez, Alvaro Llanos, Diego R. Gonzalez-Escribano, Arturo Univ Valladolid Dept Informat ETS Informat E-47011 Valladolid Spain

Speculative parallelization is a runtime technique that optimistically executes sequential code in parallel, checking that no dependence violations arise. In the case of a dependence violation, all mechanisms proposed so far either switch to sequential execution, or conservatively stop and restart the offending thread and all its successors, potentially discarding work that does not depend on this particular violation. In this work we systematically explore the design space of solutions for this problem, proposing a new mechanism that reduces the number of threads that should be restarted when a data dependence violation is found. Our new solution, called exclusive squashing, keeps track of inter-thread dependencies at runtime, selectively stopping and restarting offending threads, together with all threads that have consumed data from them. We have compared this new approach with existent solutions on a real system, executing different applications with loops that are not analyzable at compile time and present as much as 10% of inter-thread dependence violations at runtime. Our experimental results show a relative performance improvement of up to 14%, together with a reduction of one-third of the numbers of squashed threads. The speculative parallelization scheme and benchmarks described in this paper are available under request.

关键词： Thread-level speculation optimistic parallelization loop-based parallelization

来源：评论

学校读者我要写书评

暂无评论

A Shape Analysis for Optimizing Parallel Graph Programs 11

A Shape Analysis for Optimizing Parallel Graph Programs

引用

38th Symposium on Principles of Programming Languages

作者： Prountzos, Dimitrios Manevich, Roman Pingali, Keshav McKinley, Kathryn S. Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781450304900

Computations on unstructured graphs are challenging to parallelize because dependences in the underlying algorithms are usually complex functions of runtime data values, thwarting static parallelization. One promising general-purpose parallelization strategy for these algorithms is optimistic parallelization. This paper identifies the optimization of optimistically parallelized graph programs a:: a new application area, and develops the first shape analysis for addressing this problem. Our shape analysis identifies failsafe points in the program after which the execution is guaranteed not to abort and backup copies of modified data are not needed;additionally, the analysis can be used to eliminate redundant conflict checking. It uses two key ideas: a novel top-down heap abstraction that controls state space explosion, and a strategy for predicate discovery that exploits common patterns of data structure usage. We implemented the shape analysis in TVLA, and used it to optimize benchmarks from the Lonestar suite. The optimized programs were executed on the Galois system. The analysis was successful in eliminating all costs related to rollback logging for our benchmarks. Additionally, it reduced the number of lock acquisitions by a factor ranging from 10x to 50x, depending on the application and the number of threads. These optimizations were effective in reducing the running times of the benchmarks by factors of 2x to 12 x

关键词： Abstract Interpretation Compiler Optimization Concurrency Parallelism Shape Analysis Static Analysis Amorphous Data-parallelism Irregular Programs optimistic parallelization Synchronization Overheads Cautious Operators

来源：评论

学校读者我要写书评

暂无评论

Elixir: A System for Synthesizing Concurrent Graph Programs 12

Elixir: A System for Synthesizing Concurrent Graph Programs

引用

ACM International Conference on Object Oriented Programming Systems Languages and Applications

作者： Prountzos, Dimitrios Manevich, Roman Pingali, Keshav Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450315616

Algorithms in new application areas like machine learning and network analysis use "irregular" data structures such as graphs, trees and sets. Writing efficient parallel code in these problem domains is very challenging because it requires the programmer to make many choices: a given problem can usually be solved by several algorithms, each algorithm may have many implementations, and the best choice of algorithm and implementation can depend not only on the characteristics of the parallel platform but also on properties of the input data such as the structure of the graph. One solution is to permit the application programmer to experiment with different algorithms and implementations without writing every variant from scratch. Auto-tuning to find the best variant is a more ambitious solution. These solutions require a system for automatically producing efficient parallel implementations from high-level specifications. Elixir, the system described in this paper, is the first step towards this ambitious goal. Application programmers write specifications that consist of an operator, which describes the computations to be performed, and a schedule for performing these computations. Elixir uses sophisticated inference techniques to produce efficient parallel code from such specifications. We used Elixir to automatically generate many parallel implementations for three irregular problems: breadth-first search, single source shortest path, and betweenness-centrality computation. Our experiments show that the best generated variants can be competitive with handwritten code for these problems from other research groups;for some inputs, they even outperform the handwritten versions.

关键词： Algorithms Languages Performance Verification Synthesis Compiler Optimization Concurrency Parallelism Amorphous Data-parallelism Irregular Programs optimistic parallelization

来源：评论

学校读者我要写书评

暂无评论

Structure-driven Optimizations for Amorphous Data-parallel Programs

Structure-driven Optimizations for Amorphous Data-parallel P...

引用

15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Mendez-Lojo, Mario Nguyen, Donald Prountzos, Dimitrios Sui, Xin Hassaan, M. Amber Kulkarni, Milind Burtscher, Martin Pingali, Keshav Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA

ISBN: (纸本)9781605587080

Irregular algorithms are organized around pointer-based data structures such as graphs and trees, and they are ubiquitous in applications. Recent work by the Galois project has provided a systematic approach for parallelizing irregular applications based on the idea of optimistic or speculative execution of programs. However, the overhead of optimistic parallel execution can be substantial. In this paper, we show that many irregular algorithms have structure that can be exploited and present three key optimizations that take advantage of algorithmic structure to reduce speculative overheads. We describe the implementation of these optimizations in the Galois system and present experimental results to demonstrate their benefits. To the best of our knowledge, this is the first system to exploit algorithmic structure to optimize the execution of irregular programs.

关键词： Amorphous Data-parallelism Irregular Programs optimistic parallelization Synchronization Overheads Cautious Operator Implementations One-shot Optimization Iteration Coalescing

来源：评论

学校读者我要写书评

暂无评论

Towards a Science of Parallel Programming 10

Towards a Science of Parallel Programming

引用

19th International Conference on Parallel Architectures and Compilation Techniques

作者： Pingali, Keshav Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

How do we give parallel programming a more scientific foundation? In this talk, I will discuss the approach we are taking in the Galois project.

ISBN: (纸本)9781450301787

How do we give parallel programming a more scientific foundation? In this talk, I will discuss the approach we are taking in the Galois project.

关键词： Irregular algorithms Graph computations Operator Formulation of Algorithms Amorphous Data-parallelism optimistic parallelization Multicore processors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：