Parallel Computing for Data Science

3.12. RANDOM TASK PERMUTATION 75

and

e = ic (3.6)

with c being the chunk size:

c = n/p (3.7)

(assuming n is divisible by p).

Let µ and σ

2

represent the mean and variance of the t

i

:

µ =

1

n

n

X

i=1

t

i

(3.8)

σ

2

=

1

n

n

X

i=1

(t

i

− µ)

2

(3.9)

Note that these are not the mean and variance of some hypothesized parent

distribution. No probabilistic model is being assumed for the t

i

; indeed,

they are not even being assumed random. So, µ and σ

2

are simply the

mean and variance of the set of numbers t

1

, ..., t

n

.

Then T

s

, ..., T

e

form a simple random sample (i.e. without replacement)

from t

1

, ..., t

n

. From finite-population sampling theory, the total computa-

tion time U

i

for the i

th

pro ...