research-article

Probabilistic analysis of bufferless pipelines of real-time tasks

Authors:

Daniele Fontanelli,

Luigi Palopoli,

Bernardo Villalba FríasAuthors Info & Claims

SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing

Pages 1751 - 1758

https://doi.org/10.1145/2851613.2851676

Published: 04 April 2016 Publication History

Abstract

In this paper, we consider real--time applications consisting of multiple tasks, which are executed on computing cores managed by a resource reservatin scheduler. The tasks are organised in a linear topology (pipeline). The result produced by a task as a result of one of its activations is used as input for the task at the next stage of the pipeline. The time required for each execution of a task is a random variable. We assume a bufferless communication semantic, whereby a data item produced by a task is outright dropped if the consumer is not ready to execute.

Assuming a bufferless communication simplifies the computation of the probability distribution of the end--to--end delay, since when an item is correctly processed by the pipeline its accumulated delay is simply the sum of the delays incurred in each stage. However, data can be dropped at any stage if the pipeline, and this requires a precedure to compute the probability of such an event. This computation is the main problem addressed in the paper, where we also show the practical applicability of the approach through a set of experiments.

References

[1]

L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, Madrid, Spain, December 1998.

Digital Library

[2]

L. Abeni and G. Buttazzo. Qos guarantee using probabilistic dealines. In Proceedings of the IEEE Euromicro Conference on Real-Time Systems, York, England, June 1999.

[3]

L. Abeni and G. Buttazzo. Stochastic analysis of a reservation-based system. In Proceedings of the 15th International Parallel and Distributed Processing Symposium., San Francisco, California, April 2001.

Digital Library

[4]

L. Abeni, N. Manica, and L. Palopoli. Efficient and robust probabilistic guarantees for real-time tasks. Journal of Systems and Software, 85(5):1147--1156, 2012.

Digital Library

[5]

G. Bernat, A. Colin, and S. Petters. pwcet: A tool for probabilistic worst-case execution time analysis of real-time systems. REPORT-UNIVERSITY OF YORK DEPARTMENT OF COMPUTER SCIENCE YCS, 2003.

[6]

T. Cucinotta and L. Palopoli. Qos control for pipelines of tasks using multiple resources. Computers, IEEE Transactions on, 59(3):416--430, March 2010.

Digital Library

[7]

L. Cucu and E. Tovar. A framework for the response time analysis of fixed-priority tasks with stochastic inter-arrival times. ACM SIGBED Review - Special issue: The work-in-progress (WIP) session of the RTSS 2005, 3(1):7--12, January 2006.

Digital Library

[8]

J. L. Diaz, D. F. Garcia, K. Kim, C. G. Lee, L. Lo Bello, J. M. López, S. L. Min, and O. Mirabella. Stochastic analysis of periodic real-time systems. In Real-Time Systems Symposium, 2002. RTSS 2002. 23rd IEEE, pages 289--300. IEEE, 2003.

Digital Library

[9]

J. L. Diaz, J. M. López, M. Garcia, A. M. Campos, K. Kim, and L. Lo Bello. Pessimism in the stochastic analysis of real-time systems: Concept and applications. In Real-Time Systems Symposium, 2004. Proceedings. 25th IEEE International, pages 197--207. IEEE, 2005.

Digital Library

[10]

D. Fontanelli, L. Palopoli, and L. Abeni. The Continuous Stream Model of Computation for Real--Time Control. In Proceedings of the IEEE Real-Time Systems Symposium, Vancouver, Canada, 4-6 Dec. 2013. IEEE.

Digital Library

[11]

M. K. Gardner and J. Liu. Analyzing stochastic fixed-priority real-time systems. In Proceedings of the 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS99), pages 44--58. Springer, March 1999.

Digital Library

[12]

P. Jayachandran and T. Abdelzaher. A delay composition theorem for real-time pipelines. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 29--38. IEEE, 2007.

Digital Library

[13]

P. Jayachandran and T. Abdelzaher. Delay composition algebra: A reduction-based schedulability algebra for distributed real-time systems. In Proceedings of the Real-Time Systems Symposium (RTSS), pages 259--269. IEEE, 2008.

Digital Library

[14]

P. Jayachandran and T. Abdelzaher. Delay composition in preemptive and non-preemptive real-time pipelines. Real-Time Systems, 40(3):290--320, 2008.

Digital Library

[15]

D.-I. Kang, R. Gerber, and M. Sakena. Performance-based design of distributed real-time systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium, pages 2--13, June 1997.

Digital Library

[16]

D.-I. Kang, R. Gerber, and M. Saksena. Parametric design synthesis of distributed embedded systems. IEEE Trans. Computers, 49(11):1155--1169, 2000.

Digital Library

[17]

K. Kim, J. L. Diaz, L. Lo Bello, J. M. López, C. G. Lee, and S. L. Min. An exact stochastic analysis of priority-driven periodic real-time systems and its approximations. IEEE Transactions on Computers, 54(11):1460--1466, 2005.

Digital Library

[18]

N. Manica, L. Palopoli, and L. Abeni. Numerically efficient probabilistic guarantees for resource reservations. In Emerging Technologies Factory Automation (ETFA), 2012 IEEE 17th Conference on, pages 1--8, Sept 2012.

[19]

D. Maxim and L. Cucu-Grosjean. Response time analysis for fixed-priority tasks with multiple probabilistic parameters. In Proceedings of the IEEE Real-Time Systems Symposium, Vancouver, British Columbia, Canada, December 2013.

Digital Library

[20]

A. Mills and J. Anderson. A stochastic framework for multiprocessor soft real-time scheduling. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 311--320. IEEE, April 2010.

Digital Library

[21]

L. Palopoli, D. Fontanelli, L. Abeni, and B. Villalba Frias. An analytical solution for probabilistic guarantees of reservation based soft real--time systems. Parallel and Distributed Systems, IEEE Transactions on, PP(99):1--1, 2015.

Digital Library

[22]

L. Palopoli, D. Fontanelli, N. Manica, and L. Abeni. An analytical bound for probabilistic deadlines. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 179--188. IEEE, 2012.

Digital Library

Cited By

Fontanelli DPalopoli L(2018)On Soft Real-Time Implementation of LQG Controllers2018 IEEE 13th International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2018.8442078(1-8)Online publication date: Jun-2018
https://doi.org/10.1109/SIES.2018.8442078
Pan CXie MLiu YWang YXue CWang YChen YHu J(2017)A lightweight progress maximization scheduler for non-volatile processor under unstable energy harvestingACM SIGPLAN Notices10.1145/3140582.308103852:5(101-110)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081038
Jiang WSha EZhuge QDong HChen X(2017)Optimal functional unit assignment and voltage selection for pipelined MPSoC with guaranteed probability on time performanceACM SIGPLAN Notices10.1145/3140582.308103652:5(41-50)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081036
Show More Cited By

Index Terms

Probabilistic analysis of bufferless pipelines of real-time tasks
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
  2. Real-time systems

Recommendations

Probabilistic Deadline Miss Analysis of Real-Time Systems Using Regenerative Transient Analysis
RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

Quantitative evaluation of real-time systems demands for analysis frameworks that go beyond worst-case assumptions, since some parameters could be better characterized by a random variable than by a deterministic value. On the one hand, this opens ...
Probabilistic job symbiosis modeling for SMT processor scheduling
ASPLOS XV: Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems

Symbiotic job scheduling boosts simultaneous multithreading (SMT) processor performance by co-scheduling jobs that have `compatible' demands on the processor's shared resources. Existing approaches however require a sampling phase, evaluate a limited ...
An intra-task DVS algorithm exploiting path probabilities for real-time systems
Special issue: IEEE RTAS 2005 work-in-progress

In this paper, we present a novel intra-task Dynamic Voltage Scheduling (DVS) algorithm based on the knowledge of frequently executed paths in the control flow graph for real time systems. The basic idea is to construct a common path composing all the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing

April 2016

2360 pages

ISBN:9781450337397

DOI:10.1145/2851613

Conference Chair:
Sascha Ossowski
University Rey Juan Carlos, Spain

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 April 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Commission

Conference

SAC 2016

Sponsor:

SIGAPP

SAC 2016: Symposium on Applied Computing

April 4 - 8, 2016

Pisa, Italy

Acceptance Rates

SAC '16 Paper Acceptance Rate 252 of 1,047 submissions, 24%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
47
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fontanelli DPalopoli L(2018)On Soft Real-Time Implementation of LQG Controllers2018 IEEE 13th International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2018.8442078(1-8)Online publication date: Jun-2018
https://doi.org/10.1109/SIES.2018.8442078
Pan CXie MLiu YWang YXue CWang YChen YHu J(2017)A lightweight progress maximization scheduler for non-volatile processor under unstable energy harvestingACM SIGPLAN Notices10.1145/3140582.308103852:5(101-110)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081038
Jiang WSha EZhuge QDong HChen X(2017)Optimal functional unit assignment and voltage selection for pipelined MPSoC with guaranteed probability on time performanceACM SIGPLAN Notices10.1145/3140582.308103652:5(41-50)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081036
Zhang MYing Y(2017)Towards SMT-based LTL model checking of clock constraint specification language for real-time and embedded systemsACM SIGPLAN Notices10.1145/3140582.308103552:5(61-70)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081035
Ding XZhang ZJia ZJu LZhao MHuang H(2017)Unified nvTCAM and sTCAM architecture for improving packet matching performanceACM SIGPLAN Notices10.1145/3140582.308103452:5(91-100)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081034
Wang YZhang MYang J(2017)Towards memory-efficient processing-in-memory architecture for convolutional neural networksACM SIGPLAN Notices10.1145/3140582.308103252:5(81-90)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081032
Lee GHeo SKim BKim JKim H(2017)Integrated IoT programming with selective abstractionACM SIGPLAN Notices10.1145/3140582.308103152:5(51-60)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081031
Jiang WSha EZhuge QDong HChen XNagarajan VShao Z(2017)Optimal functional unit assignment and voltage selection for pipelined MPSoC with guaranteed probability on time performanceProceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3078633.3081036(41-50)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3078633.3081036
Jiang WSha EZhuge QChen X(2016)Optimal functional-unit assignment and buffer placement for probabilistic pipelinesProceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis10.1145/2968456.2968467(1-10)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1145/2968456.2968467
Dematté LPriami CRomanel A(2008)Modelling and simulation of biological processes in BlenXACM SIGMETRICS Performance Evaluation Review10.1145/1364644.136465335:4(32-39)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1145/1364644.1364653
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents