Tapestry: weaving execution and synchronization models

Gao, Guang R.With the advent of the many-core era of computing, finding parallelism has become a key battleground to the performance of computer algorithms. Traditional methods focused on providing users with synchronization primitives, standard threading models, and shared memory models. However, it was clear that these models were limited in performance. Thus, many new forms of synchronization and parallel models were designed focusing on the big three types of parallelism: data, task, and dataflow. Nevertheless, all these models (1) only solve a particular subset of problems, (2) provide limited extendability for addressing new forms of parallelism, (3) and require a new languages with poor fine-grain performance. As an approach to find a unified solution to these problems, Tapestry is an easily extendable portable compiler-free runtime. It is designed to quickly explore new or traditional synchronization and execution models for multi-core and many-core architectures by separating synchronization and threading models. The main contributions of this thesis are: 1. Design of the Tapestry runtime and model to explore synchronization features or execution models that supports the mixing of all of the big three types of parallelism. 2. Proposal of extendable threaded dependency model of execution that expands traditional threads, and the creation of optimizations to extend traditional models to support finer-grain parallelism. 3. Implementation of Tapestry runtime library using only C++ 98 for 2 different platforms and 3 different operating systems with better performance and scalability than OpenMP Tasks and Cilk Plus. Because of these aspects, my preliminary studies with Tapestry have shown that the performance and scalability of the three types of parallelism can be improved through the use of fine-grain optimizations and careful queue design. And through other studies, I have shown the benefits of dataflow synchronization to reduce operating noise caused by thread context switching. Tapestry has been enormously beneficial in these aspects of study allowing optimizations to be easily applied across all synchronization and threading models showing significant improvements can be made to industry level parallel software such as OpenMP and Intel Cilk Plus.University of Delaware, Department of Electrical and Computer EngineeringM.E.C.E.G