Research On Scheduling Algorithm For Parallel Programs Based On EasyHPS Under Cluster Environment

With the increasing volumes of objects and data processed in scientific research,there is more urgent demand for high performance computer. Currently at thehardware level, technology is already quite good for constructing parallel computingenvironment. While in the opposite, the technology of developing and designingparallel application at the software level is far behind.In order to simplify parallel programming and improve the efficiency to designparallel applications, a runtime system named EasyHPS which orient to the mixdistributed multi-core cluster environment has been designed and implemented by theHigh Performance Computing Lab, Tianjin University. EasyHPS is based on a set ofcustomized parallel programming model DAG data driven model and is used fordata-intensive applications. EasyHPS makes the programmers to focus on thealgorithm of a specific application by abstracting and encapsulating the parallel details,creating processes (threads), allocating data and scheduling tasks.On the other hand, scheduling is a very important issue in parallel computing. Adynamic scheduling mechanism has been adopted in EasyHPS, which may have agood load balancing but increases the overhead of runtime system. In addition, sinceEasyHPS is mainly used for dynamic programming algorithms with regular taskgraphs, dynamic scheduling mechanism is not the best choice for this type ofapplication. We have studied existing scheduling algorithms for parallel programs andpropose a new scheduling algorithms named HPS-FCSC which is used mainly for thespecific types of applications supported by EasyHPS.In the algorithm of HPS-FCSC, first sort ready tasks based on certain propertiesof them. In order to schedule tasks in well order, the relationship between the tasks’properties and the finish time must be considered. First sort tasks based on theproperty having the biggest influence on finish time. If there is a tie, then sort tasksbased on the property having smaller influence on finish time, and so on. Afterfinishing the ready task sorting, then begin to schedule tasks according to thecharacteristics of the DP algorithm in bioinformatics. The process of schedulingmakes reducing the scheduled length as the primary purpose and reducing thecommunication cost as the secondary purpose. This paper then compares the HPS-FCSC scheduling algorithm with the originaldynamic scheduling algorithm of EasyHPS by applying both on the Smith-Watermanalgorithm (including both SWLAG and SWGG). This experiment has proved thevalidity of HPS-FCSC algorithm in the system of EasyHPS. Simulation has also beenconducted in order to prove the effectiveness of HPS-FCSC algorithm in other typesof application. In the simulation, four other list scheduling algorithms has been usedin the parallel gaussian elimination programs as well as HPS-FCSC. The sameexperiment also conducted in other20randomly generated task graphs. Both resultsshow the effectiveness of HPS-FCSC.