| In this dissertation, a new scheduling scheme called Osculant is studied. The Osculant scheduler is bottom-up, self-organized, and designed for distributed heterogeneous computing systems. In the first part of the dissertation, performance evaluations of uniform latency communication (UCL) and non-uniform latency communication (NUCL) networks are performed. By studying the analytical model and simulation results of UCL networks, we found that network performance can be predictable if the job arrival rate is known in advance. However, UCL networks' high cost growth rate prohibits it from being applied in general distributed computing systems. Conversely, NUCL networks are more scalable and economical but are more difficult to predict the communication performance. Studies show that locality properties are the keys to improve performance of NUCL systems. In the Osculant, we develop new techniques in exploiting localities embedded in the applications and systems.; Several new dynamic bidding strategies were introduced and investigated. Compared to the top-down scheduling scheme, the performance-bidding and energy-based bidding methods improve the system throughput rate and average job energy consumption rate. Multiple-bid methods are developed to further improve the performance of single-bid strategies (e.g., the performance- and energy-based bidding methods). Dynamic Jobpost Bidding Model and Resource Contractor Bidding Model are the two examples of this category. Experimental results show very promising performance growth over the single-bid methods. It is also found that system ethos can be altered to suit the user demands and environmental changes by choosing different bidding methods. Moreover, with multiple-bid methods, system status information is progressively gathered through multiple job announcement and bidding processes. It is shown that scheduling overheads, can be effectively reduced by this scheme.; The Osculant Job Profile Generator (JPG) generates job profiles on-line so that other nodes can estimate resource requirements and job completion cost. The Multi-layer Jobpost Protocol (MJP) is developed to announce jobs to the computing system. The MJP is found to be robust and self-regulated. Studies of other modules in the Osculant Shell reveal even more potential of the Osculant scheduling scheme. |
