On algorithm design and programming model for multi-threaded computing

Programming model;Parallel computing;Transactional memory;Maximum flow

He, Zhengyu ; Electrical and Computer Engineering

University:Georgia Institute of Technology

Department:Electrical and Computer Engineering

关键词: Programming model;    Parallel computing;    Transactional memory;    Maximum flow;   

Others  :  https://smartech.gatech.edu/bitstream/1853/43635/1/he_zhengyu_201205_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The objective of this work is to investigate the algorithm design and theprogramming model of multi-threaded computing. Designing multi-threadedalgorithms is very challenging - when multiple threads need to communicate orcoordinate with each other, efficient synchronization support is needed.However, synchronizations are known to be expensive on the emergingmulti-/many-core processors, especially when the number of threads increases. Tofully unleash the power of such processors, carefully investigations are neededin both algorithm design and programming models for multi-threaded systems.In this dissertation, we first present an asynchronous multi-threaded algorithmfor the maximum network flow problem. This algorithm is based on the classicalpush-relabel algorithm and completely removes the use of locks and barriers fromits original parallel version.While this algorithmic method showseffectiveness, it is challenging to generalize the success to othermulti-threaded problem. We next focus on improving the transactional memory, apromising mechanism to construct multi-threaded programs. A queuing-theory-basedmodel is developed to analyze the performance of different transactional memorysystems. Based on the results of the model, we emphasize on the contentionmanagement mechanism of transactional memory systems.A profiling-basedadaptive contention management scheme is finally proposed to cope with theproblem that none of the static contention management schemes can keep goodperformance on all platforms for all types of workload.From this research, weshow that it is necessary and worthwhile to explore both the algorithm designaspect and the programming model aspect for multi-thread computing.