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

Data-localization scheduling inside processor-cluster for multigrain parallel processing

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1997年第4期E80D卷 473-479页

作者： Yoshida, A Koshizuka, K Ogata, W Kasahara, H Department of Electrical Electronics and Computer Engineering Waseda University Tokyo 169 Japan

This paper proposes a data-localization scheduling scheme inside a processor-cluster for multigrain parallel processing, which hierarchically exploits parallelism among coarse-grain tasks like loops, medium-grain tasks like loop iterations and near-fine-grain tasks like statements. The proposed scheme assigns near-fine-grain or medium-grain tasks inside coarse-grain tasks onto processors inside a processor-cluster so that maximum parallelism can be exploited and inter-processor data transfer can be minimum after data-localization for coarse-grain tasks across processor-clusters. Performance evaluation on a multiprocessor system OSCAR shows that multigrain parallel processing with the proposed data-localization scheduling can reduce execution time for application programs by 10% compared with multigrain parallel processing without data-localization.

关键词： task scheduling data-localization automatic data decomposition multigrain parallel processing parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of a communication-efficient data-parallel program compiling system

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2001年第5期17卷 825-839页

作者： Shih, KP Lai, CY Sheu, JP Tseng, YC Tamkang Univ Dept Comp Sci & Informat Engn Taipei 251 Taiwan Natl Cent Univ Dept Comp Sci & Informat Engn Tao Yuan 320 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan

In this paper, we present the design and implementation of a data-parallel compiling system. The system has been implemented on a DEC Alpha 3000 workstation and incorporated into a parallel programming environment called UPPER (User-interactive Parallel Programming EnviRonment). Given an HPF program, the built-in compiler system can automatically analyze the access pattern of the HPF program, enumerate the computation and communication sets, and then generate the SPMD code for execution on nCUBE/2. Moreover, the user interface is designed to help the programmer to capture some information during the compilation and execution phases, including interprocessor communication, distribution of data elements onto processors, and execution results.

关键词： communication sets distributed-memory multicomputers high performance Fortran (HPF) parallelizing compilers single program multiple data (SPMD)

来源：评论

学校读者我要写书评

暂无评论

Compiling array references with affine functions for data-parallel programs

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 1998年第4期14卷 695-723页

作者： Wei, WH Shih, KP Sheu, JP Natl Cent Univ Dept Comp Sci & Informat Engn Chungli 320 Taiwan

An important research topic is parallelizing of compilers to generate local memory access sequences and communication sets while compiling a data-parallel language into an SPMD (Single Program Multiple Data) program. In this paper, we present a scheme to efficiently enumerate local memory access sequences and to evaluate communication sets. We use a class table to store information that is extracted from array sections and data distribution patterns. Given array references and data distributions, we can utilize the class table to generate communication sets in closed forms. Furthermore, we derive the algorithms for sending and receiving necessary data between processors. An algorithm for generating the class table is presented, and the time complexity of this algorithm is O(s), where s is the array section stride. The technique of generating communication sets for one index variable has been implemented on a DEC Alpha 3000 workstation. The experimental results confirm the advantage of our scheme, especially when the array section stride is larger than the block size. Finally, we adapt our approach to handle array references with multiple index variables. The time complexity for constructing the whole class table is O(s(2)).

关键词： communication set data-parallel language distributed memory multicomputers HPF parallelizing compilers SPMD

来源：评论

学校读者我要写书评

暂无评论

Efficient loop partitioning for parallel codes of irregular scientific computations

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2003年第9期E86D卷 1825-1834页

作者： Guo, MY Univ Aizu Dept Comp Software Aizu Wakamatsu 9658580 Japan

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

关键词： parallelizing compilers irregular scientific application communication optimization owner computes rule loop partitioning distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

Enhanced look-ahead scheduling technique to overlap communication with computation

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1998年第11期E81D卷 1205-1212页

作者： Li, DC Iwahori, Y Hayashi, T Ishii, N Nagoya Inst Technol Educ Ctr Informat Proc Nagoya Aichi 4668555 Japan

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

关键词： parallelizing compilers interprocessor communication program optimization compile-time scheduling heuristics directed acyclic graphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

PROPERTIES OF SIMULATED ANNEALING AND GENETIC ALGORITHMS FOR MAPPING DATA TO MULTICOMPUTERS

引用

Parallel Algorithms and Applications 1997年第4期12卷 279-296页

作者： Nashat Mansour[a] Jalal Kawash[a] Hassan Diab[b] [a] Lebanese American University Computer Science Program Beirut Lebanon [b] American University of Beirut Electrical Engineering Dept. Beirut Lebanon

We experimentally analyze some properties of simulated annealing algorithms (SA) and genetic algorithms (GA) for mapping data to multicomputers. These properties include sensitiviiy to user parameters, fault tolerance capability, and applicability to different multicomputer topologies. Some user parameters are included in the objective function and are architecture- or problem-dependent parameters. The others are used in the GA and SA algorithms. The fault tolerance capability is demonstrated by mapping data to a multicomputer with some faulty processors. We assume a hypercube multicomputer architecture in most experiments. However, mapping to mesh, array, ring, tree, and star graph topologies is also demonstrated. The experimental results show that the GA and SA are insensitive to user parameters in wide ranges, completely fault tolerant, and unbiased towards particular multicomputer topologies. These properties of flexibility and general applicability, which are lacking in other heuristic algorithms, make the GA and SA attractive for automatic parallelization systems.

关键词： automatic parallelization data mapping load partitioning and balancing scheduling parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

RUNTIME AND LANGUAGE SUPPORT FOR COMPILING ADAPTIVE IRREGULAR PROGRAMS ON DISTRIBUTED-MEMORY MACHINES

引用

SOFTWARE-PRACTICE & EXPERIENCE 1995年第6期25卷 597-621页

作者： HWANG, YS MOON, B SHARMA, SD PONNUSAMY, R DAS, R SALTZ, JH SYRACUSE UNIV NW PARALLET ARCHITECTURES CTR SYRACUSE NY 13244 USA UNIV MARYLAND UMIACS COLLEGE PK MD 20742 USA

In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed-memory message-passing machines, such as the paragon, Delta, CM-5 and SP-1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors;it supports efficient index translation mechanisms and provides users high-level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real-life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle-in-cell code, DSMC. Besides providing runtime support to users, CHAOS tan also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.

关键词： DISTRIBUTED-MEMORY MULTIPROCESSORS RUNTIME COMPILATION ADAPTIVE IRREGULAR PROGRAMS parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Commutativity Analysis

引用

International Journal of Foundations of Computer Science 1997年第1期8卷 81-94页

作者： Oscar H. Ibarra Pedro C. Diniz Martin C. Rinard University of California Santa Barbara California 93106-5110 U.S.A Supported in part by NSF/NASA/ARPA Grant IRI94-11330. Sponsored by the PRAXIS XXI program administrated by Portugal's JNICT – Junta Nacional de Investigação Científica e Tecnológica and holds a Fulbright travel grant. Supported in part by an Alfred P. Sloan Research Fellowship.

Two operations commute if they generate the same result regardless of the order in which they execute. Commutativity is an important property — commuting operations enable significant optimizations in the fields of parallel computing, optimizing compilers, parallelizing compilers and database concurrency control. Algorithms that statically decide if operations commute can be an important component of systems in these fields because they enable the automatic application of these optimizations. In this paper we define the commutativity decision problem and establish its complexity for a variety of basic instructions and control constructs. Although deciding commutativity is, in general, undecidable or computationally intractable, we believe that efficient algorithms exist that can solve many of the cases that arise in practice.

关键词： Computational complexity commutativity analysis program symbolic analysis parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Automated transformation of sequential divide-and-conquer algorithms into parallel programs

引用

COMPUTERS AND ARTIFICIAL INTELLIGENCE 1995年第6期14卷 579-596页

作者： Freisleben, B Kielmann, T UNIV SIEGEN DEPT ELECT ENGN & COMP SCI FB12 D-57068 SIEGEN GERMANY

Divide-and-conquer algorithms obtain the solution to a given problem by dividing it into subproblems, solving these recursively and combining their solutions. In this paper we present a system that automatically transforms sequential divide-and-conquer algorithms written in the C programming language into parallel code which is then executed on message-passing multicomputers. The user of the system is expected to add only a few annotations to an existing sequential program. The strategies required for transforming sequential source code to executable binaries are discussed. The performance speedups attainable will be illustrated by several examples.

关键词： divide-and-conquer algorithms automatic parallelization parallelizing compilers message-passing multicomputers transputer systems workstation clusters

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：