Zhu, Huanzhou (2016) Developing graph-based co-scheduling algorithms with GPU acceleration. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Zhu_2016.pdf - Submitted Version - Requires a PDF viewer. Download (2611Kb) | Preview

Request Changes to record.

Abstract

On-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes the performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the performance degradation. Most existing contention-aware co-schedulers only consider serial jobs. However, there often exist both parallel and serial jobs in computing systems. This thesis aims to tackle these issues. We start with modelling the problem of co-scheduling the mix of serial and parallel jobs as an Integer Programming (IP) problem. Then we construct a co-scheduling graph to model the problem, and a set of algorithms are developed to find both optimal and near-optimal solutions. The results show that the proposed algorithms can find the optimal co-scheduling solution and that the proposed approximation technique is able to find the near optimal solutions. In order to improve the scalability of the algorithms, we use GPU to accelerate the solving process. A graph processing framework, called WolfPath, is proposed in this thesis. By taking advantage of the co-scheduling graph, WolfPath achieves significant performance improvement. Due to the long preprocessing time of WolfPath, we developed WolfGraph, a GPU-based graph processing framework that features minimal preprocessing time and uses the hard disk as a memory extension to solve large-scale graphs on a single machine equipped with a GPU device. Comparing with existing GPU-based graph processing frameworks, WolfGraph can achieve similar execution time but with minimal preprocessing time.

Item Type:	Thesis or Dissertation (PhD)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH):	Multiprocessors, Parallel processing (Electronic computers), Cache memory, Graphics processing units, Computer systems -- Evaluation, Computer scheduling, Integer programming
Official Date:	May 2016
Dates:	Date Event May 2016 Submitted
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	He, Ligang
Format of File:	pdf
Extent:	xvii, 198 leaves : illustrations, charts
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads