| 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'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.
|
