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

31st International Conference on Parallel Processing (ICPP 2002)

作者： Hwang, GH Natl Taiwan Normal Univ Dept Informat & Comp Educ Taipei Taiwan

ISBN: (纸本)0769516807

In this paper, we present a new algorithm for computing the communication sets in array section movements with block-cyclic (cyclic(k) in HPF) distribution. Ourframework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed. We use formal proof and experimental results to show that it is more efficient than previous solution to the same problem. Another important contribution of this paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple(LCM) of block sizes is not a huge integer We demonstrate it by thorough complexity analyses and extensive experimental results.

关键词： HPF compiler distributed memory machines parallelizing compiler data parallel programs block-cyclic distributions

来源：评论

学校读者我要写书评

暂无评论

A technique to eliminate redundant inter-processor communication on parallelizing compiler TINPAR

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1999年第2期27卷 97-109页

作者： Kubota, A Tatsumi, S Tanaka, T Goshima, M Mori, S Nakashima, H Tomita, S Hiroshima City Univ Fac Informat Sci Hiroshima Japan Kyoto Univ Grad Sch Informat Kyoto Japan Toyota Technol Inst Dept Informat & Comp Sci Toyohashi Aichi Japan

Optimizing inter-processor(PE) communication is crucial for parallelizing compilers for message-passing parallel machines to achieve high performance. In this paper, we;propose a technique to eliminate redundant inter-PE messages. This technique utilizes data-flow analysis to find a definition point that corresponds to a use point where the definition and the use occur in different PEs. If several read accesses occurred in the same PE use the data defined at the same definition point in another PE, redundant inter-PE messages are eliminated as Follows: only one inter-PE communication is performed for the earliest read access and the previously received data are used for the following read. In order to guarantee the consistency of the data, a valid flag and a sent nag are provided for each chunk of received data. The control of these flags is equivalent to the coherence control by the self invalidation on a compiler aided cache coherence scheme.

关键词： parallelizing compiler message-passing multiprocessor dependence analysis data-flow analysis message coalescing

来源：评论

学校读者我要写书评

暂无评论

Using knowledge-based systems for research on parallelizing compilers

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2001年第3期13卷 181-208页

作者： Yang, CT Tseng, SS Fann, YW Tsai, TK Hsieh, MH Wu, CT Natl Space Program Off Ground Syst Sect Hsinchu 300 Taiwan Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 300 Taiwan

The main function of parallelizing compilers is to analyze sequential programs, in particular the loop structure, to detect hidden parallelism and automatically restructure sequential programs into parallel subtasks that are executed on a multiprocessor. This article describes the design and implementation of an efficient parallelizing compiler to parallelize loops and achieve high speedup rates on multiprocessor systems. It is well known that the execution efficiency of a loop can be enhanced if the loop is executed in parallel or partially parallel, such as in a DOALL or DOACROSS loop. This article also reviews a practical parallel loop detector (PPD) that is implemented in our PFPC on finding the parallelism in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by verifying array subscripts. In addition, a new model by using knowledge-based approach is proposed to exploit more loop parallelisms in this paper. The knowledge-based approach integrates existing loop transformations and loop scheduling algorithms to make good use of their ability to extract loop parallelisms. Two rule-based systems, called the KPLT and IPLS, are then developed using repertory grid analysis and attribute-ordering tables respectively, to construct the knowledge bases. These systems can choose an appropriate transform and loop schedule, and then apply the resulting methods to perform loop parallelization and obtain a high speedup rate. For example, the IPLS system can choose an appropriate loop schedule for running on multiprocessor systems. Finally, a runtime technique based on the inspector/executor scheme is proposed in this article for finding available parallelism on loops. Our inspector can determine the wavefronts of a loop with any complex indirected array-indexing pattern by building a DEF-USE table. The inspector is fully parallel without any synchronization. Experimental results show that the new method can resolve any complex data dependence patter

关键词： parallelizing compiler knowledge-based system loop parallelization multithreaded OS program restructuring

来源：评论

学校读者我要写书评

暂无评论

Array operation synthesis to optimize HPF programs on distributed memory machines

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2001年第4期61卷 467-500页

作者： Hwang, GH Lee, JK Ju, RDC Natl Chi Nan Univ Dept Informat Management Nantou Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan Intel Corp Microprocessor Res Labs Santa Clara CA 95052 USA

An increasing number of programming languages;such as Fortran 90, HPF, and APL, provide a rich set of intrinsic array functions and array expressions. These constructs, which constitute an important part of data parallel languages, provide excellent opportunities for compiler optimizations. The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time has been shown (A, T, Budd, ACM Trans. Programm. Lang, Syst. 6 (July 1984), 297-313;G. H. Hwang et al,, bz "Proc. of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, 1995," pp. 112-122) to be an effective scheme for optimizing programs on flat shared memory parallel architectures. It remains, however, to be studied how the synthesis scheme can be incorporated into optimizing HPF-like programs on distributed memory machines by taking into account communication costs. In this paper, we propose solutions to address this issue. We first show how to perform array operation synthesis on HPF programs, and we demonstrate its performance benefits on distributed memory machines with real applications. In addition, to prevent a situation we call "synthesis anomaly," we present an optimal solution to guide the array synthesis process on distributed memory machines. Due to the optimal problem being NP-hard, we further develop a practical strategy that compilers can use on distributed memory machines with HPF programs. Our synthesis engine is implemented as a Web-based tool, called Syntool, and experimental results show significant performance improvement over the base codes for HPF code fragments from real applications on parallel machines. Our experiments were performed on three distributed memory machines: an 8-node DEC Alpha Farm, a 16-node TBM SP-2, and a 16-node nCUBE/2. (C) 2001 Academic Press.

关键词： HPF compiler array operation synthesis distributed memory machines compiler optimization parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

The efficient computation of ownership sets in HPF

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2001年第8期12卷 769-788页

作者： Joisha, PG Banerjee, P Northwestern Univ Inst Technol Ctr Parallel & Distributed Comp Dept Elect & Comp Engn Evanston IL 60208 USA

Ownership sets are fundamental to the partitioning of program computations across processors by the owner-computes rule. These sets arise due to the mapping of arrays onto processors. In this paper, we focus on how ownership sets can be efficiently determined in the context of the HPF language and show how the structure of these sets can be symbolically characterized in the presence of arbitrary array alignment and array distribution directives. Our starting point is a system of equalities and inequalities due to Ancourt et al. [1] that captures the array mapping problem in HPF. We arrive at a refined system that enables us to efficiently solve for the ownership set using the Fourier-Motzkin Elimination technique and that requires the course vector as the only auxiliary vector. The formulation makes it possible to enumerate the elements of the ownership set exactly once, a feature that is very beneficial when such sets are applied to handle Do loops qualified by HPF's INDEPENDENT directive. We develop important and general properties pertaining to HPF alignments and distributions and show how they can be used to eliminate redundant communication due to array replication. Polynomial-time schemes that determine whether the ownership set of a particular processor, with respect to some array, is the empty set or whether the ownership set of every processor, with respect to some array, is the empty set, are presented. We show how distribution directives with unspecified processor meshes can be efficiently handled at compile time. We also show how to avoid the generation of communication code when pairs of array references are ultimately mapped onto the same processors. Experimental data demonstrating the improved code performance that the latter optimization enables is presented and discussed.

关键词： HPF array alignment array distribution ownership set Fourier-Motzkin Elimination technique parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Non-linear array data dependence test

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2001年第2期57卷 145-154页

作者： Huang, TC Yang, CM Natl Sun Yat Sen Univ Dept Elect Engn Kaohsiung 80424 Taiwan

Data dependence analysis is the most essential process while parallelizing a sequential program. Most current data dependence tests cannot handle array subscripts that are non-linear expressions. In this paper, we present a new parallelization algorithm, called non-linear array subscripts (NLA) test, to deal with non-linear or complex array subscripts. In this scheme, the iterations subject to loop-carried dependence are scheduled into different wavefronts, while the iterations with no loop-carried dependence are assigned into the same wavefront. Based on the wavefront information, the original loop is then transformed into parallel code. Our experimental results on shared-memory parallel machines HP SPP2000 and ALR Quad6 prove the high effectiveness of the NLA test. (C) 2001 Elsevier Science Inc. All rights reserved.

关键词： data dependence test non-linear array subscripts parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Time stamp algorithms for runtime parallelization of DOACROSS loops with dynamic dependences

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2001年第5期12卷 433-450页

作者： Xu, CZ Chaudhary, V Wayne State Univ Dept Elect & Comp Engn Detroit MI 48202 USA

This paper presents a time stamp algorithm for runtime parallelization of general DOACROSS loops that have indirect access patterns. The algorithm follows the INSPECTOR/EXECUTOR scheme and exploits parallelism at a fine-grained memory reference level. It features a parallel inspector and improves upon previous algorithms of the same generality by exploiting parallelism among consecutive reads of the same memory element. Two variants of the algorithm are considered: One allows partially concurrent reads (PCR) and the other allows fully concurrent reads (FCR). Analyses of their time complexities derive a necessary condition with respect to the iteration workload for runtime parallelization. Experimental results for a Gaussian elimination loop, as well as an extensive set of synthetic loops on a 12-way SMP server, show that the time stamp algorithms outperform iteration-level parallelization techniques in most test cases and gain speedups over sequential execution for loops that have heavy iteration workloads. The PCR algorithm performs best because it makes a better trade-off between maximizing the parallelism and minimizing the analysis overhead. For loops with light or unknown iteration loads, an alternative speculative runtime parallelization technique is preferred.

关键词： compiler parallelizing compiler runtime support inspector-executor doacross loop dynamic dependence

来源：评论

学校读者我要写书评

暂无评论

Implementing a dynamic processor allocation policy for multiprogrammed parallel applications in the Solaris™ operating system

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2001年第6期13卷 449-464页

作者： Yue, KK Lilja, DJ Univ Minnesota Minnesota Supercomp Inst Dept Elect & Comp Engn Minneapolis MN 55455 USA Sun Microsyst Inc Palo Alto CA 94303 USA

Parallel applications typically do not perform well in a multiprogrammed environment that uses time-sharing to allocate processor resources to the applications' parallel threads. Co-scheduling related parallel threads, or statically partitioning the system, often can reduce the applications' execution times, but at the expense of reducing the overall system utilization. To address this problem, there has been increasing interest in dynamically allocating processors to applications based on their resource demands and the dynamically varying system load. The Loop-Level Process Control (LLPC) policy (Yue K, Lilja D. Efficient execution of parallel applications in multiprogrammed multiprocessor systems. 10th International Parallel Processing Symposium, 1996;448-456) dynamically adjusts the number of threads an application is allowed to execute based on the application's available parallelism and the overall system load. This study demonstrates the feasibility of incorporating the LLPC strategy into an existing commercial operating system and parallelizing compiler and provides further evidence of the performance improvement that is possible using this dynamic allocation strategy. In this implementation, applications are automatically parallelized and enhanced with the appropriate LLPC hooks so that each application interacts with the modified version of the Solaris operating system. The parallelism of the applications are then dynamically adjusted automatically when they are executed in a multiprogrammed environment so that all applications obtain a fair share of the total processing resources. Copyright (C) 2001 John Wiley & Sons, Ltd.

关键词： multiprogramming process scheduling processor allocation operating system parallelizing compiler shared-memory multiprocessor performance measurement

来源：评论

学校读者我要写书评

暂无评论

PACWON: A parallelizing compiler for workstations on a network

引用

JOURNAL OF SYSTEMS ARCHITECTURE 1998年第2期45卷 157-176页

作者： Das, D Das, PP Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India

The current influx of networked workstations has prompted people to use this platform as a multiprocessing environment. In addition, tools like the Parallel Virtual Machine (PVM) has fuelled the growth even further. In this work we present the design and some possible future strategies for automatically parallelizing sequential programs using a compilation tool called PACWON for a network of workstations (NOW). The sequential programs are written using a subset of C - without pointers and structures. The target language is C embedded with PVM library calls. The automatically parallelized programs are run on a NOW environment. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compiler network of workstations parallel virtual machine clustering block graphs cloning

来源：评论

学校读者我要写书评

暂无评论

A model of parallelizing compiler on multithreading operating systems

引用

International Journal of Modelling and Simulation 1998年第1期18卷 9-15页

作者： Yang, Chao-Tung Tseng, Shian-Shyong Hsiao, Ming-Chang Dept. of Comp. and Info. Science National Chiao Tung University Hsinchu 300 Taiwan Switch Technology Laboratory Telecommunication Laboratories Min. of Transp. and Communications Taoyuan Taiwan Tung Hai University Taiwan National Chiao Tung University Taiwan Laboratory of Knowledge Engineering Prog. Lang. in Comp. and Info. Sci. National Chiao Tung University Taiwan ACM Taiwan Dept. of Comp. and Info. Science National Chiao Tung University Taiwan Computer Center Taiwan Dept. of Comp. and Info. Science Taiwan Computer Center Ministry of Education China IEEE Taiwan National Cheng Kung University Taiwan Switch Technology Laboratory Telecommunication Laboratories Min. of Transp. and Commun. ROC Taiwan

Multithreading support seems to be the most obvious approach for helping programmers to take the advantage of parallelism by operating systems. Although multithreading for a lot of multiprocessors is powerful, we sometimes still lack good parallelizing compilers to help programmers exploit parallelism and gain performance benefit. In this paper, a model of FORTRAN parallelizing compiler on multithreading OSF/1 is first proposed and then generalized to be useful hi constructing a parallelizing compiler for a particular language, to generate insight into the development of a high-performance parallelizing compiler.

关键词： Model Multithreading P Threads Parallelism parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：