|
Explicit Multi-Threading (XMT) is a new conceptual framework (or paradigm) for general-purpose computing. Research over the last two decades by academic algorithm designers has produced a huge knowledge-base of parallel algorithmic methods, which is arguably second in its magnitude only to serial algorithms. The model of parallel computation used for developing this knowledge-based is called PRAM (for parallel-random-access machine, or model). The (virtual) thread structure of PRAM-like algorithms is very dynamic: the number of threads that need to be generated changes frequently, new threads are generated and terminated frequently, and often threads are relatively short. Perhaps the most distinguishing feature about the XMT framework is that it envisions an extension to a standard instruction set which aspires to efficiently implement PRAM-like algorithms; XMT does so using explicit multi-threaded instruction-level parallelism (ILP). XMT is a fine-grained parallel computational paradigm covering the spectrum from algorithms through architecture to implementation. We tried to minimize changes to current practice: new elements are added to computer languages, architecture and implementation, only where needed. The more detailed presentation in the SPAA'98 paper is by way of a bridging model. Among other things, a bridging model provides a design space for algorithm designers and programmers, as well as a design space for computer architects. It is convenient to describe our wider vision regarding ``parallel-computing-on-a-chip'' as a two-stage development and therefore two bridging models are presented: Spawn-based multi-threading (Spawn-MT) and Elastic multi-threading (EMT). |
