Content deleted Content added
Citation bot (talk | contribs) m Add: hdl. | You can use this bot yourself. Report bugs here.| Activated by User:Marianne Zimmerman |
m Open access bot: hdl updated in citation with #oabot. |
||
| (13 intermediate revisions by 7 users not shown) | |||
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 [[parallel random-access machine|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.
This large body of parallel algorithms knowledge for the PRAM model and their relative simplicity motivated building computers whose programming can be guided by these parallel algorithms. Since productivity of parallel programmers has long been considered crucial for the success a parallel computer, simplicity of algorithms is important.
Line 10:
Experimental work published in 2011 and 2012 demonstrates significantly greater speedups for advanced PRAM algorithms on XMT prototypes than for the same problems on state-of-the-art multi-core computers.
Work published in 2018 shows that lock-step parallel programming (using ICE) can achieve the same performance as the fastest hand-tuned multi-threaded code on XMT systems. Such inductive lock-step approach stands in contrast to multi-threaded programming approaches of many other
The XMT paradigm was introduced by [[Uzi Vishkin]].
Line 19:
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
The XMT multi-core computer systems provides run-time load-balancing of multi-threaded programs incorporating several patents. One of them <ref>Vishkin, Uzi. Spawn-join instruction set architecture for providing explicit multithreading. U.S. Patent 6,463,527. See also {{harvtxt|Vishkin|Dascal|Berkovich|Nuzman|1998}}.</ref> generalizes the [[program counter]] concept, which is central to the [[von Neumann architecture]] to multi-core hardware.
==XMT prototyping and links to more information==
In January 2007, a 64-processor computer <ref>University of Maryland, press release, June 26, 2007: [http://www.newsdesk.umd.edu/scitech/release.cfm?ArticleID=1459 "Maryland Professor Creates Desktop Supercomputer"] {{Webarchive|url=https://web.archive.org/web/20091214195046/http://www.newsdesk.umd.edu/scitech/release.cfm?ArticleID=1459 |date=2009-12-14 }}.</ref> named Paraleap,<ref>University of Maryland, A. James Clark School of Engineering, press release, November 28, 2007: [http://www.eng.umd.edu/media/pressreleases/pr112707_superwinner.html "Next Big "Leap" in Computing Technology Gets a Name"].</ref> that demonstrates the overall concept was completed. The XMT concept was presented in {{harvtxt|Vishkin|Dascal|Berkovich|Nuzman|1998}} and {{harvtxt|Naishlos|Nuzman|Tseng|Vishkin|2003}} and the XMT 64-processor computer in {{harvtxt|Wen|Vishkin|2008}}. Since making parallel programming easy is one of the biggest challenges facing computer science today, the demonstration also sought to include teaching the basics of PRAM algorithms and XMTC programming to students ranging from high-school {{harvtxt|Torbert|Vishkin|Tzur|Ellison|2010}} to graduate school.
Experimental work reported in {{harvtxt|Caragea|Vishkin|2011}} for the [[Maximum flow problem]], and in two papers by {{
XMT prototyping was culminated in {{harvtxt|Ghanim|Vishkin|Barua|2018}}, establishing that lock-step parallel programming (using ICE) can achieve the same performance as the fastest hand-tuned multi-threaded code on XMT systems. This 2018 result sharpens the contrast between XMT programming and the multi-threaded programming approaches employed by nearly all
==References==
Line 41:
| doi=10.1145/321812.321815
| citeseerx=10.1.1.100.9361
| s2cid=16416106
}}.
*{{Citation
Line 61 ⟶ 62:
| year = 1992
| isbn = 978-0-201-54856-3
}}
* {{Citation
Line 75:
| year = 2001
| isbn = 978-0-471-35351-5
}}
*{{Citation
Line 84 ⟶ 83:
| year = 2003
| title = Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach
| journal = Theory of
| volume = 36
| issue =5
| pages = 551–552
| doi =10.1007/s00224-003-1086-6
| s2cid = 1929495
| url=http://www.umiacs.umd.edu/users/vishkin/XMT/spaa01-j-03.pdf
}}.
Line 98:
| last4 = Ellison | first4 = David
| year = 2010
| title = Proceedings of the 41st ACM technical symposium on Computer science education - SIGCSE '10
| title = Is teaching parallel algorithmic thinking to high-school student possible? One teacher's experience. ▼
| pages = 290▼
| doi =10.1145/1734263.1734363
|
▲|
▲| pages =
| isbn = 9781450300063
| doi =▼
| doi-access = free
}}.
*{{Citation
Line 117:
| doi=
| contribution-url=http://www.umiacs.umd.edu/users/vishkin/XMT/spaa98.ps
}}.
* {{Citation
Line 140 ⟶ 139:
| url=http://www.umiacs.umd.edu/users/vishkin/XMT/CompFrontiers08.pdf
| isbn=9781605580777
| s2cid=11557669
}}.
*{{Citation
Line 149:
| journal=Communications of the ACM
| volume=54
}}.
*{{Citation
Line 160 ⟶ 161:
| title-link=Symposium on Parallelism in Algorithms and Architectures
| isbn=9781450307437
| s2cid=5511743
}}.
*{{Citation
Line 167 ⟶ 169:
| contribution=Better speedups using simpler parallel programming for graph connectivity and biconnectivity
| pages=103–114
| year=
| doi=10.1145/2141702.2141714
| isbn=9781450312110
| s2cid=15095569
}}.
*{{Citation
Line 177 ⟶ 180:
| contribution=Brief announcement: speedups for parallel graph triconnectivity
| pages=190–192
| year=
| doi=10.1145/2312005.2312042
| title-link=Symposium on Parallelism in Algorithms and Architectures
| isbn=9781450312134
| s2cid=16908459
}}.
*{{Citation
Line 191 ⟶ 195:
| volume=57
| issue=4
| s2cid=30098719
}}.
*{{Citation
Line 204 ⟶ 209:
| doi=10.1109/TPDS.2017.2754376
| hdl=1903/18521
| doi-access=free
| hdl-access=free
}}.
==Notes==
{{reflist
==External links==
| |||