Institut für Computersprachen
Programmiersprachen und Übersetzer
 | Diplomarbeit |
|---|---|
| Titel | Partial Evaluation of Numerical Algorithms |
| Autor | Baier, Romana |
| Erscheinungsjahr | 1996 |
| Inventardatum | 08.10.1996 |
| Abstract | Wir untersuchten partielle Auswertung für Anwendungen aus Wissenschaft und Technik. Unser Ziel war es, die Anwendbarkeit partieller Auswertung für numerische Software zu bewerten und Erfolge, Beschränkungen und mögliche Verbesserungen zu analysieren. Numerische Algorithmen sind einer der härtesten Tests für partielle Auswertung, weil sie bereits sehr effizient implementiert sind. Effizienz, das heißt hier rasche Programmlaufzeit, ist besonders wichtig für wissenschaftliche und technische Anwendungen. Partielle Auswertung ist eine Methode zur automatischen Programmoptimierung, ähnlich vom Konzept her, aber doch in vieler Hinsicht unterschiedlich zu optimierenden Compilern. Die Optimierungen werden erreicht durch ein Ändern der Zeiten zu denen Operationen ausgeführt werden. Ein partieller Auswerter spezialisiert Programme unter Berücksichtigung bekannter Eingabedaten. Die dabei entstehenden Programme sind für gewöhnlich schneller. Um repräsentative Ergebnisse zu erhalten, haben wir 23 numerische Algorithmen aus wichtigen Bereichen der Wissenschaft und Technik ausgewählt, darunter: lineare Gleichungen, Vektor-Matrix Berechnungen, numerische Integration, Interpolation und Statistik. Alle Programme wurden in Fortran77 geschrieben, mit einem partiellen auswerter für Fortran spezialisiert und mit einem kommerziellen Fortran Compiler compiliert. Weiters untersuchtenwir mögliche Änderungen der Quellprogramme für eine verbesserte Spezialisierung, und wir analysierten die möglichen und erreichten Laufzeitverbesserungen. Wir zeigen Beschränkungen des vewendeten partiellen Auswerters auf und geben Vorschläge für Verbesserungen an. Die Ergebnisse variieren abhängig von der Struktur und von dem Verwendungszweck des numerischen Programmes. Die erhaltenen Laufzeitverbesserungen sind im Durchschnitt geringer als für nicht numerische Anwendungen, jedoch im allgemeinen groß genug, um den Einsatz partieller Auswertung zu rechtfertigen. Nur wenige Algorithmen erzielten hohe Laufzeitverbesserungen, wie z.B. die Fast Fourier Transformation. Diese Arbeit zeigt eine erste substantielle und systematische Studie über partielle Auswertung numerischer Algorithmen. Teile dieser Arbeit wurden bereits veröffentlicht. |
| Status | Verfügbar |