Content deleted Content added
→References: A significant new reference was added |
No edit summary |
||
Line 1:
''' Explicit Multi-Threading ''' (''' XMT ''') is a [[computer science]] paradigm for building and programming parallel computers designed around the [[Parallel Random Access Machine]] ([[PRAM]]) parallel computational model. A more direct explanation of XMT starts with the rudimentary abstraction that made serial computing simple: that any single instruction available for execution in a serial program executes immediately. A consequence of this abstraction is a step-by-step (inductive) explication of the instruction available next for execution. The rudimentary parallel abstraction behind XMT, dubbed Immediate Concurrent Execution (ICE) in {{harvtxt|Vishkin|2011}}, is that indefinitely many instructions available for concurrent execution execute immediately. A consequence of ICE is a step-by-step (inductive) explication of the instructions available next for concurrent execution. Moving beyond the serial von Neumann computer (the only successful general purpose platform to date), the aspiration of XMT is that computer science will again be able to augment mathematical induction with a simple one-line computing abstraction
The [[random access machine]] ([[RAM]]) is an [[abstract machine]] model used in computer science to study algorithms and complexity for standard serial computing. The PRAM computational model is an abstract parallel machine model that had been introduced to similarly study parallel algorithms and complexity for [[parallel computing]], when they were yet to be built. Researchers have developed a large body of knowledge of parallel algorithms for the PRAM model. These parallel algorithms are also known for being simple, by standards of other approaches to parallel algorithms.
Line 12:
The Explicit Multi-Threading (XMT) computing paradigm integrates several levels of abstraction.
The work-time (WT) (sometimes called work-depth) framework, introduced by {{harvtxt|Shiloach|Vishkin|1982}}, provides a simple way for conceptualizing and describing parallel algorithms. In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is, in fact, guided by the proof of a scheduling theorem due to {{harvtxt|Brent|1974}}. The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. For example, the WT framework was adopted as the basic presentation framework in the parallel algorithms books (for the PRAM model) {{harvtxt|JaJa|1992}} and {{harvtxt|Keller|Kessler|Traeff|2001}}, as well as in the class notes {{harvtxt|Vishkin|2009}}. {{harvtxt|Vishkin|2011}} explains the simple connection between the WT framework and the more rudimentary ICE abstraction noted above.
The XMT paradigm can be programmed using [[XMTC]], a parallel multi-threaded programming language which is a small extension of the programming language C. The XMT paradigm include a programmer’s workflow that starts with casting an algorithm in the WT framework and proceeds to programming it in XMTC.
| |||