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

Efficient interprocedural array data-flow analysis for automatic program parallelization

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2000年第3期26卷 244-261页

作者： Gu, JJ Li, ZY Sun Microsyst Inc Palo Alto CA 94303 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Since sequential languages such as Fortran and C are more machine-independent than current parallel languages, it is highly desirable to develop powerful parallelization-tools which can generate parallel codes, automatically or semiautomatically, targeting different parallel architectures. Array data-flow analysis is known to be crucial to the success of automatic parallelization. Such an analysis should be performed interprocedurally and symbolically and it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if not carefully designed. How to enhance the efficiency of this analysis to a practical level remains an issue largely untouched to date. This paper presents techniques for efficient interprocedural array data-flow analysis and documents experimental results of its implementation in a research parallelizing compiler. Our techniques are based on guarded array regions and the resulting tool runs faster, by one or two orders of magnitude, than other similarly powerful tools.

关键词： parallelizing compiler array data-flow analysis interprocedural analysis symbolic analysis

来源：评论

学校读者我要写书评

暂无评论

Revisiting communication code generation algorithms for message-passing systems

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2006年第5期21卷 323-344页

作者： Ferner, Clayton Univ N Carolina Dept Comp Sci 601 S Coll Rd Wilmington NC 28403 USA

In this paper, we investigate algorithms for generating communication code to run on distributed-memory systems. We modify algorithms from previously published work and prove that the algorithms produce correct code. We then extend these algorithms to incorporate the mapping of virtual to physical processors and prove the correctness of this extension. This technique can reduce the number of interprocessor messages. In the examples that we show, the total number of messages was reduced from O(N-2) to O(P-2), where N is the input size and P is the number of physical processors. The reason that it is important to revisit communication code generation and to introduce a formal specification of the incorporation of mapping in the communication code generation is so that we can make use of the many scheduling heuristics proposed in the literature. We need a generalized mapping function so that we can apply different mapping and scheduling heuristics proposed in the literature for each input program, therefore improving the average performance.

关键词： parallelizing compiler Parallel computation Distributed-memory Message-passing Mapping Code generation

来源：评论

学校读者我要写书评

暂无评论

An overlapping task assignment scheme for hierarchical coarse-grain task parallel processing

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2006年第11期18卷 1335-1351页

作者： Yoshida, Akimasa Toho Univ Dept Informat Sci Chiba 2748510 Japan

This paper proposes an overlapping task assignment scheme for the hierarchical coarse-grain task parallel processing on multiprocessor systems. In coarse-grain task parallel processing, the compiler extracts parallelism among coarse-grain tasks automatically and the coarse-grain tasks are assigned to processor clusters at runtime. However, several programs may decrease the processor-cluster utilization factor owing to lack of parallelism inside each coarse-grain task. Therefore, in order to improve the processor-cluster utilization factor, this paper proposes the execution scheme with overlapping task assignment whose dynamic scheduler can assign several coarse-grain tasks to a processor cluster simultaneously. Also, the performance evaluations by simulations and executions on SMP showed that the proposed scheme could reduce the execution time remarkably. Copyright (c) 2006 John Wiley & Sons, Ltd.

关键词： parallelizing compiler coarse-grain parallelism dynamic scheduling SMP overlapping assignment task graph

来源：评论

学校读者我要写书评

暂无评论

A practical run-time technique for exploiting loop-level parallelism

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2000年第3期54卷 259-271页

作者： Huang, TC Hsu, PH Natl Sun Yat Sen Univ Dept Elect Engn Kaohsiung 804 Taiwan

In order to exploit potential parallelism of loops, in which the array access patterns cannot be analyzed at compile-time, parallelizing compilers must rely on the run-time dependence analysis techniques. The LRPD test is noted in this field for its applicability. It assumes full parallelism and executes speculatively, then examines the correctness of parallel execution after loop termination. We extended the concept and developed a practical run-time technique, called the speculative parallelization with new technology (SPNT) test, to further exploit loop-level parallelism. Two main characteristics make the SPNT test distinguished. The first is improving the success rate of speculative parallelization by eliminating all cross-iteration data dependences except the cross-processory flow dependences. The second is reducing the failure penalty by aborting the speculative parallel execution immediately once a cross-processor flow dependence is detected during the execution. Our experimental results on shared-memory parallel machines lip SPP2000 and ALR QUAD6 prove the high effectiveness of the SPNT test. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： parallelizing compiler data dependence analysis run-time technique speculative parallelization inspector/executor

来源：评论

学校读者我要写书评

暂无评论

EXTENSIONS TO CYCLE SHRINKING

引用

INTERNATIONAL JOURNAL OF HIGH SPEED COMPUTING 1995年第2期7卷 265-284页

作者： SETHI, A BISWAS, S SANYAL, A INDIAN INST TECHNOL DEPT COMP SCI & ENGNBOMBAY 400076MAHARASHTRAINDIA

An important part of a parallelizing compiler is the restructuring phase, which extracts parallelism from a sequential program. We consider an important restructuring transformation called cycle shrinking [5], which partitions the iteration space of a loop so that the iterations within each group of the partition can be executed in parallel. The method in [5] mainly deals with dependences with constant distances. In this paper, we propose certain extensions to the cycle shrinking transformation. For dependences with constant distances, we present an algorithm which, under certain fairly general conditions, partitions the iteration space in a minimal number of groups. Under such conditions, our method is optimal while the previous methods are not. We have also proposed an algorithm to handle a large class of loops which have dependences with variable distances. This problem is considerably harder and has not been considered before in full generality.

关键词： parallelizing compiler RESTRUCTURING TRANSFORMATIONS DEPENDENCE DISTANCES CYCLE SHRINKING

来源：评论

学校读者我要写书评

暂无评论

Communication optimization on automatic program parallelization

Communication optimization on automatic program parallelizat...

引用

8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing/3rd ACIS International Workshop on Self-Assembling Wireless Networks

作者： Dong Chun-Li Zhao Rong-Cai Ma Zhuo-Jie Li Dong-Hong Natl Digital Switching Syst Engn & Technol Res Ct Zhengzhou 450002 Peoples R China

ISBN: (纸本)9780769529097

Minimizing communication by increasing the locality of data references is an important optimization for achieving high performance on distributed memory machines. But in the progress of decomposition, reorganization is inevitable. And the communication produced by reorganization is inevitable too. In this paper, the authors present a linear decomposition algorithm that automatically finding computation and data decomposition, including finding data and computations decomposition that has data reorganization communication. And the authors improve the method and reduce the communication cost by merging parallel regions with the same data decomposition.

关键词： parallelizing compiler MPI data reorganization parallel region merging data decomposition computation decomposition

来源：评论

学校读者我要写书评

暂无评论

An overview of the APC compiler for distributed memory machines

An overview of the APC compiler for distributed memory machi...

引用

International Conference on Parallel and Distributed Processing Techniques and Applications

作者： Zotov, S Institute for Microprocessors Russian Academy of Sciences Moscow 117997 GSP-7 Block 1 Nahimovski prosp. 36 Russian Federation

ISBN: (纸本)1892512459

The APC compiler provides automatic parallelization of sequential FORTRAN77 programs for efficient execution on distributed memory machines. It performs source to source transformation making one-dimensional block data partitioning and loops distribution decisions, reduction recognition and I/O statements processing. APC consists of the two main components: Analyzer and Partitioner. Analyzer is used as a platform to parse the source program into an intermediate representation and to perform useful analysis and transformations. Partitioner makes all the decisions about data partitioning, loops distributions and program modification. A special Parallelization Interface component was designed to adapt Analyzer for the task of automatic parallelization of sequential programs. This paper presents a technique that is used to automatically parallelize sequential programs and describes Parallelization Interface to Analyzer which provides Partitioner with objects affecting parallelization and dependencies between the objects. The paper also presents first results obtained on Fortran77 tests. Though significant work remains to optimize the algorithms presented in this article, preliminary results lead us to believe APC will generate efficient code for a large class of data-parallel programs.

关键词： Automatic dynamic data partitioning parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Pattern-based Automatic Parallelization of Representative-based Clustering Algorithms 5

Pattern-based Automatic Parallelization of Representative-ba...

引用

5th IEEE International Conference on Data Science and Advanced Analytics (IEEE DSAA)

作者： Islam, Saiyedul Balasubramaniam, Sundar Gupta, Shruti Brajesh, Shikhar Badlani, Rohan Labhishetty, Nitin Baid, Abhinav Goyal, Poonam Goyal, Navneet Birla Inst Technol & Sci Pilani Dept Comp Sci & Informat Syst Adv Data Analyt & Parallel Technol Lab Pilani Campus Pilani Rajasthan India BITS Pilani Pilani Rajasthan India

ISBN: (纸本)9781538650905

Ease of programming and optimal parallel performance have historically been on the opposite side of a tradeoff, forcing the user to choose. With the advent of the Big Data era and rapid evolution of sequential algorithms, the data analytics community can no longer afford the tradeoff. We observed that several clustering algorithms often share common traits-particularly, algorithms belonging to same class of clustering exhibit significant overlap in processing steps. Here, we present our observation on domain patterns in Representative-based clustering algorithms and how they manifest as clearly identifiable programming patterns when mapped to a Domain Specific Language (DSL). We have integrated the signatures of these patterns in the DSL compiler for parallelism identification and automatic parallel code generation. Our experiments on different state-of-the-art parallelization frameworks shows that our system is able to achieve near-optimal speedup while requiring a fraction of the programming effort, making it an ideal choice for the data analytics community.

关键词： Clustering Domain Specific Language parallelizing compiler High Performance Computing Programming Patterns

来源：评论

学校读者我要写书评

暂无评论

OSCAR API for Real-Time Low-Power Multicores and Its Performance on Multicores and SMP Servers

OSCAR API for Real-Time Low-Power Multicores and Its Perform...

引用

22nd International Workshop on Languages and compilers for Parallel Computing

作者： Kimura, Keiji Mase, Masayoshi Mikami, Hiroki Miyamoto, Takamichi Shirako, Jun Kasahara, Hironori Waseda Univ Dept Comp Sci & Engn Shinjuku Ku Tokyo Japan

ISBN: (纸本)9783642133732

OSCAR (Optimally Scheduled Advanced Multiprocessor) API has been designed for real-time embedded low-power multicores to generate parallel programs for various multicores from different vendors by using the OSCAR parallelizing compiler. The OSCAR API has been developed by Waseda University in collaboration with Fujitsu Laboratory, Hitachi, NEC, Panasonic, Renesas Technology, and Toshiba in an METI/NEDO project entitled "Multicore Technology for Realtime Consumer Electronics." By using the OSCAR API as an interface between the OSCAR compiler and backend compilers, the OSCAR compiler enables hierarchical multigrain parallel processing with memory optimization under capacity restriction for cache memory, local memory, distributed shared memory, and on-chip/off-chip shared memory;data transfer using a DMA controller;and power reduction control using DVFS (Dynamic Voltage and Frequency Scaling), clock gating, and power gating for various embedded multicores. In addition, a parallelized program automatically generated by the OSCAR, compiler with OSCAR API can be compiled by the ordinary OpenMP compilers since the OSCAR API is designed on a subset of the OpenMP. This paper describes the OSCAR API and its compatibility with the OSCAR compiler by showing code examples. Performance evaluations of the OSCAR compiler and the OSCAR. API are carried out using an IBM Power5+ workstation, an IBM Power6 high-end SMP server, and a newly developed consumer electronics multicore chip RP2 by Renesas, Hitachi and Waseda. From the results of scalability evaluation, it is found that on an average, the OSCAR compiler with the OSCAR API can exploit 5.8 times speedup over the sequential execution on the Power5+ workstation with eight cores and 2.9 times speedup on RP2 with four cores, respectively. In addition, the OSCAR compiler can accelerate an IBM XL Fortran compiler up to 3.3 times on the Power6 SMP server. Due to low-power optimization on RP2, the OSCAR compiler with the OSCAR API achie

关键词： Multicore API parallelizing compiler Power Reduction

来源：评论

学校读者我要写书评

暂无评论

A Polyhedral Compilation Framework for Loops with Dynamic Data-Dependent Bounds 2018

A Polyhedral Compilation Framework for Loops with Dynamic Da...

引用

27th International Conference on compiler Construction (CC)

作者： Zhao, Jie Kruse, Michael Cohen, Albert Ecole Normale Super INRIA Paris France Ecole Normale Super DI Paris France

ISBN: (纸本)9781450356442

We study the parallelizing compilation and loop nest optimization of an important class of programs where counted loops have a dynamic data-dependent upper bound. Such loops are amenable to a wider set of transformations than general while loops with inductively defined termination conditions: for example, the substitution of closed forms for induction variables remains applicable, removing the loop-carried data dependences induced by termination conditions. We propose an automatic compilation approach to parallelize and optimize dynamic counted loops. Our approach relies on affine relations only, as implemented in state-of-the-art polyhedral libraries. Revisiting a state-of-the-art framework to parallelize arbitrary while loops, we introduce additional control dependences on data-dependent predicates. Our method goes beyond the state of the art in fully automating the process, specializing the code generation algorithm to the case of dynamic counted loops and avoiding the introduction of spurious loop-carried dependences. We conduct experiments on representative irregular computations, from dynamic programming, computer vision and finite element methods to sparse matrix linear algebra. We validate that the method is applicable to general affine transformations for locality optimization, vectorization and parallelization.

关键词： parallelizing compiler loop nest optimization polyhedral model dynamic counted loop

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：