ABSTRACT
This chapter looks at parallelization techniques for non-scientific applications that mainly rely on linked data structures (LDS) as their main data structures. LDS include all data structures that use a collection of nodes that are linked together with pointers, such as linked lists, trees, graphs, hash tables, etc. LDS accesses exhibit a high degree of loop-carried dependence, preventing the loop parallelization techniques to be applied successfully. The chapter focuses on these techniques, and illustrates the practical application of the techniques on a linked list. It also focuses on features that are common in these techniques and apply them to a simple LDS – a linked list. The chapter provides a basic framework on which readers can build further investigation into parallelization techniques for LDS. It also provides readers appreciation of how locks may be used in non-scientific applications that utilize LDS, and how lock granularity is related to the amount of concurrency that can be exploited and the programming complexity.
