The week's pick
Reseach Article
Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints
| 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
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
- 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.
- 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.
- Krzysztof Apt. Principles of constraint programming. 2003.
- 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.
- 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.
- Sanjoy K. Baruah and Giuseppe Lipari. Executing aperiodic jobs in a multiprocessor constant-bandwidth server implementation. In ECRTS, pages 109–116, 2004.
- Lawrence Livermore National Laboratory Blaise Barney. Introduction to parallel computing. Web, 2010.
- Giorgio C. Buttazzo, Enrico Bini, and Yifan Wu. Partitioning real-time applications over multicore reservations. IEEE Trans. Industrial Informatics, 7(2):302–315, 2011.
- H-Yi Chao and M P. Harper. Minimizing redundant dependencies and interprocessor synchronizations. International Journal of Parallel Programming, 23:245–262, 1994.
- 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.
- L. Cucu, N. Pernet, and Y. Sorel. Periodic real-time scheduling: from deadline-based model to latency-based model. Annals of Operations Research, 2007.
- 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.
- 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.
- S. M. Goddard and Jr. On the management of latency in the synthesis of real-time signal processing systems from processing graphs, 1998.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Yuan Shi. Reevaluating amdahl's law and gustafson's law. Technical report, Temple University, Philadelphia, PA 19122, October 1996.
- F Tutzauer. Entropy as a measure of centrality in networks characterized by path-transfer flow. Social Networks, 29(2), 2007.
- S. V. N. Vishwanathan, N. Schraudolph, R. Kondor, and K. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201–1242, 2010.
Index Terms
Keywords