A Study of a Transactional Parallel Routing Algorithm

Abstract

Transactional memory proposes an alternative synchro-nization primitive to traditional locks. Its promise is to sim-plify the software development of multi-threaded applica-tions while at the same time delivering the performance of parallel applications using (complex and error prone) fine grain locking. This study reports our experience implementing a real-istic application using transactional memory (TM). The ap-plication is Lee’s routing algorithm and was selected for its abundance of parallelism but difficulty of expressing it with locks. Each route between a source and a destination point in a grid can be considered a unit of parallelism. Starting from this simple approach, we evaluate the exploitable par-allelism of a transactional parallel implementation and ex-plore how it can be adapted to deliver better performance. The adaptations do not introduce locks nor alter the essence of the implemented algorithm, but deliver up to 20 times more parallelism. The adaptations are derived from un-derstanding the application itself and TM. The evaluation simulates an abstracted TM system and, thus, the results are independent of specific software or hardware TM im-plemented, and describe properties of the application. 1.