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

INTEGER PROGRAMMING FOR ARRAY SUBSCRIPT ANALYSIS

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第6期6卷 662-668页

作者： SUBHLOK, J KENNEDY, K RICE UNIV DEPT COMP SCIHOUSTONTX 77251

We present a nevi method to determine whether a Convex region contains any integer points, The method is designed for array subscript analysis in parallel programs. The general problem is whether a system of linear equalities and inequalities has an integer solution,A set of known techniques is used to transform the problem to that of finding whether a convex region contains any integer points. The main result of the paper is a set of new search procedures that identify an integer solution in a convex region, or prove that no integer solutions exist. They are based on the geometrical properties of convex regions that are not empty, but also do not contain any integer points. The results contribute to exact and efficient dependence and synchronization analysis of parallel programs.

关键词： SUBSCRIPT ANALYSIS DEPENDENCE TESTING INTEGER PROGRAMMING parallelizing compilers PARALLEL PROGRAM ANALYSIS SYNCHRONIZATION ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

A computation plus communication load balanced loop partitioning method for distributed memory systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1999年第3期58卷 515-545页

作者： Pande, S Bali, T Univ Cincinnati Dept ECECS Compiler Res Lab Cincinnati OH 45221 USA

Due to a significant communication overhead of sending and receiving data, the loop partitioning approaches on distributed memory systems must guarantee not just the computation load balance but computation + communication load balance. The previous approaches in loop partitioning have achieved a communication-free. computation load balanced iteration space partitioning solution for a limited subset of DOALL loops. But a large category of DOALL loops inevitably result in communication and the tradeoffs between computation and communication must be carefully analyzed for these loops in order to balance out the combined computation time and communication overheads. In this work, we describe a partitioning approach based on the above motivation for the general cases of DOALL loops. Our goal is to achieve a computation + communication load balanced partitioning through static data and iteration space distribution. Our approach first performs partitioning of iteration and data spaces of a loop nest by analyzing communication and parallelism;it then performs architecture-dependent analysis to adjust the granularity of partitions. load balance each partition with respect to total computation + communication, and then performs mapping of partitions onto the available number of processors. This multiphase partitioning method works as follows. First, the code partitioning phase analyzes the references in the body of the DOALL loop nest and determines a set of directions for reducing a larger degree of communication by trading a lesser degree of parallelism. The partitioning is carried out in the iteration space of the loop by cyclically following a set of direction vectors such that the data references are maximally localized and reused, eliminating a larger communication volume than parallelism. We then perform data space partitioning based on a new larger partition owns rule to minimize the communication overhead for a compute intensive partition by localizing its reference

关键词： parallelizing compilers distributed memory systems data partitioning communication optimizations loop partitioning and scheduling

来源：评论

学校读者我要写书评

暂无评论

Exploitation of parallelism to nested loops with dependence cycles

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2004年第12期50卷 729-742页

作者： Chang, WL Chu, CP Ho, M So Taiwan Univ Technol Dept Informat Management Tainan 710 Taiwan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

In this paper, we analyze the recurrences from the breakability of the dependence links formed in general multi-statements in a nested loop. The major findings include: (1) A sink variable renaming technique, which can reposition an undesired anti-dependence and/or output-dependence link, is capable of breaking an anti-dependence and/or output-dependence link. (2) For recurrences connected by only true dependences, a dynamic dependence concept and the derived technique are powerful in terms of parallelism exploitation. (3) By the employment of global dependence testing, link-breaking strategy, Tarjan's depth-first search algorithm, and a topological sorting, an algorithm for resolving a general multi-statement recurrence in a nested loop is proposed. Experiments with benchmark cited from Vector loops showed that among 134 subroutines tested, 3 had their parallelism exploitation amended by our proposed method. That is, our offered algorithm increased the rate of parallelism exploitation of Vector loops by approximately 2.24%. (C) 2004 Published by Elsevier B.V.

关键词： parallelizing compilers vectorizing compilers loop optimization data dependence analysis dependence cycle parallelism exploitation

来源：评论

学校读者我要写书评

暂无评论

Eliminating synchronization bottlenecks using adaptive replication

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2003年第3期25卷 316-359页

作者： Rinard, MC Diniz, PC MIT Comp Sci Lab Cambridge MA 02139 USA Univ So Calif ISI Marina Del Rey CA 90202 USA

This article presents a new technique, adaptive replication, for automatically eliminating synchronization bottlenecks in multithreaded programs that perform atomic operations on objects. Synchronization bottlenecks occur when multiple threads attempt to concurrently update the same object. It is often possible to eliminate synchronization bottlenecks by replicating objects. Each thread can then update its own local replica without synchronization and without interacting with other threads. When the computation needs to access the original object, it combines the replicas to produce the correct values in the original object. One potential problem is that eagerly replicating all objects may lead to performance degradation and excessive memory consumption. Adaptive replication eliminates unnecessary replication by dynamically detecting contention at each object to find and replicate only those objects that would otherwise cause synchronization bottlenecks. We have implemented adaptive replication in the context of a parallelizing compiler for a subset of C++. Given an unannotated sequential program written in C++, the compiler automatically extracts the concurrency, determines when it is legal to apply adaptive replication, and generates parallel code that uses adaptive replication to efficiently eliminate synchronization bottlenecks. In addition to automatic parallelization and adaptive replication, our compiler also implements a lock coarsening transformation that increases the granularity at which the computation locks objects. The advantage is a reduction in the frequency with which the computation acquires and releases locks;the potential disadvantage is the introduction of new synchronization bottlenecks caused by increases in the sizes of the critical sections. Because the adaptive replication transformation takes place at lock acquisition sites, there is a synergistic interaction between lock coarsening and adaptive replication. Lock coarsening drives down the

关键词： algorithms experimentation performance atomic operations commutativity analysis parallel computing parallelizing compilers replication synchronization

来源：评论

学校读者我要写书评

暂无评论

Compiler-based tools for analyzing parallel programs

引用

PARALLEL COMPUTING 1998年第3-4期24卷 401-420页

作者： Armstrong, B Kim, SW Park, I Voss, M Eigenmann, R Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

In this paper, we present several tools for analyzing parallel programs. The tools are built on top of a compiler infrastructure, which provides advanced capabilities for symbolic program analysis and manipulation. The tools can display characteristics of a program and relate this information to data gathered from instrumented program runs and other performance analysis tools. They also support an interactive compilation scenario, giving the user feedback on how the compilation process performed and how to improve it. We will present case studies demonstrating the tool use. These include the characterization of an industrial application and the study of new compiler techniques and portable parallel languages. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers parallel programming tools integrated tools program characterization performance analysis

来源：评论

学校读者我要写书评

暂无评论

Automatically partitioning threads for multithreaded architectures

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1999年第2期58卷 159-189页

作者： Tang, XA Gao, GR Univ Delaware Dept Elect & Comp Engn Newark DE 19716 USA

There is an enormous amount of parallelism exposed to fine-grain multithreaded architectures to cover latencies. It is a demanding task for a multi-threading programmer to manage such a degree of parallelism by hand. To use multithreaded architectures efficiently it is essential to have compiler support for automatically partitioning: programs into threads. This paper solves a fundamental problem in compiling for multithreaded architectures, automatically partitioning a program into threads. The focus of such partitioning is to overlap the remote communication latency and minimize the total execution time. We first formulate the partitioning problem based on a multithreaded execution cost model. Then, we prove such a formulation is NP-hard. Therefore, we propose two heuristic thread-partitioning methods to solve this problem in practice. The advanced partitioning algorithm is a novel extension of list scheduling, and it takes advantage of the cost model to generate near-optimum partitioning results. The remote-path-based partitioning algorithm is a simplified version of the advanced one but it is easy for compiler implementation. The two partitioning algorithms were implemented respectively in a thread partitioning testbed and a research EARTH-C compiler. The experimental results show that both partitioning algorithms are effective to generate efficient threaded code, and code generated by the compiler is comparable to hand-written code. (C) 1999 Academic Press.

关键词： thread partitioning thread scheduling multithreaded compilers multithreaded architectures parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Tiling nested loops into maximal rectangular blocks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1996年第2期35卷 123-132页

作者： Chen, YS Wang, SD Wang, CM NATL TAIWAN UNIV DEPT ELECT ENGNTAIPEI 106TAIWAN ACAD SINICA INST INFORMAT SCITAIPEI 115TAIWAN

In this paper, an approach to thing nested loops for maximizing parallelism is proposed, The proposed method aims at aggregating independent computations of a loop nest into rectangular blocks and maximizing the block sizes for maximizing parallelism, At first, all the independent computations that can be executed in the first time unit are identified. These computations are called the initially independent computations, Then it is shown that all of them can be collected as a union of rectangular blocks, So, based on these, the entire iteration space of the loops is partitioned into rectangular blocks for maximizing parallelism, The proposed method is formulated as systematic procedures which can easily be implemented in a parallelizing compiler, It is shown that when the wavefront transformation is combined with the proposed method, the loops can always be tiled so that the tile size is greater than one. In comparison with previous work on thing, the proposed method is shown to have several advantages as summarized in the conclusions of this paper. (C) 1996 Academic Press, Inc.

关键词： Uniform dependencies Transformation Algorithms Rectangular Synclitism Unit of time algorithms parallelizing compilers parallelism Thing Blocks

来源：评论

学校读者我要写书评

暂无评论

Program analysis techniques for transforming programs for parallel execution

引用

PARALLEL COMPUTING 2002年第3期28卷 455-469页

作者： Psarris, K Univ Texas Dept Comp Sci San Antonio TX 78249 USA

In a multiple processor system, computer programs have to be redesigned to efficiently use the parallel processors and deliver higher performance. One major approach is automatic detection of parallelism, in which existing conventional sequential programs are translated into parallel programs, in order to benefit from the presence of multiple processors. Optimizing compilers rely upon pro-ram analysis techniques to detect data dependences between program statements, The results of the analysis enable the compiler to identify code fragments that can be executed in parallel. The proposed dependence analysis techniques fall into two different categories: either efficient and approximate tests or exact but exponential. In this paper, we show that exact data dependence information can be computed efficiently in practice. The Banerjee inequality and the GCD test are the two tests traditionally used to determine statement data dependence in automatic parallelization of loops, These tests are approximate in the sense that they are necessary but not sufficient conditions for data dependence. In an earlier work we formally studied the accuracy of the Banerjee and GCD tests and derived a set of conditions that can be tested along with the Banerjee inequality and the GCD test to obtain exact data dependence information. In this work, we perform an empirical study to explain and demonstrate the accuracy of the Banerjee and GCD tests in actual practice. Our experiments indicate that exact data dependence information can be computed in linear time in practice. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers data dependence program analysis automatic parallelization compiles optimization

来源：评论

学校读者我要写书评

暂无评论

Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 1999年第2期17卷 89-132页

作者： Diniz, PC Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA MIT Comp Sci Lab Boston MA 02139 USA

This article presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code;each Version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical land unrealizable) optimal algorithm that uses the best policy at every point during the execution.

关键词： parallel computing parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

A framework for efficient data redistribution on distributed memory multicomputers

引用

JOURNAL OF SUPERCOMPUTING 2001年第3期20卷 243-265页

作者： Guo, MY Nakata, I Univ Aizu Dept Comp Software Aizu Wakamatsu Fukushima Japan Hosei Univ Fac Comp & Informat Sci Tokyo Japan

Array redistribution is required often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution;otherwise the performance of the programs will degrade considerably. The redistribution overheads consist of two parts: index computation and inter-processor communication. In this paper, by using a notation for the local data description called an LDD, we propose a framework to optimize the array redistribution algorithm both in index computation and inter-processor communication. That is, our work makes an effort to optimize not only the computation cost but also communication cost for array redistribution algorithms. We present an efficient index computation method and generate a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. Some experiments show the efficiency and flexibility of our techniques.

关键词： parallelizing compilers HPF array redistribution communication scheduling distributed memory machines

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：