Path: utzoo!attcan!uunet!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!hubcap!slim
From: slim@cis.ohio-state.edu (Scott Whitman)
Newsgroups: comp.parallel
Subject: Re: Virtual processor ratio (was Re: Paris and Programming the Connection Machine)
Message-ID: <8428@hubcap.clemson.edu>
Date: 19 Mar 90 14:25:47 GMT
Sender: fpst@hubcap.clemson.edu
Organization: Ohio State Computer Science Department
Lines: 41
Approved: parallel@hubcap.clemson.edu

In regards to virtual processor comments, right now I am working on
theorizing the nearly optimal ratio for a particular application
of virtual processors to real processors.  In this case, I am
working on a BBN Butterfly and the virtual processors are really just
tasks.  In any case, I am trying to come up with a theory for determining
apriori what a nearly optimal ratio would be based on the size of
the input data and the number of processors one is working on (i.e., the
best ratio may change as depending one how many processors are assigned
to the problem).

In general, I believe that an increase in this ratio is worthwhile in order
to reduce the end-effects problem.  However, a certain point of no return
is hit when the overhead of starting a certain number of tasks exceeds
the gains one receives in reducing the end effects.  At this point, we have
hit the nearly optimal ratio (actually, just prior to this).

Anyway, we are trying to determine a good heuristic to use to obtain this
ratio.  Right now I am more or less basing it on the input data size, and
the overhead to start a new task, and additionally, the fact that the
dataset somewhat increases in size due to duplication as the ratio increases.

The problem is that I don't believe this model is very accurate.  In fact,
for two inputs of the same size, it is not necessarily true that the time will
be nearly the same for each.  It is roughly true, though, that a larger input
size results in a longer overall time and so our model bases its heuristic
on this fact.  Obviously the machine parameters also make a great deal of
difference, but for the moment we are ignoring these.

What I'd like to know is if anyone has any comments regarding this strategy
and also if there are any papers on this subject matter.

		Advthanksance,


		-Scott Whitman


--
 Scott Whitman, Department of Computer and Information Science
 slim@cis.ohio-state.edu    or   ...!{pyramid,killer}!osu-cis!slim
The Ohio State University; 2036 Neil Ave. Columbus OH USA 43210-1277