Konrad-Zuse-Zentrum
|
ZIB PaperWeb
|
|
|
| 00-33 | Florian Schintke
Ermittlung von Programmlaufzeiten anhand von Speicherzugriffen, Microbenchmarks und Simulation von Speicherhierarchien |   |
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ücksichtigt.
In dieser Diplomarbeit wird ein Simulator
für Speicherhierarchien
präsentiert, der die
Berechnung von Programmausführungszeiten
nach dem LDA-Modell erlaubt.
Mit Hilfe des Simulators wird die These geprüft,
daß mit
diesem Modell die Ausführungszeit eines
Programms adäquat
abgeschätzt werden kann.
Mit dem Simulator ist es erstmals praktikabel
möglich,
Programmausführungszeiten
nach dem LDA-Modell zu bestimmen.
Der Simulator kann für Systeme mit
unterschiedlichen Speicherarchitekturen
konfiguriert werden und unterstützt
Mehrprozessorsysteme
mit gemeinsamem Speicher (SMP-Systeme) mit
verschiedenen
Kohärenzprotokollen.
Der Simulator kann mit den Ergebnissen von
Microbenchmarks konfiguriert werden, die die
Architekturparameter einer Speicherhierarchie messen.
Die Ergebnisse bestätigen die These
nicht nur für Einzelprozessorsysteme,
sondern auch für
SMP-Systeme, wo gleichzeitig interagierende
Prozessoren
gegenseitig ihre Zugriffssequenz auf
Zwischenspeicher beeinflussen.
Zusätzlich wurde eine neue Einsatzmöglichkeit
des LDA-Modells entwickelt, um die
Ausführungszeit von Programmteilen
zu bestimmen.
Einzelne Zugriffskosten
können einem mehrerer parallel
laufender Modelle zugeordnet werden.
Dadurch können Kosten, die Zugriffe auf einzelne
Speicherbereiche verursachen, separat bestimmt werden.
Diese Profiling-Technik erlaubt Optimierungen
an Datenstrukturen und Speicherzugriffsmustern
durch präzise und
gezielte Informationsproduktion.
Abstract:
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.
Keywords: Cache-Simulator,
Microbenchmarks,
SMP-System,
Kostenmodell,
Speicherhierarchie
CR: C.4