劉邦鋒臺灣大學：資訊工程學研究所許俊琛Hsu, Chun-ChenChun-ChenHsu2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/54041As cluster systems become increasingly popular, more and more paralle applications require need not only computing power but also significant I/O performance. However, the I/O subsystem has become the bottleneck of the overall system performance for years due to slower improvement of the second storage devices. In recent years parallel I/O has drawn an increasing attention as a promising approach to eliminate this bottleneck. To improve I/O efficiency of a cluster system computation tasks must be carefully assigned to processors, so that the communication overheads within the group the processors of the task, and those I/O traffics that connect processors of the task to I/O system are both optimized. Earlier processor allocation strategies considered the optimization of communication traffic or I/O traffic only. Since both the communication and I/O traffic can cause network contention, we develop two groups of algorithms -- binary tree based methods and Snake-Hilbert curve based methods, that address the issues of both communication and I/O traffics simultaneously. The experimental results indicate that for tasks that have different mixture of communication and I/O traffics, our algorithms have very good performance in terms of overall parallel I/O efficiency. We also developed two mathematical evaluating criteria -- ``compactness' and ``spatial compactness', to determine the fitness of allocation algorithms in terms of geometrical adjacency of processors. The theoretical results of these two criteria are also presented in this dissertation.Contents 1 Introduction 6 2 Communication Model 10 3 Algorithms 13 3.1 Binary-Tree Allocations Group . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1 Binary-Tree Allocation . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.2 Static Binary-Tree Allocation . . . . . . . . . . . . . . . . . . . . . 16 3.1.3 Dynamic Binary-Tree Allocation . . . . . . . . . . . . . . . . . . . . 16 3.1.4 Non-contiguous Binary-Tree Allocations . . . . . . . . . . . . . . . 17 3.2 Snake-Hilbert Allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1 Snake-Hilbert Allocation . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.2 Mirrored Snake-Hilbert Allocation . . . . . . . . . . . . . . . . . . . 22 4 Compact Allocation 24 4.1 Multiple Buddy Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Spatially Compact Allocation . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2.1 Spatially Compact Binary Tree Allocation . . . . . . . . . . . . . . 27 4.3 Compactness Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Experiments 30 5.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.1.1 Simulation Guidelines . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.1.2 Communication Patterns . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2.1 The Impacts of Con‾gurable Parameters . . . . . . . . . . . . . . . 31 5.2.2 Result Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Conclusions 39305597 bytesapplication/pdfen-US平行輸出入器配置叢集計算processor allocationparallel I/Othesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54041/1/ntu-93-R91922100-1.pdf