The Giotto Programming Language: Scheduling Theory and Helicopter Implementation

Benjamin Horowitz
(Professor Thomas A. Henzinger)
(DARPA) SEC F33615-C-98-3614

Giotto is a real-time programming language for control systems. A control application typically consists of communicating periodic tasks, together with mode switches that enable and disable tasks. We are pursuing two lines of research relating to Giotto:

(1) Scheduling theory for Giotto. Giotto is platform-independent, and thus does not specify in detail how Giotto programs are to be scheduled. The Giotto compiler's current scheduling algorithm interprets Giotto's operational semantics quite literally. We are investigating how this literal interpretation may be relaxed, allowing more Giotto programs to be scheduled. Our starting point is precedence-constrained scheduling models, drawn from the scheduling theory literature. Single-mode, single-processor Giotto programs may be modeled as periodic instances of 1 | rj; dj; prec; pmtn | - (the problem of scheduling dependent tasks with release times, deadlines, and preemption on a single processor). Using a novel extension of standard earliest deadline first scheduling algorithms, I have developed an algorithm for schedule synthesis that captures interesting schedule optimizations and is polynomial-time. One direction in which these results can be generalized is multi-mode programs. I have developed a novel model, of conditional scheduling problems, that captures the branching behavior of multi-mode programs, and permits the synthesis of schedules in polynomial time. Another direction in which these results might be generalized is multi-processor programs. For distributed and multi-CPU settings, almost all precedence-constrained scheduling models are NP-hard, so I am focusing instead on load-balancing approximation algorithms. This work is being done in conjunction with Tom Henzinger.

(2) A Giotto-based helicopter control system. In conjunction with this theoretical work, we are implementing a Giotto-based helicopter control system for a Yamaha RMAX helicopter, with two goals in mind. The first goal is to produce a modular implementation. The control computer must be prepared to communicate with a wide variety of sensors--global positioning system, inertial measurement unit, etc.--each with its own data format and timing behavior. To manage the complexity in the helicopter control system, we use platform-based design, which introduces multiple layers of abstraction between application and implementation. The second goal is to produce a testable implementation. Since testing the control system on the actual helicopter is time consuming and somewhat risky, we have built a hardware-in-the-loop simulator for the Yamaha RMAX. The idea is to replace the helicopter itself with a simulated model of the helicopter's dynamics. The control system, however, remains the same, and may be tested against the simulator rather than the helicopter itself. This work is being done in conjunction with Judy Liebman, Cedric Ma (who have both graduated), John Koo, Tom Henzinger, Alberto Sangiovanni-Vincentelli, and Shankar Sastry.


Figure 1: Precedence constraints for a single-mode Giotto program

[1]
T. A. Henzinger, B. Horowitz, and C. M. Kirsch, "Giotto: A Time-triggered Language for Embedded Programming," Proc. Int. Workshop on Embedded Software, Tahoe City, CA, October 2001.
[2]
B. Horowitz, J. Liebman, C. Ma, T. J. Koo, T. A. Henzinger, A. Sangiovanni-Vincentelli, and S. Sastry, "Embedded Software Design and System Integration for Rotorcraft UAV Using Platforms," Proc. IFAC World Congress, Barcelona, Spain, July 2002.

More information (http://www-cad.eecs.berkeley.edu/~bhorowit/) or

Send mail to the author : (bhorowit@cs.berkeley.edu)


Edit this abstract