Fast multi-threading on shared memory multiprocessors

Abstract

This thesis implements a fast multi-threaded shared memory multiprocessor scheduler that runs on Linux machines. The main concern is efficiency in scheduling and in inter-thread and network communication, giving good performance when executing fine grain user level threads. Also emphasis was made to create a scheduler that is scalable with the number of processors and still provide transparency to the application developer. This thesis starts off with a version of MESH that runs on a uniprocessor machine and modifies it into SMP-MESH, a version that runs on shared memory multiprocessor machines, the system being easily scalable to any number of processors. MESH is a tightly coupled fine grain user level thread scheduler providing very fast scheduling and communication rates. Our multiprocessor implementation allows the concurrent execution of user level threads, through the use of a shared run queue together with concurrent inter-thread communication. Shared resources exist that are protected through the use of spin-locks. SMP-MESH implements all the advantages of parallel processing. The system caters for load balancing and well behaved idling. Also specific race hazards that might increase latency or lead to deadlock are investigated. An investigation of the overheads introduced in the new implementation is presented. It is seen how a variety of benchmarks assess different parts of the scheduler and communication sections of SMP-MESH. Light is shed on the thread granularity limit beyond which contention for shared resources starts to influence performance adversely. This thesis shows that an SMP implementation of the uniprocessor MESH is the obvious step in the evolution of MESH resulting in considerable speedup while still maintaining all the fast techniques present originally