We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints

by Omar Kermia
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 62 - Number 14
Year of Publication: 2013
Authors: Omar Kermia
10.5120/10145-4978

Omar Kermia . Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints. International Journal of Computer Applications. 62, 14 ( January 2013), 1-7. DOI=10.5120/10145-4978

@article{ 10.5120/10145-4978,
author = { Omar Kermia },
title = { Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints },
journal = { International Journal of Computer Applications },
issue_date = { January 2013 },
volume = { 62 },
number = { 14 },
month = { January },
year = { 2013 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume62/number14/10145-4978/ },
doi = { 10.5120/10145-4978 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:11:45.539565+05:30
%A Omar Kermia
%T Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints
%J International Journal of Computer Applications
%@ 0975-8887
%V 62
%N 14
%P 1-7
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper focuses on the analysis of real-time non preemptive multiprocessor scheduling with precedence and several latency constraints. It aims to specify a schedulability condition which enables a designer to check a priori -without executing or simulating- if its scheduling of tasks will hold the precedences between tasks as well as several latency constraints imposed on determined pairs of tasks. It is shown that the required analysis is closely linked to the topological structure of the application graph. More precisely, it depends on the configuration of tasks paths subject to latency constraints. As a result of the study, a sufficient schedulability condition is introduced for precedences and latency constraints in the hardest configuration in term of complexity with an optimal number of processors in term of applications parallelism. In addition, the proposed conditions provides a practical lower bounds for general cases. Performances results and comparisons with an optimal approach demonstrate the effectiveness of the proposed approach.

References
  1. Luca Abeni, Tommaso Cucinotta, Giuseppe Lipari, Luca Marzario, and Luigi Palopoli. Qos management through adaptive reservations. Real-Time Systems, 29(2-3):131– 155, 2005.
  2. G. M. Amdahl. Validity of the single-processor approach to achieving large scale computing capabilities. In AFIPS Conference Proceedings, volume 30, pages 483– 485. AFIPS Press, 1967.
  3. Krzysztof Apt. Principles of constraint programming. 2003.
  4. F. Balarin, L. Lavagno, P. Murthy, and A. Sangiovannivincentelli. Scheduling for embedded real-time systems. IEEE Design and Test of Computers, 15(1):71–82, 1998.
  5. Sanjoy K. Baruah and Joel Goossens. The edf scheduling of sporadic task systems on uniform multiprocessors. In IEEE Real-Time Systems Symposium, pages 367–374, 2008.
  6. Sanjoy K. Baruah and Giuseppe Lipari. Executing aperiodic jobs in a multiprocessor constant-bandwidth server implementation. In ECRTS, pages 109–116, 2004.
  7. Lawrence Livermore National Laboratory Blaise Barney. Introduction to parallel computing. Web, 2010.
  8. Giorgio C. Buttazzo, Enrico Bini, and Yifan Wu. Partitioning real-time applications over multicore reservations. IEEE Trans. Industrial Informatics, 7(2):302–315, 2011.
  9. H-Yi Chao and M P. Harper. Minimizing redundant dependencies and interprocessor synchronizations. International Journal of Parallel Programming, 23:245–262, 1994.
  10. Tommaso Cucinotta. Optimum scalability point for parallelisable real-time components. In Proceedings of the International Workshop on Synthesis and Optimization Methods for Real-time and Embedded Systems (SOMRES 2011), Vienna, Austria, November 2011.
  11. L. Cucu, N. Pernet, and Y. Sorel. Periodic real-time scheduling: from deadline-based model to latency-based model. Annals of Operations Research, 2007.
  12. L. Cucu and Y. Sorel. Non-preemptive scheduling algorithms and schedulability conditions for real-time systems with precedence and latency constraints. (RR-5403):33, 2004.
  13. Christian Glasser, Christian Reitwiessner, Heinz Schmitz, and Maximilian Witek. Approximability and hardness in multi-objective optimization. In Proceedings of the Programs, proofs, process and 6th international conference on Computability in Europe, CiE'10, 2010.
  14. S. M. Goddard and Jr. On the management of latency in the synthesis of real-time signal processing systems from processing graphs, 1998.
  15. R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Ronnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of Discrete Mathematics, 1979.
  16. Chih-wen Hsueh and Kwei-jay Lin. Scheduling realtime systems with end-to-end timing constraints using the distributed pinwheel model. IEEE Transactions on Computers, 49(1):51–66, 2000.
  17. Kai Huang, Jian-Jia Chen, and Lothar Thiele. Energyefficient scheduling algorithms for periodic power management for real-time event streams. In RTCSA (1), pages 83– 92, 2011.
  18. K. Jeffay, D. F. Stanat, and C. U. Martel. On nonpreemptive scheduling of periodic and sporadic tasks. In Proceedings of the 12 th IEEE Symposium on Real-Time Systems, pages 129–139, December 1991.
  19. O. Kermia. Optimizing distributed real-time embedded system handling dependence and several strict periodicity constraints. Advances in Operations Research, page 10. 1155/2011/561794, 2011.
  20. Philippe Laborie. Ibm ilog cp optimizer for detailed scheduling illustrated on three problems. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science. 2009.
  21. Cong Liu and James H. Anderson. Supporting graph-based real-time applications in distributed systems. Real-Time Computing Systems and Applications, International Workshop on, 1:143–152, 2011.
  22. Yuchun Ma, Zhuoyuan Li, Jason Cong, Xianlong Hong, G. Reinman, Sheqin Dong, and Qiang Zhou. Microarchitecture pipelining optimization with throughput-aware floorplanning. In Proceedings of the 2007 Asia and South Pacific Design Automation Conference, 2007.
  23. Yuan Shi. Reevaluating amdahl's law and gustafson's law. Technical report, Temple University, Philadelphia, PA 19122, October 1996.
  24. F Tutzauer. Entropy as a measure of centrality in networks characterized by path-transfer flow. Social Networks, 29(2), 2007.
  25. S. V. N. Vishwanathan, N. Schraudolph, R. Kondor, and K. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201–1242, 2010.
Index Terms

Computer Science
Information Sciences

Keywords

Real-Time Systems Multiprocessor Scheduling Schedulability Analysis Combinatorial Problems Latency Constraints

Powered by PhDFocusTM