From: Honghai Liu (liu789_at_hotmail.com)
Date: Mon Jan 26 2004 - 00:29:36 PST
Reviewer: Honghai Liu
The paper describes the performance implication under different data structures and algorithms in thread management. Furthermore, detailed model analysis is given.
Separating notion of execution from the rest of process results creates thread. The only different data structures among threads are program counter, stack and a control block, which appears to be very little to worry about. However, the paper shows different strategies to implement thread management can make so huge differences in respect of performance.
Two optimizations are straightforward: deferring allocating stack until thread startup and storing deal located control blocks and stacks in free lists, which are not focused upon by the paper.
Instead, the author concentrates on thread management strategies in terms of latency (un-contention scenario) and throughput (contention scenario). Locking in thread management is not required on uni-processors; however, it matters a lot in multi-processor threading environment. Five alternatives for locking are presented, with different locks(single/multiple), ready queues(central/local) and idle processors(queue/ no-queue). A very simple threads were prototyped and run under these alternatives and it is concluded that choice of alternatives has a large relative impact on both latency and throughput for applications with fine-grained parallelism.
It is surprising to see there exists several spin-waiting strategies, among which the analysis of Ethernet-style backoff and queue-based algorithms are most eye opening.
Overall, the paper not only presents the results from different locking and spin-waiting algorithms, but also develops excellent models to accurately explain unexpected behaviors. This makes the paper a must-read for those who are serious on developing any thread systems.
It is a little pity that there is no discussion on Kernel level and User level threads management in the paper. All the experiments were done in user level, and how the results would be like for similar experiments in context of kernel-level threads is definitively an intriguing area to explore.
This archive was generated by hypermail 2.1.6 : Mon Jan 26 2004 - 00:29:48 PST