@misc{Schintke2000, author = {Schintke, Florian}, title = {Ermittlung von Programmlaufzeiten anhand von Speicherzugriffen, Microbenchmarks und Simulation vonSpeicherhierarchien}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6018}, number = {00-33}, year = {2000}, abstract = {\\{\bf Zusammenfassung:} Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten ber{\"u}{}cksichtigt. In dieser Diplomarbeit wird ein Simulator f{\"u}{}r Speicherhierarchien pr{\"a}{}sentiert, der die Berechnung von Programmausf{\"u}{}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These gepr{\"u}{}ft, da\ss{} mit diesem Modell die Ausf{\"u}{}hrungszeit eines Programms ad{\"a}{}quat abgesch{\"a}{}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel m{\"o}{}glich, Programmausf{\"u}{}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann f{\"u}{}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterst{\"u}{}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Koh{\"a}{}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse best{\"a}{}tigen die These nicht nur f{\"u}{}r Einzelprozessorsysteme, sondern auch f{\"u}{}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffssequenz auf Zwischenspeicher beeinflussen. Zus{\"a}{}tzlich wurde eine neue Einsatzm{\"o}{}glichkeit des LDA-Modells entwickelt, um die Ausf{\"u}{}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten k{\"o}{}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch k{\"o}{}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch pr{\"a}{}zise und gezielte Informationsproduktion.Cost models are used to determine the execution time of programs, to compare the efficiency of algorithms, and to analyse the behaviour of memory hierarchies. The Latency-of-Data-Access (LDA) model that takes into account multiple hierarchical memory levels with different latencies, is a newly proposed, innovative cost model. In this diploma-thesis, a simulator for memory hierarchies is presented that allows the calculation of execution times using the LDA-model. The simulator is used to prove the claim that the execution time of a program can be accurately estimated with the LDA-model. With the simulator, it is for the first time possible to determine the execution time of programs with this model in a practical way. The simulator can be configured for systems with various cache architectures and supports shared memory (SMP) multiprocessor systems with different cache coherence protocols. The simulator can be configured with the results from microbenchmarks which measure the architectural properties of a memory hierarchy. The results confirm the claim not only for single processor systems, but also for SMP systems, where concurrently interacting processors influence each others cache access sequence. Additionally, a new field of usage of the LDA-model was developed to determine execution times of program parts. Single access costs can be assigned to one of several parallel running models. As an example the costs of accesses to different memory areas can be split and determined separately. This profiling technique allows to optimise data structures and memory access patterns of sequential and parallel SMP programs by precise production of information.}, language = {de} }