Naslov
Optimal Harmonic Period Assignment With Constrained Number of Distinct Period Values

Autori
Pavić, Ivan ; Džapo, Hrvoje

Izvornik
IEEE Access (2169-3536) 8 (2020); 175697-175712

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
harmonic period assignment ; period optimization ; real-time systems

Sažetak
Harmonic periods have been of great importance in the design of real-time applications due to their high schedulability, predictability, and ease of analysis. Therefore, period assignment is an important part of the design process of many real-time systems. This includes various applications such as radar dwell tasks, robotics, and industrial control applications, where tasks are specified using period ranges and worst-case execution times. In this paper, we study the issue of assigning a fixed number of harmonic periods from period ranges to maximize utilization in real-time systems. In the existing period assignment approaches, the number of different harmonic period values in the solution was not addressed. In this work, we show that, in real-time systems in which the number of available task periods is restricted, such a constraint is crucial for efficient system design. We formally define the problem in the context of existing harmonic period assignment research. We show that this problem is at least weakly NP-hard and devise an optimal algorithm and suboptimal heuristics. Based on an extensive evaluation on synthetically generated task sets, we conclude that our approach is efficient and applicable in a variety of real-world scenarios.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo

POVEZANOST RADA