在可分割負載(divisible load)分配的研究文獻中，許多演算法被提出並實作在不同環境中[5, 12, 14, 16, 20]，而在可分割負載分配理論中，最主要的目的即為試圖去找出分配到各個處理器的最佳負載比例(load fraction)大小進而讓整體處理時間能縮到最短，以達到高效能的目的。使用管線化通訊(pipelined communication)技術能夠顯著地降低處理器的等待時間，進而達到更好的執行效能，而過去的管線化通訊研究著重在同質環境中，也就是各個處理器與傳輸連結擁有相同的處理能力與傳送能力。本論文首先提出了一種在異質線性網路多處理機中分配可分割負載的演算法，並且推導出傳送到各個處理器的負載片段大小與處理時間的計算公式。另外因為實作在異質環境，將會產生某些處理器會在不同的時間點完成計算，也就是說，在此線性網路的所有處理器無法同時完成計算，本論文也提出了一種可能的解決方式。最後，提出了一些數據證明了本論文提出的演算法之效能顯著地優於過去論文研究所提出的演算法。

In divisible loads distribution researches, many algorithms were proposed and applied to homogeneous processors with different network topologies. The main purpose in the divisible loads theory is to find the optimal load fractions that were distributed to each processor for achieving the minimal processing time. Using the pipelined communications can significantly reduce the waiting time of processors and reach better performance. In the past, most researches focused on the homogeneous networks to which every processor and link in the network have identical capability. This research firstly proposes an algorithm to distribute the load fractions to every processor in heterogeneous linear network, and then derives some equations of load fractions and processing time. Next, because the proposed method is applied in the heterogeneous network, it may cause some time differences that will result in some processors terminating at different times. Therefore, a probable solution to solve it is also proposed. Finally, we give some numerical examples to demonstrate that our proposed method outperforms the methods of the past researches.

[1] T. G. Robertazzi, “Ten reasons to use divisible load theory,” IEEE Computer, vol, 36, no. 5, pp. 63-68, 2003.
[2] Keqin Li, “Improved methods for divisible load distribution on k-dimensional meshes using pipelined communications” IEEE Transactions on parallel and distributed systems, vol.14, no. 12, pp. 1250-1261, 2003.
[3] S. Suresh, V. Mani, S.N. Omkar, H.J. Kim, N. Sundararaja, ”A new load distribution strategy for linear network with communication delays”, Mathematics and Computers in Simulation, vol.79, pp. 1488-1501, 2009.
[4] Y. C. C and T. G, “Distributed computation with communication delays”, IEEE trans. Aerospace and Electronic Systems, vol. 24, no. 6,pp. 700-712, 1988.
[5] S. Bataineh and T. Robertazzi, “Bus-oriented load sharing for a network of sensor driven processors”, System, Man and Cybernetics, IEEE Transactions on, vol. 21, pp. 1202-1205, 1991.
[6] V. Bharadwaj, X. Li, and C. C. Ko, ”Efficient partitioning and scheduling of computer vision and image processing data on bus networks using divisible load analysis”, Image and Vision Computing, vol.18, pp.919-938, 2000.
[7] J. Blazewicz, M. Drozdowski, and M. Markiewicz, “Divisible task scheduling-concept and verification”, Parallel Computing, vol.25, pp.87-98, 1999.
[8] S. Chan, V. Bharadwaj, and D, Ghose, ”Large matrix-vector products on distributed bus networks with communication delays using the divisible load paradigm: performance analysis and simulation”, Mathematics and Computers in Simulation, vol.58, pp.71-92, 2001.
[9] M. Drozdowski and P. Wolniewicz, “Out-of-core divisible load processing”, Parallel and Distributed Systems, IEEE Transactions on, vol.14, pp.1048-1056, 2003.
[10] J. Guo, J. Yao, and L. Bhuyan, “An efficient packet scheduling algorithm in network processors”, in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, pp. 807-818, 2005.
[11] B. Veeravalli, X. Li, and C. C. Ko, “On the influence of start-up costs in scheduling divisible loads on bus networks” Parallel and Distributed Systems, IEEE Transactions on, vol. 11, pp. 1288-1305, 2000.
[12] T. G. Robertazzi, “Processor equivalence for daisy chain load sharing processors”, Aerospace and Electronic Systems, IEEE Transactions on, vol.29, pp. 1216-1221, 1993.
[13] B. Veeravalli and W. H. Min, “Scheduling divisible loads on heterogeneous linear daisy chain networks with arbitrary processor release times”, Parallel and Distributed Systems, IEEE Transactions on, vol. 15, pp. 273-288, 2004.
[14] C. Banino, O. Beaumont, L. Carter, J. Ferrante, A. Legrand, and Y. Robert, “Scheduling strategies for master-slave tasking on heterogeneous processor platforms”, Parallel and Distributed Systems, IEEE Transactions on, vol. 15, pp. 319-330, 2004.
[15] O. Beaumont, A. Legrand, and Y. Robert, “The master-slave paradigm with heterogeneous processors”, Parallel and Distributed Systems, IEEE Transactions on, vol. 14, pp. 897-908, 2003.
[16] V. Bharadwaj, D. Ghose, and V. Mani, “Multi-installment load distribution in tree networks with delays”, Aerospace and Electronic Systems, IEEE Transactions on, vol. 31, pp. 897-908, 1995.
[17] S. Charcranoon, T. G. Robertazzi, and S. Luryi, “Parallel processor configuration design with processing/transmission costs”, Computers, IEEE Transactions on, vol. 49, pp. 987-997, 2000.
[18] Y. C. Cheng and T. Robertazzi, “Distributed computation for a tree network with communications delays”, Aerospace and Electronic Systems, IEEE Transactions on, vol. 26, pp. 511-516, 1990.
[19] K. Li, “New Divisible Load Distribution Methods using Pipelined Communication Techniques on Tree and Pyramid Networks”, Aerospace and Electronic Systems, IEEE Transactions on, vol. 47, pp. 806-819, 2011.
[20] J. Blazewicz and M. Drozdowski, “Scheduling divisible jobs on hepercubes”, Parallel Computing, vol. 21, pp. 1945-1956, 1995.
[21] J. Blazewicz, M. Drozdowski, and M. Markiewicz, “Divisible task scheduling-concept and verification”, Parallel Computing, vol. 25, pp. 87-98, 1999.
[22] C. Y. Chen and C. P. Chu, “Improved methods for divisible load distribution on d-dimensional hypercube using multi-installment”, Journal of the Chinese Institute of Engineers, vol. 31, pp. 1199-1206, 2008.
[23] X. Li, B. Veeravalli, and C. C. Ko, “Divisible load scheduling on a hypercube cluster with finite-size buffers and granularity constraints”, Cluster Computing and the Grid, 2001. Proceedings. First IEEE/ACM International Symposium on, pp. 660-667, 2001.