An extension to DAG based scheduling for partial dependent tasks An Approach to optimize partial dependent tasks in a distributed system

摘要

Real time applications are now utilizing the computational power of multiprocessor and distributed systems [1] to improve their performance. Usually, these applications solve either data-intensive or compute-intensive problems. Applications executing on distributed systems provide faster response time than running on a stand-alone machine. For an application to execute on a distributed system it has to be decomposable into small and independent tasks, where a task is a single independent unit of execution. These tasks can be distributed to various nodes on a HPC[2] grid or cluster for faster execution. The task allocation to processors on a distributed or multiprocessor system is an NP hard problem [3] and determining an optimal solution has exponential complexity. Some problems cannot be completely decomposable into independent tasks due to the nature of application; this is due to the interdependencies of the tasks. Even if the application is not completely parallelizable, it will execute faster than executing it sequentially, if some of the tasks execute in parallel. As part of this paper, we describe an approach for scheduling tasks on a distributed environment by resolving the partial dependent tasks using the Directed Acyclic Graphs (DAG) [4] and Matrix Manipulation.