Untersuchung der Implementierbarkeit eines lock-freien binären Suchbaumes

Abstract

So wie wir Menschen, verbringen auch Computer eine beträchtliche Zeit mit Datenverarbeitung: Sie schlagen unter anderem -Kontostände, Flugreservierungen, Rechnungen undZahlungen- [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 Bereichdes parallelen Rechnens fällt. Die effiziente Datenmanipulation von mehreren Prozessoren gleichzeitig bedarf neuerDatenstrukturen, die für diesen Einsatz ausgelegt sind. Lock-freie Datenstrukturen tragendieses Potential, da sie nicht auf blockierende Synchronisationstechniken zurückgreifen. Indieser Arbeit wird der Lock-freie Algorithmus von Chatterjee et al.[CNT14] zur parallelenManipulation einer Baum-Datenstruktur untersucht. Diese Diplomarbeit beschäftigt sich mit der Frage, ob der Algorithmus von Chatterjeeet al. so ausführlich beschrieben wurde, dass er sich im Rahmen dieser Arbeit in einausfü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 eigensentwickelten Fehler-Injektion konnten die Kernelemente des Algorithmus implementiertwerden. Letztendlich konnte der Algorithmus von Chatterjee et al. bis auf einen parallelenSpezialfall vollständig und mit allen Funktionalitäten implementiert werden. Das Ergebnisdeutet 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 alsErfolg zu verbuchen war.

Like humans, computers also spend a considerably great amount of time on data process ing: 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.