Mark Smotherman
Last major update: April 2005
(Minor update: November 2007)
Summary: Multithreading first appeared in the 1950s, and simultaneous multithreading (SMT) was investigated by IBM in 1968.
(under construction)
Most attempts at a history of multithreaded processors start with the PPUs in the CDC 6600. However, the ideas of sharing a single execution path among multiple threads of execution started at least a decade earlier.
First, there are a number of types of multithreading.
thread-level speculation
http://citeseer.nj.nec.com/purser00study.html
http://citeseer.nj.nec.com/luk01tolerating.html
http://citeseer.nj.nec.com/collins01dynamic.html
http://citeseer.nj.nec.com/zilles01executionbased.html
http://citeseer.nj.nec.com/reinhardt00transient.html
http://citeseer.nj.nec.com/steffan00scalable.html
http://citeseer.nj.nec.com/85835.html
http://citeseer.nj.nec.com/sohi95multiscalar.html
http://citeseer.nj.nec.com/rauchwerger95lrpd.html
Patents
A second instruction counter and a second set of registers were added to the simulator to make the ACS-360 into a multithreaded design. Instructions were tagged with an additional "red/blue" bit to designate the instruction stream and register set; and, as project members had expected, the utilization of the functional units was increased since more independent instructions were available.
(apparently this same scheme was later investigated for use on the S/370 model 195)
[see also: M. J. Flynn and A. Podvin, "Shared Resource Multiprocessing," IEEE Computer, Mar. 1972, pp. 20-28.]
From interview with Joel Emer:
"The challenge in processor design has been getting better single-threaded performance. I hadn't seriously considered multithreading since I finished my Ph.D. on that subject in the late '70s. Then I saw this research from the University of Washington [Dean Tullsen, Susan Eggers, Henry Levy, 1995] where they proposed doing simultaneous multithreading. I was really inspired by this idea of doing things simultaneously. I thought, 'Well that's compatible with the out-of-order design style that we're moving towards. And that gives us the opportunity to develop the best single-threaded machine we can, and do multithreading as well.'
We had this persistent problem of low utilization of individual components. That meant that there was a lot of opportunity to get more performance out of the machine. Their idea was 'Hey, just fill those opportunities with instructions from another program.' I was working with Rebecca Stamm at Digital Equipment Corporation and we worked through a way of incorporating this SMT idea into an out-of-order design. We began to collaborate with the University of Washington and studying the application of SMT in an out-of-order context.
... So in the first go around, Dean [Tullsen] wrote a simulator and came back and said, 'I ran the out-of-order SMT, and I got performance that's worse than if I didn't run multiple threads.' Then he noticed that he was having resource clogging problems. One of the threads would get a huge number of instructions in some part of the machine, and it would just bottleneck that part. None of the other threads could get any work done.
We had a conference call and out of that we realized that resource allocation, or choosing what to do, was the key to getting it to work. We proposed some schemes and then explored 'How do we choose which instructions should be executing now?'
The result was a second paper on SMT that Rebecca and I coauthored with the researchers from the University of Washington. And that's the seminal paper that explains how important it is to choose which instruction stream to fetch instructions from at any point in time."
see also "Multithreaded processors," The Computer Journal, Volume 45, Issue 3, 2002, pp. 320-348.
[History page] [Mark's homepage] [CPSC homepage] [Clemson Univ. homepage]
mark@cs.clemson.edu