An algorithm for automatically obtaining distributed and fault-tolerant static schedules

Abstract

Our goal is to automatically obtain a distributed and fault-tolerant embedded system: distributed because the system must run on a distributed architecture; fault-tolerant because the system is critical. Our starting point is a source algorithm, a target distributed architecture, some distribution constraints, some indications on the execution times of the algorithm operations on the processors of the target architecture, some indications on the communication times of the data-dependencies on the communication links of the target architecture, a number of fail-silent processor failures that the obtained system must tolerate, and finally some real-time constraints that the obtained system must satisfy. In this article, we present a scheduling heuristic which, given all these inputs, produces a fault-tolerant, distributed, and static scheduling of the algorithm on the architecture, with an indication whether or not the real-time constraints are satisfied. The fault-tolerance is achieved with software redundancy of the algorithm's operations and data communications. In previous work, we proposed a solution to this problem in the special case where the processors communicate via a single multi-point medium, i.e., a bus. The scheduling heuristic presented here is complementary and more general since it also addresses architectures with point-to-point communication links.

BibTeX entry

@InProceedings{GKSS03,
  author = 	 {A. Girault and H. Kalla and M. Sighireanu and Y. Sorel},
  title = 	 {An Algorithm for Automatically Obtaining Distributed and
                  Fault-Tolerant Static Schedules},
  booktitle = 	 {International Conference on Dependable Systems and
                  Networks, DSN'03},
  year =	 2003,
  address =	 {San-Francisco, USA},
  month =	 jun,
  publisher =	 {IEEE},
}