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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Real-time avionics optimization


    Weitere Titelangaben:

    Mathematische Optimierung von Echtzeitsystemen im Flugzeugdesign


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    2011


    Format / Umfang :

    6 Seiten, 7 Bilder, 3 Quellen




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch




    Real-time, Ada-based, avionics processing

    Bate, D. / Ott, G. / Morton, B. | Tema Archiv | 1990



    Optimization of multicast light-trees in real-time avionics WDM network

    Xiong, Ying / He, Feng / Xiong, Huagang | IEEE | 2012


    Real-time flight management avionics software system

    CHELINI, J. / FARMER, R. | AIAA | 1981


    Real-Time Java Virtual Machine for Avionics (Preprint)

    A. Armbruster / E. Pla / J. Baker et al. | NTIS | 2006