臺灣博碩士論文加值系統

格網計算(Grid Computing)是一個正在崛起的嶄新計算架構。這種計算架構正在被許多科學研究所使用中。這種計算架構原本僅止於加速運算上的功用，但現在已經已衍生出新的一種:”資源分享”的概念。在這種概念之下，在虛擬組織(Virtual Organization)中的成員，可以共享彼此的資源以完成他們自己的工作。
在這種資源分享的架構下，我們會希望使用者的工作是一個工作流程，將所有的細節工作都事先定義好，而後藉由代理人程式來進行資源調配的工作。在調配資源的過程當中，我們必需要解決不同的工作流程中，同時對同一個資源的要求衝突。依照以往的集中管理方式，或許可以解決這個問題，但也同時遇到其他問題，如：對集中排程者(centralized scheduler)負載過重、或是排程者發生問題而導致整個系統停擺。
基於以上的理由，所以我們想採取去集中式排程(decentralized scheduling)。在我們的系統中，我們採用市場機制(market mechanism)的方法。一方面讓工作流程代理人(Work-flow Agent)根據外在狀況調整工作流程的資源要求時程(schedule)，而另一方面也由市場中間人(Market Broker Agent)來調整資源的相關資訊，並回報給各工作流程代理人，最後達到平衡時，我們將可以確定各工作流程可以被正確地執行。
最後我們將會比較我們提出的兩種解決市場振盪的兩種方法─機率及α法─的效果及與先到先處理(First Come First Serve)法的差距。

The Grid Computing is a new emerging computing infrastructure. It provides a new platform to share computational resources. Every participant has his own jobs to execute. How to schedule all participants’ jobs is an important problem. For each job, we have an execution workflow. In the traditional system, there is a centralized scheduler. Because of some problems, like single-node failure, and load-balancing consideration, we want to solve the scheduling problem without a central scheduler.
In this paper, we take the market-oriented programming into our simulation. We create several Workflow Agents to plan feasible schedules for the work-flows according to the market prices of the resources and a Market Broker Agent to coordinate the simultaneous resources accesses.
We describe our system model and compare two methods -- probability and α-method -- with the centralized scheduling algorithm FCFS

Chapter 1 Introduction 1
1.1 What is Grid Computing 1
1.2 An Example for Illustration 3
1.3 Potential Problems of Grid Computing 4
1.4 Motivation 5
1.5 Related Work 7
Condor/Condor-G 7
Acution/Combinatorial Auction 8
1.6 Problem Definition 10
1.7 Market-Oriented Programming 12
1.7.1 What is Market-Oriented Programming 12
1.7.2 Why to Use Market-Oriented Programming 13
1.8 Ogranization of Thesis 14
Chapter 2 Market Model and System Architecture 15
2.1 Revised Market-Oriented Programming 15
2.1.1 Definition and Assumption 15
2.1.2 Market Model 16
2.1.3 Utility Function of a Work-flow Agent 18
2.1.4 Market-Price Adjustment 19
2.2 System Architecture 20
2.2.1 Architecture 20
2.2.2 Components 22
Information Service Agent 22
Resource Provider Agent 22
Market Broker Agent 23
Work-flow Agent 24
Chapter 3 Experiment and Discussion 29
3.1 Implementation 29
3.2 Experimant and Discussion 31
Chapter 4 Conclusion and Future Work 38
Reference 41
Appendix The Work-flow Representation XML Content 43

1. Ian Foster, Carl Kesselman, Jeffrey M. Nick, Steven Tuecke. The Physiology of the
Grid: An Open Grid Services Architecture for Distributed Systems Integration.
Open Grid Service Infrastructure WG, Global Grid Forum, June 22, 2002.
2. Ian Foster, Carl Kesselman, Steven Tuecke, The Anatomy of the Grid: Enabling
Scalable Virtual Organizations, International Journal of Supercomputer
Applications and High Performance Computing, 2001
3. Ian Foster, Carl Kesselman, The Grid: Blueprint for a New Computing
Infrastructure, 2nd Edition. Morgan Kaufmann, ISBN:1-55860-933-4, 2004.
4. Mario Cannataro, Domenico Talia, and Paolo Trunfio, Distributed data mining on
the grid, Future Generation Computer Systems, volume 18, pages 1101-1112, 2002
5. The Condor Project, http://www.cs.wisc.edu/condor/
6. Rajesh Raman, Miron Livny, and Marvin Solomon, Matchmaking: Distributed
Resource Management for High Throughput Computing, Proceedings of the
Seventh IEEE International Symposium on High Performance Distributed
Computing, 1998
7. James Frey, Todd Tannenbaum, Ian Foster, Miron Livny, and Steven Tuecke,
Condor-G: A Computation Management Agent for Multi-Institutional Grids,
Journal of Cluster Computing, volume 5, pages 237-246, 2002.
8. Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial
auctions, Artificial Intelligence, volume 135, pages 1-54, 2002
9. David C. Parkes, iBundle: An Efficient Ascending Price Bundle Auction,
Proceedings of the 1st ACM conference on Electronic commerce, 1999
10.Luke Hunsberger, Barbara J. Grosz, A Combinatorial Auction for Collaborative
Planning, In Proceedings of the Fourth International Conference on Multi-Agent
Systems, IEEE Computer Society Press, pages 151-158, 2000
11.Michael P. Wellman, William E. Walsh, Auction Protocols for Decentralized
Scheduling, Games and Economic Behavior, volume 35, pages 271-303, 2001
12.Gerhard Weiss, Multiagent Systems: A Modern Approach to Decentralized
Artificial Intelligence, pages 201-233, MIT Press, ISBN: 0262731312, 2000
13.Michael P. Wellman, Market-Oriented Programming: Some Early Lessons,
Market-Based Control: A Paradigm for Distributed Resource Allocation, World
Scientific, 1996.
14.Andreu Mas-Colell, Michael Whinston, and Jerry R. Green, Microeconomic
Theory, Oxford University Press, ISBN:0195073401, 1995
15.The DataGrid Project, http://eu-datagrid.web.cern.ch/eu-datagrid/
16.GriPhyN, the Grid Physics Network, http://www.griphyn.org/
17.Michael P. Wellman, A Market-Oriented Programming Environment and its
Application to Distributed Multicommodity Flow Problems, Journal of Artificial
Intelligence Research, volume 1, pages 1-23, 1993
18.M. Johnson, P. Chang, J. Bradshaw, M. Breedy, L. Bunch, S. Kulkarni, J. Lott, N.
Suri, A. Uszok, and Von-Wun Soo, Kaos Semantic Policy and Domain Services:
An Application of DAML to Web Services-Based Grid Architectures, AAMAS
workshop on Web Services, 2003
19.Java Agent Development Framework, http://jade.tilab.com/