In modernen Flugzeugen übernimmt der Bordcomputer einen wichtigen Teil der Flugkontrolle. Dementsprechend ist es wichtig, dass der Computer zu jeder Zeit exakt laut Spezifikation arbeitet. Einen Bordcomputer zu entwickeln ist eine hochgradig komplexe Aufgabe. Unter anderem muss folgenes Problem gelöst werden. Periodisch wiederkehrende Tasks (Programmabläufe und Berechnungen) müssen auf sinnvolle Weise den im Flugzeug vorhandenen Recheneinheiten zugeteilt werden. Für jede Recheneinheit muss dann ein gültiger Schedule berechnet werden, d. h. es muss sichergestellt werden, dass jede Task die ihr laut Spezifikation zustehende Rechenintervalle nutzen kann, ohne in Konflikt mit anderen Tasks derselben Recheneinheit zu treten. Allein dieses Problem, eine gültige Zuteilung mit Schedules zu berechnen, ist selbst mit Hilfe von modernen Rechnern sehr schwierig zu lösen. Alle bekannten algorithmischen Ansätze sind zu ineffizient, um Systeme industrieller Komplexität zu berechnen. Wir beschreiben, wie sich ein tieferes Verständnis der mathematischen Struktur des Problems nutzen lässt, um ein vollkommen neuartiges mathematisches Modell des Problems abzuleiten. Im Rahmen des "Algorithm-Engineering"-Paradigmas haben wir das neue Modell implementiert. Das daraus resultierende Programm ist um Größenordnungen schneller als alle bisher bekannten Ansätze. Insbesondere können wir erstmals Instanzen lösen, die ein gesamtes Flugzeug beschreiben, wodurch unser Programm zu einem industrietauglichen Werkzeug wird.
We report on the solution of a difficult optimization problem which arises in avionics industry. When constructing the on-board controlling-network of an airplane, the engineers need to solve a computationally highly complex problem. The goal is to assign periodic tasks to the processors on the plane and define a schedule for each processor. Current state-of-the-art approaches to tackle the problem are by far not powerful enough to solve instances of real-world size. With the help of the powerful algorithm engineering paradigm we analyzed the mathematical properties of the scheduling problem and designed sophisticated software based on the structural insights. We were able to design a model that outperformed current state-of-the-art approaches by several orders of magnitude. In particular, we could solve industrial size real-world instances to optimality. Our methods lead, for the first time, to an industrial strength tool to schedule aircraft sized instances.
Real-time avionics optimization
Mathematische Optimierung von Echtzeitsystemen im Flugzeugdesign
it - Information Technology ; 53 , 6 ; 274-279
2011
6 Seiten, 7 Bilder, 3 Quellen
Aufsatz (Zeitschrift)
Englisch
Real-time, Ada-based, avionics processing
Tema Archiv | 1990
|Real-time flight management avionics software system
AIAA | 1981
|Real-Time Java Virtual Machine for Avionics (Preprint)
NTIS | 2006
|