Scheduling Techniques in Resource Shared Large-Scale Clusters

Department of Computer Science and EngineeringTo support various types of applications submitted by multiple users, a large-scale cluster composed of different types of computing platforms, such as supercomputers, grids, and clouds, can be used. Since the applications have different characteristics and resource requirement and the computing platforms also have different hardware and execution environment, the fairness among the users cannot be guaranteed by simply distributing available resources to users equally. Since the applications submitted by multiple users are executed concurrently, the system performance depends on how these applications are scheduled on the cluster. Therefore, in order to effectively support the multiple users, the resource provider should consider the efficiency of the system not only but also the fairness among the users. In this thesis, we study how to achieve fairness among the users and improving system efficiency in the resource shared environment. First, we present the resource scheduling for multi-user and multi-application workload in heterogeneous distributed computing system. We evaluate the performance of loosely coupled applications used in real scientific domains and discuss the suitability of the heterogeneous distributed computing systems composed of multiple computing platforms from supercomputers, grids, and clouds. Then we propose the preference-based resource scheduling algorithm that improves system performance when the preferences of the applications have reflected the characteristics of the applications and the platforms properly. We also present the three resource allocation policies that address fairness, efficiency, and user satisfaction which is crucial metrics to evaluate the large-scale heterogeneous distributed computing systems for multi-user and multi-application workloads. To investigate the performance effects for the fairness by different scheduling decisions, we present a two-level scheduling algorithm that distributes resource by considering the affinity of each application to a platform and map tasks to a computing node by considering the affinity of each application to co-running applications. Our extensive simulation result shows that our resource scheduling algorithm effectively support the different types of challenging applications on the heterogeneous distributed computing systems. Second, we present Cache Affinity and Virtualization-Aware (CAVA) resource manager in Hadoop to efficiently utilize a scarce in-memory cache in a virtualized cluster for big-data analytics applications. CAVA measures the cache affinity of an application at runtime which represents the performance gain from the in-memory cache hit. To efficiently utilize a scarce in-memory cache, CAVA assigns high priority to applications that show high cache affinity and access popular input data. CAVA also leverages additional levels of data locality by considering the virtual machine topology. We also present FairCAVA, that achieves the fairness among multiple users when utilizing in-memory cache resources, for big-data analytics. In FairCAVA, to guarantee the fairness among the users, the users are assigned a portion of the in-memory cache, so that every user can utilize a certain amount of in-memory cache even if the access frequency of the file that the user accesses and the cache affinity of the applications that user executes are relatively low. Our experimental results show that CAVA resource manager efficiently utilizes the scarce in-memory cache based on the cache affinity of applications, and FairCAVA provides a higher level of fairness than CAVA with competitive system efficiency.clos