Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19615
標題: 利用梯度逼近最佳等待時間的資源分配技巧
A Gradient-Based Technique for Near-Optimal Waiting Time in Resource Allocation
作者: 王健亞
Wang, Jen-Ya
關鍵字: Gradient;梯度;Linearly convergent;Optimization;Grid computing;Parallel computing;Mobile computing;Average waiting time;線性收斂;最佳化;網格計算;平行計算;行動計算;平均等待時間
出版社: 資訊科學與工程學系所
引用: [1] G. Aggarwal, T. Feder, R. Motwani, R. Panigrahy, and A. Zhu, "Algorithms for the Database Layout Problem," in Proceedings of International Conference on Database Theory, 2005, pp. 619-625. [2] E. Ardizzoni, A.A. Bertossi, M.C. Pinotti, S. Ramaprasad, R. Rizzi, and M.V.S. Shashanka, "Optimal Skewed Data Allocation on Multiple Channels with Flat Broadcast per Channel," IEEE Transactions on Computers, Vol. 54, No. 5, pp. 558-572, 2005. [3] C. Blum and A. Roli, "Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison," ACM Computing Surveys, Vol. 35, No. 3, pp. 268-308, 2003. [4] B. Boeckmann, A. Bairoch, R. Apweiler, M.-C. Blatter, A. Estreicher, E. Gasteiger, K. M. Martin, Michoud, C. O'Donovan, I. Phan, S. Pilbout, and M. Schneider, "The SWISS-PROT Protein Knowledgebase and its Supplement TrEMBL in 2003," Nucleic Acids Research, Vol. 31, pp. 365-370, 2003. [5] P.M. Broadwell, "Response Time as a Performability Metric for Online Services," Technical Report, UCB CSD-04-1324, Electrical Engineering and Computer Science Department, University of California at Berkeley, USA, 2004. [6] J. Broberg, P. Zecephongsekul, and Z. Tari, "Approximating Bounded General Service Distributions," in Proceedings of the 12th IEEE Symposium on Computers and Communications (ISCC), 2007, pp. 817-823. [7] P. Bucher and A. Bairoch, "A Generalized Profile Syntax for Biomolecular Sequences Motifs and its Function in Automatic Sequence Interpretation," in Proceedings 2nd International Conference on Intelligent Systems for Molecular Biology, 1994, pp. 53-61. [8] F.S. Budnick, D. McLeavey, and R. Mojena, Principles of Operations Research for Management, 2 ed.: IRWIN, 1988. [9] R.L. Burden and J.D. Faires, Numerical Analysis: PWS-KENT, 1988. [10] T. Cakar, R. Koker, and H.I. Demir, "Parallel Robot Scheduling to Minimize Mean Tardiness with Precedence Constraints Using a Genetic Algorithm," Advances in Engineering Software, Vol. 39, pp. 47-54, 2008. [11] J. Carretero, F. Xhafa, and A. Abraham, "Genetic Algorithm Based Schedulers for Grid Computing Systems," International Journal of Innovative Computing, Information and Control Vol. 3, No. 6, pp. 1-19, 2007. [12] V. Cerny, "A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm," Journal of Optimization Theory and Applications, Vol. 40, pp. 41-51, 1985. [13] W.W. Chu, "Optimal File Allocation in a Multiple Computer System," IEEE Transactions on Computers, Vol. C-18, No. 10, pp. 885-889, 1969. [14] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms: McGraw-Hill, 2001. [15] Y.S. Dai, G. Levitin, and X. Wang, "Optimal Task Partition and Distribution in Grid Service System with Common Cause Failures," Future Generation Computer Systems, Vol. 23, No. 2, pp. 209-218, 2007. [16] F. Desprez and A. Vernois, "Simultaneous Scheduling of Replication and Computation for Data-Intensive Applications on the Grid," Journal of Grid Computing, Vol. 4, No. 1, pp. 19-31, 2006. [17] M. Dorigo and G.D. Caro, The ant colony optimization meta-heuristic, New ideas in optimization: McGraw-Hill, 1999 [18] J.W. Fowler, P. Wirojanagud, and E.S. Gel, "Heuristics for Workforce Planning with Worker Differences," European Journal of Operational Research, Vol. 190, pp. 724-740, 2008. [19] F. Glover, "Future Paths for Integer Programming and Links to Artificial Intelligence," Computers and Operations Research, Vol. 13, pp. 533-549, 1986. [20] M. Harchol-Balter, "Job Placement with Unknown Duration and No Preemption Performance Evaluation," ACM SIGMETRICS Performance Evaluation Review, Vol. 28, No. 4, pp. 3-5, 2001. [21] M. Harchol-Balter and A.B. Downey, "Exploiting Process Lifetime Distributions for Dynamic Load Balancing," ACM Transactions Computer Systems, Vol. 15, pp. 253-285, 1997. [22] J.L. Huang and M.S. Chen, "Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment," IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 9, pp. 1143-1156, 2004. [23] Y.F. Huang and J.M. Huang, "Disk Scheduling on Multimedia Storage Servers," IEEE Transaction on Computers, Vol. 53, No. 1, pp. 77-82, 2004. [24] R. Ito and K. Suyama, "A Heuristic Approach to SP2 Term Allocation for Fir Filter Based on Least Mean Square Criteria," International Journal of Innovative Computing, Information and Control Vol. 1, No. 1, pp. 65-71, 2005. [25] S.A. Jarvis, L. He, D.P. Spooner, and G.R. Nudd, "The Impact of Predictive Inaccuracies on Execution Scheduling," Performance Evaluation, Vol. 60, pp. 127-139, 2005. [26] K.F. Jea, J.Y. Wang, and S.Y. Chen, "A Linearly Convergent Method for Broadcast Data Allocation," Computers and Mathematics with Applications, Vol. 56, No. 2, pp. 324-338, 2008. [27] H. Kameda, J. Li, C. Kim, and Y. Zhang, Optimal Load Balancing in Distributed Computer Systems: Springer, 1997. [28] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems: Springer, 2004. [29] S. Lee and H. Bahn, "Data Allocation in MEMS-based Mobile Storage Devices," IEEE Transactions on Consumer Electronics, Vol. 52, No. 2, pp. 472-476, 2006. [30] M. Lei, S.V. Vrbsky, and X. Hong, "An On-line Replication Strategy to Increase Availability in Data Grids," Future Generation Computer Systems, Vol. 24, No. 2, 2008. [31] C.J. Liao, C.W. Chao, and C.H. Lin, "Minimizing the Sum of Job Completion Times on Capacitated Two-parallel Machines," European Journal of Operational Research, In Press, Corrected Proof, 2008. [32] H.C. Lin and C.S. Raghavendra, "A Dynamic Load-Balancing Policy with a Central Job Dispatcher (LBC)," IEEE Transactions on Software Engineering, Vol. 18, No. 2, pp. 148-158, 1992. [33] L. Lu, L. Zhang, and J. Yuan, "The Unbounded Parallel Batch Machine Scheduling with Release Dates and Rejection to Minimize Makespan," Theoretical Computer Science, Vol. 396, pp. 283-289, 2008. [34] D. Martin, A.v. Moorsel, and G. Morgan, "Efficient Resource Management for Game Server Hosting," in Proceedings of the 2008 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing (ISORC), 2008, pp. 593-596. [35] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics, 3 ed.: Springer, 2002. [36] D. Nurmi, J. Brevik, and R. Wolski, "Modeling Machine Availability in Enterprise and Wide-Area Distributed Computing Environments," Lecture Notes in Computer Science, Vol. 3648, pp. 432-441, 2005. [37] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables: SIAM, 2000. [38] W.C. Peng and M.S. Chen, "Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment," Wireless Networks, Vol. 9, No. 2, pp. 117-129, 2003. [39] W.C. Peng, J.L. Huang, and M.S. Chen, "Dynamic Leveling: Adaptive Data Broadcasting in a Mobile Computing Environment," Mobile Networks and Applications, Vol. 8, No. 4, pp. 355-364, 2003. [40] L. Qi, H. Jin, I. Foster, and J. Gawor, "Provisioning for Dynamic Instantiation of Community Services," IEEE Internet Computing, Vol. 12, No. 2, pp. 29-36, 2008. [41] X. Qin, "Design and Analysis of a Load Balancing Straegy in Data Grids, "Future Generation Computer Systems, Vol. 23, pp. 132-137, 2007. [42] R.L. Rardin, Optimization in Operations Research: Prentice Hall, 1998. [43] A. Ravindran, D.T. Phillips, and J.J. Solberg, Operations Research Principles and Practice: Wiley, 1987. [44] P. Sanders, "Asynchronous Scheduling of Redundant Disk Arrays," IEEE Transactions on Computers, Vol. 52, pp. 1170-1184, 2003. [45] A. Silberschatz, H.F. Korth, and S. Sudarshan, Database System Concepts: McGraw Hill, 2002. [46] R. Subrata, A.Y. Zomaya, and B. Landfeldt, "Game-Theoretic Approach for Load Balancing in Computational Grids," IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 1, pp. 66-76, 2008. [47] H.A. Taha, Operations Research An Introduction, 6 ed.: Prentice Hall, 1997. [48] P. Tsirimpas, A. Tatarakis, I. Minis, and E.G. Kyriakidis, "Single Vehicle Routing with a Predefined Customer Sequence and Multiple Depot Returns," European Journal of Operational Research, Vol. 187, No. 2, pp. 483-495, 2008. [49] C. Voudouris and E. Tsang, "Guided local search," European Journal of Operational Research, Vol. 113, No. 2, pp. 469-499, 1999. [50] J.Y. Wang and K.F. Jea, "A Near-Optimal Database Allocation for Reducing the Average Waiting Time in the Grid Computing Environment," Information Sciences, Vol. 179, No. 21, pp. 3772-3790, 2009. [51] J. Wingstrom and H. Casanova, "Probabilistic Allocation of Tasks on Desktop Grids," in Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 2008, pp. 1-8. [52] C. Wu, L. Yeh, H. Huang, L. Arminski, J. Castro-Alvear, Y. Chen, Z. Hu, P. Kourtesis, R. Ledley, and B. Suzek, "The Protein Information Resource," Nucleic Acids Research, Vol. 31, pp. 345-347, 2003. [53] W.G. Yee, S.B. Navathe, E. Omiecinski, and C. Jermaine, "Efficient Data Allocation over Multiple Channels at Broadcast Servers," IEEE Transactions on Computers, Vol. 51, No. 10, pp. 1231-1236, 2002. [54] B. Zheng, X. Wu, X. Jin, and D.L. Lee, "Broadcast Scheduling: TOSA: A Near-optimal Scheduling Algorithm for Multi-channel Data Broadcast," in Proceedings of the 6th International Conference on Mobile Data Management, 2005, pp. 29-37. [55] Globus Alliance, "Globus Toolkit, "http://www.globus.org/, 2009.
摘要: 
本論文提出一個利用梯度的最佳化技巧,它藉由適當分配計算資源以降低使用者的平均等待時間。本研究主要動機是來自許多大型科學計畫(例如蛋白質結構比對)或商業應用(例如線上遊戲),必須隨時保持較佳的等待時間才能維持客戶滿意度與繼續營運的需求。我們首先將此資源分配問題從原整數空間Z^n轉換到歐氏空間R^n,然後利用所提出梯度技巧在R^n空間中求出轉換問題的最佳解,最後再將此最佳解轉換回原空間Z^n得到原問題的近似最佳解。由理論分析得知此技巧能線性收斂以及能逼近最佳等待時間,此外我們也輔以實驗結果來印證此技巧的收斂速度與解答品質。利用此技巧,系統設計者僅花費些許執行時間即能完成資源部署,並提供近似最佳平均等待時間。以上結果顯示若將此技巧應用到其它類似最佳化問題(例如繞徑問題),則大有可能得到同樣的近似最佳結果。

In this dissertation, we propose a gradient-based technique that properly partitions and allocates resources in order to minimize the average waiting time for users in several computing environments. It is motivated by that there are many large-scale scientific projects (e.g., protein structure matching) and commercial applications (e.g., online game) and their waiting time needs to be lowered down for sustaining customer satisfaction. First, such a partition/allocation problem is mapped from the integer space Z^n to the Euclidean space R^n. Then, the optimal solution to the mapped problem in R^n is discovered by the proposed technique which optimally divides the resources and distributes them to multiple sites/nodes/locations. Finally, a near-optimal solution to the original problem is obtained by mapping the optimal solution to the mapped problem from R^n back to Z^n. The theoretical analyses show that the proposed technique converges linearly and generates a near-optimal average waiting time. We also present experimental results that confirm the convergence speed and solution quality of the proposed technique. Using the proposed technique, a system designer spends only a little execution time for deploying his/her resources and provides users with a near-optimal average waiting time. Importantly, the proposed technique can be extended to other similar optimization problems (e.g., vehicle routing problem) and can promisingly achieve the same near-optimal results.
URI: http://hdl.handle.net/11455/19615
其他識別: U0005-1708200910055800
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.