Global Partial Replicate Computation Partitioning

Wang Yiran; Chen Li; Feng Xiaobing; Zhang Zhaoqing

Journal of Computer Research and Development > 2006 > 43(12): 2158-2165.

Wang Yiran, Chen Li, Feng Xiaobing, Zhang Zhaoqing. Global Partial Replicate Computation Partitioning[J]. Journal of Computer Research and Development, 2006, 43(12): 2158-2165.

Citation:

Wang Yiran, Chen Li, Feng Xiaobing, Zhang Zhaoqing. Global Partial Replicate Computation Partitioning[J]. Journal of Computer Research and Development, 2006, 43(12): 2158-2165.

Citation:

Wang Yiran, Chen Li, Feng Xiaobing, Zhang Zhaoqing. Global Partial Replicate Computation Partitioning[J]. Journal of Computer Research and Development, 2006, 43(12): 2158-2165.

PDF (868 KB)

Global Partial Replicate Computation Partitioning

1(Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080) 2(Graduate University of Chinese Academy of Sciences, Beijing 100049)

More Information

Published Date: December 14, 2006

Graphical Abstract

Abstract

Abstract

Early parallelizing compilers use the owner-computes rule to partition computation. Partial replication is then introduced to reduce near-neighbor communication at the cost of some repeated computation. It is an important optimization that improves the performance and scalability of parallel programs. Former exploration of partial replicate computation partitioning is limited within a single loop nest, and no explicit cost model is used. In this paper, a formal description of more general partial replicate computation partitioning problems is presented, which is called global partial replicate computation partitioning. As redundant message elimination exerts great influence on the effect of such optimizations, a linear cost model is introduced, which considers its effect. A framework is also developed, which employs the integer linear programming method. Experimental results show that the solution is superior to local approaches. Compared with the heuristic method, the new approach can deal with more general cases and is easier to adapt to different data distribution.
- parallelizing compiler,
- distributed memory systems,
- partial replicate computation partitioning,
- data parallel

FullText(HTML)

References (0)

[1]	Ma Zhaojia, Shao En, Di Zhanyuan, Ma Lixian. Porting and Parallel Optimization of Common Operators Based on Heterogeneous Programming Models[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330869
[2]	Zhou Ze, Sun Yinghui, Sun Quansen, Shen Xiaobo, Zheng Yuhui. An Adversarial Detection Method Based on Tracking Performance Difference of Frequency Bands[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440428
[3]	Li Maowen, Qu Guoyuan, Wei Dazhou, Jia Haipeng. Performance Optimization of Neural Network Convolution Based on GPU Platform[J]. Journal of Computer Research and Development, 2022, 59(6): 1181-1191. DOI: 10.7544/issn1000-1239.20200985
[4]	Xie Zhen, Tan Guangming, Sun Ninghui. Research on Optimal Performance of Sparse Matrix-Vector Multiplication and Convoulution Using the Probability-Process-Ram Model[J]. Journal of Computer Research and Development, 2021, 58(3): 445-457. DOI: 10.7544/issn1000-1239.2021.20180601
[5]	Zhang Jun, Xie Jingcheng, Shen Fanfan, Tan Hai, Wang Lümeng, He Yanxiang. Performance Optimization of Cache Subsystem in General Purpose Graphics Processing Units: A Survey[J]. Journal of Computer Research and Development, 2020, 57(6): 1191-1207. DOI: 10.7544/issn1000-1239.2020.20200113
[6]	Gu Rong, Yan Jinshuang, Yang Xiaoliang, Yuan Chunfeng, and Huang Yihua. Performance Optimization for Short Job Execution in Hadoop MapReduce[J]. Journal of Computer Research and Development, 2014, 51(6): 1270-1280.
[7]	Zhang Fengjun, Zhao Ling, An Guocheng, Wang Hongan, Dai Guozhong. Mean Shift Tracking Algorithm with Scale Adaptation[J]. Journal of Computer Research and Development, 2014, 51(1): 215-224.
[8]	Lü Na and Feng Zuren. Adaptive Multi-Resolutional Image Tracking Algorithm[J]. Journal of Computer Research and Development, 2012, 49(8): 1708-1714.
[9]	Li Shanqing, Tang Liang, Liu Keyan, Wang Lei. A Fast and Adaptive Object Tracking Method[J]. Journal of Computer Research and Development, 2012, 49(2): 383-391.
[10]	Zheng Ruijuan, Wu Qingtao, Zhang Mingchuan, Li Guanfeng, Pu Jiexin, Wang Huiqiang. A Self-Optimization Mechanism of System Service Performance Based on Autonomic Computing[J]. Journal of Computer Research and Development, 2011, 48(9): 1676-1684.