On algorithm design and programming model for multi-threaded computing

The objective of this work is to investigate the algorithm design and the programming model of multi-threaded computing. With the rapid advancement in multi- /many-core processors, multi-threaded computing has attracted a lot of attention recently. Designing multi-threaded algorithms is very challenging though - when multiple threads need to communicate or coordinate with each other, efficient synchronization support is needed. However, synchronizations are known to be expensive on the emerging multi-/many-core processors, especially when the number of threads increases. To fully unleash the power of such processors, carefully investigations are needed in both algorithm design and programming models for multi-threaded systems.;In this dissertation, we first study the algorithm design aspect of the problem. In particular, we present an asynchronous multi-threaded algorithm for the maximum network flow problem. This algorithm is based on the classical push-relabel algorithm and completely removes the use of locks and barriers from its original parallel version. Experiment results show that such algorithmic innovation can significantly improve the execution speed by enabling higher levels of parallelism.;While this algorithmic method shows effectiveness, it is challenging to generalize the success to other multi-threaded problem. We next focus on improving the synchronization primitives for those algorithms that still need efficient synchronization methods. More specifically, we study the transactional memory, which is believed by many researchers to be a promising mechanism for constructing multi-threaded programs. A queuing-theory-based model is developed to analyze the performance of different transactional memory systems. Based on the results of the model, we emphasize on the contention management scheme of transactional memory systems that would effectively reduce the contention level and significantly improve the performance. A profiling-based adaptive contention management scheme is proposed to cope with the problem that none of the static contention management schemes can keep good performance on all platforms for all types of workload. Experiment results prove that our adaptive contention management scheme is able to yield a consistently good performance across different benchmarks and platforms.;From the above research, we show that it is necessary and worthwhile to explore both the algorithm design aspect and the programming model aspect for multi-thread computing. New algorithm designs with the target of the multi-threading would benefit from the emerging multi-/many-core platform. At the same time, we still need to improve the current programming model to enhance the programmability and performance for the algorithms that rely on intensive synchronizations.