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

Generating communication sets of array assignment statements for block-cyclic distribution on distributed memory parallel computers

引用

PARALLEL COMPUTING 2002年第9期28卷 1329-1368页

作者： Lee, P Chen, WY Acad Sinica Inst Sci Informat Taipei Taiwan

This paper is concerned with the design of efficient algorithms for generating global name-pace communication sets based on execution of array assignment statements for arbitrary strides and block sizes on distributed-memory parallel computers. We will present a hybrid approach, which combines the advantages of the set-theoretic method and the integer lattice method for generating communication sets. When block sizes are extremely small or large, a cyclic-based or a row-wise set-theoretic method is used. For other cases when block sizes are medium, we propose a new integer lattice method, in which data in each local block are treated as a unit. The first virtual referenced element in each virtual referenced local block can be generated efficiently by using an integer lattice method, in which the left boundary of index domain in each processing element is extended for this purpose. Then, the physical referenced elements in each physical referenced local block can be determined by the intersection of two closed forms, whose result is also a closed form. Because the cost of generating indices for packing and unpacking messages at the sending and receiving ends may be expensive for certain cases, we also study the conventional communication model and the deposit communication model. As each of the proposed algorithms and the communication models has its special use for certain cases, we thus identify rules of thumb to decide the most suitable algorithm for dealing with general cases. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： array assignment statements communication sets distributed-memory machines global name space integer lattice method parallelizing compilers set-theoretic method

来源：评论

学校读者我要写书评

暂无评论

An exact data dependence testing method for quadratic expressions

引用

INFORMATION SCIENCES 2007年第23期177卷 5316-5328页

作者： Wu, Jia-Hwa Chu, Chih-Ping Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Optimizing compilers relies on program analysis techniques to detect data dependence between program statements. Data dependence testing is a basic step in detecting loop-level parallelism in numerical program. Most studies indicate that data dependence tests cannot handle nonlinear-expression array subscripts. This study presents an exact dependence test that can handle quadratic expression array subscripts precisely. The proposed method detects whether a quadratic equation is monotonically increasing or decreasing, and then reduces the integer solution interval of each variable by repeated projection. When the effective solution interval for any variable shrinks to empty, no integer solutions exist for this quadratic equation;otherwise, all integer solutions can be found, implying that parallelism of a loop can be exploited. (C) 2007 Elsevier Inc. All rights reserved.

关键词： dependence test parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

SYNCHRONIZATION AND COMMUNICATION COSTS OF LOOP PARTITIONING ON SHARED-MEMORY MULTIPROCESSOR SYSTEMS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第4期3卷 505-512页

作者： GUPTA, R Department of Computer Science University of Pittsburgh Pittsburgh PA USA

To exploit loop level parallelism on shared memory multiprocessor systems, loops are decomposed and their execution scheduled on different processors in parallel. This paper presents strategies for static loop decomposition and scheduling as well as compiler assisted run-time scheduling that take into account, in addition to the cost of performing operations, the overhead costs associated with a decomposition and schedule. An algorithm for static decomposition of multidimensional loops based upon the operation execution costs, communication costs, and synchronization costs is discussed. Following the decomposition of a program, synchronization instructions are introduced to ensure correct program execution. An algorithm for determining the explicit synchronization instructions that should be introduced in a program to ensure correct execution of the program with arbitrarily nested loops is presented. Techniques for reducing run-time scheduling, communication and synchronization costs due to self scheduling, a compiler assisted run-time scheduling technique, of multidimensional loops are also presented. Experiments performed on the Encore multiprocessor system demonstrate that the techniques developed can reduce overhead costs.

关键词： COMMUNICATION parallelizing compilers PROGRAM DECOMPOSITION RUN-TIME SCHEDULING SHARED MEMORY MULTIPROCESSOR SYSTEMS SYNCHRONIZATION

来源：评论

学校读者我要写书评

暂无评论

Dependence analysis with direction vector for array references

引用

COMPUTERS & ELECTRICAL ENGINEERING 2001年第5期27卷 375-393页

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

We presented a new scheme for exact data dependence analysis, called interval reduction (IR) test in J. Sys. Software [2000;52(1):55-65]. This scheme reduces the solution interval of each constraint variable in the dependence equation by repeated projection. Once the effective solution interval of any constraint variable shrinks to empty, this linear diophantine equation contains no integer solution and the memory accesses subject to this constraint are then independent. Otherwise, all the integer solutions can be enumerated. IR test is an efficient and exact data dependence test method. In the original presentation, only general dependence is considered. If there exists a dependence, we do not care what the direction vector is. In this paper, we extend the IR test to check the data dependence subject to an arbitrary direction vector. Experimental results are presented to show its effectiveness compared to the omega test and power test. (C) 2001 Elsevier Science Ltd. All rights reserved.

关键词： array references data dependence analysis direction vector interval reduction test linear diophantine equation parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Non-strict independence-based program parallelization using sharing and freeness information

引用

THEORETICAL COMPUTER SCIENCE 2009年第46期410卷 4704-4723页

作者： Gras, Daniel Cabeza Hermenegildo, Manuel V. Univ Politecn Madrid Fac Informat E-28040 Madrid Spain

The current ubiquity of multi-core processors has brought renewed interest in program parallelization. Logic programs allow studying the parallelization of programs with complex, dynamic data structures with (declarative) pointers in a comparatively simple semantic setting. In this context, automatic parallelizers which exploit and-parallelism rely on notions of independence in order to ensure certain efficiency properties. "Non-strict" independence is a more relaxed notion than the traditional notion of "strict" independence which still ensures the relevant efficiency properties and can allow considerable more parallelism. Non-strict independence cannot be determined solely at run-time ("a priori") and thus global analysis is a requirement. However, extracting non-strict independence information from available analyses and domains is non-trivial. This paper provides on one hand an extended presentation of our classic techniques for compile-time detection of non-strict independence based on extracting information from (abstract interpretation-based) analyses using the now well understood and popular Sharing + Freeness domain. This includes algorithms for combined compile-time/run-time detection which involve special run-time checks for this type of parallelism. In addition, we propose herein novel annotation (parallelization) algorithms, URLP and CRLP, which are specially suited to non-strict independence. We also propose new ways of using the Sharing + Freeness information to optimize how the run-time environments of goals are kept apart during parallel execution. Finally. we also describe the implementation of these techniques in our parallelizing compiler and recall some early performance results. We provide as well an extended description of our pictorial representation of sharing and freeness information. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Parallelism Automatic parallelization Abstract interpretation Abstract domains Sharing and freeness Non-strict independence parallelizing compilers Declarative languages Logic programming

来源：评论

学校读者我要写书评

暂无评论

Optimizing irregular HPF applications using halos

引用

CONCURRENCY-PRACTICE AND EXPERIENCE 2000年第2-3期12卷 137-155页

作者： Benkner, S NEC Europe Ltd C&C Res Labs D-53757 St Augustin Germany

This paper presents extensions of High Performance Fortran (HPF) for specifying non-local access patterns of distributed arrays, called halos, and for controlling communication associated with these non-local accesses. Using these features, crucial optimization techniques required for an efficient parallelization of irregular applications may be applied. The information provided by halos is utilized by the compiler and the runtime system for optimizing the management of distributed arrays and the computation of communication schedules. High-level communication primitives for halos enable the programmer to avoid redundant communication, to reuse communication schedules, and to hide communication overheads by overlapping communication with computation. Performance results of a kernel from a crash simulation application on the NEC Cenju-4, the IBM SP2, and on the NEC SX-4 demonstrate that by using the proposed extensions, a performance close to handwritten message-passing codes can he achieved for irregular problems. Copyright (C) 2000 John Wiley & Sons, Ltd.

关键词： irregular applications data distribution parallelizing compilers runtime parallelization High Performance Fortran language extensions

来源：评论

学校读者我要写书评

暂无评论

PARTITIONING AND MAPPING NESTED LOOPS ON MULTIPROCESSOR SYSTEMS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1991年第4期2卷 430-439页

作者： SHEU, JP TAI, TH Department of Electrical Engineering National Central University Chungli Taiwan

Intensive scientific algorithms can usually be formulated as nested loops which are the main source of parallelism. When a nested loop is executed in parallel, the total execution time is composed of two parts-the computation time and the communication time. For a message-passing multiprocessor system, performance declines rapidly as the communication overhead is higher than the corresponding computation. In this paper, a method for parallel executing nested loops with constant loop-carried dependencies on message-passing multiprocessor systems to reduce the communication overhead is presented. First, we partition the nested loop into blocks which result in little communication without concern for the topology of machines. For a given linear time transformation found by the hyperplane method, the iterations of a nested loop are partitioned into blocks such that the communication among the blocks is reduced while the execution ordering defined by the time transformation is not perturbed. Then, the partitioned blocks generated by the partitioning method are mapped onto multiprocessor systems according to the specific properties of various machines. We propose a heuristic mapping algorithm for the hypercube machines.

关键词： HYPERCUBES HYPERPLANE METHOD MESSAGE-PASSING MULTIPROCESSOR SYSTEMS parallelizing compilers SYSTOLIC ARRAYS WAVE-FRONT METHOD

来源：评论

学校读者我要写书评

暂无评论

Parallel molecular dynamics in a parallelizing SML compiler

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2003年第9期E86D卷 1569-1576页

作者： Scaife, N Hayashi, R Horiguchi, S Grad. School of Information Science JAIST Ishikawa-ken 923-1292 Japan

We have constructed a parallelizing compiler for Standard ML (SML) based upon algorithmic skeletons [3]. We present an implementation of a Parallel Molecular Dynamics (PMD) simulation in order to compare our functional approach with a traditional imperative approach. Although we present performance data, the principal benefits from our approach are in the modularity of the code and the ease of programming. Extant FORTRAN90 code for an O(N-2) algorithm is translated, firstly into imperative SML and then into purely functional SML which is then parallelized. The ease of programming and the performance of the FORTRAN90 and SML code are compared. Modest parallel performance is obtained from the parallel SML but with a much slower sequential execution time compared to the FORTRAN90. We then improve the implementation with a ring topology implementation which gives much closer performance to the FORTRAN90 implementation.

关键词： parallelizing compilers standard ML FORTRAN90 parallel molecular dynamics

来源：评论

学校读者我要写书评

暂无评论

Contention-free communication scheduling for array redistribution

引用

PARALLEL COMPUTING 2000年第10期26卷 1325-1343页

作者： Guo, MY Nakata, I Yamashita, Y Univ Tsukuba Inst Informat Sci & Elect Tsukuba Ibaraki 3050006 Japan Univ Lib & Informat Sci Tsukuba Ibaraki 3058550 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 may degrade considerably. The redistribution overheads consist of two parts: index computation and interprocessor communication. If there is no communication scheduling in a redistribution algorithm, the communication contention may occur, which increases the communication waiting time. In order to solve this problem, in this paper, we propose a technique to schedule the communication so that it becomes contention-free, Our approach initially generates a communication table to represent the communication relations among sending nodes and receiving nodes. According to the communication table, we then generate another table named communication scheduling table. Each column of communication scheduling table is a permutation of receiving node numbers in each communication step. Thus the communications in our redistribution algorithm are contention-free. Our approach can deal with multi-dimensional "shape changing redistribution". (C) 2000 Elsevier Science B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

HIERARCHICAL COMPILATION OF MACRO DATA-FLOW GRAPHS FOR MULTIPROCESSORS WITH LOCAL MEMORY

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第7期5卷 720-736页

作者： PRASANNA, GNS AGARWAL, A MUSICUS, BR MIT COMP SCI LABCAMBRIDGEMA 02139 MIT ELECTR RES LABCAMBRIDGEMA 02139

This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macro operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loops, where the precedence constraints between the loops are known, can be viewed as macro dataflow graphs. The hierarchical compilation approach comprises a processor allocation phase followed by a partitioning phase. In the processor allocation phase, using estimated speedup functions for the macro nodes, computationally efficient techniques establish the sequencing and parallelism of macro operations for close-to-optimal run-times. The second phase partitions the computations in each macro node to maximize communication locality for the level of parallelism determined by the processor allocation phase. The same approach can also be used for programs consisting of multiple-loop nests, when each of the nested loops can be characterized by a speedup function. These ideas have been implemented in a prototype structure-driven compiler, SDC, for expressions of matrix operations. The paper presents the performance of the compiler for several matrix expressions on a simulator of the Alewife multiprocessor.

关键词： PARALLEL PROCESSING PARALLEL COMPILATION parallelizing compilers COMMUNICATION LOCALITY TASK SCHEDULING DISTRIBUTED-MEMORY MULTIPROCESSORS CACHE-COHERENT MULTIPROCESSORS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：