The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms

Current formal models of real-time workloads were designed within the context of uniprocessor real-time systems; hence, they are often not able to accurately represent salient features of multiprocessor real-time systems. Researchers have recently attempted to overcome this shortcoming by applying w...

Full description

Saved in:

Bibliographic Details
Main Author:	Chuprat, Suriayati
Format:	Thesis
Language:	English
Published:	2009
Subjects:	QA Mathematics
Online Access:	http://eprints.utm.my/id/eprint/13589/1/SuriayatiChupratPFS2009.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.13589
record_format	uketd_dc
spelling	my-utm-ep.135892018-10-14T07:23:42Z The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms 2009 Chuprat, Suriayati QA Mathematics Current formal models of real-time workloads were designed within the context of uniprocessor real-time systems; hence, they are often not able to accurately represent salient features of multiprocessor real-time systems. Researchers have recently attempted to overcome this shortcoming by applying workload models from Divisible Load Theory (DLT) to real-time systems. The resulting theory, referred to as Real-time Divisible Load Theory (RT-DLT), holds great promise for modeling an emergent class of massively parallel real-time workloads. However, the theory needs strong formal foundations before it can be widely used for the design and analysis of real-time systems. The goal of this thesis is to obtain such formal foundations, by generalizing and extending recent results and concepts from multiprocessor real-time scheduling theory. To achieve this, recent results from traditional multiprocessor scheduling theory were used to provide satisfactory explanations to some apparently anomalous observations that were previously made upon applying DLT to real-time systems. Further generalization of the RT-DLT model was then considered: this generalization assumes that processors become available at different instants of time. Two important problems for this model were solved: determining the minimum number of processors needed to complete a job by its deadline; and determining the earliest completion time for a job upon a given cluster of such processors. For the first problem, an optimal algorithm called MINPROCS was developed to compute the minimum number of processors that ensure each job completes by its deadline. For the second problem, a Linear Programming (LP) based solution called MIN-� was formulated to compute the earliest completion time upon given number of processors. Through formal proofs and extensive simulations both algorithms have been shown to improve the nonoptimal approximate algorithms previously used to solve these problems. 2009 Thesis http://eprints.utm.my/id/eprint/13589/ http://eprints.utm.my/id/eprint/13589/1/SuriayatiChupratPFS2009.pdf application/pdf en public phd doctoral Universiti Teknologi Malaysia, Faculty of Science Faculty of Science
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA Mathematics
spellingShingle	QA Mathematics Chuprat, Suriayati The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
description	Current formal models of real-time workloads were designed within the context of uniprocessor real-time systems; hence, they are often not able to accurately represent salient features of multiprocessor real-time systems. Researchers have recently attempted to overcome this shortcoming by applying workload models from Divisible Load Theory (DLT) to real-time systems. The resulting theory, referred to as Real-time Divisible Load Theory (RT-DLT), holds great promise for modeling an emergent class of massively parallel real-time workloads. However, the theory needs strong formal foundations before it can be widely used for the design and analysis of real-time systems. The goal of this thesis is to obtain such formal foundations, by generalizing and extending recent results and concepts from multiprocessor real-time scheduling theory. To achieve this, recent results from traditional multiprocessor scheduling theory were used to provide satisfactory explanations to some apparently anomalous observations that were previously made upon applying DLT to real-time systems. Further generalization of the RT-DLT model was then considered: this generalization assumes that processors become available at different instants of time. Two important problems for this model were solved: determining the minimum number of processors needed to complete a job by its deadline; and determining the earliest completion time for a job upon a given cluster of such processors. For the first problem, an optimal algorithm called MINPROCS was developed to compute the minimum number of processors that ensure each job completes by its deadline. For the second problem, a Linear Programming (LP) based solution called MIN-� was formulated to compute the earliest completion time upon given number of processors. Through formal proofs and extensive simulations both algorithms have been shown to improve the nonoptimal approximate algorithms previously used to solve these problems.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Chuprat, Suriayati
author_facet	Chuprat, Suriayati
author_sort	Chuprat, Suriayati
title	The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
title_short	The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
title_full	The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
title_fullStr	The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
title_full_unstemmed	The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
title_sort	deadline-based scheduling of divisible real-time workloads on multiprocessor platforms
granting_institution	Universiti Teknologi Malaysia, Faculty of Science
granting_department	Faculty of Science
publishDate	2009
url	http://eprints.utm.my/id/eprint/13589/1/SuriayatiChupratPFS2009.pdf
_version_	1747814964421197824

The deadline-based scheduling of divisible real-time workloads on multiprocessor platforms

Similar Items