MLTP - A Multi-Layer (M×N) Thread Package for SMP Linux (Thesis Project)

History

The Multi-layer Thread Package was the thesis project that I did for my Masters in Computer Science from the Universtity of California, Santa Barbara in September 2000.

I started thinking about this project back in 1998. Linux version 2.0 with Symmetric Multiprocessing (SMP) support had been out for a few years, but it was far from perfect. For starters, there was a lot of locking within the kernel, preventing a decent amount of code from running in parallel. Linux version 2.2 came out the following year and removed a lot of the spinlocks in the kernel, but the BigKernelLock still existed and context switching between processes was still relatively expensive.

I was interested in parallelizing algorithms. Breaking up algorithms into multiple processes allows them to run in parallel. Each SMP processor can execute its own process. The problem is, if there are more processes than processors, you bump into the slow context switching problems whenever a processor switches to another process.

My idea was to avoid context switching by parallelizing the algorithm in user-level threads that run on top of kernel level threads. Then I could restrict the kernel-level threads to match the number of processors and have as many user-level threads as made sense for the algorithm. In theory MLTP can help to maximize parallel execution by keeping the number of context switches that go through the kernel to a minimum.

NOTE: MLTP was completed in 2000. The state-of-art Intel x86 processors had a 32-bit architecture. The MLTP source code assumes a 32-bit x86 architecture and will not compile for any other architectures.

Background

The multi-level thread package (MLTP) contributes an extensible, open source, two-level thread package for SMP Linux on 32-bit Intel x86 processors. By layering user-level threads on top of kernel-level threads, MLTP is able to provide most of the advantages of both thread user- and kernel-level architectures while limiting the disadvantages. MLTP provides:

• Low per-thread overhead. Each user-level thread requires a small amount of space to store context registers and its own private stack. No kernel resources are utilized by MLTP user-level threads.
• Quick thread context switching. User-level thread context switching under MLTP does not require any kernel intervention, there are no kernel traps or process context switches and rescheduling. User-level context switching does not require computations to be made in order to determine which thread should be executed next, therefore the time required for a context switch does not increase as the number of threads increases.
• Multi-processor utilization. By running user-level threads on top of kernel-level threads, the user-level threads may run on multiple processors and still take advantage of a shared thread space.

MLTP has been created as an open source, extensible, and well commented thread package so that it may serve as a platform for further research in multi-level thread systems in SMP Linux. In an attempt to maintain clarity and portability, MLTP does not utilize any kernel patches to provide a multi-layer threading. It is not the intention of this project to be the final authority on the subject of multi-level threads for SMP Linux.

MLTP has been benchmarked using both synthetic and application benchmarks, demonstrating a flexible set of primitives and performance improvements which may exceed ten percent when compared to kernel-level threads alone.

Thesis Documents and Source

Last updated on December 29, 2018