Please use this identifier to cite or link to this item:
doi:10.22028/D291-25801
Title: | Integer linear programming vs. graph-based methods in code generation |
Author(s): | Kästner, Daniel Langenbach, Marc |
Language: | English |
Year of Publication: | 1998 |
SWD key words: | Technische Informatik Lineare Programmierung |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | 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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-3542 hdl:20.500.11880/25857 http://dx.doi.org/10.22028/D291-25801 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1998/01 |
Date of registration: | 23-Jun-2005 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
codegen.pdf | 661,5 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.