Subject: Re: Multiprocessor with NetBSD ?
To: NetBSD-current <current-users@netbsd.org>
From: mike stone <bsdusr@yawp.com>
List: current-users
Date: 06/04/2001 13:42:11
> I'm not aware of any system that will give "a factor of N
> speed up, for each Nth processor". I do not believe it
> possible for inherent reasons of memory and i/o contention
> alone.

there are two major problems:  the Von Neumann bottleneck, and
Amdahl's Law.

the Von Neumann bottleneck means that ultimately, the speed of
the memory bus is the limiting factor in any tightly-coupled
MP system.   if data travels between RAM and the CPUs at a
maximum rate of N bits per second, that's your theoretical upper
limit on processing speed, regardless of how many CPUs you have.
CPUs can't crunch data if they don't have data to crunch.

no matter how fast your memory bus is, you can keep adding CPUs
until you saturate it.    from then on, every additional CPU you
add will just sit idle because it's starved for data.

the memory bus of a tightly-coupled MP system is an inescapable
serial dependency in an otherwise parallel system.   and that leads
us straight into Amdahl's Law.

Amdahl's Law states that the speedup of parallel processing is:

     S = N / (B*N) + (1-B)

where N is the number of processors, and B is the percentage of
serial dependency in the system.   a quick script:

     $B = .05;

     for $i (1..50) {
         $N = $i * 5;
         $S = $N/(($N*$B) + (1-$B));

         $max = ($S > $max) ? $S : $max;
         push @S, $S;
     }

     $max = int ($max) + 1;

     for $i (0..$max) {
         $l = '';
         $n = $max - $i;

         for $s (@S) {
             $l .= ($s > $n) ? '|' : ' ';
         }
         print $l, "\n";
     }

                                       ||||||||||||||||
                          |||||||||||||||||||||||||||||
                    |||||||||||||||||||||||||||||||||||
                |||||||||||||||||||||||||||||||||||||||
             ||||||||||||||||||||||||||||||||||||||||||
            |||||||||||||||||||||||||||||||||||||||||||
          |||||||||||||||||||||||||||||||||||||||||||||
         ||||||||||||||||||||||||||||||||||||||||||||||
        |||||||||||||||||||||||||||||||||||||||||||||||
        |||||||||||||||||||||||||||||||||||||||||||||||
       ||||||||||||||||||||||||||||||||||||||||||||||||
       ||||||||||||||||||||||||||||||||||||||||||||||||
      |||||||||||||||||||||||||||||||||||||||||||||||||
      |||||||||||||||||||||||||||||||||||||||||||||||||
     ||||||||||||||||||||||||||||||||||||||||||||||||||
     ||||||||||||||||||||||||||||||||||||||||||||||||||
     ||||||||||||||||||||||||||||||||||||||||||||||||||
     ||||||||||||||||||||||||||||||||||||||||||||||||||
     ||||||||||||||||||||||||||||||||||||||||||||||||||


shows that for constant B greater than 0, speedup is far from linear
with respect to N.

so.. the two real concerns of building MP sytems are making sure you
have enough memory bus to feed all your CPUs, and trimming as much
serial dependency out of the code as possible.   for tightly-linked
MP systems, sharing the memory bus is an inescapable serial dependency,
so you're pretty much stuck with sub-linear speedup.




mike
.