Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25713
Titel: Retargetable postpass optimisation by integer linear programming
VerfasserIn: Kästner, Daniel
Sprache: Englisch
Erscheinungsjahr: 2000
Kontrollierte Schlagwörter: Signalprozessor ; Codegenerierung ; Ganzzahlige lineare Optimierung
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
Abstract: In the area of embedded systems stringent timing constraints in connection with severe cost restrictions have led to the development of specialised, irregular hardware architectures designed to efficiently execute typical applications of digital signal processing. The code quality achieved by traditional high-level language compilers for irregular architectures often cannot satisfy the requirements of the target applications. Thus many DSP applications are still developed in assembly language. However due to the increasing software complexity and the shrinking design-cycles of embedded processors there is an urgent demand for code generation techniques that are able to produce high-quality code for irregular architectures. The PROPAN system has been developed as a retargetable framework for high-quality code optimisations and machine-dependent program analyses at postpass, i.e. assembly level. The postpass orientation allows PROPAN to be integrated in existing tool chains with moderate effort. The retargetability concept of PROPAN is based on the combination of generic and generative mechanisms. All relevant information about the target architecture is specified in a dedicated machine description language TDL. From that description a phase-coupled optimiser is generated which can perform global instruction scheduling, register reassignment, and resource allocation by integer linear programming. PROPAN allows to select between an order-indexed and a time-indexed ILP formulation such that the more appropriate modelling can be chosen individually for each target architecture. The generated integer linear programs can be solved either exactly providing a provably optimal solution to the modelled problems, or by the use of ILP-based approximations. The basic idea of the approximative methods is the iterative solution of partial relaxations of the original problem. This way the computation time can be reduced significantly and still a very high solution quality can be obtained. With PROPAN ILP-based postpass optimisers for two widely used contemporary digital signal processors, the Analog Devices ADSP-2106x and the Philips Trimedia TM1000 have been generated. Additionally PROPAN is integrated in a framework for calculating worst-case execution time guarantees for real-time systems where a TDL specification of the Infineon TriCore is used. Finally PROPAN has been successfully used in a commercial postpass optimiser for the Infineon C166 microprocessor.
Eingebettete Systeme unterliegen engen Kostenschranken, typische Anwendungen stellen jedoch hohe Leistungsanforderungen. Dies hat zur Entwicklung spezialisierter irregulärer Hardwarearchitekturen geführt, für die traditionelle Codeerzeugungs- und -optimierungsverfahren keine zufriedenstellenden Ergebnisse erzielen. Anwendungsprogramme für eingebettete Systeme werden daher oft in Assembler programmiert. Eine Ursache hierfür ist die gegenseitige Abhängigkeit der Codeerzeugungsphasen, das sogenannte Phasenkopplungsproblem. Ganzzahlige lineare Programmierung (ILP) jedoch ermöglicht es, verschiedene Teilprobleme in einer homogenen Problembeschreibung zu integrieren und gemeinsam zu lösen. In der vorliegenden Arbeit werden zwei strukturierte ILP-Formulierungen zur globalen, phasengekoppelten Codeoptimierung für irreguläre Architekturen vorgestellt. Der Zusammenhang zwischen dem Hardwareentwurf der Zielarchitektur und der geeigneten Modellierungsmethode für ganzzahlige lineare Programme wird herausgestellt. Zur Beschleunigung der Berechnungen werden ILP-basierte Approximationen entwickelt, die eine sehr hohe Codequalität erzielen und die Berechnungszeit im Vergleich zur exakten Lösung deutlich senken. Die Optimierungen wurden in einem retargierbaren System für Postpassoptimierungen und -analysen, genannt PROPAN, implementiert. Eine neue Architekturbeschreibungssprache TDL ermöglicht eine kurze und prägnante Spezifikation der relevanten Hardwareeigenschaften der Zielarchitektur. Aus der TDL-Beschreibung wird ein hardwaresensitiver Postpassoptimierer generiert, der durch Einsatz ganzzahliger linearer Programmierung effizienzsteigernde Transformationen von Assemblercode durchführt. Das System wurde für verschiedene repräsentative Standardprozessoren retargiert. Die experimentellen Ergebnisse belegen die Anwendbarkeit dieses Verfahrens.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-1994
hdl:20.500.11880/25769
http://dx.doi.org/10.22028/D291-25713
Erstgutachter: Reinhard Wilhelm
Tag der mündlichen Prüfung: 22-Dez-2000
Datum des Eintrags: 23-Apr-2004
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
DanielKaestner_ProfDrReinhardWilhelm.pdf6,13 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.