Optimizing Data Locality in CAF

Abstract

Die Speicherarchitektur moderner Mehrprozessorsysteme ist hierarchisch strukturiert. Mehrere Ebenen von Caches und eine Non-Uniform Memory Access (NUMA) Architektur wurden eingeführt um die Zugri szeiten von den CPU Cores auf die benötigten Daten zu verringern. Dies führt zu inhomogen Ausführungsgeschwindigkeiten von Anwendungen mit einer Abhängigkeit vom Ort der Daten. Durch die Berücksichtigung dieses Lokalitätsprinzips kann die Geschwindigkeit von Anwendungen und Software-Bibliotheken, wie zum Beispiel bei dem C++ Actor Framework (CAF), deutlich verbessert werden. CAF ist eine Implementierung des Aktormodells, ein mächtiges Entwurfsmuster für verteilte und nebenläu ge Anwendungen. In CAF wird RandomWork-Stealing (RWS) als Standard-Scheduler genutzt. RWS skaliert exzellent, ist einfach gehalten und benötigt nur sehr wenig Informationen über das System. Dies hat den Nachteil, dass es keine Wissen über die Speicherarchitektur hat, das Lokalitätsprinzip ignoriert und Möglichkeiten versäumt die Performanz von Anwendungen zu verbessern. In dieser Arbeit entwickeln wir einen Scheduler, der das Wissen über die Speicherarchitektur ausnutzt um die Performanz von aktorbasierten Anwendungen zu verbessern. Wir implementieren und analysieren den Scheduler in CAF unter Berücksichtigung eines Kompromisses zwischen der Kommunikations- und der Ausführungslokalität. Die Kommunikationlokalität beschreibt die Distanz zwischen kommunizierenden Aktoren während die Ausführungslokalität die Distanz zwischen dem auszuführenden Aktor und seinen abgelegten Daten beschreibt. Ausführliche Analysen zeigen, dass datenintensive Anwendungen bis zu 44% schneller auf einer 64 Core NUMA-Maschine laufen können.

Memory architectures of modern processors are hierarchically structured. Multiple level of caches and a non-uniform memory access architecture (NUMA) are introduced to reduce access latency from processing units to their current working set. These lead to inhomogeneous performance characteristics depending on where the data is located. Optimizing the data locality of applications or libraries like the C++ Actor Framework (CAF) can signi cantly improve the performance. CAF is an implementation of the actor model. It is a powerful software pattern for concurrent and distributed computing. CAF is designed for using multiple, exchangeable schedulers with a default choice of random work-stealing (RWS). RWS is excellently scalable, and by choosing a random victim scheduling is kept simple with minimal information required. On the downside, it is unaware of the memory architecture, ignores data locality and misses opportunities to improve the application performance. In this thesis, we contribute a locality-guided scheduling that exploits knowledge about the host system to improve the performance of actor based applications. We implement and thoroughly analyze a CAF scheduler which considers the trade-o between communication locality and execution locality. The former describes the locality of communicating actors, while the latter the locality between a worker which executes an actor and the location of its data. Extensive performance evaluations show a performance gain for data intensive application of up to 44% on a 64 core NUMA machine.