Prediction Model for Scheduling an Irregular Graph Algorithms on CPU–GPU Hybrid Cluster Framework

The improvement of innovations in science, technology and industry is happening in a current trend because of hybrid many-core Graphical processing units (GPUs), and multi-core central processing units (CPUs) based cluster. In this article, we have designed a prediction model using parameters such as computation and communication cost of irregular graph algorithms. To schedule irregular graph algorithms on the best set of processors of the hybrid cluster, we used our prediction models that predict the execution time of irregular graph algorithms and recorded as the performance history of the data. A reasonable set of data is used to educate the prediction model. The data forecasted by the model can be used and compared against actual runtimes to increase the accurateness of the model and decrease or eliminate any errors. We have tested our scheduling strategy using irregular graph algorithms Breadth-First Search(BFS) and Depth-first search(DFS) benchmark applications on the hybrid cluster. Our algorithm shows that up to 75.32% average performance improvement for BFS against TORQUE. Similarly, when compared to our predictive scheduling algorithm against TORQUE for DFS we achieved 89.68%. And 18.52% of average percentage prediction errors compared to the linear regression model.