Explicit multi-threading

The Explicit Multi-Threading (XMT) computing paradigm integrates several levels of abstraction. The work-time (WT) (sometimes called work-depth) framework, introduced by , 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 . 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) and , as well as in the class notes . 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. The XMT multi-core computer systems provides run-time load-balancing of multi-threaded programs incorporating several patents. One of them 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 named Paraleap, that demonstrates the overall concept was completed. The XMT concept was presented in and and the XMT 64-processor computer in . 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 to graduate school. Experimental work reported in for the Maximum flow problem, and in two papers by 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. XMT prototyping was culminated in , 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 many other-core systems, whose race conditions and other demands tend to challenge, and sometimes even fail programmers . ==References==