Dana Vrajitoru
B424 Parallel and Distributed Programming

Embarrassingly Parallel Algorithms

Ideal Case

Variations / Hybrid Systems

Classic Examples

Monte Carlo Simulations

      Total points: 65
Points inside the circle: 56
pi ~= 4*56/65 = 3.44615

Sequential Algorithm

Count_pt(int N) {
  double count_in = 0;
  for (i=0; i < N; i++) {
    x = randr(-1, 1);
    y = randr(-1, 1);
    if (x*x+y*y <= 1)
      count_in++;
  }
  return count_in;
}
Pi(N) {
  return 4*Count_pt(N)/N;
}

Parallel Algorithm

n = N/no_proc; // assuming N is a multiple of no_proc
Master_count(n) {   
  Broadcast(n, 0);
  my_count = Count_pt(n);
  for (i=1; i < no_proc; i++) {
    Recv(count, i);
    my_count += count;
  }
  return my_count;
}
Slave_count() {
  Broadcast(n, 0);
  my_count = Count_pt(n);
  Send(my_count, 0);
}
Here the call to the function Master_count replaces the function call Count_pt in the function PI.

Pseudo Random Numbers

An Example
A common way to generate pseudo-random numbers is using large primes a and c:
y0 = s; // the seed
y0 = s;
yi+1 = a yi + c
We can convert it to a dependency on a number several positions back.
yi+k = ak yi + (ak-1 + ... + a2 + a + 1) c = ak + c (ak-1)/(a-1)

k Steps If we denote by A = ak and C = c(ak-1)/(a-1), then
yi+k = A yi + C (*)
computes the kth next number in the sequence.

The master computes p0, p1, ..., pk-1 using the simple formula, then sends them to each process.

Each process generates its own random numbers from the seed received from the master using (*).