Combined task and message scheduling in distributed real-time systems. Abdelzaher, T. & Shin, K. IEEE Transactions on Parallel and Distributed Systems, 10(11):1179–1191, November, 1999. doi abstract bibtex The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B & B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.
@article{abdelzaher1999Combined,
title = {Combined task and message scheduling in distributed real-time systems},
volume = {10},
issn = {2161-9883},
doi = {10.1109/71.809575},
abstract = {The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B \& B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.},
number = {11},
journal = {IEEE Transactions on Parallel and Distributed Systems},
author = {Abdelzaher, Tarek and Shin, Kang},
month = nov,
year = {1999},
keywords = {CPU utilizations, Computer Society, Concurrent computing, Costs, Delay, Message passing, Optimal scheduling, Processor scheduling, Real time systems, Scheduling algorithm, System recovery, application concurrency, application domain, branch-and-bound technique, combined task/message scheduling, communicating tasks, distributed hard real time systems, distributed real-time systems, exclusion constraints, feasible schedule, greedy heuristic, intertask interactions, maximum task lateness, message passing, message scheduling, offline scheduling, optimal solution, optimal task schedule, processor scheduling, real time channel, real-time systems, resource-constraint model, search tree, simulation study, system size, task completion time, task deadline, task schedule, time bounded communication paradigm, tree searching},
pages = {1179--1191}
}
Downloads: 0
{"_id":"qWCGvJpjDTGGYx6im","bibbaseid":"abdelzaher-shin-combinedtaskandmessageschedulingindistributedrealtimesystems-1999","authorIDs":[],"author_short":["Abdelzaher, T.","Shin, K."],"bibdata":{"bibtype":"article","type":"article","title":"Combined task and message scheduling in distributed real-time systems","volume":"10","issn":"2161-9883","doi":"10.1109/71.809575","abstract":"The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B & B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.","number":"11","journal":"IEEE Transactions on Parallel and Distributed Systems","author":[{"propositions":[],"lastnames":["Abdelzaher"],"firstnames":["Tarek"],"suffixes":[]},{"propositions":[],"lastnames":["Shin"],"firstnames":["Kang"],"suffixes":[]}],"month":"November","year":"1999","keywords":"CPU utilizations, Computer Society, Concurrent computing, Costs, Delay, Message passing, Optimal scheduling, Processor scheduling, Real time systems, Scheduling algorithm, System recovery, application concurrency, application domain, branch-and-bound technique, combined task/message scheduling, communicating tasks, distributed hard real time systems, distributed real-time systems, exclusion constraints, feasible schedule, greedy heuristic, intertask interactions, maximum task lateness, message passing, message scheduling, offline scheduling, optimal solution, optimal task schedule, processor scheduling, real time channel, real-time systems, resource-constraint model, search tree, simulation study, system size, task completion time, task deadline, task schedule, time bounded communication paradigm, tree searching","pages":"1179–1191","bibtex":"@article{abdelzaher1999Combined,\n\ttitle = {Combined task and message scheduling in distributed real-time systems},\n\tvolume = {10},\n\tissn = {2161-9883},\n\tdoi = {10.1109/71.809575},\n\tabstract = {The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B \\& B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.},\n\tnumber = {11},\n\tjournal = {IEEE Transactions on Parallel and Distributed Systems},\n\tauthor = {Abdelzaher, Tarek and Shin, Kang},\n\tmonth = nov,\n\tyear = {1999},\n\tkeywords = {CPU utilizations, Computer Society, Concurrent computing, Costs, Delay, Message passing, Optimal scheduling, Processor scheduling, Real time systems, Scheduling algorithm, System recovery, application concurrency, application domain, branch-and-bound technique, combined task/message scheduling, communicating tasks, distributed hard real time systems, distributed real-time systems, exclusion constraints, feasible schedule, greedy heuristic, intertask interactions, maximum task lateness, message passing, message scheduling, offline scheduling, optimal solution, optimal task schedule, processor scheduling, real time channel, real-time systems, resource-constraint model, search tree, simulation study, system size, task completion time, task deadline, task schedule, time bounded communication paradigm, tree searching},\n\tpages = {1179--1191}\n}\n\n","author_short":["Abdelzaher, T.","Shin, K."],"key":"abdelzaher1999Combined","id":"abdelzaher1999Combined","bibbaseid":"abdelzaher-shin-combinedtaskandmessageschedulingindistributedrealtimesystems-1999","role":"author","urls":{},"keyword":["CPU utilizations","Computer Society","Concurrent computing","Costs","Delay","Message passing","Optimal scheduling","Processor scheduling","Real time systems","Scheduling algorithm","System recovery","application concurrency","application domain","branch-and-bound technique","combined task/message scheduling","communicating tasks","distributed hard real time systems","distributed real-time systems","exclusion constraints","feasible schedule","greedy heuristic","intertask interactions","maximum task lateness","message passing","message scheduling","offline scheduling","optimal solution","optimal task schedule","processor scheduling","real time channel","real-time systems","resource-constraint model","search tree","simulation study","system size","task completion time","task deadline","task schedule","time bounded communication paradigm","tree searching"],"downloads":0},"bibtype":"article","biburl":"https://bibbase.org/zotero/romain_jacob","creationDate":"2020-03-11T17:05:50.101Z","downloads":0,"keywords":["cpu utilizations","computer society","concurrent computing","costs","delay","message passing","optimal scheduling","processor scheduling","real time systems","scheduling algorithm","system recovery","application concurrency","application domain","branch-and-bound technique","combined task/message scheduling","communicating tasks","distributed hard real time systems","distributed real-time systems","exclusion constraints","feasible schedule","greedy heuristic","intertask interactions","maximum task lateness","message passing","message scheduling","offline scheduling","optimal solution","optimal task schedule","processor scheduling","real time channel","real-time systems","resource-constraint model","search tree","simulation study","system size","task completion time","task deadline","task schedule","time bounded communication paradigm","tree searching"],"search_terms":["combined","task","message","scheduling","distributed","real","time","systems","abdelzaher","shin"],"title":"Combined task and message scheduling in distributed real-time systems","year":1999,"dataSources":["GSdyza34Yogv8tQFT"]}