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

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

Basic information

• Original name: Distribuované výpočty složitých stavových prostorů
• Name in Czech: Distribuované výpočty složitých stavových prostorů
• Name (in English): Distributed computation of complex state spaces
• Authors: KŘENEK, Aleš (203 Czech Republic, guarantor, belonging to the institution) and Igor PETERLÍK (703 Slovakia, belonging to the institution).
• Edition: Olomouc, Širokopásmové sítě a jejich aplikace, p. 176-185, 10 pp. 2005.
• Publisher: CESNET, z.s.p.o.

Other information

• Original language: Czech
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Czech Republic
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• RIV identification code: RIV/00216224:14310/05:00013752
• Organization unit: Faculty of Science
• ISBN: 80-244-1035-4
• Keywords in English: state space seach; latency; distributed computing
• Tags: distributed computing, latency, state space seach

Abstract

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.

Abstract (in English)

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.

Links

• MSM0021622413, plan (intention): Name: Proteiny v metabolismu a při interakci organismů s prostředím

Investor: Ministry of Education, Youth and Sports of the CR, Proteins in metabolism and interaction of organisms with the environment

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems