Contentions-conscious dynamic but deterministic scheduling of computational and communication tasks

ABSTRACT

Real Time Operating Systems (RTOS) for Multiprocessor System-on-Chip (MPSoC) are not well tackling with the scheduling of communication load between the tasks running on different processors. Traditionally communications and computations are considered separately leading to a great complexity in the analysis of the system behavior. We have explicitly scheduled the Inter-Processor Communication (IPC) on the shared medium considering all the parameters affecting its cost i.e. link contention, node contention and synchronization overhead. We have proposed a dynamic but deterministic communication model and have embedded it with the scheduling of the tasks on processors (RTOS kernel services) to get the deterministic behavior of the application.

REFERENCES

• 1: Yen-Kuang Chen , Rainer Lienhart , Eric Debes , Matthew Holliman , Minerva Yeung, The Impact of SMT/SMP Designs on Multimedia Software Engineering " A Workload Analysis Study, Proceedings of the Fourth IEEE International Symposium on Multimedia Software Engineering, p.336, December 11-13, 2002
• 2: Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]
• 3: Vilgot Claesson , Cecilia Ekelin , Neeraj Suri, The Event-Triggered and Time-Triggered Medium-Access Methods, Proceedings of the Sixth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'03), p.131, May 14-16, 2003
• 4: Muhammad Ali Livani and Jorg Kaiser "EDF consensus on CAN Bus Access for dynamic Real-Time Applications" in José Rolim (Ed.): Lecture Notes in Computer Science, Vol. 1388, pp.1088--1097, Springer Verlag, 1998.
• 5: Jing-Jang Hwang , Yuan-Chieh Chow , Frank D. Anger , Chung-Yee Lee, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, v.18 n.2, p.244-257, April 1989 [doi>10.1137/0218016]
• 6: Ion Stoica , Florin Sultan , David Keyes, A SIMPLE HYPERBOLIC MODEL FOR COMMUNICATION IN PARALLEL PROCESSING ENVIRONMENT, Institute for Computer Applications in Science and Engineering (ICASE), 1994
• 7: Sudeep Pasricha , Nikil Dutt , Mohamed Ben-Romdhane, Automated throughput-driven synthesis of bus-based communication architectures, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120920]
• 8: M. Dertouzos and Mok "Multiprocessor Scheduling in a Hard Real-Time Environment" In Proceedings of the 7th IEEE Texas Conference on Computing Systems pages 5-1|5--12, November 1978.
• 9: F. Muhammad "Contention-conscious Dynamic but deterministic scheduling of computational and communication tasks", Master thesis, 2005
• 10: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 11: Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, p.207, June 12-14, 1996
• 12: Benchmarking the Task Graph Scheduling Algorithms, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.531, March 30-April 03, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance, Reliability, Verification

Keywords:
RTOS, SoC, architecture, deterministic scheduling, multiprocessor