10.3 Paralleles Suchen

Parallele Suchverfahren verursachen einen Kommunikationsoverhead aufgrund von

• Datentransfer
• idle times (Leerlauf wegen Lastungleichheit)
• memory contention (gleichzeitiger Speicherzugriff)

Zusätzlich kann ein Suchoverhead entstehen, da der parallele Algorithmus ggf. andere Teile des Suchraums exploriert als der sequentielle Algorithmus.

Lastungleichgewicht bei Aufteilung für 2 bzw. 4 Prozessoren

Offenbar kann eine statische Lastverteilung zu großem Ungleichgewicht führen. Also muß zur Laufzeit eine dynamische Lastverteilung stattfinden.

Generelles Schema für dynamische Lastverteilung