In a heterogeneous distributed system composed of various types of computing platforms such as supercomputers, grids, and clouds, a two-level scheduling approach can be used to effectively distribute resources of the platforms to users in the first-level, and map tasks of the users in nodes for each platform in the second-level for executing many-task applications. When scheduling heterogeneous resources, service providers of the system should consider the fairness among multiple users as well as the system efficiency. However, the fairness cannot be achieved by simply distributing an equal amount of resources from each platform to every user. In this paper, we investigate how to address the fairness issue among multiple users in a heterogeneous distributed system. We present three first-level resource allocation policies of a provider affinity first policy, an application affinity first policy, and a platform affinity based round-robin policy, and two second-level task mapping policies of a most affected first policy and a co-runner affinity based round-robin policy. Using trace-based simulations, we evaluate the performance of various combinations of the first and second level scheduling policies. Our extensive simulation results demonstrate that the first-level policy plays a crucial role to achieve relatively good fairness.

We present EclipseMR, a novel MapReduce framework prototype that efficiently utilizes a large distributed memory in cluster environments. EclipseMR consists of double-layered consistent hash rings - a decentralized DHT-based file system and an in-memory key-value store that employs consistent hashing. The in-memory key-value store in EclipseMR is designed not only to cache local data but also remote data as well so that globally popular data can be distributed across cluster servers and found by consistent hashing. In order to leverage large distributed memories and increase the cache hit ratio, we propose a locality-aware fair (LAF) job scheduler that works as the load balancer for the distributed in-memory caches. Based on hash keys, the LAF job scheduler predicts which servers have reusable data, and assigns tasks to the servers so that they can be reused. The LAF job scheduler makes its best efforts to strike a balance between data locality and load balance, which often conflict with each other. We evaluate EclipseMR by quantifying the performance effect of each component using several representative MapReduce applications and show EclipseMR is faster than Hadoop and Spark by a large margin for various applications.

Summary In this paper, we conduct a comparative study of relatively simple yet effective scheduling policies for many‐task applications where multiple users with varying numbers of tasks are actively sharing a common system infrastructure. We have implemented three different scheduling mechanisms that can address fairness and user response time respectively in a common middleware stack called HTCaaS, which is a pilot‐job–based multi‐level scheduling system running on top of production‐level clusters. As a representative case of our many‐task applications, we have leveraged the virtual screening application, which is a computational technique used in drug discovery process to select the most promising candidate drugs for in vitro testing from millions of chemical compounds, which typically requires a substantial amount of computing resources and efficient processing of docking simulations. Our comparative experimental results of different scheduling policies show how we can effectively support multiple users in a shared resource environment by balancing between user satisfaction and overall system performance, provide guidelines to improve system utilization, and address additional technical challenges to support various many‐task applications.

Many-Task Computing (MTC) has been a new computing paradigm that aims to bridge the gap between traditional High-Throughput Computing (HTC) and High-Performance Computing (HPC). MTC applications from various scientific domains such as pharmaceuticals, astronomy, physics often consist of a very large number (from thousands to even billions) of data-intensive (tens of MB of I/O per second) tasks with relatively short per task execution times (from seconds to minutes). Each task in MTC applications may require relatively small amount of data processing especially compared to existing Big Data applications typically based on larger data block sizes (e.g. the default block size in Hadoop is 64MB). However, they can consist of much larger numbers of tasks where each task communicates through files instead of message passing interfaces such as MPI in HPC applications. Therefore, MTC can be another type of data-intensive workload where a large number of data processing tasks should be efficiently processed within a relatively short period of time. In this paper, we present design and implementation of MOHA (Many-task computing On HAdoop) which can make an effective convergence of MTC technologies and the existing Big Data platform Hadoop. MOHA is developed as a Hadoop YARN application so that it can transparently co-host existing MTC applications with other Big Data processing frameworks such as MapReduce in a single Hadoop cluster. Our evaluation results based on microbenchmark show that MOHA can substantially reduce the overall execution time of many-task processing with minimal amount of resources compared to an existing Hadoop YARN application. In addition, MOHA can efficiently dispatch a large number of tasks which can be crucial to support challenging MTC applications. MOHA can bring many interesting research issues related to data grouping and declustering on Hadoop Distributed File System (HDFS), scalable job/metadata management, dynamic task load balancing which can ultimately contribute to a new data processing framework in the YARN based Hadoop 2.0 ecosystem.

High-Throughput Computing (HTC) and Many-Task Computing (MTC) paradigms employ loosely coupled applications which consist of a large number, from tens of thousands to even billions, of independent tasks. To support such large-scale applications, a heterogeneous computing system composed of multiple computing platforms with different types such as supercomputers, grids, and clouds can be used. On allocating heterogeneous resources of the system to multiple users, there are three important aspects to consider: fairness among users, efficiency for maximizing the system throughput, and user satisfaction for reducing the average user response time. In this paper, we present three resource allocation policies for multi-user and multi-application workloads in a heterogeneous computing system. These three policies are a fairness policy, a greedy efficiency policy, and a fair efficiency policy. We evaluate and compare the performance of the three resource allocation policies over various settings of a heterogeneous computing system and loosely coupled applications, using simulation based on the trace from real experiments. Our simulation results show that the fair efficiency policy can provide competitive efficiency, with a balanced level of fairness and user satisfaction, compared to the other two resource allocation policies.

Recent emerging applications from a wide range of scientific domains often require a very large number of loosely coupled tasks to be efficiently processed. To support such applications effectively, all the available resources from different types of computing platforms such as supercomputers, grids, and clouds need to be utilized. However, exploiting heterogeneous resources from the platforms for multiple loosely coupled many-task applications is challenging, since the performance of an application can vary significantly depending on which platform is used to run it, and which applications co-run in the same node with it. In this paper, we analyze the platform and co-runner affinities of many-task applications in distributed computing platforms. We perform a comprehensive experimental study using four different platforms, and five many-task applications. We then present a two-level scheduling algorithm, which distributes the resources of different platforms to each application based on the platform affinity in the first level, and maps tasks of the applications to computing nodes based on the co-runner affinity for each platform in the second level. Finally, we evaluate the performance of our scheduling algorithm, using a trace-based simulator. Our simulation results demonstrate that our scheduling algorithm can improve the performance up to 30.0%, compared to a baseline scheduling algorithm.

Traditional High-Throughput Computing (HTC) consists of running many loosely-coupled tasks that are independent but requires a large amount of computing power during significant period of time. However, recent emerging applications requiring millions or even billions of tasks to be processed within a relatively short period of time have expanded the traditional HTC into Many-Task Computing (MTC).In silico drug discovery offers an efficient alternative to reduce the cost of drug development and discovery process. For this purpose, virtual screening is used to select the most promising candidate drugs for in vitro testing from millions of chemical compounds. This process requires a substantial amount of computing resources and high-performance processing of docking simulations, which shows the typical characteristics of MTC applications. As the number of users performing this virtual screening process increases with limited available computing resources, it becomes crucial to devise an effective scheduling policy that can ensure a certain degree of fairness and user satisfaction. In this paper, we present a comparative analysis of scheduling mechanisms for the virtual screening workflow where multiple users in the system are sharing a common service infrastructure. To effectively support these multiple users, the underlying system should be able to consider fairness, user response time and overall system throughput. We have implemented two different scheduling algorithms which can address fairness and user response time respectively in a common middleware stack call edHTCaaS which is a pilot-job based multi-level scheduling system running on top of a dedicated production-level cluster. Throughout comparative analysis of two different scheduling mechanisms targeting different metrics on top of a single H/W and S/W system, we can give an insight to the research community on the design and implementation of a scheduling mechanism that can trade-off user fairness and overall system performance which's crucial to support challenging MTC applications.

We present some recent and ongoing work in our decentralized desktop computing grid project. Specifically, we discuss matching jobs with compute nodes in a peer-to-peer grid of heterogeneous platforms, and the implementation of our algorithms in a concrete system.

Desktop grids have evolved to combine Peer-to-Peer and Grid computing techniques to improve the robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.

The goal of the work described in this paper is to design and build a scalable infrastructure for executing grid applications on a widely distributed set of resources. Such grid infrastructure must be decentralized, robust, highly available, and scalable, while efficiently mapping application instances to available resources in the system. However, current desktop grid computing platforms are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. Fortunately, these problems can be addressed through the capabilities promised by new techniques and approaches in peer-to-peer (P2P) systems. By employing P2P services, our system allows users to submit jobs to be run in the system and to run jobs submitted by other users on any resources available in the system, essentially allowing a group of users to form an ad-hoc set of shared resources. The initial target application areas for the desktop grid system are in astronomy and space science simulation and data analysis.

Our goal is to design and build a scalable infrastructure for executing desktop grid applications on a widely distributed set of resources, employing Peer-to-Peer services for robustness and scalability. As such a system scales to large configurations and heavy workloads it becomes a challenging problem to efficiently match jobs with different resource requirements to available heterogeneous computational resources, to provide good load balancing, and to obtain high system throughput and low job turnaround times.We propose two novel approaches to job scheduling and efficient resource matching, a Rendezvous Node Tree and a Content-Addressable Network (CAN) based algorithms. We have performed a comparative analysis of these two different approaches, to give insight into the design and implementation of scalable resource discovery algorithms in a distributed and heterogeneous grid environment.The poster will describe the overall structure of our matchmaking frameworks and provide performance results obtained via simulations and a preliminary peer implementation.