Access Restriction

Author Vishkin, Dascal ♦ Vishkin, Uzi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract Algorithms for the problem of list ranking are empiricallystudied with respect to the Explicit Multi-Threaded (XMT) platformfor instruction-level parallelism (ILP). The main goal of thisstudy is to understand the differences between XMT and moretraditional parallel computing implementation platforms/models asthey pertain to the well studied list ranking problem. The main twofindings are: (i) good speedups for much smaller inputs arepossible and (ii) in part, the first finding is based on a newvariant of a 1984 algorithm, called the No-Cut algorithm. The paperincorporates analytic (non-asymptotic) performance analysis intoexperimental performance analysis for relatively small inputs. Thisprovides an interesting example where experimental research andtheoretical analysis complement one another. ExplicitMulti-Threading (XMT) is a fine-grained computation frameworkintroduced in our SPAA'98 paper. Building on some key ideas ofparallel computing, XMT covers the spectrum from algorithms througharchitecture to implementation; the main implementation relatedinnovation in XMT was through the incorporation of low-overheadhardware and software mechanisms (for more effective fine-grainedparallelism). The reader is referred to that paper for detail onthese mechanisms. The XMT platform aims at faster single-taskcompletion time by way of ILP.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 5

Open content in new tab

   Open content in new tab
Source: ACM Digital Library