Towards minimum WCRT bound for DAG tasks under prioritized list scheduling algorithms

• Many modern real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Recent studies show that the worst-case response time (WCRT) bound of a DAG task can be significantly reduced when the execution order of the vertices is determined by the priority assigned to each vertex of the DAG. How to obtain the optimal vertex priority assignment, and how far from the best-known WCRT bound of a DAG task to the minimum WCRT bound are still open problems. In this paper, we aim to construct the optimal vertex priority assignment and derive the minimum WCRT bound for the DAG task. We encode the priority assignment problem into an integer linear programming (ILP) formulation. To solve the ILP model efficiently, we do not involve all variables or constraints. Instead, we solve the ILP model iteratively, i.e., we initially solve the ILP model with only a few primary variables and constraints, and then at each iteration, we increment the ILP model with the variables and constraints which are more likely to derive the optimal priority assignment. Experimental work shows that our method is capable of solving the ILP model optimally without involving too many variables or constraints, e.g., for instances with 50 vertices, we find the optimal priority assignment by involving 12.67% variables on average and within several minutes on average.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Engineering (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

NATURVETENSKAP  -- Fysik -- Annan fysik (hsv//swe)

NATURAL SCIENCES  -- Physical Sciences -- Other Physics Topics (hsv//eng)

Nyckelord

directed acyclic graph

integer linear programming

Multicore processing

Parallel processing

prioritized list scheduling

Real-time systems

response time bound

Scheduling algorithms

Sun

Task analysis

Time factors

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)