A unified mapping framework for heterogeneous computing systems and computational grids

In Heterogeneous Computing (HC) systems and computational grids, a diverse set of geographically distributed resources is used to solve challenging problems. A major challenge in using these systems is to effectively use available resources. System resources are shared among applications. Applications are submitted from various user sites with specific quality of service requirements. One way to take advantage of HC systems is to decompose an application into several tasks based on the computational requirements. Different tasks may be best suited for different machines. Once the application is decomposed into tasks, each task needs to be assigned to a suitable machine (matching problem) and task executions need to be ordered in time (scheduling problem) to optimize a given objective function.; The focus of this dissertation is the matching and scheduling (defined as mapping) of application tasks onto HC systems and computational grids. We introduce a unified framework that can be used for mapping applications onto system resources. Our framework consists of four key components: system model, application model, mapping problem, and mapping algorithms. The framework incorporates the concept of advance reservation where system resources can be reserved in advance for specific time intervals. Our mapping algorithms are developed in such a way that all resource requirements are considered at the same time in a unified manner to achieve better mapping decisions.; Based on this framework, we develop efficient mapping algorithms for two novel problems. The first problem is mapping applications with multiple resource requirements and data replication. Our algorithms for this problem are of two types: level-by-level algorithms and greedy algorithms. The second problem is mapping a set of applications with resource co-allocation requirements. Application tasks have two types of constraints to be satisfied: precedence constraints and resource sharing constraints. Two different approaches are used to develop the heuristic algorithms: independent-set approach and critical-resource approach. For this mapping problem, we also develop a lower bound on the optimal schedule length. Performance evaluation shows the effectiveness of our mapping algorithms for both problems.