Path: utzoo!attcan!uunet!ns-mx!iowasp!deimos.cis.ksu.edu!rutgers!cs.utexas.edu!samsung!sol.ctr.columbia.edu!emory!hubcap!rrt
From: rrt@romeo.cs.duke.edu (Russell R. Tuck)
Newsgroups: comp.parallel
Subject: Re: Virtual processor ratio (was Re: Paris and Programming the Connection Machine)
Message-ID: <8403@hubcap.clemson.edu>
Date: 16 Mar 90 14:16:55 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 32
Approved: parallel@hubcap.clemson.edu

In article <8374@hubcap.clemson.edu> bcsaic!carroll@beaver.cs.washington.edu (Jeff Carroll) writes:
>	I've read a couple of statements now to the effect that
>efficiency improves as virtual processor ratio increases. This seems
>counterintuitive, as I would expect each virtual processor to add
>(superlinearly) to the overhead of "processor management".

There are two unavoidable costs to virtual processors that I know of.
(1) Physical PE memory is shared by virtual processors, so memory available
    per virtual processor is inversely proportional to VPR.
(2) Each operation has to be done VPR times, so it takes VPR times as long.

There are also two kinds of processing overhead that I know of.
(a) Any PE addresses have to be adjusted for each repetition of the operation.
    This is just adding a constant, I think.
(b) Every operation, regardless of VPR, has to be sent from host to sequencer.
Note that all the overhead is linear (1,2,a) or constant (b) in VPR.

Here's the explanation for improved efficiency at high VPR as I understand it.
Host to sequencer overhead dominates execution time for operations with VPR=1.
The sequencer handles (2) and (a), so (b) is invariant (or nearly so) with
respect to VPR.  (1) affects whether programs run out of PE memory, but not
the speed of those that don't.  So larger VPRs get to amortize (b) over more 
work, and so make better use of the available PE cycles.
 
PS- I over-generalized when I said recently that MIMD folks blithely asssume
    constant-time parallel memory access.  Some do, but many others don't, as
    a friend working on the BBN Butterfly here at Duke reminded me.  Sorry.
 
Russ Tuck                              rrt@cs.duke.edu
Computer Science Department            ...!{decvax|mcnc}!duke!rrt
Duke University                        
Durham, NC 27706, USA                  (919) 660-6527