Optimal Discrete Rate Adaptation for Distributed Real-Time Systems with End-to-End Tasks

Content Provider	Semantic Scholar
Author	Chen, Yingming Lu, Chenyang Koutsoukos, Xenofon D.
Copyright Year	2007
Abstract	Many distributed real-time systems face the challenge of dynamically maximizing system utility in response to fluctuations in system workload. We present the MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. The key novelty and advantage of MPRA is that it can efficiently produce optimal solutions in response to workload changes such as dynamic task arrivals. Through oline preprocessing MPRA transforms a NP-hard utility optimization problem to a set of simple linear functions in different regions expressed in term of CPU utilization changes caused by workload variations. At run time MPRA produces optimal solutions by evaluating the linear function for the current region. Analysis and simulation results show that MPRA maximizes system utility in the presence of varying workloads, while reducing the online computation complexity to polynomial time. Type of Report: Other Department of Computer Science & Engineering Washington University in St. Louis Campus Box 1045 St. Louis, MO 63130 ph: (314) 935-6160 Optimal Discrete Rate Adaptation for Distributed Real-Time Systems with End-to-End Tasks Yingming Chen Chenyang Lu Xenofon Koutsoukos Department of Computer Science and Engineering Department of Electrical Engineering Washington University in St. Louis and Computer Science St. Louis, MO 63130 Vanderbilt University {yingming, lu}@cse.wustl.edu Nashville, TN 37235 xenofon.koutsoukos@vanderbilt.edu Abstract Many distributed real-time systems face the challenge of dynamically maximizing system utility in response to fluctuations in system workload. We present the MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. The key novelty and advantage of MPRA is that it can efficiently produce optimal solutions in response to workload changes such as dynamic task arrivals. Through offline preprocessing MPRA transforms a NP-hard utility optimization problem to a set of simple linear functions in different regions expressed in term of CPU utilization changes caused by workload variations. At run time MPRA produces optimal solutions by evaluating the linear function for the current region. Analysis and simulation results show that MPRA maximizes system utility in the presence of varying workloads, while reducing the online computation complexity to polynomial time.Many distributed real-time systems face the challenge of dynamically maximizing system utility in response to fluctuations in system workload. We present the MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. The key novelty and advantage of MPRA is that it can efficiently produce optimal solutions in response to workload changes such as dynamic task arrivals. Through offline preprocessing MPRA transforms a NP-hard utility optimization problem to a set of simple linear functions in different regions expressed in term of CPU utilization changes caused by workload variations. At run time MPRA produces optimal solutions by evaluating the linear function for the current region. Analysis and simulation results show that MPRA maximizes system utility in the presence of varying workloads, while reducing the online computation complexity to polynomial time.
File Format	PDF HTM / HTML
DOI	10.7936/K72805TF
Alternate Webpage(s)	https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1119&context=cse_research&httpsredir=1&referer=
Alternate Webpage(s)	https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1119&context=cse_research
Alternate Webpage(s)	http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1119&context=cse_research
Alternate Webpage(s)	https://doi.org/10.7936/K72805TF
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article