workman@decwrl.dec.com (Will Workman) (02/13/90)
I will ask our system analyst, Tim Busse, to respond to your
request for published papers on problems that do not lend
themselves to data parallel techniques, but your integer
sorting problem along with other sorts lend themselves to
data parallel techniques due to the reductions possible on
sets performed in parallel. If you would like to discuss
via phone, please call Tim on (301) 571-9480. Also, as
you may know, we are working with Jos. Flaherty on putting
one of our MP-1 systems into the RPI CS Dept over the next
few months.
Best Regards > > Will Workman, Dir of Fed Mkt, MasPar
>From fpst@hubcap.clemson.edu Fri Feb 9 16:45:33 1990
Received: by armada.MasPar.Com (5.57/Ultrix2.0-B)
id AA01399; Fri, 9 Feb 90 16:46:11 PST
Received: by decwrl.dec.com; id AA10849; Fri, 9 Feb 90 05:13:56 -0800
Received: by hubcap.clemson.edu; Fri, 9 Feb 90 08:13:39 -0500
Date: Fri, 9 Feb 90 08:13:39 -0500
From: fpst@hubcap.clemson.edu (Steve Stevenson)
Message-Id: <9002091313.AA13496@hubcap.clemson.edu>
To: DELAGI@SUMEX-AIM.Stanford.EDU, workman@argosy,
awilkinson@nasamail.nasa.gov, chokchai@encore.kent.edu,
dwk@cs.tufts.edu, harrison@tcg.anl.gov, hcube-users@hamlet.caltech.edu,
hcube-users@mtu.edu, incoming-parallel@ntt-20.ntt.jp,
kaojh@eecs.nwu.edu, lnl%psuecl.bitnet@relay.cs.net,
local-parallel%inmos.co.uk@nss.cs.ucl.ac.uk,
munnari!sheila.cs.jcu.oz.au!olivier@uunet.UU.NET,
pratt@cs.stanford.edu, rkz@TYRANNOSAURUS.SCRC.Symbolics.COM,
scherrer@lovada.dec.com, yuris@flossie.che.wisc.edu
Status: R
Newsgroups: comp.parallel
Approved: parallel@hubcap.clemson.edu
From: valoisj@turing.cs.rpi.edu (John Valois)
Subject: Non-optimal parallel algorithms
I am looking for references to problems for which the best known
parallel algorithms are not optimal; i.e. the work (processor-time
product) done by the parallel algorithm is greater than the running
time of a sequential algorithm.
Three problems I know of are integer sorting, maximal independent set,
and unweighted single source shortest paths. I am especially
interested in problems for which the parallel and sequential work
differ by more than a log factor.
Replies by e-mail, please.
John Valois