Scheduling parallel programs involving parallel database interactions

Abstract

In this study, we develop a new static scheduling scheme which integrates parallel programming environments with parallel database systems to optimize program execution. In parallel programming, a sequential program is first converted to a task graph either with programmer guidance or by a restructuring compiler. Next, a scheduling algorithm assigns the nodes of the task graph to processors. However a question arises when some tasks have to access a parallel database system. Our scheme extends static list scheduling approach to efficiently execute database accesses of parallel programs. To handle database interaction, input task graph is regenerated indicating task(s) with database interaction and these tasks are modified according to parallel database system characteristics (such as query type, database partitioning knowledge etc. ). Then the proposed algorithm runs on the expanded graph by using a new heuristic which is referred to as DTF (Database Task First). To prove the usefulness of our scheme we take the TPM (Task-to Processor Mapping) algorithm as the base. As a first step, TPM algorithm is modified to work on expanded task graph and highest priorities are always given to database tasks. Then some task graphs with database interaction are scheduled with the original TPM using the earliest task first heuristic and compared with the modified version. Early simulation results show that considering database interaction during scheduling and DTF heuristics drastically improve scheduling performance. It is also important to note that our scheme is not dependent on any specific scheduling algorithm and any algorithm can be modified to handle database interactions in the way proposed in this study.