NZK c.5 /03 - Jiang, W.

Novinky zeměměřické knihovny č.5/2003

*JIANG, W. - FRASER, D.*	VÚGTK 26 430
Paralelní způsob zpracování družicových snímků za pomoci rozděleného paměťového systému MIMD
[A Parallel Satellite Image Processing Approach Using a Distributed Memory MIMD System]

Přeložil S. Semerádová (zkráceno).
Zdiby: VÚGTK, 2003. - 3 s.
In: Cartography. - ISSN 0069-0805. - Roč.31, č.2 (2002), s.135-142 : 5 obr. - Res. angl. - Lit.11.

Klíčová slova: DPZ, zpracování obrazu, MIMD

Úvod

Stále vzrůstající množství a různorodost dat dálkového průzkumu Země klade vysoké nároky na postupy vyhodnocení. Cílem výzkumného projektu financovaného fondem VPAC (Victorian Partnership of Advanced Computing) je určit optimální nastavení paralelního zpracování družicových snímků na počítači typu MIMD. Empiricky byl postup zkoušen na určování náchylnosti půdy k zasolení.

Většina digitálních zpracovatelských systémů je založena na sekvenčním postupu nazvaném von Neumannův model. V důsledku své struktury může von Neumannův počítač složený z jednoho procesoru a jedné paměťové jednotky vykonávat instrukce pouze sekvenčně a vždy jen na jedné datové sadě. Navzdory rychlému vývoji kapacity zpracovávaných dat je tak fyzicky omezen jeho výpočetní výkon.

V dálkovém průzkumu Země se však setkáváme s komplexním zpracováním mohutných objemů dat. Radiometr MODIS nesený družicí TERRA má např. 36 spektrálních kanálů s různým rozlišením a slouží pro odvození veličin jako jsou povrchová teplota, vegetační index, půdní kryt apod. Celkové množství dat získaných z této družice je pak 1 TB denně. Pro projekty týkající se životního prostředí je navíc potřeba provádět multitemporální analýzy nebo zpracovávat obrazová data v reálném čase.

Jednou z možností urychlení procesu je paralelní zpracování, jehož základ tvoří rozdělení náročných výpočtů mezi několik procesorů. Přes veliký potenciál tohoto postupu je ho dosud málo využíváno, částečně proto, že jeho zapojení vyžaduje náročné přebudování zpracovatelských systémů. Při vytváření efektivního paralelního systému je potřeba rozdělit úkoly nebo data mezi procesory a zajistit mezi nimi komunikaci. Pro to existovalo donedávna jen málo dostupných nástrojů.

Paralelní architektura

Pro klasifikaci počítačů se používá nejčastěji Flynnova taxonomie, dělící počítače podle toku instrukcí a proudů dat na čtyři hlavní typy:

SISD (Single Instruction Single Data) - tradiční von Neumannův model,
SIMD (Single Instruction Multiple Data) - jeden tok instrukcí probíhá na několika datových proudech,
MISD (Multiple Instruction Single Data) - více instrukcí probíhá na jediném proudu dat. Všeobecně je to nerealistický model pro paralelní výpočty,
MIMD (Multiple Instruction Multiple Data) - více instrukcí probíhá na několika proudech dat - každý procesor tak může vykonávat vlastní program.

Z těchto čtyř typů jsou pro paralelní výpočty rozšířeny systémy SIMD a MIMD. V SIMD systému vysílá řídicí jednotka stejný kód ke všem procesorům a není tudíž třeba se starat o jejich synchronizaci. Systém MIMD je flexibilnější, ale mohou u něj nastat problémy se sladěním úrovní procesu i dat, nebo s alokací procesorů. U tradičního počítače je veškerá paměť adresována procesorem, u SIMD a MIMD systémů máme na vybranou, zda dovolit každému procesoru přístup k celé paměti, nebo přidělit každému jen její část. První způsob se dá nazvat sdílená paměť, druhý rozdělená paměť. Při rozdělené paměti nenastávají kolize, ale je potřeba zřídit síť pro komunikaci mezi procesory, které jinak mohou komunikovat přes sdílenou paměť. Pro zabudování sítě je instalován zvláštní hardware a software, což komunikaci zpomaluje.

Struktura družicových snímků

Obecně se družicové snímky skládají z rastrových dvojdimenzionálních dat, třetí rozměr je dán počtem vrstev (např. spektrálních pásem).

Paralelní zpracování snímku na MIMD systému s distribuovanou pamětí

Systém sestává z několika nezávislých počítačů označených jako uzly, s vlastním procesorem a lokální pamětí. Všechny uzly jsou napojeny na řídicí síť, která zprostředkovává komunikaci. Na tomto počítači lze rozdělovat jak data, tak funkce. Snadné dělení rastrových dat vede k tomu, že dělení dat převažuje. Pro implementaci paralelního zpracování je potřeba zavést systém posílání zpráv. Ten zajišťuje:

Řízení procesu: spuštění/ukončení.
Komunikaci: vysílání zpráv od jednoho procesoru k druhému.
Kolektivní komunikaci: vysílání a příjem zpráv od skupiny procesorů.
Synchronizační primitivy: indikace, jakmile proces dosáhne určitého bodu.

Rozdělení snímku pro paralelní zpracování

Způsob, jakým je snímek rozdělen, má významný vliv na efektivitu aplikace. Některé operace pracují vždy pouze s jedním pixelem, zatímco jiné vyžadují i přilehlé oblasti a je potřeba jim kromě vlastních dat přidělit i nutné okolí. Pro samotné rozdělení obrazu existuje mnoho metod, lze rozdělovat podle pravidelných i nepravidelných regionů, spektrálních pásem nebo (při multitemporální analýze) podle časových rovin. Cílem při výběru dělicího postupu je minimalizovat frekvenci alokace paměti a síťovou komunikaci.

Případová studie

Případová studie se zabývá vývojem paralelního klasifikačního modelu pro zjišťování salinity půdy, která pro Austrálii znamená hlavní ekologický problém.

Klíčovou otázkou je určení vývojového trendu zasolování. Hlavním indikátorem očekávané slanosti je hladina podzemní vody a ta má úzký vztah k zavlažení. Zavlažení bylo zjištěno z dat skenerů Multispectral Scanner a Thematic Mapper družice Landsat, přičemž byly použity snímky pro každý rok v období mezi rokem 1980 a současností.

Dělení obrazu: snímky ze tří různých let jsou rozděleny mezi dva procesory.

Implementace systému

Zvolená dekompozice snímků je naznačena na obrázku. Pro jednoduchost byl vybrán pravidelný rozklad s nutným okolím. Výše popsaná metoda byla implementována pomocí jazyka C a knihovny MPI (Message Passing Interface - rozhraní pro posílání zpráv). Celý postup lze popsat v následujících krocích:

Inicializace procesu.
Určení kontrolních a podřízených procesorů.
Rozdělení snímků na bloky.
Alokace bloků podřízeným procesorům pomocí kontrolního procesoru.
Provedení úkolu podřízenými procesory - při ukončení je vyslán signál ke kontrolnímu procesoru.
Kontrolní procesor obdrží signál o ukončení od podřízeného procesoru a přiřadí mu další blok obrazu, dokud nejsou zpracovány všechny.
Jsou-li zpracovány všechny bloky, proces je ukončen.

Hodnocení průběhu

Test byl proveden na systému s 32 počítači Compaq ES40 (4 procesory, alphaEV68 na 833 MHz s 2 GB pamětí a 72 GB lokálních disků) tedy celkem se 128 procesory a 64 GB paměti. Omezením byly průtahy v komunikaci a fakt, že úloha není zcela rozložitelná. Ukazuje se nicméně, že další rozvoj paralelního zpracování má své opodstatnění.