NDLI: On the Problem of Finding Optimal Harmonic Periods

Please wait, while we are loading the content...

A Formal Approach for Flexible Modeling and Analysis of Transaction Timeliness and Isolation

Traversal time for weakly synchronized CAN bus

Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor

Schedulability analysis of dependent probabilistic real-time tasks

Intrusion-Damage Assessment and Mitigation in Cyber-Physical Systems for Control Applications

Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks

Supporting Suspension-based Locking Mechanisms for Real-Time Networks-on-chip

Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous Multiprocessors

Time for Reactive System Modeling: Interactive Timing Analysis with Hotspot Highlighting

Quantifying Energy Consumption for Practical Fork-Join Parallelism on an Embedded Real-Time Operating System

MILP-based Deadline Assignment for End-to-End Flows in Distributed Real-Time Systems

A Practical Message ID Assignment Policy for Controller Area Network that Maximizes Extensibility

Preemptive scheduling of dependent periodic tasks modeled by synchronous dataflow graphs

On Fixed-Priority Schedulability Analysis of Sporadic Tasks with Self-Suspension

On Task Period Assignment in Multiprocessor Real-Time Control Systems

Time-sensitive Software-defined Network (TSSDN) for Real-time Applications

State-based Communication on Time-predictable Multicore Processors

Partitioning and Interface Synthesis in Hierarchical Multiprocessor Real-Time Systems

Enabling Compositionality for Multicore Timing Analysis

Modeling Parallel Real-time Tasks with Di-Graphs

Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Independent yet Tight WCRT Analysis for Individual Priority Classes in Ethernet AVB

Computing latency of a real-time system modeled by Synchronous Dataflow Graph

Uniprocessor Scheduling Strategies for Self-Suspending Task Systems

Quantifying the Effect of Period Ratios on Schedulability of Rate Monotonic

No-wait Packet Scheduling for IEEE Time-sensitive Networks (TSN)

Mapping hard real-time applications on many-core processors

EDF-hv: An Energy-Efficient Semi-Partitioned Approach for Hard Real-Time Systems

Analysis of Write-back Caches under Fixed-priority Preemptive and Non-preemptive Scheduling

Reducing Response-Time Bounds for DAG-Based Task Systems on Heterogeneous Multicore Platforms

Adaptive Fair Scheduler: Fairness in Presence of Disturbances

On the Problem of Finding Optimal Harmonic Periods

Improving the Schedulability of Mixed Criticality Cyclic Executives via Limited Task Splitting

A Software Managed Stack Cache for Real-Time Systems

On the Problem of Finding Optimal Harmonic Periods

Content Provider	ACM Digital Library
Author	Årzén, Karl-Erik Xu, Yang Mohaqeqi, Morteza Nasri, Mitra Cervin, Anton
Abstract	Harmonic periods have wide applicability in industrial realtime systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. This property decreases the jitters which happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic. First, we assume that an interval is determined a priori for each task from which its period can be selected. The goal is to assign a (harmonic) period to each task such that the total system utilization is maximized while the task set remains feasible. We show that this problem is (at least) weakly NP-hard. This is shown by reducing the NP-complete number partitioning problem to the mentioned harmonic period assignment problem. Afterwards, we consider a variant of the problem in which the periods are not restricted to a special interval and the objective is to minimize the total weighted sum of the periods with the same feasibility constraint. We present two approximation algorithms for the second problem and show that the maximum error of these algorithms is bounded by a factor of 2. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.
Starting Page	171
Ending Page	180
Page Count	10
File Format	PDF
ISBN	9781450347877
DOI	10.1145/2997465.2997490
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-10-19
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The complexity of finding periods

Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

On Finding Primal- and Dual-Optimal Bases (1991)

On Finding Primal- and Dual-Optimal Bases (1991)

On the Periods of Harmonic and Meromorphic Forms on Klein Surfaces

On the Hardness of Finding Optimal Multiple Preset Dictionaries

On the Empirical Scaling of Run-time for Finding Optimal Solutions to the Traveling Salesman Problem

The Global Optimal Algorithm of Reliable Path Finding Problem Based on Backtracking Method

Optimal Fractionation Problem

On the Problem of Finding Optimal Harmonic Periods

Similar Documents

The complexity of finding periods

Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

On Finding Primal- and Dual-Optimal Bases (1991)

On Finding Primal- and Dual-Optimal Bases (1991)

On the Periods of Harmonic and Meromorphic Forms on Klein Surfaces

On the Hardness of Finding Optimal Multiple Preset Dictionaries

On the Empirical Scaling of Run-time for Finding Optimal Solutions to the Traveling Salesman Problem

The Global Optimal Algorithm of Reliable Path Finding Problem Based on Backtracking Method

Optimal Fractionation Problem

On the Problem of Finding Optimal Harmonic Periods