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

Efficient methods for kr→r and r→kr array redistribution

JOURNAL OF SUPERCOMPUTING 1998年第3期12卷 253-276页

作者： Hsu, CH Chung, YC Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

Array redistribution is usually required to enhance algorithm performance in many parallel programs on distributed memory multicomputers. Since it is performed at run-time, there is a performance tradeoff between the efficiency of new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present efficient algorithms for BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) and BLOCK-CYCLIC(r) to BLOCK-CYCLIC(kr) redistribution. The most significant improvement of our methods is that a processor does not need to construct the send/receive data sets for a redistribution. Based on the packing/unpacking information that derived from the BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) redistribution and vice versa, a processor can pack/unpack array elements into (from) messages directly. To evaluate the performance of our methods, we have implemented our methods along with the Thakur's methods and the PITFALLS method on an IBM SP2 parallel machine. The experimental results show that our algorithms outperform the Thakur's methods and the PITFALLS method for all test samples. This result encourages us to use the proposed algorithms for array redistribution.

关键词： array redistribution distributed memory multicomputers data distribution runtime support

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improving communication scheduling for array redistribution

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2005年第5期65卷 553-563页

作者： Guo, MY Pan, Y Univ Aizu Dept Comp Software Aizu Wakamatsu Fukushima 9658580 Japan Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Many scientific applications require array redistribution when the programs run 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. If there is no communication scheduling in a redistribution routine, the inter-processor communication will incur a larger communication idle time when there exists node contention and/or difference among message lengths during one particular communication step. In order to solve this problem, in this paper, we propose an efficient scheduling scheme that not only minimizes the number of communication steps and eliminates node contention, but also minimizes the difference of message lengths in each communication step. Thus, the communication idle time is reduced in redistribution routines. (c) 2005 Elsevier Inc. All rights reserved.

关键词： automatic parallelization array redistribution communication scheduling block-cyclic distribution MPI distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

Efficient methods for multi-dimensional array redistribution

引用

JOURNAL OF SUPERCOMPUTING 2000年第1期17卷 23-46页

作者： Hsu, CH Chung, YC Dow, CR Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

In many scientific applications, array redistribution is usually required to enhance data locality and reduce remote memory access on distributed memory multicomputers. Since the redistribution is performed at run-time, there is a performance tradeoff between the efficiency of the new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present efficient methods for multi-dimensional array redistribution. Based on the previous work, the basic-cycle calculation technique, we present a basic-block calculation (BBC) and a complete-dimension calculation (CDC) techniques. We also developed a theoretical model to analyze the computation costs of these two techniques. The theoretical model shows that the BBC method has smaller indexing costs and performs well for the redistribution with small array size. The CDC method has smaller packing/unpacking costs and performs well when array size is large. When implemented these two techniques on an IBM SP2 parallel machine along with the PITFALLS method and the Prylli's method, the experimental results show that the BBC method has the smallest execution time of these four algorithms when the array size is small. The CDC method has the smallest execution time of these four algorithms when the array size is large.

关键词： array redistribution distributed memory multicomputers the basic-block calculation technique the complete-dimension calculation technique

来源：评论

学校读者我要写书评

暂无评论

COMMUNICATION-FREE DATA ALLOCATION TECHNIQUES FOR PARALLELIZING COMPILERS ON multicomputers

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 1994年第9期5卷 924-938页

作者： CHEN, TS SHEU, JP Department of Computer Science and Information Engineering National Central University Chungli Taiwan

In distributed memory multicomputers, local memory accesses are much faster than those involving interprocessor communication. For the sake of reducing or even eliminating the interprocessor communication, the array elements in programs must be carefully distributed to local memory of processors for parallel execution. In this paper, we devote our efforts to the techniques of allocating array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. We first analyze the pattern of references among all arrays referenced by a nested loop, and then partition the iteration space into blocks without interblock communication. The arrays can be partitioned under the communication-free criteria with nonduplicate or duplicate data. Finally, a heuristic method for mapping the partitioned array elements and iterations onto the fixed-size multicomputers under the consideration of load balancing is proposed. Based on our methods, the nested loops can execute without any communication overhead on the distributed memory multicomputers. Moreover, the performance of the strategies with nonduplicate and duplicate data for matrix multiplication is studied.

关键词： DATA ALLOCATION DATA DEPENDENCE distributed memory multicomputers INTERPROCESSOR COMMUNICATION PARALLELIZING COMPILERS

来源：评论

学校读者我要写书评

暂无评论

Efficient data distribution scheme for multi-dimensional sparse arrays

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2007年第1期23卷 315-327页

作者： Lin, Chun-Yuan Chung, Yeh-Ching Natl Tsing Hua Univ Inst Mol & Cellular Biol Hsinchu 300 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan

Array operations are useful in a large number of important scientific codes, such as molecular dynamics, finite-element methods, climate modeling, etc. It is a challenging problem to provide an efficient data distribution for irregular problems. Multi-dimensional (AM) sparse array operations can be used in atmosphere and ocean sciences, image processing, etc., and have been an extensively investigated problem. In our previous work, a data distribution scheme, Encoding-Decoding (ED), was proposed for two-dimensional (2D) sparse arrays. In this paper, ED is extended to be useful for MD sparse arrays first. Then, the performance of ED is compared with that of Send Followed Compress (SFC) and Compress Followed Send (CFS). Both theoretical analysis and experimental tests were conducted and then shown that ED is superior to SFC and CFS for all of evaluated criteria.

关键词： data compression method data distribution scheme data layout distributed memory multicomputers sparse ratio sparse array

来源：评论

学校读者我要写书评

暂无评论

Compiler and run-time support for exploiting regularity within irregular applications

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2000年第2期11卷 119-135页

作者： Lain, A Chakrabarti, DR Banerjee, P Hewlett Packard Corp Bristol BS34 8QZ Avon England Northwestern Univ Ctr Parallel & Distributed Comp ECE Dept Evanston IL 60208 USA

This paper starts from a well-known idea. that structure in irregular problems improves sequential performance, and tries to show that the same structure can also be exploited for parallelization of irregular problems on a distributed-memory multicomputer. In particular, we extend a well-known parallelization technique called run-time compilation to use structure information that is explicit on the array subscripts. This paper presents a number of internal representations suited to particular access patterns and shows how various preprocessing structures such as translation tables, trace arrays, and interprocessor communication schedules can be encoded in terms of one or more of these representations. We show how loop and index normalization are important for detection of irregularity in array references, as well as the presence of locality in such references. This paper presents methods for detection of irregularity, feasibility of inspection, and finally, placement of inspectors and interprocessor communication schedules. We show that this process can be automated through extensions to an HPF/Fortran-77 distributed-memory compiler (PARADIGM) and a new runtime support for irregular problems (PILAR) that uses a variety of internal representations of communication patterns. We devise performance measures which consider the relationship between the inspection cost, the execution cost, and the number of times the executor is invoked so that a comparison of the competing schemes can be performed independent of the number of iterations. Finally, we show experimental results on an IBM SP-2 that validate our approach. These results show that dramatic improvements in both memory requirements and execution time can be achieved by using these techniques.

关键词： irregular applications iterative runtime support compiler support distributed memory multicomputers runtime compilation

来源：评论

学校读者我要写书评

暂无评论

A basic-cycle calculation technique for efficient dynamic data redistribution

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 1998年第4期9卷 359-377页

作者： Chung, YC Hsu, CH Bai, SW Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

Array redistribution is usually required to enhance algorithm performance in many parallel programs on distributed memory multicomputers. Since it is performed at run-time, there is a performance trade-off between the efficiency of the new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present a basic-cycle calculation technique to efficiently perform BLOCK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution. The main idea of the basic-cycle calculation technique is, first, to develop closed forms for computing source/destination processors of some specific array elements in a basic-cycle, which is defined as lcm(s, t)/gcd(s, t). These closed forms are then used to efficiently determine the communication sets of a basic-cycle. From the source/destination processor/data sets of a basic-cycle, we can efficiently perform a BLOCK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution. To evaluate the performance of the basic-cycle calculation technique, we have implemented this technique on an IBM SP2 parallel machine, along with the PITFALLS method and the multiphase method. The cost models for these three methods are also presented. The experimental results show that the basic-cycle calculation technique outperforms the PITFALLS method and the multiphase method for most test samples.

关键词： data redistribution the basic-cycle calculation technique the PITFALLS method the multiphase method distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

A generalized basic-cycle calculation method for efficient array redistribution

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2000年第12期11卷 1201-1216页

作者： Hsu, CH Bai, SW Chung, YC Yang, CS Feng Chia Univ Dept Informat Engn Taichung 40704 Taiwan Natl Sun Yat Sen Univ Inst Comp & Informat Engn Kaohsiung 80424 Taiwan

In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(S) over P processors to BLOCK-CYCLIC(f) over Q processors array redistribution. In the GBCC method, a processor first computes the source/destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, fQ)/(gcd(s t) x P) in the source distribution and lcm(sP, tQ)/(gcd(s,t) x Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables to minimize the data-movement operations. Since each generalized basic-cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multidimensional array redistributions is also presented.

关键词： redistribution generalized basic-cycle calculation method distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

A generalized processor mapping technique for array redistribution

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2001年第7期12卷 743-757页

作者： Hsu, CH Chung, YC Yang, DL Dow, CR Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

In many scientific applications, array redistribution is usually required to enhance data locality and reduce remote memory access in many parallel programs on distributed memory multicomputers. Since the redistribution is performed at runtime, there is a performance trade-off between the efficiency of the new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present a generalized processor mapping technique to minimize the amount of data exchange for BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) array redistribution and vice versa. The main idea of the generalized processor mapping technique is first to develop mapping functions for computing a new rank of each destination processor. Based on the mapping functions, a new logical sequence of destination processors can be derived. The new logical processor sequence is then used to minimize the amount of data exchange in a redistribution. The generalized processor mapping technique can handle array redistribution with arbitrary source and destination processor sets and can be applied to multidimensional array redistribution. We present a theoretical model to analyze the performance improvement of the generalized processor mapping technique. To evaluate the performance of the proposed technique, we have implemented the generalized processor mapping technique on an IBM SP2 parallel machine. The experimental results show that the generalized processor mapping technique can provide performance improvement over a wide range of redistribution problems.

关键词： array redistribution generalized processor mapping distributed memory multicomputers runtime support

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：