跳到主要內容

臺灣博碩士論文加值系統

(54.83.119.159) 您好!臺灣時間:2022/01/17 08:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:馬詠程
研究生(外文):Yung-Cheng Ma
論文名稱:兼顧負載與儲存量平衡的叢集Web伺服器資料配置
論文名稱(外文):Load and Storage Balanced Data Allocation for Clustered Web Server
指導教授:鍾崇斌
指導教授(外文):Chung-Ping Chung
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:160
中文關鍵詞:負載平衡儲存量平衡平行資訊檢索
外文關鍵詞:load balancingstorage balancingparallel information retrieval
相關次數:
  • 被引用被引用:0
  • 點閱點閱:208
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
本論文提出資料配置方法, 以設計合乎成本效益的叢集Web伺服器(clustered Web server). 最近幾年, 許多熱門網站使用大型叢集系統(cluster), 以儲存大量資料並滿足效能需求. 這些叢集系統的主要應用為作為資訊檢索系統(information retrieval)及檔案伺服器. 網際網路的迅速成長帶來了新的挑戰: 資料配置須對執行效能與儲存空間作整體的考量, 且須有計量方法以設計大型叢集系統. 針對上述挑戰, 本論文將探討下列研究議題:
(1) 平行程式工作配置演算法,
(2) 用於平行資訊檢索系統上的posting file切割方法,
(3) 兼顧覆載與儲存量平衡的資料配置方法.
利用這些研究結果, 我們將發展出設計叢集系統的計量方法, 以盡量少的成本滿足效能需求.
第一個議題是要提出能獲得最佳解的演算法, 將平行程式分配到多個處理機上. 平行程式以點(node)與連線(edge)皆帶有weight的task graph表示之. 此工作配置演算法的目的, 是要考慮負載平衡(load balancing)與通訊負擔(communication overhead), 以降低平行程式的執行時間. 我們提出branch-and-bound演算法以循找最佳解. 此演算法偵測task graph中的群聚性質, 以減少搜尋空間.實驗結果顯示, 與A*-algorithm相比, 所提的pruning rule能有效的減少搜尋空間.
在第二個研究主題中, 我們針對平行資訊檢索系統, 提出 posting file切割方法. 叢集系統利用分散在各工作站上的posting file, 以平行計算的方式處理query. 此演算法的目的, 是要降低處理query的平均時間. 此演算法依據 document-ID 進行切割, 使得在平行處理query的時候, 不須在工作站間傳遞posting. 我們建立機率模型, 將切割posting file轉化為追求負載平衡的工作配置問題. 第一個研究主題所提的演算法將可用於尋求最佳解. 我們並提出逼近演算法, 以polynomial time切割posting file, 並以實驗檢驗提出的切割方法.
第三個研究主題提出兼顧負載與與儲存量平衡的資料配置演算法. 此演算法將大小不同的許多資料項目分配到各工作站上. 其理論基礎是 MMPacking演算法. MMPacking分配與複製相同大小的資料項目, 以追求負載與儲存量平衡. 我們的主要構想, 是利用 bin packing 將問題化簡成MMPacking所處理的問題. 我們並證明所提的演算法是 asymptotical 1-optimal. 當問題規模夠大時, 所得的結果接趨近於最佳解.
利用所提的資料配置演算法, 我們提出計量方法, 以設計合乎成本效益的叢集Web伺服器. 此計量方法的目的, 是要降低滿足效能需求所需的硬體成本.硬體成本由工作站數量, 及每部工作站的儲存空間大小決定.為了達到此目的, 須兼顧負載與儲存量平衡. 我們建立效能模型, 以計算 throughput 與 response time.此計量方法大幅簡化設計大型叢集系統的方法.

This dissertation proposes methodologies to design a cost-effective
clustered Web server.
In recent years,
many major Web sites use large-scale clusters to cope with high
request arrival rate and store huge amount of data.
The clustered system is to serve as an information retrieval system or
a file server.
The growth of Internet usage brings the new challenges:
both high performance and storage efficiency has to be considered, and
a quantitative method is desired to design a large-scale cluster.
Research topics to tackle these challenges are
(1) load balancing for communicated tasks,
(2) posting file partitioning for parallel information retrieval,
and
(3) load and storage balanced data allocation for variable-size
items.
The final results are quantitative methods to minimize the hardware cost
of the cluster subject to given performance requirements.
The first topic is to propose an exact algorithm for allocating communicating
tasks onto parallel processors.
A parallel program is modeled as a node- and edge-weighted task graph.
The task allocation problem is to assign tasks to processors.
The objective is to minimize the execution time of the parallel program,
considering both load balancing and communication overhead.
We propose a branch-and-bound algorithm to find an optimal assignment.
The efficiency of the algorithm comes from that we apply task-clustering
based pruning rule to reduce the search space to be traversed.
The experiment shows that, comparing to the A*-algorithm,
the pruning rule reduces the search space significantly.
The second topic is to propose posting file partitioning algorithm for
parallel information retrieval.
A query is processed in parallel using a partitioned posting file distributed
on a cluster of workstations.
The objective is to minimize the average query processing time.
Our approach is as follows.
The partitioning follows the partition-by-document-ID principle such that,
during parallel query processing,
no postings are transferred between workstations.
Probability model is established to formulate posting file partitioning
as task allocation for load balancing.
Optimal solution can be found by the proposed algorithm for the first issue.
Heuristic algorithms are proposed to generate a partitioned posting file
in polynomial time.
Experiment shows that the simple heuristics achieve almost linear speedup.
The third topic is to propose approximate algorithms for load and storage
balanced data allocation.
The algorithms allocate variable-size items onto identical workstations.
The objective is to minimize storage requirement per workstation subject
to a load balancing constraint.
Two algorithms are proposed: one allows item replications and the other
does not.
Our approach is as follows.
The foundation is MMPacking which allocates and replicates identical-size
items for load and storage balancing.
The key idea of our proposed algorithms is problem reduction to
MMPacking using bin packing.
For each of the proposed algorithm,
we prove that the load balancing constraint is satisfied with
asymptotically 1-optimal storage cost.
That is, when problem-scale exceeds certain threshold,
the proposed algorithms generate almost-optimal solutions.
These proposed algorithms result in quantitative method to design a
cost-effective clustered Web server.
The quantitative method determines cluster configuration from statistical
data.
The objective is to minimize the hardware cost of the cluster subject to
given performance requirements.
Hardware cost of the cluster depends on the number of workstations and
storage capacity of a workstation in the cluster.
To achieve the objective, both load and storage balancing are required.
Performance models are established to calculate throughput and response time
from data allocation.
Due to the differences on data allocation and request distribution features,
performance models are established for parallel information retrieval
and clustered file server separately.
The quantitative method greatly simplifies the methodology of designing
large-scale clusters.
This research makes cost-management possible for Internet business.

1. Introduction
2. Optimal Task Allocation
3. Posting File Partitioning for Parallel Information Retrieval
4. Load and Storage Balanced Data Allocation
5. Quantitative Method for Information Retrieval System Design
6. Quantitative Method for Clustered File Server Design

Bibliography
[1] Google search engine (http://www.google.com)."
[2] W. B. Frakes and R. Baeza-Yates, Information Retrieval: Data Structures and
Algorithms. 1992.
[3] K. Hwang and Z. Xu, Scalable Parallel Computing: Technology, Architecture, and
Programming. 1997.
[4] E. G. Coffman, M. R. Garey, and D. S. Johnson, An application of bin-packing to
multiprocessor scheduling," SIAM Journal on Computing, Vol. 7, No. 1, pp. 1-17,
1978.
[5] H. S. Stone, Multiprocessor scheduling with the aid of network algorithms,"
IEEE Transactions on Software Engineering, Vol. SE-3, No. 1, pp. 85-94, 1979.
[6] P. Y. Richard, E. Y. S. Lee, and M. Tsuchiya, A task allocation model for dis-
tributed computing systems," IEEE Transactions on Computers, Vol. C-31, No. 1,
pp. 41-47, 1982.
[7] W. Dowdy and D. Foster, Comparative models of the file assignment problem,"
ACM Computing Surveys, Vol. 14, No. 2, pp. 287-313, 1982.
[8] B. Wah, File placement on distributed computer systems," Computer, Vol. 17,
No. 1, pp. 23-32, 1984.
[9] C. C. Shen and W. H. Tsai, A graph matching approach to optimal task assignment
in distributed computing systems using a minimax criterion," IEEE Transactions
on Computers, Vol. C-34, No. 3, pp. 197-203, 1985.
[10] J. B. Sinclair, Efficient computation of optimal assignment for distributed tasks,"
Journal of Parallel and Distributed Computing, Vol. 4, pp. 342-362, 1987.
[11] V. M. Lo, Heuristic algorithms for task assignment in distributed systems," IEEE
Transactions on Computers, Vol. 37, No. 11, pp. 1384-1397, 1988.
[12] J. Wolf and K. Pattipati, A file assignment problem model for extended local
area network environments," Proceedings of 10th International Conference on Dis-
tributed Computing Systems, Vol. 17, No. 1, 1990.
[13] A. Billionnet, M. C. Costa, and A. Sutter, An efficient algorithm for a task alloca-
tion problem," Journal of the Association for Computing Machinery, Vol. 39, No.
3, pp. 502-518, 1992.
[14] N. S. Bowen, C. N. Nikolaou, and A. Ghafoor, On the assignment problem of ar-
bitrary process systems to heterogeneous distributed systems," IEEE Transactions
on Computers, Vol. 41, No. 3, pp. 257-273, 1992.
[15] D. Rotem, G. Schloss, and A. Segev, Data allocation of multi-disk databases,"
IEEE Trans. Knowledge and Data Engineering, Vol. 5, No. 5, pp. 882-877, 1993.
[16] C. M. Woodside and G. G. Monforton, Fast allocation of processes in distributed
and parallel systems," IEEE Transactions on Parallel and Distributed Systems,,
Vol. 4, No. 2, pp. 164-174, 1993.
[17] D. T. Peng and K. G. Shin, Optimal scheduling of cooperative tasks in a dis-
tributed system using an enumerative method," IEEE Transactions on Software
Engineering, Vol.19 , No. 3, pp. 253-267, 1993.
[18] H. C. Chou and C. P. Chung, An optimal instruction scheduler for superscalar
processor," IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 3,
pp. 303-313, 1995.
[19] T. D. C. Little and D. Venkatesh, Popularity-based assignment of movies to storage
devices and video-on-demand system," ACM/Springer Multimedia System, Vol. 2,
No. 6, pp. 280-287, 1995.
[20] H. Lee and T. Park, Allocating data and workload among multiple servers in a
local area network," Information Systems, Vol. 20, No. 3, 1995.
[21] C. J. Hou and K. G. Shin, Allocation of periodic task modules with precedence
and deadline constraints in distributed real-time systems," IEEE Transactions on
Computers, Vol. 48, No. 12, pp. 1336-1356, 1997.
[22] C. C. Hui and S. T. Chanson, Allocating task interaction graphs to processors in
heterogeneous networks," IEEE Transactions on Parallel and Distributed Systems,
Vol. 8, No. 9, pp. 908-925, 1997.
[23] C. H. Lee and K. G. Shin, Optimal task assignment in homogeneous networks,"
IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 2, pp. 119-128,
1997.
[24] B. Narendran, S. Rangarajan, and S. Yajnik, Data distribution algorithm for load
balanced fault-tolerant web access," Proceedings of 16th Symposium on Reliable
Distributed Systems, pp. 97-106, 1997.
[25] D. N. Serpanos, L. Georgiadis, and T. Bouloutas, MMPacking: a load and storage
balancing algorithm for distributed multimedia servers," IEEE Trans. Circuits and
Systems for Video Technology, Vol. 8, No. 1, pp. 13-17, 1998.
156
[26] P. A. Tom and C. S. R. Murthy, Algorithms for reliability-oriented module allo-
cation in distributed computing systems," Journal of Systems and Software, Vol.
40, p. 1998, 125-138.
[27] M. Colajanni, P. S. Yu, and D. M. Dias, Analysis of task assignment policies
in scalable distributed web-server systems," IEEE Transactions on Parallel and
Distributed Systems, Vol. 9, No. 6, pp. 585-599, 1998.
[28] L. W. Lee, P. Scheuermann, and R. Vingralek, File assignment in parallel i/o
systems with minimal variance of service time," IEEE Transactions on Computers,
Vol. 49, No. 2, pp. 127-140, 2000.
[29] T. E. Anderson, M. D. Dahlin, J. M. Neefe, D. A. Patterson, and D. S. R. an d
R. Y. Wang, Serverless network file systems," ACM Transactions on Computer
Systems, Vol. 14, No. 1, pp. 41-79, 1996.
[30] J. H. Howard, M. L. Kazar, D. A. N. S. G. Menees, M. Satyanarayanan, R. . N.
Sidebotham, and M. J. West, Scale and performance in a distributed file system,"
ACM Transactions on Computer Systems, Vol. 6, No. 1, pp. 51-81, 1988.
[31] J. H. Hartman and J. K. Ousterhout, The zebra striped network file system,"
ACM Transactions on Computer Systems, Vol. 13, No. 3, pp. 274-310, 1995.
[32] V. S. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenepoel, and
E. Nahum, Locality-aware request distribution in cluster-based network servers,"
Proceedings of 8th Symposium on Architectural Support of Programming Languages
and Operating Systems, pp. 205-216, 1998.
[33] V. Cardellini, M. Colajanni, and P. S. Yu, Redirection algorithm for load sharing
in distributed web-server systems," Proceedings of 19th International Conference
on Parallel and Distributed Comput ing Systems, pp. 528-535, 1999.
[34] D. Kim, C. H. Park, and D. Park, Request rate adaptive dispatching architecture
for scalable internet server," Proceedings of International Conference on Cluster
Computing, pp. 289-296, 2000.
[35] L. Aversa and A. Bestavros, Load balancing a cluster of web servers using dis-
tributed packet rewriting," Proceedings of International Performance, Computing
and Communication Conferenc e, pp. 24-29, 2000.
[36] E. Casalicchio and S. Tucci, Static and dynamic scheduling algorithm for scal-
able web server farm," Proceedings of 9th Euromicro Workshop on Parallel and
Distributed Processing, pp. 369-376, 2001.
[37] E. Horowitz, S. Sahni, and B. Rajasekaran, Computer Algorithms/C++. 1996.
[38] H. El-Rewini, T. G. Lewis, and H. H. Ali, Task Scheduling in Parallel and Dis-
tributed Systems. 1994.
[39] R. Buyya, High Performance Cluster Computing Volume 1: Architectures and Sys-
tems. 1999.
[40] M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the
Theory of NP-Completeness. 1979.
[41] P. H. Hart, N. J. Nilsson, and B. Rapheal, A formal basis for the heuristic de-
termination of minimum cost paths," IEEE Transactions Systems and Cybernetics,
Vol. 4, No. 2, pp. 100-107, 1968.
[42] W. H. Kohler and K. Steiglitz, Characterization and theoretical comparison of
branch-and-bound algorithms for permutation problems," Journal of the Associa-
tion for Computing Machinery, Vol. 21, No. 1, pp. 140-156, 1974.
[43] C. Stanll and B. Kahle, Parallel free-text search on the connection machine sys-
tem," Communications of the ACM, Vol. 29, No. 12, pp. 1229-1239, 1986.
[44] J. K. Cringean, R. England, G. A. Manson, and P. Willett, Parallel text search-
ing in serial les using a processor farm," Proceedings of the 13th ACM SIGIR
Conference on Research and Development in Information Retrieval, pp. 429-445,
1990.
[45] D. K. Lee, Massive parallelism on the hybrid text-retrieval machine," Information
Processing and Management, Vol. 31, No. 6, pp. 815-830, 1995.
[46] H. S. Stone, Parallel querying of large databases: a case study," IEEE Computer,
pp. 11-21, 1987.
[47] G. Salton and C. Buckley, Parallel text search methods," Communications of the
ACM, Vol. 31, No. 2, pp. 202-215, 1988.
[48] C. Stanfill, Partitioned posting files: a parallel inverted file structure for informa-
tion retrieval," Proceedings of the 13th International Conference on Research and
Development in Information Retrieval, pp. 413-428, 1990.
[49] B. Mansand and C. Stanfill, An information retrieval test-bed on the cm-5," Pro-
ceedings of the 2nd Text REtrieval Conference, pp. 117-122, 1993.
[50] S. F. Reddaway, High speed text retrieval from large database on a massively par-
allel processor," Information Processing and Management, Vol. 27, No. 4, pp. 311-
316, 1991.
[51] B. S. Jeong and E. Omiecinski, Inverted file partitioning schemes in multiple disk
systems," IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 2,
pp. 142-153, 1995.
[52] B. A. Riberio-Neto, J. P. Kitajima, and G. Navarro, Parallel generation of in-
verted files for distributed text collections," Proceedings of the 18th International
Conference of the Chilean Society of Computer Science, pp. 149-157, 1998.
[53] I. H. Witten, A. Moffat, and T. C. Bell, Managing Gigabytes: Compressing and
Indexing on Documents and Images. 1999.
158
[54] A. Moffat and L. Stuiver, Exploiting clustering in inverted file compression," Pro-
ceedings of 1996 Data Compression Conference, pp. 82-91, 1996.
[55] G. Salton, Automatic Text Processing: the Transformation, Analysis, and Retrieval
of Information by Computer. 1989.
[56] G. Zipf Human Behavior and the Principle of Least Effort, 1949.
[57] P. Elias, Universal codeword sets and representations of the integers," IEEE Trans-
actions on Information Theory, Vol. IT-21, No. 2, pp. 194-203, 1975.
[58] J. Bently and A. C. C. Yao, An almost optimal algorithm for unbounded search-
ing," Information Processing Letters, Vol. 5, No. 3, pp. 82-87, 1976.
[59] S. W. Golumb, Run-length encodings," IEEE Transactions on Information The-
ory, Vol. IT-12, No. 3, pp. 399-401, 1966.
[60] V. P. Kumar, Introduction to Parallel Computing: Design and Analysis of Algo-
rithms. 1994.
[61] A. Arpaci-Dusseau, R. Arpaci-Dusseau, D. E. Culler, J. M. Hellerstein, and D. Pat-
terson, High performance sorting on networks of workstations," Proceedings of
1997 ACM SIGMOD Conference, 1997.
[62] A. Arpaci-Dusseau, R. Arpaci-Dusseau, D. E. Culler, J. M. Hellerstein, and D. Pat-
terson, Searching for the sorting record: experiences in tuning now-sort," Proceed-
ings of 1998 Symposium on Parallel and Distributed Tools, 1998.
[63] J. Hennessy and D. A. Patterson, Computer Architecture: a Quantitative Approach,
2nd edition. 1996.
[64] A. Moffat and J. Zobel, Self-indexing inverted files for fast text retrieval," ACM
Transactions on Information Systems, Vol. 14, No. 4, pp. 349-379, 1996.
[65] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, Worst-
case performance bounds for simple one-dimensional packing algorithms," SIAM
Journal on Computing, Vol. 3, No. 4, pp. 299-325, 1974.
[66] D. K. Hardman, Proceedings of TREC Text Retrieval Conference. 1992.
[67] R. Nelson, Probability, Stochastic Process, and Queueing Theory: the Mathematics
of Computer Performance Modeling. 1995.
[68] L. Kleinrock, Queueing Systems, Volume 1: Theory. 1975.
[69] T. M. Kroeger, J. Mogul, and C. Maltzahn,
ftp://ftp.digital.com/pub/dec/traces/proxy/webtraces.html," 1996.
[70] A. Tomasic and H. G. Molina, Performance of inverted indices in shared-nothing
distributed text document information retrieval systems," IEEE Transactions on
Parallel and Distributed Systems, Vol. 6, No. 2, pp. 142-153, 1995.
[71] I. J. Aalbersberg and F. Sijstermans, High quality and high performance full-
text document retrieval: the parallel infoguide system," Proceedings of the First
International Conference on Parallel and Distributed Information Systems, pp. 142-
150, 1991.
[72] J. Zobel, A. Moffat, and K. Ramamohanarao, Inverted files versus signature
files for text indexing," ACM Transactions on Database Systems, Vol. 23, No. 4,
pp. 453-490, 1998.
[73] C. Faloutsos, Access methods for text," ACM Computing Surveys, Vol. 17, No. 1,
pp. 49-74, 1985.
[74] S. H. Chung, S. C. Oh, K. R. Ryu, and S. H. Park, Parallel information retrieval on
a distributed memory multiprocessor system," Proceedings of the 3rd International
Conference on Algorithms and Architectures for Parallel Processing, pp. 163-176,
1997.
[75] A. MacFarlane, J. A. McCann, and S. E. Robertson, Parallel search using par-
titioned inverted files," Proceedings of the 7th International Symposium on String
Processing and Information Retrieval, pp. 209-220, 2000.
[76] A. N. Vo and A. Moffat, Compressed inverted file with reduced decoding over-
heads," Proceedings of the 21st ACM SIGIR Conference on Research and Develop-
ment in Information Retrieval, pp. 290-297, 1998.
[77] Y. C. Ma and C. P. Chung, A dominance relation enhanced branch-and-bound
task allocation," To appear in Journal of Systems and Software.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top