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?

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

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

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

Vielzahl von Entscheidungs- und Optimierungsprobleme

Verschiedene Methodologien parallel ausführbar

Effektive ArbeitslastKommunikationImplizit durch Struktur

Speed-up reduziertKommunikations-OverheadSuch-Overhead

Agenda

Documents

Agenda diciembre alemán

25.05.2003Köln - W.Janka1 AGENDA 21 Rückblick Lokale Agenda 21 der Stadt Neumarkt (Tag der Visionen – 18.5.2003) Ausstellung Agenda 21 an der Staatlichen

AGENDA TODI 2016

Smart.con SAP 2012 Agenda

Agenda alemán julio

Agenda 29. februar:

Agenda Agrichen - Conferencia

Agenda 08.03-15.03.2015

Kultur agenda

Agenda agosto alemà

Agenda febrero alemán

fetisch agenda

agenda alema mayo

UDEF_2014_02_28_Gürtel_análsis agenda Crespo

Agenda 2010

Nachhaltigkeit Dekade Agenda

Agenda noviembre alemán

Was ist die lokale Agenda? Agenda = Handlungsprogramm Agenda 21 = Globales Programm zur Lösung der Umweltzerstörung, Armut und Unterentwicklung ↔ wurde

Agenda 21 Agenda (lat.): was zu tun ist 21: für das 21. Jahrhundert

Agenda Theiner