在可分割負載分佈的方法中，典型的線性網路分佈方法是應用管線化通訊。在本篇論文裡，我們首先提出一個應用管線化通訊和多重配置處理的方法，如此便能減少初始的分佈時間以達到最佳的效能。考慮當起始時間(start-up costs)存在的情況下，因為應用計算和通訊重疊方法的關係，處理器計算完成的時間並不一致，因此我們提出一個考慮起始時間來分佈負載的方法。在超立方體拓樸(hypercube topology)中，典型的方法為每一階層在一次的傳送時間內把所要傳送的負載分配給下一階層，之後只計算負載不再傳送，如此將會有許多的通訊閒置時間。在本篇論文裡，我們提出二個應用管線化通訊和多重配置處理的方法來解決通訊閒置時間的問題以達到最佳的效能。最後導出我們所提出的演算法之平行執行時間函數和增速函數。經過分析後，上述問題在我們的演算法中得到顯著的效能改善。

　In the divisible load distribution, the classic method on linear arrays distributes divisible load by means of time intervals of variable length for pipelined communication. In this paper, we first propose a method which employs multi-installment processing with pipelined communication to reduce initial distribution time and to achieve better performance. Considering situations that the start-up costs exist, the communication and computation can not be finished at the same time. Therefore, we propose an improved method which employs pipelined communication to distribute divisible load on linear arrays for such situations. In the hypercube topology, the classic method distributes divisible load by means that each layer transmits one load fraction to next layer. This classic load distribution method carries out that only one communication period on each layer, resulting in too much communication idle-time on each layer. In this paper, we propose two algorithms which use pipelined communication with multi-installment to solve the communication idle-time problem and to achieve better performance. By our algorithms, we observed significant improvement of performance on the speedup diagram which shows an exponential curve of performance. The speedup could be excellent and very close to system limitation especially, when the computation-communication ratio exceeds a certain value. The closed form solutions to the function of parallel execution time and speedup based on the proposed methods are also derived.

[1] K. Li, “Improved Methods for Divisible Load Distribution on k-Dimensional Meshes Using Pipelined Communications,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no.12, pp. 1250-1261, Dec. 2003.
[2] B.V and W.H.M, “ Scheduling Divisible Loads on Heterogeneous Linear Daisy Chain Networks with Arbitrary Processor Release Times” IEEE Trans. Parallel and Distributed Systems, vol. 15, no.3, pp. 273-288, Mar. 2004.
[3] X. Li, B.V and C.C.K “Divisible Load Scheduling on a Hypercube Cluster with Finite-size Buffers and Granularity Constraints,” IEEE/ACM International Symposium, pp. 660–667, May 2001.
[4] Beaumont. O, Casanova. H, Legrand. A, Robert. Y and Yang, Y, “Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems,” IEEE Trans. Parallel and Distributed Systems, vol. 16, no. 3, pp. 207-218 Mar. 2005
[5] Drozdowski. M and Wolniewicz. P, “Out-of-core divisible load processing,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 10, pp. 1048-1056 Oct. 2003.
[6] Li. K, “Accelerating divisible load distribution on tree and pyramid networks using pipelined communications,” Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, pp. 228, April 2004.
[7] Y.C.C and T.G, “Distributed Computation with Communication Delays,” IEEE Trans. Aerospace and Electronic Systems, vol. 24, no. 6, pp. 700-712, Nov. 1988.
[8] Jeeho. Sohn, Robertazzi. T.G. and Luryi. S, “Optimizing computing costs using divisible load analysis,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 3, pp. 225–234, Mar. 1998.
[9] S. Charcranoon, T.G.. Robertazzi and S. Luryi, “Parallel processor configuration design with processing/transmission costs,” IEEE Trans. Computers, vol. 49, no. 9, pp. 987–991, Sept. 2000.
[10] B. Veeravalli, Xiaolin. Li and C.C. Ko, “On the influence of start-up costs in scheduling divisible loads on bus networks,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 12, pp. 1288–1305, Dec. 2000.
[11] O. Beaumont, A. Legrand and Y. Robert, “Optimal algorithms for scheduling divisible workloads on heterogeneous systems,” Parallel and Distributed Processing Symposium, Apr. 2003.
[12] H.J. Kim, T. Kim and V. Mani, “Scheduling divisible loads in non-blocking mode of communication: optimal sequencing and arrangement in a single-level tree network,” SCOReD 2002. Research and Development, pp. 464–467, Jul. 2002.
[13] G.D. Barlas, “Collection-aware optimum sequencing of operations and closed-form solutions for the distribution of a divisible load on arbitrary processor trees,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 5, pp. 429–441, May 1998.
[14] W. Glazek, “Distributed computation in a three-dimensional mesh with communication delays,” PDP '98. Proceedings of the Sixth Euromicro Workshop on Parallel and Distributed Processing, pp. 38–42, Jan. 1998.
[15] V. Bharadwaj, D. Ghose, and V. Mani, “Multi-Installment Load Distribution in Tree Networks with Delays,” IEEE Trans. Aerospace and Electronic Systems, vol. 31, no. 2, pp. 555–567, 1995.
[16] A. Grama, A. Gupta, G. Karypis and V. Kumar, “Introduction to Parallel Computing 2nd,” Addison-Wesley, 2003.
[17] Y. Yang and H. Casanova. “Multi-round algorithm for scheduling divisible workload applications: analysis and experimental evaluation.”, Technical Report CS2002-0721, Dept. of Computer Science and Engineering, University of California, San Diego, 2002.