臺灣博碩士論文加值系統

在許多不同的可分割負載(divisible load)問題領域中，其演算法的計算量與問題的大小呈非線性關係。可分割負載理論中，主要的目的為找出分配給網路中各個處理器的最佳負載片段大小去讓總負載處理時間能夠最短。本篇論文首先提出兩個在同質線性網路多處理機中分配非線性可分割負載的演算法，其總負載在初始時位在網路邊界的根(root)處理器。若總負載初始時位在網路內部的根處理器，本論文也提出一個分佈非線性可分割負載的演算法。在這些演算法中，本研究推導出負載片段大小與總負載處理時間的計算式，另外在考慮計算和通訊初始成本(start-up cost)存在的狀況下，推導出每個演算法的總負載處理時間以及適當的處理器數目。最後，證明本論文所提出的演算法之效能明顯優於過去研究所提出的演算法。

In many diverse areas with divisible loads, the computational cost of the algo-rithm is a nonlinear function of the load size. The main purpose of the Divisible Load Theory (DLT) is obtaining the optimal load fraction in each processor to minimize the entire load processing time. This thesis proposed two different nonlinear computational load distribution algorithms for the homogeneous processors with daisy chain networks, to which the entire loads are originated from root processor located on the boundary initially. If the entire loads are originated form the interior (root) processor, this thesis also proposed a divisible load distribution algorithm. In order to reduce the idle time before each processor starts to compute, we also address a nonlinear computational load distribution algorithm for boundary root processor case with multiple installments. For these algorithms, the closed-form expression of the load fraction for each processor and the entire processing time are derived. Moreover, the entire load processing time and the proper number of the processors are also obtained for the case the start-up cost is considered. At the end, the performance of the proposed algorithms significantly outperforms the classic algorithm is also proved in the thesis.

List of Tables VI
List of Figures VII
Chapter 1. Introduction 1
1.1 Motivation and Purpose 2
1.2 Contribution 3
1.3 Organization 4
Chapter 2. Background and Literature Survey 5
2.1 The Divisible Load Theory (DLT) 5
2.2 A Load Distributing Strategy for Linear Network 6
2.3 Nonlinear Computational Loads 9
Chapter 3. Models and Notations 10
3.1 Daisy Chain Network 10
3.2 Notations 11
3.3 Computational Loads 13
Chapter 4. Algorithms for Boundary Root Processor Case 15
4.1 Algorithm R : Completing the Communication in Phase One 16
4.2 Algorithm Q : Completing the Communication during Phase One and Phase Two 23
4.3 Algorithms with Start-up Costs Considered 32
4.4 Discussion of Results 37
Chapter 5. Algorithm for Interior Root Processor Case 40
5.1 Algorithm L : Completing the Communication during Phase One and Phase Two 41
5.2 Algorithm with Start-up Costs Considered 51
5.3 Discussion of Results 54
Chapter 6. Algorithm for Boundary Root Processor Case with Multiple Installments 55
6.1 Algorithm M 55
6.2 Algorithm with Start-up costs Considered 62
6.3 Discussion of Results 65
Chapter 7. Conclusions and Further Research 67
REFERENCE 69

[1]S. Suresh, V. Mani, S. Omkar, H. Kim, and N. Sundararajan, A new load distribution strategy for linear network with communication delays, Mathematics and Computers in Simulation, vol. 79, pp. 1488-1501, 2009.
[2]Y.-C. Cheng and T. G. Robertazzi, Distributed computation with communication delay [distributed intelligent sensor networks], Aerospace and Electronic Systems, IEEE Transactions on, vol. 24, pp. 700-712, 1988.
[3]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.
[4]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.
[5]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.
[6]B. Veeravalli and S. Ranganath, Theoretical and experimental study on large size image processing applications using divisible load paradigm on distributed bus networks, Image and Vision Computing, vol. 20, pp. 917-935, 2002.
[7]Y. Yang, K. Van Der Raadt, and H. Casanova, Multiround algorithms for scheduling divisible loads, Parallel and Distributed Systems, IEEE Transactions on, vol. 16, pp. 1092-1102, 2005.
[8]J. Błażewicz, M. Drozdowski, and M. Markiewicz, Divisible task scheduling–concept and verification, Parallel Computing, vol. 25, pp. 87-98, 1999.
[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, 2005, pp. 807-818.
[11]B. Veeravalli and N. Viswanadham, Suboptimal solutions using integer approximation techniques for scheduling divisible loads on distributed bus networks, Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, vol. 30, pp. 680-691, 2000.
[12]S. Bataineh and T. Robertazzi, Bus-oriented load sharing for a network of sensor driven processors, Systems, Man and Cybernetics, IEEE Transactions on, vol. 21, pp. 1202-1205, 1991.
[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]J. Błażewicz, M. Drozdowski, F. Guinand, and D. Trystram, Scheduling a divisible task in a two-dimensional toroidal mesh, Discrete Applied Mathematics, vol. 94, pp. 35-50, 1999.
[15]Y.-K. Chang, J.-H. Wu, C.-Y. Chen, and C.-P. Chu, Improved methods for divisible load distribution on k-dimensional meshes using multi-installment, Parallel and Distributed Systems, IEEE Transactions on, vol. 18, pp. 1618-1629, 2007.
[16]T. G. Robertazzi, Processor equivalence for daisy chain load sharing processors, Aerospace and Electronic Systems, IEEE Transactions on, vol. 29, pp. 1216-1221, 1993.
[17]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.
[18]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.
[19]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. 555-567, 1995.
[20]S. Charcranoon, T. G. Robertazzi, and S. Luryi, Parallel processor configuration design with processing/transmission costs, Computers, IEEE Transactions on, vol. 49, pp. 987-991, 2000.
[21]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.
[22]Y.-C. Cheng and T. Robertazzi, Distributed computation for a tree network with communication delays, Aerospace and Electronic Systems, IEEE Transactions on, vol. 26, pp. 511-516, 1990.
[23]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.
[24]X. Li, B. Veeravalli, and C. C. Ko, Divisible load scheduling on a hypercube cluster with finite-size buffers and granularity constraints, in Cluster Computing and the Grid, 2001. Proceedings. First IEEE/ACM International Symposium on, 2001, pp. 660-667.
[25]J. Błazewicz and M. Drozdowski, Scheduling divisible jobs on hypercubes, Parallel Computing, vol. 21, pp. 1945-1956, 1995.
[26]W. Glazek, Distributed computation in a three-dimensional mesh with communication delays, in Parallel and Distributed Processing, 1998. PDP'98. Proceedings of the Sixth Euromicro Workshop on, 1998, pp. 38-42.
[27]K. Li, Improved methods for divisible load distribution on k-dimensional meshes using pipelined communications, Parallel and Distributed Systems, IEEE Transactions on, vol. 14, pp. 1250-1261, 2003.
[28]D. H. Low, B. Veeravalli, and D. A. Bader, On the design of high-performance algorithms for aligning multiple protein sequences on mesh-based multiprocessor architectures, Journal of Parallel and Distributed Computing, vol. 67, pp. 1007-1017, 2007.
[29]M. Drozdowski and W. Głazek, Scheduling divisible loads in a three-dimensional mesh of processors, Parallel Computing, vol. 25, pp. 381-404, 1999.
[30]X. Li, B. Veeravalli, and C. Ko, Distributed image processing on a network of workstations, International Journal of Computers and Applications, vol. 25, pp. 136-145, 2003.
[31]L. Xiaolin, V. Bharadwaj, and C. Ko, Experimental study on processing divisible loads for large size image processing applications using PVM clusters, International Journal of Computers and Applications, ACTA Press, 2001.
[32]A. Plaza, J. Plaza, and D. Valencia, Impact of platform heterogeneity on the design of parallel algorithms for morphological processing of high-dimensional image data, The Journal of Supercomputing, vol. 40, pp. 81-107, 2007.
[33]C.-k. Lee and M. Hamdi, Parallel image processing applications on a network of workstations, Parallel Computing, vol. 21, pp. 137-160, 1995.
[34]V. Bharadwaj, D. Ghose, V. Mani, and T. G. Robertazzi, Scheduling divisible loads in parallel and distributed systems vol. 8: Wiley-IEEE Computer Society Press, 1996.
[35]D. T. Altilar and Y. Paker, Optimal scheduling algorithms for communication constrained parallel processing, in Euro-Par 2002 Parallel Processing, ed: Springer, 2002, pp. 197-206.
[36]P. Li, B. Veeravalli, and A. A. Kassim, Design and implementation of parallel video encoding strategies using divisible load analysis, Circuits and Systems for Video Technology, IEEE Transactions on, vol. 15, pp. 1098-1112, 2005.
[37]B. Veeravalli, L. Chen, H. Y. Kwoon, G. K. Whee, S. Y. Lai, L. P. Hian, and H. C. Chow, Design, analysis, and implementation of an agent driven pull-based distributed video-on-demand system, Multimedia Tools and Applications, vol. 28, pp. 89-118, 2006.
[38]X. Li, B. Veeravalli, and V. K. Prasanna, A window-assisted video partitioning strategy for partitioning and caching video streams in distributed multimedia systems, Journal of Parallel and Distributed Computing, vol. 67, pp. 738-754, 2007.
[39]J. Guo and L. Adviser-Bhuyan, Message scheduling in a cluster-based active router for multimedia applications, 2006.
[40]J. Yao, J. Guo, and L. Bhuyan, Fair link striping with FIFO delivery on heterogeneous channels, Computer Communications, vol. 31, pp. 3427-3437, 2008.
[41]A. Legrand, A. Su, and F. Vivien, Minimizing the stretch when scheduling flows of biological requests, in Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, 2006, pp. 103-112.
[42]K. Ko and T. G. Robertazzi, Signature search time evaluation in flat file databases, Aerospace and Electronic Systems, IEEE Transactions on, vol. 44, pp. 493-502, 2008.
[43]H. M. Wong, D. Yu, B. Veeravalli, and T. G. Robertazzi, Data intensive grid scheduling: multiple sources with capacity constraints, in Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, 2003, pp. 7-11.
[44]X.-L. Li and J.-N. Cao, Coordinated workload scheduling in hierarchical sensor networks for data fusion applications, Journal of Computer Science and Technology, vol. 23, pp. 355-364, 2008.
[45]J. T. Hung and T. G. Robertazzi, Scheduling nonlinear computational loads, Aerospace and Electronic Systems, IEEE Transactions on, vol. 44, pp. 1169-1182, 2008.
[46]T. R. J.T. Hung, Distributed Scheduling of Nonlinear Computational Loads, presented at the Conference on Information Sciences and Systems, 2003.
[47]S. Suresh, H. Kim, C. Run, and T. Robertazzi, Scheduling nonlinear divisible loads in a single level tree network, The Journal of Supercomputing, vol. 61, pp. 1068-1088, 2012.
[48]S. Suresh, C. Run, H. J. Kim, T. G. Robertazzi, and Y.-I. Kim, Scheduling second-order computational load in master-slave paradigm, Aerospace and Electronic Systems, IEEE Transactions on, vol. 48, pp. 780-793, 2012.
[49]K. B. Khalifa, M. Boubaker, N. Chelbi, and M. H. Bedoui, Learning vector quantization neural network implementation using parallel and serial arithmetic, International Journal of Computer Sciences and Engineering Systems, vol. 2, pp. 251-256, 2008.
[50]Y. Bai and R. C. Ward, Parallel block tridiagonalization of real symmetric matrices, Journal of Parallel and Distributed Computing, vol. 68, pp. 703-715, 2008.