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

Parallelism Detection Using Graph Labelling

LOBACHEVSKII JOURNAL OF MATHEMATICS 2022年第10期43卷 2893-2900页

作者： Telegin, P. N. Baranov, A. V. Shabanov, B. M. Tikhomirov, A. I. Russian Acad Sci Joint Supercomp Ctr Branch Fed State Inst Sci Res Inst Syst Anal Moscow 119334 Russia

Usage of multiprocessor and multicore computers implies parallel programming. Tools for preparing parallel programs include parallel languages and libraries as well as parallelizing compilers and convertors that can perform automatic parallelization. The basic approach for parallelism detection is analysis of data dependencies and properties of program components, including data use and predicates. In this article a suite of used data and predicates sets for program components is proposed and an algorithm for computing these sets is suggested. The algorithm is based on wave propagation on graphs with cycles and labelling. This method allows analysing complex program components, improving data localization and thus providing enhanced data parallelism detection.

关键词： parallel programming program parallelization graph wave algorithm graph labelling.

来源：评论

学校读者我要写书评

暂无评论

LLVM based approach to static analysis of C programs in SAPFOR

LLVM based approach to static analysis of C programs in SAPF...

引用

Ivannikov Memorial Workshop (IVMEM)

作者： Kataev, Nikita RAS Keldysh Inst Appl Math Moscow Russia

ISBN: (纸本)9781538676905

Heterogeneous computational systems are becoming very popular nowadays. However, developing efficient parallel programs, that can exploit the potential parallelism of these systems, still remains difficult for most of application programmers. program parallelization may require significant transformation of the original program. SAPFOR (System FOR Automated parallelization) aims to simplify the development of parallel programs of scientific-technical calculations. It was designed to perform source-to-source transformation of a sequential program for execution on heterogeneous computational systems. This paper discusses the implementation of program analysis in SAPFOR. The presented approach relies on LLVM (Low Level Virtual Machine) capabilities to examine a program. SAPFOR explores the properties of low-level program representation to recognize related properties of the program in programming language. Some kind of IR-level transformations may be applied without any loss of analysis accuracy. Furthermore, these transformations allow us to increase the quality of program analysis.

关键词： program analysis program parallelization source-to-source transformation LLVM SAPFOR

来源：评论

学校读者我要写书评

暂无评论

MicroSpec: Speculation-Centric Fine-Grained parallelization for FSM Computations 16

MicroSpec: Speculation-Centric Fine-Grained Parallelization ...

引用

International Conference on Parallel Architectures and Compilation (PACT)

作者： Qiu, Junqiao Zhao, Zhijia Ren, Bin Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Coll William & Mary Dept Comp Sci Williamsburg VA 23187 USA

ISBN: (纸本)9781450341219

Finite state machines (FSMs) are basic computation models that play essential roles in many applications. Enabling efficient parallel FSM execution is critical to the performance of these applications. However, they are very challenging to parallelize due to their inherent data dependencies that occur at each step of computations. Existing efforts on FSM parallelization either explore coarse-grained speculative parallelism or leverage parallel prefix-sum. The former ignores prevalent fine-grained hardware parallelism on modern processors (such as ILP or SIMD par-allelism) while the latter limits the benefits of fine-grained parallelism mainly to state enumeration. This work presents MicroSpec, a set of parallelization techniques that, for the first time, expose fine-grained speculative parallelism to FSM computations. Based on a rigorous analysis of three types of parallelism at fine-grained level, MicroSpec consists of a list of four fine-grained speculative parallelization approaches along with a speculation-oriented data transformation. Experiments on a large set of real-world FSM bench-marks show that MicroSpec achieves substantial performance improvement over the state-of-the-art.

关键词： program parallelization Finite State Machine FSM SIMD Speculative parallelization Vectorization

来源：评论

学校读者我要写书评

暂无评论

Communication-aware parallelization Strategies for High Performance Applications

Communication-aware Parallelization Strategies for High Perf...

引用

IEEE-Computer-Society Annual Symposium on VLSI (ISVLSI)

作者： Ashraf, Imran Bertels, Koen Khammassi, Nader Le Lann, Jean-Christophe Delft Univ Technol Comp Engn Lab Delft Netherlands ENSTA Bretagne LabSTICC UMR CNRS 6285 Brest France

ISBN: (纸本)9781479987191

With the advent of multicore processor architectures and the existence of a huge legacy code base, the need for efficient and scalable parallelizing compilers is growing. Where multi-core processors were seen as the way forward to address the known challenges such as the memory, power and ILP wall, efficient parallelization to make use of the multiple cores, is still an open issue. In this paper, we present two complementary tools, MCROF and XPU which provide an alternative development path to parallelise applications and that address the challenges of identifying potential parallelism and exploiting it in a different way. The MCROF tool provides a detailed profile of the data flowing inside an application and the XPU programming paradigm provides an intuitive and simple interface to express parallelism as well as the necessary runtime support. We demonstrate through two different use cases that better performance up to 4x can be achieved than available commercial compilers.

关键词： Data-communication profiling program parallelization Multicore Parallel programming

来源：评论

学校读者我要写书评

暂无评论

Effective Transactional Memory Execution Management for Improved Concurrency

引用

ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 2014年第3期11卷 23-49页

作者： Gonzalez-Mesa, M. A. Gutierrez, Eladio Zapata, Emilio L. Plata, Oscar Univ Malaga Dept Comp Architecture E-29071 Malaga Spain

This article describes a transactional memory execution model intended to exploit maximum parallelism from sequential and multithreaded programs. A program code section is partitioned into chunks that will be mapped onto threads and executed transactionally. These transactions run concurrently and out of order, trying to exploit maximum parallelism but managed by a specific fully distributed commit control to meet data dependencies. To accomplish correct parallel execution, a partial precedence order relation is derived from the program code section and/or defined by the programmer. When a conflict between chunks is eagerly detected, the precedence order relation is used to determine the best policy to solve the conflict that preserves the precedence order while maximizing concurrency. The model defines a new transactional state called executed but not committed. This state allows exploiting concurrency on two levels: intrathread and interthread. Intrathread concurrency is improved by having pending uncommitted transactions while executing a new one in the same thread. The new state improves interthread concurrency because it permits out-of-order transaction commits regarding the precedence order. Our model has been implemented in a lightweight software transactional memory system, TinySTM, and has been evaluated on a set of benchmarks obtaining an important performance improvement over the baseline TM system.

关键词： Design Experimentation Performance Transactional memory concurrency exploitation dependence analysis optimistic concurrency program parallelization

来源：评论

学校读者我要写书评

暂无评论

Lightweight Fault Detection in Parallelized programs

Lightweight Fault Detection in Parallelized Programs

引用

11th IEEE/ACM International Symposium on Code Generation and Optimization (CGO)

作者： Tan, Li Feng, Min Gupta, Rajiv Univ Calif Riverside CSE Dept Riverside CA 92521 USA NEC Lab Amer Princeton NJ USA

ISBN: (纸本)9781467355254;9781467355247

A popular approach for producing parallel software is to develop a sequential version of an application and then incrementally introduce parallel constructs to parallelize different parts of the application. During the parallelization process, programming errors may be introduced, causing concurrency bugs. In this paper we develop a technique for runtime detection of data dependence faults (i.e., data races and atomicity violations) introduced during parallelization. By leveraging the availability of two versions of the program, the sequential one and the parallelized one, we comparison check dynamic data dependences exercised during executions of the two versions to identify faults. To reduce the cost of comparison checking we develop three optimizations. The first optimization causes only a subset of dynamically exercised data dependences to be comparison checked. The second optimization shows that not all instances of a dynamically exercised data dependence need to be comparison checked. The third optimization shows that static analysis of parallelizing constructs can be exploited to eliminate the need for executing the parallelized version altogether. In addition, our solution is applicable when different program executions on the same input may follow different execution paths, it is effective in situations where the fault introduced manifests itself rarely during execution, and it is also effective in pinpointing the location of the fault in the program. We implemented and evaluated our approach using ten benchmarks. The experimental results indicate an average slowdown of 3x to perform fault detection.

关键词： program parallelization debugging dependence violation data races atomicity violations

来源：评论

学校读者我要写书评

暂无评论

Exploiting Application Data-Parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2009年第2期17卷 234-247页

作者： Banerjee, Sudarshan Bozorgzadeh, Elaheh Dutt, Nikil Univ Calif Irvine Ctr Embedded Comp Syst Irvine CA 92697 USA

Partial dynamic reconfiguration, often called run-time reconfiguration (RTR), is a key feature in modern reconfigurable platforms. In this paper, we present parallelism granularity selection (PARLGRAN), an application map in approach that maximizes performance of application task chains on architectures with such capability. PARLGRAN essentially selects a suitable granularity of data-parallelism for individual data parallel tasks while considering key issues such as significant reconfiguration overhead and placement constraints. It integrates granularity selection very effectively in a joint scheduling and placement formulation, necessary due to constraints imposed by partial RTR. As a key step to validating PARLGRAN, we additionally present an exact strategy (integer linear programming formulation). We demonstrate that PARLGRAN generates high-quality schedules with: 1) a set of small test cases where we compare our results with the exact strategy;2) a very large set of synthetic experiments with over a thousand data-points where we compare it with a simpler strategy that tries to statically maximize data-parallelism, i.e., only considers resource availability;and 3) a detailed application case study of JPEG encoding. The application case-study confirms that blindly maximizing data-parallelism can result in schedules even worse than that generated by a simple (but RTR-aware) approach oblivious to data-parallelism. Last, but very important, we demonstrate that our approach is well-suited for true on-demand computing with detailed execution time estimates on a typical embedded processor. Heuristic execution time is comparable to task execution time, i.e., it is feasible to integrate PARLGRAN in a run-time scheduler for dynamically reconfigurable architectures.

关键词： Dynamic reconfiguration program parallelization

来源：评论

学校读者我要写书评

暂无评论

Modeling Optimistic Concurrency using Quantitative Dependence Analysis 08

Modeling Optimistic Concurrency using Quantitative Dependenc...

引用

ACM SIGPLAN Symposium on Principles and Practice of Parallel programming (PPoPP 08)

作者： von Praun, Christoph Bordawekar, Rajesh Cascaval, Calin IBM Research Yorktown Heights NY USA

ISBN: (纸本)9781595939609

This work presents a quantitative approach to analyze parallelization opportunities in programs with irregular memory access where potential data dependences mask available parallelism. The model captures data and causal dependencies among critical sections as algorithmic properties and quantifies them as a density computed over the number of executed instructions. The model abstracts from runtime aspects such as scheduling, the number of threads, and concurrency control used in a particular parallelization. We illustrate the model on several applications requiring ordered and unordered execution of critical sections. We describe a run-time tool that computes the dependence densities from a deterministic single-threaded program execution. This density metric provides insights into the potential for optimistic parallelization, opportunities for algorithmic scheduling, and performance defects due to synchronization bottlenecks. Based on the results of our analysis, we classify applications into three categories with low, medium, and high dependence densities. Applications with low dependence density are naturally good candidates for optimistic concurrency, applications with medium density may require a scheduler that is aware of the algorithmic dependencies for optimistic concurrency to be effective, and applications with high dependence density may not be suitable for parallelization.

关键词： available parallelism dependence analysis dependence density implicit parallelism optimistic concurrency program parallelization transactional memory

来源：评论

学校读者我要写书评

暂无评论

Implicit Parallelism with Ordered Transactions 07

Implicit Parallelism with Ordered Transactions

引用

ACM SIGPLAN Symposium on Principles and Practice of Parallel programming

作者： von Praun, Christoph Ceze, Luis Cascaval, Calin IBM Research Yorktown Heights NY University of Illinois at Urbana-Champaign Urbana-Champaign IL

ISBN: (纸本)9781595936028

Implicit Parallelism with Ordered Transactions (IPOT) is all extension of sequential or explicitly parallel programming models to support speculative parallelization. The key idea is to specify opportunities for parallelization in a sequential program using annotations similar to transactions. Unlike explicit parallelism, IPOT annotations do not require the absence of data dependence, since the parallelization relies oil runtime support for speculative execution. IPOT as a parallel programming model is determinate, i.e., program semantics are independent of the thread scheduling. For optimization, non-determinism can be introduced selectively. We describe the programming model of IPOT and an online tool that recommends boundaries of ordered transactions by observing a sequential execution. On three example HPC workloads we demonstrate that Our method is effective in identifying opportunities for fine-grain parallelization. Using the automated task recommendation tool, we were able to perform the parallelization of each program within a few hours.

关键词： parallel programming program parallelization implicit parallelism thread-level speculation transactional memory ordered transactions

来源：评论

学校读者我要写书评

暂无评论

Abstract specialization and its applications

引用

ACM SIGPLAN NOTICES 2003年第10期38卷 269-283页

作者： Puebla, G Hermenegildo, M Tech Univ Madrid UPM Dept Comp Sci Madrid Spain Univ New Mexico Dept CS & E & C Engn Albuquerque NM 87131 USA

The aim of program specialization is to optimize programs by exploiting certain knowledge about the context in which the program will execute. There exist many program manipulation techniques which allow specializing the program in different ways. Among them, one of the best known techniques is partial evaluation, often referred to simply as program specialization, which optimizes programs by specializing them for (partially) known input data. In this work we describe abstract specialization, a technique whose main features are: (1) specialization is performed with respect to "abstract" values rather than "concrete" ones, and (2) abstract interpretation rather than standard interpretation of the program is used in order to propagate information about execution states. The concept of abstract specialization is at the heart of the specialization system in CiaoPP, the Ciao system preprocessor. In this paper we present a unifying view of the different specialization techniques used in CiaoPP and discuss their potential applications by means of examples. The applications discussed include program parallelization, optimization of dynamic scheduling (concurrency), and integration of partial evaluation techniques.

关键词： languages performance theory abstract interpretation program specialization partial evaluation program optimization program parallelization logic programming static analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：