| Abstract | A defining challenge for research in computer science and engineering hasbeen the ongoing quest for reducing the completion time of a single
computation task. Even outside the parallel processing communities, there
is little doubt that the key to further progress in this quest is to do
parallel processing of some kind. A recently proposed parallel processing
framework that spans the entire spectrum from (parallel) algorithms to
architecture to implementation is the explicit multi-threading (XMT)
framework. This framework provides:
(i) simple and natural parallel algorithms for essentially every
general-purpose application, including notoriously difficult irregular
integer applications, and
(ii) a multi-threaded programming model for these algorithms which
allows an ``independence-of-order'' semantics: every thread can proceed at
its own speed, independent of other concurrent threads. To the extent
possible, the XMT framework uses established ideas in parallel processing.
This paper presents XMT-M, a microarchitecture implementation of the XMT
model that is possible with current technology. XMT-M offers an
engineering design point that addresses four concerns: buildability,
programmability, performance, and scalability. The XMT-M hardware is
geared to execute multiple threads in parallel on a single chip: relying
on very few new gadgets, it can execute parallel threads without
busy-waits! Existing code can be run on XMT-M as a single thread without
any modifications, thereby providing backward compatibility for commercial
acceptance. Simulation-based studies of XMT-M demonstrate considerable
improvements in performance relative to the best serial processor even for
small, and therefore practical, input sizes.
(Also cross-referenced as UMIACS-TR-99-55)
|
