[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
RE: what if "languages" don't respond to 754R ?
Nick,
Thanks for contributing to most interesting discussions.
IMHO, you have only shown that reproducible results are
not possible in a particular scenario, not for parallel codes
in general.
If one looked at matrix multiplication, for example, many
of the computations can be done in parallel with reproducible
results. For example, each processor can computed a distinct
result-matrix value in parallel, w/o affecting reproducibility.
In fact, the assignment of output-point to processor can be done
differently, while yielding the same result.
Are you perhaps more concerned about a specific class of parallel
codes?
Cheers,
DVJ
-----Original Message-----
From: stds-754@xxxxxxxx [mailto:stds-754@xxxxxxxx]On Behalf Of Nick
Maclaren
Sent: Friday, July 13, 2007 6:31 AM
To: stds-754@xxxxxxxx
Subject: Re: what if "languages" don't respond to 754R ?
I have asserted that it is impossible to impose a reproducibility
requirement on parallel codes, and I think that it is fair to justify my
statement. Here is a sketch of a common class of problem that cannot be
made reproducible without serialising it. There are many others.
There is a large (indefinite) number of task descriptions in an input
queue (it is irrelevant where that is, on disk or in memory). Each task
takes an unpredictable amount of time to complete, with no certainty
that its distribution has a mean (i.e. it may have a very long tail,
or it may not).
Each task can be handled independently on a single CPU, and delivers a
floating-point number, normally distributed with mean 0 and variance 1.
The program's specification is to return an estimate of the mean as fast
as possible, subject to it it having a 95% confidence bound of no more
than +-0.001.
One obvious implementation is that threads take a task off the queue
as soon as they are ready, update the sample statistics, and the
program terminates as soon as the limit is reached. In order for this
to return a reproducible result, the order of completion of each task
must be reproducible.
In order to do that, either the relative time taken to perform two
arbitrary tasks must the same on all systems, or the threads must be
forced to complete in a reproducible order. The former is ridiculous,
and the latter is incompatible with scalability for at least some
distributions of the time taken for a task.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email: nmm1@xxxxxxxxx
Tel.: +44 1223 334761 Fax: +44 1223 334679