Agenda

Institut für Praktische Informatik

Prof. Dr. Herbert Kuchen

Kombinatorische Suche

Felix Potthoff

Seminar „Parallel Programming and Parallel Algorithms“Prof. Dr. Herbert Kuchen

Institut für Praktische InformatikWestfälische Wilhelms-Universität Münster

12.01.2010

2 Institut für Praktische InformatikProf. Dr. Herbert Kuchen

Agenda

EinführungGrundlagenMotivationSpeed-up

Divide and Conquer (DaC)Sequentieller „Divide-and-Conquer“-AlgorithmusParallele „Divide-and-Conquer“ Varianten

BacktrackingSequentieller „Backtrack“-Algorithmus Parallele „Backtracking“ VariantenDistributed Termination Detection

Alpha-Beta-SucheSequentielle „Alpha-Beta-Suche“Parallele „Alpha-Beta-Suche“

Zusammenfassung


Kombinatorische Suche

Kombinatorische SucheProzessEine oder mehr optimale oder suboptimale Lösung zu findenIn einem definierten Problembereich

Weitreichendes EinsatzgebietDatenbankenExperten Kontroll-SystemeRoutenplanung

Einführung - DaC - Backtracking - A-BSuche - Zusammenfassung


Motivation

Parallele ArchitekturenMulticore-prozessoren, Hyper-threadingShared MemoryHardware immer günstiger



Such-Methodologien

Divide and Conquer

Branch and Bound

Backtracking

Spiel-Baum-SuchenMini-Max-SucheAlpha-Beta-Suche



Speed-Up

Speed-up (Beschleunigung)N Prozessoren Speed-up = N?

Nein!



Agenda





Zusammenfassung



Einleitung Divide and Conquer

Aufteilen in TeilproblemeLösen mit DaCWeitere Teilprobleme möglich

Kombinieren zur Lösung

Anwendungsgebiete:Sortier-Algorithmen

QuicksortMergesort

…



Quicksort Algorithmus

Parameter:A – Das zu sotierende Arraylinks - Startpositionrechts - Endposition

Quicksort(A, links, rechts)

if links < rechts then

seperator Partition(A, links, rechts)

Quicksort(A, links, seperator – 1)

Quicksort(A, seperator, rechts)

end if



Quicksort Beispiel


Parameters:A – Das Array zum Sortierenlinks - Startpositionrechts - Endposition

Quicksort(A, links, rechts)if links < rechts then

seperator Partition(A, links, rechts)

Quicksort(A, links, seperator – 1)

Quicksort(A, seperator, rechts)

end if


Parallele Ausführung- Multiprozessor

Original- und Teil-Probleme in zentralem Speicher

Effiziente Arbeitslastverteilung

Bottleneck



Parallele DaC Variante – Multicomputer(1)


Teil-Probleme im Speicher eines Prozessors

Effiziente Arbeitslastverteilung

Overhead fürVerteilungKombination


Parallele DaC Variante – Multicomputer(2)


Verteilen der Teil-Probleme auf die Speicher der Prozessoren

Höherer Speed-up möglich

Gleichmäßige Arbeitslastverteilung schwieriger


Agenda





Zusammenfassung



Einleitung Backtracking

Kind-Knoten generieren

Beliebigen Kind-Knoten wählen

Kind-Knoten mit gleicher Technik bearbeiten

Rekursion abbrechen, wenn:Alle Kind-Knoten besuchtSackgasse



Anwendung Backtracking

N-Queens

4-Queens


Lösung 4-Queens-Problem [PW04]


Backtracking Suchbaum



Paralleles Backtracking

Einen Teil-Baum für jeden Prozessor

ProblemUnausgeglichene TeilbäumeBesuch unnötiger Knoten

LösungBei erster Lösung stoppenNachrichten



Distribution termination detection

LaufzeitfehlerNachrichten gleichzeitig

Dijkstra‘s „Distribution termination detection“Stellt sicher, dass sich keine Nachricht im System befindetSuccessoringProzessor, Token

FarbeNachrichtenzähler



Successorring



DDS Abbruchbedingungen

Token wieder am Ausgangspunkt

Nachrichtenzähler des Token 0

Farbe des Tokens weiß

Nachrichtenzähler des Anfangsprozessor 0



Zusammenfassung Backtracking

DFS

Lineare Speichernutzung

Effektive Arbeitslastverteilung als Grundproblem Zuteilung vieler Teilbäume als Potentielle Lösung

Distributed termination detection



Agenda





Zusammenfassung

Einleitung - DaC - Backtracking - A-BSuche - Zusammenfassung


Alpha-Beta-Suche

Spielbäume

Abschneiden (Pruning)

Alpha und BetaUnter- und ObergrenzeSuch-Fenster

Kategorisierung der Knoten



Alpha-Beta-Pruning



Pruning

Best-caseEffektiv besuchte Knoten-Anzahl reduziert von b auf Perfekt geordneter Spielbaum

Worst-caseAlle Knoten


b


Parallele Alpha-Beta-Suchen(1)

Parallele Aspiration SearchSuchbereich auf Prozessoren verteiltMehr Prozessoren

Kleinere SuchbereicheGrößeres Pruning Potential

Maximum Speedup 5 oder 6 Unabhängig von Prozessoren-Anzahl

Parallele Sub-Tree-EvaluationSuch-OverheadKommunikations-OverheadPriorisieren der Suche von Teilbäumen



Parallele Alpha-Beta-Suchen(2)

Distributed Tree SearchZuteilungsstrategie für Prozessoren

Typ-1-KnotenAlle Prozessoren zum Kind-Knoten am weitesten links

Typ-2 oder Typ-3-Knoten, sowie Ober-und UntergrenzenNeuer Prozess pro KnotenMindestens einen Prozessor pro Prozess

Erneute ZuteilungEffektive Verteilung der ArbeitslastMitsenden von Alpha- und Beta-Werten

Reduziert Such-OverheadVergrößert Kommunikations-Overhead



Agenda





Zusammenfassung



Zusammenfassung

Vielzahl von Entscheidungs- und Optimierungsprobleme

Verschiedene Methodologien parallel ausführbar

Effektive ArbeitslastKommunikationImplizit durch Struktur

Speed-up reduziertKommunikations-OverheadSuch-Overhead


Documents

Agenda