Distribuované výpočty složitých stavových prostorů

KŘENEK, Aleš a Igor PETERLÍK. Distribuované výpočty složitých stavových prostorů. In Širokopásmové sítě a jejich aplikace. Olomouc: CESNET, z.s.p.o. s. 176-185. ISBN 80-244-1035-4. 2005.

Základní údaje

• Originální název: Distribuované výpočty složitých stavových prostorů
• Název česky: Distribuované výpočty složitých stavových prostorů
• Název anglicky: Distributed computation of complex state spaces
• Autoři: KŘENEK, Aleš (203 Česká republika, garant, domácí) a Igor PETERLÍK (703 Slovensko, domácí).
• Vydání: Olomouc, Širokopásmové sítě a jejich aplikace, od s. 176-185, 10 s. 2005.
• Nakladatel: CESNET, z.s.p.o.

Další údaje

• Originální jazyk: čeština
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Česká republika
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: tištěná verze "print"
• Kód RIV: RIV/00216224:14310/05:00013752
• Organizační jednotka: Přírodovědecká fakulta
• ISBN: 80-244-1035-4
• Klíčová slova anglicky: state space seach; latency; distributed computing
• Štítky: distributed computing, latency, state space seach

Anotace

Prohledávání složitých stavových prostorů představuje výpočetně náročný úkol vhodný pro distribuované prostředí. Existuje několik algoritmů, které se tímto problémem zabývají. Mezi ně patří také Transposition-Table-Driven Work Scheduling (TDS). Jedná se o distribuovaný algoritmus, který realizuje prohledávání stavového prostoru tak, že během samotného výpočtu není potřeba žádná synchronizace mezi výpočetními uzly. Využití asynchronního komunikačního modelu s sebou přínáši nezávislost na latenci propojující sítě. V naší práci se zabýváme rozšířením tohoto algoritmu, které umožňuje plnou rekonstrukci stavového prostoru, přičemž zachovává asynchronní model výpočtu. Rozšířený algoritmus TDS jsme implementovali vrámci aplikace, která představuje interaktivní model haptického chování biomolekul v rámci virtuální reality. Jedná se o aplikací simulující chemické děje, které jsou výpočetně náročné a nemůžou být realizovány během interakce. v první fázi je proto v distribuovaném prostředí předpočítán a prohledán celý stavový prostor aplikace. V následujícím textu přínášíme popis rozšířeného algoritmu a prezentujeme výsledky jeho testování v rámci uvedené aplikace.

Anotace anglicky

Searching in complex state spaces is a computationally expensive task suitable for distributed environment. We focus on the TDS seach algorithm featuring complete independence on communication latency. We present an extension of the algorithm, allowing also a comlete reconstruction of a discrete state space, preserving the ansynchronicity of the original algorithm. The extended algorithm was successfully used in an interacitve VR chemical application -- simulation of processes which cannot be done on-line. Instead, we search the entire state space of the interaction in advance. We also present results of measurements of real behaviour of the algorithm.

Návaznosti

• MSM0021622413, záměr: Název: Proteiny v metabolismu a při interakci organismů s prostředím

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Proteiny v metabolismu a při interakci organismů s prostředím

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy