@article {18028,
	title = {Experiments with list ranking for explicit multi-threaded (XMT) instruction parallelism},
	journal = {J. Exp. Algorithmics},
	volume = {5},
	year = {2000},
	month = {2000/12//},
	abstract = {Algorithms for the problem of list ranking are empiricallystudied with respect to the Explicit Multi-Threaded (XMT) platform
for instruction-level parallelism (ILP). The main goal of this
study is to understand the differences between XMT and more
traditional parallel computing implementation platforms/models as
they pertain to the well studied list ranking problem. The main two
findings are: (i) good speedups for much smaller inputs are
possible and (ii) in part, the first finding is based on a new
variant of a 1984 algorithm, called the No-Cut algorithm. The paper
incorporates analytic (non-asymptotic) performance analysis into
experimental performance analysis for relatively small inputs. This
provides an interesting example where experimental research and
theoretical analysis complement one another. Explicit
Multi-Threading (XMT) is a fine-grained computation framework
introduced in our SPAA{\textquoteright}98 paper. Building on some key ideas of
parallel computing, XMT covers the spectrum from algorithms through
architecture to implementation; the main implementation related
innovation in XMT was through the incorporation of low-overhead
hardware and software mechanisms (for more effective fine-grained
parallelism). The reader is referred to that paper for detail on
these mechanisms. The XMT platform aims at faster single-task
completion time by way of ILP.
},
	isbn = {1084-6654},
	doi = {10.1145/351827.384252},
	url = {http://doi.acm.org/10.1145/351827.384252},
	author = {Vishkin,Dascal and Vishkin, Uzi}
}
