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

A rotate-tiling image compositing method for sort-last parallel volume rendering systems on distributed memory multicomputers

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2004年第4期20卷 643-664页

作者： Lin, CF Liao, SK Chung, YC Yang, DL Chang Jung Christian Univ Dept Informat Management Tainan 711 Taiwan Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan

The binary-swap (BS) and the parallel-pipelined (PP) methods are two well-known image compositing methods for sort-last parallel volume rendering systems. However, these two methods either restrict the number of processors to a power-of-two or require many communication steps to transform image data that results in high data communication overheads. In this paper, we present an efficient image compositing method, the rotate-tiling (RT) method, for sort-last parallel volume rendering systems on distributed memory multicomputers. According to the number of initial blocks of a partial image, the number of processors, the image sizes, and the characteristics of parallel machines, the RT method can fully utilize all available processors and minimize the data communication overheads. To evaluate the performance of the RT method, both theoretical analysis and experimental test of the BS, the PP, and the RT methods are conducted. In the theoretical analysis, we derive the best performance bound of the RT method in terms of the number of initial blocks of a partial image, the number of processors, the image sizes, and the characteristics of parallel machines. In the experimental test, we implemented these three image compositing methods on an IBM SP2 parallel machine and a PC cluster. The experimental results show that the RT method outperforms the BS and the PP methods for all test samples and match the results analyzed in the theoretical analysis.

关键词： image compositing sort-last parallel volume rendering system binary-swap parallel-pipelined rotate-tiling distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

Data distribution schemes of sparse arrays on distributed memory multicomputers

引用

JOURNAL OF SUPERCOMPUTING 2007年第1期41卷 63-87页

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

A data distribution scheme of sparse arrays on a distributed memory multicomputer, in general, is composed of three phases, data partition, data distribution, and data compression. To implement the data distribution scheme, many methods proposed in the literature first perform the data partition phase, then the data distribution phase, followed by the data compression phase. We called a data distribution scheme with this order as Send Followed Compress ( SFC) scheme. In this paper, we propose two other data distribution schemes, Compress Followed Send ( CFS) and Encoding-Decoding ( ED), for sparse array distribution. In the CFS scheme, the data compression phase is performed before the data distribution phase. In the ED scheme, the data compression phase can be divided into two steps, encoding and decoding. The encoding step and the decoding step are performed before and after the data distribution phase, respectively. To evaluate the CFS and the ED schemes, we compare them with the SFC scheme. In the data partition phase, the row partition, the column partition, and the 2D mesh partition with/without load-balancing methods are used for these three schemes. In the compression phase, the CRS/CCS methods are used to compress sparse local arrays for the SFC and the CFS schemes while the encoding/decoding step is used for the ED scheme. Both theoretical analysis and experimental tests were conducted. In the theoretical analysis, we analyze the SFC, the CFS, and the ED schemes in terms of the data distribution time and the data compression time. In experimental tests, we implemented these three schemes on an IBM SP2 parallel machine. From the experimental results, for most of test cases, the CFS and the ED schemes outperform the SFC scheme. For the CFS and the ED schemes, the ED scheme outperforms the CFS scheme for all test cases.

关键词： data distribution schemes data compression methods partition methods sparse ratio distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

Skewed data partition and alignment techniques for compiling programs on distributed memory multicomputers

引用

JOURNAL OF SUPERCOMPUTING 2002年第2期21卷 191-211页

作者： Chen, TS Chang, CY Chang Jung Univ Dept Informat Management Tainan 711 Taiwan Aletheia Univ Dept Comp & Informat Sci Taipei Taiwan

Minimizing data communication over processors is the key to compile programs for distributed memory multicomputers. In this paper, we propose new data partition and alignment techniques for partitioning and aligning data arrays with a program in a way of minimizing communication over processors. We use skewed alignment instead of the dimension-ordered alignment techniques to align data arrays. By developing the skewed scheme, we can solve more complex programs with minimized data communication than that of the dimension-ordered scheme. Finally, we compare the proposed scheme with the dimension-ordered alignment one by experimental results. The experimental results show that our proposed scheme has more opportunities to align data arrays such that data communications over processors can be minimized.

关键词： array alignment data distribution data partition distributed memory multicomputers parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Tree-based parallel load-balancing methods for solution-adaptive finite element graphs on distributed memory multicomputers

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 1999年第4期10卷 360-370页

作者： Liao, CJ Chung, YC Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

To solve the load imbalance problem of a solution-adaptive finite element application program on a distributed memory multicomputer, nodes of a refined finite element graph can be remapped to processors or load of a refined finite element graph can be redistributed based on the current load of each processor. For the former case, remapping can be performed by some fast mapping algorithms. For the latter case, a load-balancing algorithm can be applied to balance the computational load of each processor. In this paper, three tree-based parallel load-balancing methods, the MCSTLB method, the BTLB method, and the CBTLB method, were proposed to deal with the load imbalance problems of solution-adaptive finite element application programs. To evaluate the performance of the proposed methods, we have implemented those methods along with three mapping methods, the AE/ORB method, the AE/MC method, and the MLkP method, on an SP2 parallel machine. Three criteria, the execution time of mapping/load-balancing methods, the execution time of a solution-adaptive finite element application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for a solution-adaptive finite element application program, are used for the performance evaluation. The experimental results show that 1) if the initial mapping is performed by a mapping method and the same mapping method and load-balancing methods were used in each refinement to balance the load of processors, the execution time of an application program under a load-balancing method is always shorter than that of the mapping method, and 2) the execution time of an application program under the CBTLB method is shorter than that of the BTLB method and the MCSTLB method.

关键词： distributed memory multicomputers partitioning mapping load balancing solution-adaptive finite element graphs

来源：评论

学校读者我要写书评

暂无评论

A binomial tree based parallel load-balancing method for solution-adaptive finite element graphs on distributed memory multicomputers

引用

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 2001年第2期24卷 187-202页

作者： Chu, WC Yang, DL Liao, CJ Chung, YC Tunghai Univ Dept Comp Sci & Informat Engn Taichung 407 Taiwan

In this paper, we propose a binomial tree based parallel load-balancing method (BINOTPLB) to deal with the load imbalance of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the BINOTPLB method is first to construct a binomial tree based condensed processor graph. Based on the condensed processor graph, a prefix code tree is built. From the prefix code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the prefix code tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves are reached. Since each leaf is a binomial tree and a binomial tree can also be divided into two equal halves of binomial trees, the approach used to determine the schedule of a prefix code tree could also be applied to the binomial trees. We have implemented the BINOTPLB method on an SP2 parallel machine and compared its performance with two load-balancing methods, the directed diffusion method and the multilevel diffusion method, and three mapping methods, the JOSTLE-MS method, the MLkP method, and the PARTY library method. Three criteria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for an application program, are used for the performance evaluation. The experimental results show that the BINOTPLB method outperforms other methods for most of test samples.

关键词： distributed memory multicomputers partitioning mapping matching load balancing solution-adaptive finite element graphs

来源：评论

学校读者我要写书评

暂无评论

A parallel implementation of a fast multipole-based 3-D capacitance extraction program on distributed memory multicomputers

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2001年第12期61卷 1751-1774页

作者： Yuan, YH Banerjee, P Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA

Very fast and accurate 3-D capacitance extraction is essential for interconnect optimization in VLSI ultra-deep sub-micron designs (UDSM). Parallel processing provides an approach to reducing the simulation turn-around time. This paper examines the parallelization of the well-known fast multi-pole-based 3-D capacitance extraction program FASTCAP,, which employs new adaptive and preconditioning techniques. To account for the complicated data dependencies in the unstructured problems, we propose a novel generalized cost function model, which can be used to accurately measure the workload associated with each cube in the hierarchy. We then present two adaptive partitioning schemes, combined with efficient communication mechanisms with bounded buffer size, to reduce the parallel processing overhead. The overall load balance is achieved through balancing the load at each level of the multipole computation. We report detailed performance results on a variety of distributed memory parallel platforms, using standard benchmarks on 3-D capacitance extraction. (C) 2001 Academic Press.

关键词： parallel algorithms capacitance extraction fast multipole method distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

A prefix code matching parallel load-balancing method for solution-adaptive unstructured finite element graphs on distributed memory multicomputers

引用

JOURNAL OF SUPERCOMPUTING 2000年第1期15卷 25-49页

作者： Chung, YC Liao, CJ Yang, DL Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

In this paper, we propose a prefix code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load imbalance of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a prefix code tree for processors. Based on the prefix code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the prefix code tree are reached. We have implemented the PCMPLB method on an SP2 parallel machine and compared its performance with two load-balancing: methods, the directed diffusion method and the multilevel diffusion method, and five mapping methods, the AE/ORB method, the AE/MC method, the MLkP method, the PARTY library method, and the JOSTLE-MS method. An unstructured finite element graph Truss was used as a test sample. During the execution, Truss was refined five times. Three criteria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for an application program, are used for the performance evaluation. The experimental results show that (1) if a mapping method is used for the initial partitioning and this mapping method or a load-balancing method is used in each refinement, the execution time of an application program under a load-balancing method is less than that of the mapping method. (2) The execution time of an application program under the PCMPLB method is less than that of the directed diffusion method and the multilevel diffusion method.

关键词： distributed memory multicomputers partitioning mapping remapping load balancing solution-adaptive unstructured finite element models

来源：评论

学校读者我要写书评

暂无评论

PROCESSOR ALLOCATION AND SCHEDULING OF MACRO DATA-FLOW GRAPHS ON distributed-memory multicomputers BY THE PARADIGM COMPILER

PROCESSOR ALLOCATION AND SCHEDULING OF MACRO DATA-FLOW GRAPH...

引用

1993 International Conference on Parallel Processing

作者： RAMASWAMY, S BANERJEE, P UNIV ILLINOIS CTR RELIABLE & HIGH PERFORMANCE COMPURBANAIL 61801

ISBN: (纸本)0849389852

Functional or Control parallelism is an effective way to increase speedups in multicomputers. Programs for these machines are represented by Macro Dataflow Graphs (MDGs) for the purpose of functional parallelism analysis and exploitation. Algorithms for allocation and scheduling of MDGs have been discussed along with some analysis of their optimality. These algorithms attempt to minimize the execution time of any given MDG through exploitation of functional parallelism. Our preliminary results show their effectiveness over naive algorithms. © 1993 IEEE.

关键词： MACRO DATA-FLOW GRAPHS distributed memory multicomputers ALLOCATION AND SCHEDULING PARALLELIZING COMPILERS OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

Data distribution schemes of sparse arrays on distributed memory multicomputers

Data distribution schemes of sparse arrays on distributed me...

引用

31st International Conference on Parallel Processing (ICPP 2002)

作者： Lin, CY Chung, YC Liu, JS Feng Chia Univ Dept Informat Engn Taichung 407 Taiwan

ISBN: (纸本)0769516807

A data distribution scheme of sparse arrays on a distributed memory multicomputer in general, is composed of three phases, data partition, data distribution, and data compression. To implement the data distribution scheme, methods proposed in the literature first perform the data partition phase, then the data distribution phase, followed by the data compression phase. We called this scheme as Send Followed Compress (SFC) scheme. In this paper, we propose two other data distribution schemes, Compress Followed Send (CFS) and Encoding-Decoding (ED), for sparse array distribution. In the CFS scheme, the data compression phase is performed before the data distribution phase. In the ED scheme, the data compression phase can be divided into two steps, encoding and decoding. The encoding step and the decoding step are performed before and after the data distribution phase, respectively. To evaluate the CFS and the ED schemes, we compare them with the SFC scheme. Both theoretical analysis and experimental test were conducted. In theoretical analysis, we analyze the SFC, the CFS, and the ED schemes in terms of the data distribution time and the data compression time. In experimental test, we implemented these schemes on an IBM SP2 parallel machine. From the experimental results, for most of test cases, the CFS and the ED schemes outperform the SFC scheme. For the CFS and the ED schemes, the ED scheme outperforms the CFS scheme for all test cases.

关键词： Data distribution schemes Data compression methods Partition methods Sparse ratio distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

A flexible processor mapping technique toward data localization for block-cyclic data redistribution

引用

JOURNAL OF SUPERCOMPUTING 2008年第2期45卷 151-172页

作者： Huang, Jih-Woei Chu, Chih-Ping Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Array redistribution is usually needed for more efficiently executing a data-parallel program on distributed memory multicomputers. To minimize the redistribution data transfer cost, processor mapping techniques were proposed to reduce the amount of redistributed data elements. Theses techniques demand that the beginning data elements on a processor not be redistributed in the redistribution. On the other hand, for satisfying practical computation needs, a programmer may require other data elements to be un-redistributed (localized) in the redistribution. In this paper, we propose a flexible processor mapping technique for the Block-Cyclic redistribution to allow the programmer to localize the required data elements in the redistribution. We also present an efficient redistribution method for the redistribution employing our proposed technique. The data transfer cost reduction and system performance improvement for the redistributions with data localization are analyzed and presented in our experimental results.

关键词： data-parallel programming distributed memory multicomputers HPF data distribution processor mapping MPI

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：