SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-3542
URL: http://scidok.sulb.uni-saarland.de/volltexte/2005/354/


Integer linear programming vs. graph-based methods in code generation

Kästner, Daniel ; Langenbach, Marc

pdf-Format:
Dokument 1.pdf (661 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Technische Informatik , Lineare Programmierung
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Bandnummer: 1998/01
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 23.06.2005
Kurzfassung auf Englisch: A common characterictic of many applications is that they are aimed at the high-volume consumer market, which is extremely cost-sensitive. However many of them impose stringent performance demands on the underlying system. Therefore the code generation must take into account the restrictions and features given by the target architecture while satisfying these performance demands. High-level language compilers often are unable to generate code meeting these requirements. One reason is the phase coupling problem between instruction scheduling and register allocation. Many compilers perform these tasks separately with each phase ignorant of the require- ments of the other. Commonly, each task is accomplished by using heuristic methods. As the goals of the two phases often conflict, whichever phase is performed first imposes constraints on the other, sometimes producing inefficient code. Integer linear programming (ILP) provides an integrated approach to the combined instruction scheduling and register allocation problem. This way, optimal solutions can be found - albeit at the cost of high compilation times. In our experiments, we considered as target processor the 32-bit DSP ADSP-2106x. We have examined two different ILP formulations and compared them with conventional approaches including list scheduling and the critical path method. Moreover, we have investigated approximations based on the ILP formulations; this way, compilation time can be reduced considerably while still producing near-optimal results. From the results of our implementation, we have concluded that integrating ILP formulations in conventional global algorithms is a promising method for generating high-quality code.

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English