[Back]

N. Mayerhofer:
"Untersuchung der Implementierbarkeit eines lock-freien binären Suchbaumes";
Supervisor: J. Träff; Institute of Information Systems, Parallel Computing Group, 2016; final examination: 2016-10-04.

Like humans, computers also spend a considerably great amount of time on data processing: They look up account balances, flight reservations, invoices and payments [DMS14, S.183]. To speed up these processes for computers, multiple processors can process the same data in a parallel way, which corresponds to the scope of concurrent calculations. Efficient data manipulation of multiple processors at the same time requires new data structures which are designed for this use. Lock-free data structures carry this potential, as they do not rely on blocking synchronization techniques. In this work, the lock-free algorithm for parallel manipulation of the tree data structure by Chatterjee et al. is examined.
This thesis deals with the question of whether the algorithm of Chatterjee et al. is described in a way that it can be implemented to work as an executable program. Furthermore, the quality of the parallel implementation of the algorithm was examined with the help of an experimental performance analysis [RR10, S.167].
Due to the use of a test-driven development process, constraints were very closely monitored. Thereby it was possible to discover and fix errors in the course of the implementation process. By applying the finely grained debugging process called tracing and a specially developed error injection, it was possible to obtain a deep insight into the parallel flow of the application. Thus it was possible to realize important parts of the implementation.
Ultimately, the algorithm of Chatterjee et al. could not be implemented completely. However, it was possible to implement all functionalities but a parallel special case of the algorithm. The result denotes that parts of the pseudo code of Chatterjee et al., which process a particular condition, may be missing.
Finally, please note that the practice of trace debugging has been accredited as successful.

So wie wir Menschen, verbringen auch Computer eine beträchtliche Zeit mit Datenverarbeitung: Sie schlagen unter anderem "Kontostände, Flugreservierungen, Rechnungen und Zahlungen" [DMS14, S.183] nach. Um diese Vorgänge für Computer zu beschleunigen, können mehrere Prozessoren parallel dieselben Datensätze bearbeiten, was in den Bereich des parallelen Rechnens fällt.
Die effiziente Datenmanipulation von mehreren Prozessoren gleichzeitig bedarf neuer Datenstrukturen, die für diesen Einsatz ausgelegt sind. Lock-freie Datenstrukturen tragen dieses Potential, da sie nicht auf blockierende Synchronisationstechniken zurückgreifen. In dieser Arbeit wird der Lock-freie Algorithmus von Chatterjee et al.[CNT14] zur parallelen Manipulation einer Baum-Datenstruktur untersucht.
Diese Diplomarbeit beschäftigt sich mit der Frage, ob der Algorithmus von Chatterjee et al. so ausführlich beschrieben wurde, dass er sich im Rahmen dieser Arbeit in ein ausführbares Programm implementieren lässt. Weiters sollte die Güte der Implementierung des parallelen Algorithmus anhand der geleisteten Performance untersucht werden
[RR10, S.167]. Durch die Anwendung eines Test-Driven-Development Prozesses, in Kombination mit dem fein granularen Debugging Verfahren namens Tracing und einer eigens entwickelten Fehler-Injektion konnten die Kernelemente des Algorithmus implementiert werden.
Letztendlich konnte der Algorithmus von Chatterjee et al. bis auf einen parallelen Spezialfall vollständig und mit allen Funktionalitäten implementiert werden. Das Ergebnis deutet darauf hin, dass Pseudocode-Teile zur Verarbeitung eines speziellen Zustandes, die der Baum einnehmen kann, von Chatterjee et al. nicht ausgeführt wurden.
Abschließend sei erwähnt, dass die Anwendung des Trace-Debuggings Verfahrens als Erfolg zu verbuchen war.