PICOLL - kollektive Operationen für PI

Sourcen:

• picoll.c

Vergleich mit PI:

• einfacher
• keine Master/Slave-Struktur mehr (außer zum I/O)
• schneller, wenn broadcast und reduce auf ``spanning tree'' implementiert
  
  $$\tau(P) = (9 \lceil N/P \rceil + P-1) \tau_A + 2 \lceil \log_2 P \rceil \tau_C(1)$$
  
  

• Zeiten auf der N-Class:

Broadcast auf dem ``spanning tree'':

• Pseudocode bei $P = 2^d$ Prozessoren
        for i=0 to d-1
          if (me <= 2**i - 1)
            send to me + 2**i
          else if (me <= 2**(i+1) - 1)
            receive from me - 2**i
       
  
  
• Zahl der Send/Receive-Runden nur logarithmisch mit P,
• entsprechender Performance-Gewinn, falls das Verbindungsnetzwerk genügend viele gleichzeitige Sends ermöglicht