Párhuzamosított módszerek rácsos tartók geometriai érzékenységének vizsgálatára Dóbé Péter BME IIT [
[email protected]]
Tóth Krisztina BME SZT [
[email protected]]
Networkshop 2010, Debrecen 2010. április 8.
Dr. Domokos Gábor BME SZT [
[email protected]]
Közkedvelt rácsos tartók
Sydney Harbour Bridge
2011. 09. 02.
Networkshop 2010, Debrecen
2
Közkedvelt rácsos tartók
Komárom, Erzsébet híd
2011. 09. 02.
Networkshop 2010, Debrecen
3
Közkedvelt rácsos tartók
Dunaföldvár, Beszédes József híd
2011. 09. 02.
Networkshop 2010, Debrecen
4
Rúdszerkezet modell
• Rudak – nyújthatatlan – összenyomhatatlan – hajlíthatatlan
2011. 09. 02.
• Csuklók – rudak végpontjait kapcsolják össze – elfordulást megengednek súrlódásmentesen
Networkshop 2010, Debrecen
5
Rúdszerkezet modell • Síkbeli rúdszerkezetek
2011. 09. 02.
Networkshop 2010, Debrecen
6
Rúdszerkezet modell • Merevség
merev
nem merev
• Minimális merevség – rúd nem hagyható el
minimálisan merev
2011. 09. 02.
nem minimálisan merev
Networkshop 2010, Debrecen
7
Rúdszerkezet modell • Letámasztott rúdszerkezet 1 merev
nem merev
2 3
4
• Megfeleltethetı egy letámasztás nélkülivel
1
2 3 4
2011. 09. 02.
Networkshop 2010, Debrecen
8
Rúdszerkezet modell • Rúdszerkezet megadása (x3,y3) v3 (x1,y1) (x4,y4)
(x1,y1)
(x2,y2) (x3,y3)
v1
(x2,y2)
v2
v4
v3
v1
v2
(x3,y3) (x4,y4) (x1,y1)
(x2,y2)
Metrikával 2011. 09. 02.
Gráffal Networkshop 2010, Debrecen
9
Rúdszerkezet modell • A gráf elég a (minimális) merevség eldöntéséhez? • infinitezimális mozgás van merev
nem merev
Ugyanaz a gráfjuk! • Az infinitezimális mozgás ritka • Ha csak infinitezimális mozgás fordulhat elı: (minimális) generikus merevség • Ehhez elég a gráfot vizsgálni 2011. 09. 02.
Networkshop 2010, Debrecen
10
Geometriai érzékenység • Kis pontatlanság a rácsos tartó építése során A rudak mekkora részén változnak meg az erık? • Geometriai érzékenység egy lehetséges mérıszáma: érzékenységi index • Ez meghatározható a gráf alapján, tisztán kombinatorikai eszközökkel 2011. 09. 02.
Networkshop 2010, Debrecen
11
Geometriai érzékenység • Vizsgálatunk célja: – Rácsos tartó érzékenységi indexének meghatározása – általában letámasztott, – minimálisan generikusan merev – rúdszerkezeti gráfjából kiindulva.
2011. 09. 02.
Networkshop 2010, Debrecen
12
A vizsgálat lépései
L1 – Letámasztás nélküli ekvivalens gráf elıállítása L2 – Minimális generikus merevség ellenırzése L3 – Érzékenységi index meghatározása
2011. 09. 02.
Networkshop 2010, Debrecen
13
L1 – Letámasztás nélküli ekvivalens gráf elıállítása • Új élek bevezetésével könnyen elıállítható – Letámasztási csomópontok között, bizonyos szabálynak megfelelıen 1
1
2 3
4
2 3 4
• Egyszerő elıfeldolgozási lépés (gyors)
2011. 09. 02.
Networkshop 2010, Debrecen
14
L2 – Minimális generikus merevség ellenırzése • Letámasztás nélküli gráfokra: Lovász és Yemini algoritmusa – Matroidelméleti eljáráson alapul (Edmonds matroidpartíciós algoritmusa)
• Az algoritmus hatékony, de nagyon sok csukló esetén sokáig tart • Implementáció Matlab nyelven 2011. 09. 02.
Networkshop 2010, Debrecen
15
L3 – Érzékenységi index meghatározása • Az érzékenységi indexhez szükség van az összes csukló merev magjára • Merev mag: a csuklót és szomszédait tartalmazó legkisebb merev rész
• Érzékenységi index: 1-nél nem nagyobb pozitív szám; merev magok csuklószámának összege elosztva a rúdszerkezet csuklószámának négyzetével 2011. 09. 02.
Networkshop 2010, Debrecen
16
Merev mag keresése • Naiv módszer: – csuklószám szerint növekvı sorrendben ellenırizni az összes lehetséges részgráfot – a legelsı megtalált merev rész lesz a merev mag Hatékonysága nagyon rossz! (exponenciális futási idı)
• Egyelıre csak naiv implementáció van (Matlab) • Ha lesz hatékonyabb: nagyon sok csukló esetén az is sokáig tart 2011. 09. 02.
Networkshop 2010, Debrecen
17
Párhuzamosítás lehetıségei • A lépések egymásra épülnek, de külön számítási egységen végezhetık G
L1
L2
L3
I
nem
– Bemenet: G gráf – Kimenet: I érzékenységi index VAGY: „nem minimálisan generikusan merev” válasz 2011. 09. 02.
Networkshop 2010, Debrecen
18
Párhuzamosítás lehetıségei • Legegyszerőbb párhuzamosítás: különbözı rácsos tartók egymástól függetlenül G1
L1
L2
L3
I1
L3
I2
L3
I3
nem G2
L1
L2 nem
G3
L1
L2 nem
2011. 09. 02.
Networkshop 2010, Debrecen
19
Párhuzamosítás lehetıségei • L3 finomítása: csuklók merev magjai függetlenül kereshetık L3(v1) L1
L2 nem
...
G
L3(v2)
L3’
I
L3(vn)
• Egy csukló merev magja segíthet a többi merev mag megtalálásában – Szőkítheti a keresési teret – Ekkor viszont kommunikáció kell a számítási példányok között 2011. 09. 02.
Networkshop 2010, Debrecen
20
Végrehajtás griden • Az alkalmazott infrastruktúra: EGEE Grid – hungrid virtuális szervezet (VO)
• Elıkészítést igényel: Matlab nincs az erıforrásokon – Octave-val kompatibilissá tenni – vagy újraimplementálni (pl. C++)
2011. 09. 02.
Networkshop 2010, Debrecen
21
Összefoglalás • Van egy módszerünk rácsos tartók geometriai érzékenységének számítására • Ezt indokolt párhuzamosítva elvégezni – Nem minden lépése hatékony – Nagyon sok és/vagy nagyon nagy rácsos tartó
• A feladat felbontható független részekre • Ezért egy elosztott számítási rendszer, a grid erıforrásait tervezzük használni
2011. 09. 02.
Networkshop 2010, Debrecen
22
Köszönöm a figyelmet!
