Finding Optimal Harmonic Periods: Recent Results and Open Problems
Speaker:
Morteza Mohaqeqi
Date and Time
Friday, November 11th, 2016 at 14:15.
Location
Polacksbacken, ITC, room 1111.
Abstract
A set of positive numbers are said to be in a harmonic relation if they pairwise divide each other.
In the design of real-time systems, having a task set with harmonic periods essentially simplifies prominent analysis problems most of which are known to be hard in the general (i.e., not necessarily harmonic) case.
In this work, we studied the problem of finding harmonic periods for a set of real-time tasks such that an objective function is optimized.
First, it is assumed that an interval is determined a priori for the period of each task. We show that the problem is NP-Hard through a reduction from the number partitioning problem. Next, we focus on a variant of the problem in which the periods are not restricted to a range. We present two approximation algorithms with analytically-proved error bounds. Our evaluations show that the results obtained from the approximation algorithms are very close to the optimal solution. We also discuss some relevant open problems.
The talk presents joint work with Mitra Nasri, Yang Xu, Anton Cervin and Karl-Erik Årzén, and recently received the Best-paper award of the 24th International Conference on Real-Time Networks and Systems (RTNS).