Explicit multi-threading: Difference between revisions

Revision as of 16:56, 27 July 2012

Revision as of 08:09, 10 January 2013

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.

The XMT paradigm was introduced by [[Uzi Vishkin]].

==The main levels of abstraction of XMT==

The Explicit Multi-Threading (XMT) computing paradigm integrates several levels of abstraction.

Line 19 ⟶ 20:

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"].</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 {{harvtxt|Edwards|Vishkin|2012}} for the Graph Connectivity ([[Connectivity (graph theory)]]), Graph Biconnectivity ([[biconnected graph]]) and Graph Triconnectivity ([[Triconnected component]]) problems demonstrated that for some of the most advanced algorithms in the parallel algorithmic literature, the [[XMT]] paradigm can offer 8 times to over 100 times greater speedups than for the same problems on state-of-the-art multi-core computers. Each reported speedup was obtained by comparing clock cycles on an XMT prototype relative to the fastest serial algorithm running on the fastest serial machines.

Line 88 ⟶ 90:

| year = 2010

| title = Is teaching parallel algorithmic thinking to high-school student possible? One teacher’s experience.

| journal = ACM Technical Symposium on Computer Science Education (SIG CSE), Milwaukee, WI, March 10-1310–13, 2010, to appear

| volume =

| issue =

Line 145 ⟶ 147:

| title=Proc. 23rd ACM [[Symposium on Parallelism in Algorithms and Architectures]] (SPAA)

| contribution=Brief announcement: better speedups for parallel max-flow

| pages=131-134131–134

| year=2011

| doi=10.1145/1989493.1989511

Line 154 ⟶ 156:

| title=Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores

| contribution=Better speedups using simpler parallel programming for graph connectivity and biconnectivity

| pages=103-114103–114

| year=2012

| doi=10.1145/2141702.2141714

Line 163 ⟶ 165:

| title=Proc. 24th ACM [[Symposium on Parallelism in Algorithms and Architectures]] (SPAA)

| contribution=Brief announcement: speedups for parallel graph triconnectivity

| pages=190-192190–192

| year=2012

| doi=10.1145/2312005.2312042