If someone is generally klutzy, or neglects one responsibility because of the urgency of another, we jokingly say they “can’t walk and chew gum at the same time.” This is, in a sense, a statement about multi threading. Humans are used to doing multiple tasks simultaneously (though some are better at it than others). A musical performer, for instance, will be doing chording and fingering with his left hand, plucking or strumming strings with his right hand, singing lyrics and melody with his mouth, and keeping time with a tapping foot.
If we were to think of the musician as a computer, and the performance as a program, we could break the program down into 4 obvious threads. Those would be left hand, right hand, mouth, and foot. It’s the same way with walking and chewing gum; there are two obvious threads for the program. When programmers are faced with tasks like these, they can immediately see where they can get performance gains by expressing the solution using multiple threads. It becomes more difficult, however, when the task has less obvious threading boundaries.
Let’s say that a programming team is assigned the “chew gum and walk” program. They do initial analysis and decide that they could implement the program serially, but could get a significant performance improvement if they put chewing gum and walking in separate threads. As they’re about to begin implementation, word comes down that the budget for the project has been reduced, and the “chew gum” feature has been deferred to some future version of the program; version 1 will just “walk.”
At first, the team thinks that there is no longer an opportunity to gain from multi threading. But shortly they realize that walking engages 2 legs, and they can put each leg in a separate thread. They’ll have to synchronize the threads to keep the program from falling over or walking in a circle, but they know how to do that. Unfortunately, the project budget is cut again, and now the scope has been reduced to 1 leg making a walking motion. The team rises to the occasion, however, and plans multiple threads to handle the calf, thigh, knee, etc.
The opportunity for using multiple threads is really a question of task granularity. Consider the very low-level case of 3 lines of code:
1. a = a + c
2. b = b + d
3. e = a + b
The calculation in line 3 depends on the calculations in line 1 and 2. The calculation in line 2, however, does not depend on the calculation in line 1. Line 1 and 2 can be safely executed simultaneously. The overhead of explicitly starting a thread just to execute line 2 at the same time as line 1 would have negative impact on real performance, programmer efficiency, and program maintainability. However, this level of parallelism (called Instruction Level Parallelism or ILP) is a robust area of research, with the emphasis on compilers and operating systems that can determine which instructions depend on which others, and which can be executed simultaneously, all without explicit program direction.
If we go back to our musician, it now appears that there are a lot more opportunities for threading than the obvious ones. We have 10 separate digits on 2 hands, a tongue, lips, cheeks, a larynx, and much more. However, we don’t want to thread just because we can. Let’s say we write the musician program with 30 separate threads of execution. What happens when we run the program on a 1 or 2 core processor? We will likely see a loss in performance due to the overhead of thread creation, destruction, and switching.
It’s all a juggling act. We have to find the balance for threading. We want enough threads so that we can realize a performance gain, but not so many that the gain is overtaken by threading overhead. But it isn’t really a question of whether a given task can be threaded; that’s just an issue of task granularity.
Richard Bowler
rbowler@3leaf.com
Comments