Parallel Radiosity ComputationFull text in Czech (PostScript, 105 pages, 3602KB gzipped), PCL output (LaserJet 4L, 523KB in RAR format)
Paper proposed to WSCG'96 (PostScript, 10 pages, 420KB gzipped)
Abstract:
This paper is concerned with parallelization of progressive version of radiosity method with light energy overshooting and adaptive surface subdivision. A cluster of workstations under operating system Unix was chosen as parallel hardware. Inter-process communication was ensured by PVM. Because development of complex parallel programs under Unix is relatively frustrating, there was developed emulator PVM for MS-Windows first and then nearly all the work was done under this emulator on a single PC.
This paper summarizes most of today known modifications of radiosity method. But the aim was a practical parallel implementation of this modifications. There is not a detail description of all known modifications, but one can meet adaptive surfaces subdivision at the running time and light energy overshooting here. Also some special aspects of development of complex parallel programs are mentioned such as fault tolerance and environment independence. Effectivity of whole system will not dramatically decrease with workstations speed fluctuation (so that another users can work on these workstations) nor with short net disconnection. Calculation will not break even after crash of some workstation.
The Master - Worker architecture was chosen to parallelize radiosity. Whole system consists of four different process types. The Monitor process starts computing on workstations and then shows running information. Computing is controlled by process Master. Master chooses the most lighted paths and distributes them to processes Worker. It shoots light energy to scene and adaptively divides pathes. Processes Worker calculate form factors. The hemicube algorithm is used. Process Show generates output image. Show is able to save picture in Targa format or description of scene in IRIS Inventor's format. In MS-Windows operating system process Show is interactive and user can go through scene in nearly real time.
We are often interested in efficiency which can be achieved by parallel computing on more workstations. At the end of paper one can see several graphs showing achieved results. But the included graphs should be understood only as a selection of some most interesting and most important characteristics of whole developed parallel system.
Keywords:
radiosity, parallel algorithms, overshooting, progressive refinement, PVM, cluster of workstations, master-worker, form factors, halfcube, fault tolerance
Results:
Room (640x480, 22Kb)
Maze (640x480, 20Kb)
Tato prace se zabyva paralelizaci progresivni verze radiacni metody s prestrelovanim svetelne energie a adaptivnim delenim ploch v prubehu vypoctu. Jako paralelni hardware byla zvolena sit pracovnich stanic bezicich pod operacnim systemem Unix. Komunikaci mezi jednotlivymi pocitaci zajistoval system PVM. Pro relativni slozitost vyvoje paralelnich programu pod operacnim systemem Unix byl nejprve vytvoren emulator PVM pro MS-Windows, ktery umoznil vyvinout temer cely system na jednom pocitaci PC.
V teto praci je mozno nalezt shrnuti vetsiny dnes znamych modifikaci radiacni metody. Jeji teziste vsak spociva predevsim v jejich prakticke paralelni implementaci. Neuvadi podrobny popis vsech znamych modifikaci, ale zabyva se predevsim adaptivnim delenim ploch v prubehu vypoctu a prestrelovanim energie. Krome paralelizace dosud znamych modifikaci radiacni metody se prace venuje take specifickym aspektum vyvoje paralelnich programu, jako je odolnost proti chybam a vlivu okoli. Efektivita celeho systemu tedy neni vyrazne ovlivnena kolisanim vykonu pracovnich stanic (na stanicich tedy mohou pracovat i jini uzivatele) ci kratkodobym snizenim propustnosti pouzite site. Vypocet se dokonce nezastavi ani pri havarii nektere ze stanic.
K paralelizaci byla zvolena architektura Master-Worker. Cely system se sklada z procesu ctyr typu. Proces Monitor slouzi ke spusteni celeho systemu a pozdeji zobrazuje informace o prubehu vypoctu. Cely vypocet je rizen procesem Master. Tento proces vybira nejsvetlejsi plochy a distribuuje je procesum Worker. Strili energii do sceny a stara se o adaptivni deleni ploch. Procesy Worker slouzi k vypoctu konfiguracnich faktoru. K tomu pouzivaji algoritmus polokrychle. Ke generovani vysledneho obrazku slouzi proces Show. Umoznuje ulozit obrazek na disk ve formatu Targa nebo popis sceny ve formatu programu IRIS Inventor. V prostredi MS-Windows je proces Show interaktivni a umoznuje prochazet scenou temer v realnem case.
Pri paralelni implementaci algoritmu nas obvykle zajima, jake efektivity lze dosahnout pri behu na vice pocitacich. Proto cela prace vrcholi ukazkou dosazenych vysledku a jejich zhodnocenim. Ukazku dosazenych vysledku je vsak nutno chapat spise jako vyber nekolika nejdulezitejsich a nejzajimavejsich charakteristik vytvorene paralelni implementace, protoze detailni rozbor vsech zavislosti by zabral nekolikanasobne vetsi prostor.
Klicova slova:
radiacni metoda, paralelni algoritmy, prestrelovani, progresivni radiacni metoda, PVM, sit pracovnich stanic, master-worker, konfiguracni faktory, polokrychle, odolnost proti chybam
(c) 1996 J.Pelikan, last change: 8.1.1996
Send comments/requests to
Josef.Pelikan@mff.cuni.cz