SlideFinderPowerPoint search engine with thumbnail results
Newest Viewed Downloaded

Algorithm Engineering „Parallele Algorithmen“Stefan Edelkamp

Algorithm Engineering „Parallele Algorithmen“

Stefan Edelkamp

Übersicht

Parallele Musterdatenbanken Parallele Strukturierte Duplikatselimination Disjunkte Duplikatserkennungsbereiche ”Schlösser” Parallele Algorithmen Matrix-Multiplikation List Ranking Euler Tour P-Vollständigkeitstheorie

Übersicht

Parallele Musterdatenbanken Parallele Strukturierte Duplikatselimination Disjunkte Duplikatserkennungsbereiche ”Schlösser” Parallele Algorithmen Matrix-Multiplikation List Ranking Euler Tour P-Vollständigkeitstheorie

Parallele Musterdatenbanken

Only pattern databases that include the client tile need to be loaded on the client Because multiple tiles in pattern, from birds eye PDB loaded multiple times In 15-Puzzle with corner and fringe PDB this saves RAM in the order of factor 2 on each machine, compared to loading all In 36-Puzzle with 6-tile pattern databases this saves RAM in the order of factor 6 on each machine, compared to loading all Extends to additive pattern databases

Distributed Heuristic Evaluation

Assume one child processor for each tile one master processor B3 B1 B2 B8 B4 B5 B6 B7 B9 B10 B11 B12 B13 B14 B15 B0 B3 B1 B2 B8 B4 B5 B6 B7 B9 B10 B11 B12 B13 B14 B15 B0

Parallele Evaluation

35-Puzzle

Same bottleneck in external-memory search

Bottleneck: Duplicate detection Duplicate paths cause parallelization overhead A C D B B C D D D D Internal memory External memory vs. fast slow A

Disjoint duplicate-detection scopes B1 B0 B4 B0 B3 B1 B2 B8 B4 B5 B6 B7 B9 B10 B11 B12 B13 B14 B15 B0 B1 B4 B3 B2 B7 B2 B3 B7 B12 B8 B13 B15 B14 B11 B8 B12 B13 B11 B15 B14

Finding disjoint duplicate-detection scopes B1 B0 B4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 2 1 B2 B3 B7 0 1 0 B8 B12 B13 B11 B15 B14 1 2 2 0 1 2 2 2 2 1 2 2 2 2 2 0 1 1 1 0 1 0 2 3 3 2 B1 B5 B6 B4 B9 2 3 3 4 3 3

Implementation of Parallel SDD

Hierarchical organization of hash tables One hash table for each abstract node Top-level hash func. = state-space projection func. Shared-memory management Minimum memory-allocation size m Memory wasted is bounded by O(m#processors) External-memory version I/O-efficient order of node expansions I/O-efficient replacement strategy Benötigt nur ein Mutex “Schloss” B3 B1 B2 B8 B4 B5 B6 B7 B9 B10 B11 B12 B13 B14 B15 B0

Übersicht

Parallele Musterdatenbanken Parallele Strukturierte Duplikatselimination Disjunkte Duplikatserkennungsbereiche ”Schlösser” Parallele Algorithmen Matrix-Multiplikation List Ranking Euler Tour P-Vollständigkeitstheorie

Parallelle Matrix- Multiplication

Parallele Matrix Multiplication

Exklusives Schreiben

Parallele Kopien

Fazit Matrix Multiplication

Paralleles List Ranking

List Ranking

Erster Algorithmus

Showing 1 - 20 of 75 items Details

Name: 
AE-ParalleleAlgorithmen
Author: 
Arne Schuldt
Company: 
Technologie-Zentrum In...
Description: 
Algorithm Engineering „Parallele Algorithmen“Stefan Edelkamp
Tags: 
parallele | algorithmus | b15 | b11 | memory | b13 | b12 | randomisierter
Created: 
4/2/2008 9:02:34 AM
Slides: 
75
Views: 
0
Downloads: 
0
Rating: 
0


> Comment



Share this presentation
|
1234 Next >>

Comments

Share this presentation:

|
Sitemap