Wielkie wyzwania.

Tym właśnie hasłem, 5 lat temu w publikacji Grand Challenges to Computational Science, K. G. Wilson określił te problemy naszej cywilizacji, których algorytmiczne rozwiązanie przekracza możliwości najszybszych maszyn cyfrowych. Czy dzisiejsze "superliczydła" potrafią więcej niż te z roku 1989?

Tym właśnie hasłem, 5 lat temu w publikacji Grand Challenges to Computational Science, K. G. Wilson określił te problemy naszej cywilizacji, których algorytmiczne rozwiązanie przekracza możliwości najszybszych maszyn cyfrowych. Czy dzisiejsze "superliczydła" potrafią więcej niż te z roku 1989?

Twórcy jednego z pierwszych komputerów - amerykańskiego ENIAC-a - zachwyceni prędkością swojego wynalazku, uważali że parę takich maszyn zaspokoi potrzeby obliczeniowe całej ludzkości (!). Ów cud techniki lat 40., o rozmiarach lokomotywy, potrafił liczyć z szybkością 5 tys. operacji na sekundę. Dziś wielokrotnie szybszy jest zwykły PC, mieszczący cy się na każdym biurku.

Okazuje się jednak, że nasze potrzeby rosną szybciej niż możliwości kolejnych generacji komputerowych. Oczywiście nawet przeciętny użytkownik chciałby, żeby jego komputer był szybszy. Do pewnego stopnia jest to kwestią ceny. Za pięć tys. USD można nabyć bardzo nowoczesną konfigurację, która na pewno nie będzie za wolna, nawet dla wyrafinowanego oprogramowania multimedialnego. Również w typowych zastosowaniach gospodarczych nie trzeba uciekać się do najdroższych rozwiązań, aby osiągnąć zadowalające efekty szybkościowe.

Mimo to istnieją zagadnienia, dla których prędkość obliczeń jest elementem krytycznym nawet przy zastosowaniu najbardziej wydajnych rozwiązań dostępnych w świecie techniki. Wynika to z trzech powodów:

- wielkości danych do przetworzenia

- ograniczonego czasu obliczeń

- złożoności zastosowanych algorytmów.

Podczas poszukiwań geologicznych ilość informacji dostarczanych przez pojedynczą próbę sejsmiczną może osiągać wolumen wielu dziesiątek gigabajtów. Jeszcze więcej danych trzeba przetworzyć podczas obliczeń związanych z zagadnieniami współczesnej fizyki. W laboratoriach IBM ponad pół tysiąca procesorów komputera GF-11 pracowało nieprzerwanie cały rok, aby potwierdzić uzyskane eksperymentalnie wielkości mas cząstek elementarnych. Obliczenia wykorzystujące tzw. chromodynamiczną teorię kwantów (QCD) wymagały przeprowadzenia ok. t r y l i o n a operacji arytmetycznych.

Klasycznym przykładem problemu wymagającego dokonania wielu obliczeń w ograniczonym czasie jest prognozowanie pogody. Numeryczne prognozowanie pogody jest starsze niż komputery - pierwszą pracą na ten temat była książka Levisa Richardsona "Weather Prediction by Numerical Process" (Londyn, 1922). Jej autor proponował, aby do wykonywania niezbędnych obliczeń użyć jednocześnie 60 tys. rachmistrzów. Ale nawet obecnie łatwo możemy stanąć przed problemem prognozowania opadów zeszłorocznego śniegu. Mówiąc inaczej czas niezbędny dla uzyskania wyników synoptycznych jest dłuższy niż zakładany horyzont czasowy prognozy (np. 48 godzin dla prognozy dobowej).

W praktyce upraszcza się więc algorytmy prognozowania. Synoptycy z Europejskiego Centrum Prognoz Średnioterminowych w angielskim Reading korzystają z komputera Cray C9-16 oraz napisanego w Fortranie, programu IFS złożonego z 200000 linii kodu, (Integrated Forecasting System). Podstawą globalnego modelu pogodowego jest siatka składająca się z 4 mln pkt, dla których trzeba przeprowadzić obliczenia, co wymaga 2 godzin dla prognozy dziesięciodniowej. Testy Brytyjczyków wykazują jednak, że zwiększenie wiarygodności prognoz wymaga dokładniejszego modelu i nawet kilkudniowych obliczeń dla prognozy dekadowej.

Również konstrukcja samego algorytmu może powodować, że liczba operacji (czas) niezbędnych do jego zrealizowania rośnie gwałtownie wraz ze wzrostem rozmiaru zadania. Wynika z tego, że powstawanie coraz szybszych komputerów nie umniejsza znaczenia poszukiwania coraz doskonalszych algorytmów. W tym kontekście podstawową cechą algorytmu (programu) jest jego złożoność obliczeniowa, czyli czas pracy algorytmu wyrażony jako funkcja rozmiaru zadania. Przykładowo czas sumowania n liczb jest wprost proporcjonalny do n - jest to więc prosty algorytm o liniowej złożoności obliczeniowej.

Istnieje wiele zadań o wykładniczej złożoności obliczeniowej. Do trudno rozwiązywalnych należą tzw. problemy NP-zupełne, wśród nich tak klasyczne jak problem komiwojażera: znaleźć najkrótszą trasę przejazdu przez zadane miasta. Tak powszechnie stosowane dzisiaj algorytmy teoriografowe posiadają często złożoność obliczeniową zależną od kombinatorycznego czynnika n!. Wystarczy wziąć do ręki kalkulator i policzyć wartość 70!, aby zobaczyć jak złożone mogą być tego typu algorytmy. A przecież kilkadziesiąt wierzchołków grafu nie jest czymś niezwykłym, jeśli za jego pomocą modelujemy połączenia między punktami lutowniczymi na płytce drukowanej czy też strukturę związku chemicznego.

Rozwój informatyki jest więc również rozwojem superkomputerów. Jeszcze kilka lat temu dominującą konstrukcją były procesory wektorowe (vector processor) zdolne do przetwarzania wektorów, czyli grup danych o stałej długości np. całych kolumn tabeli. Tak więc siła klasycznego superkomputera polega na ponadprzeciętnej szybkości niewielu specjalnych procesorów. Jego architektura nie różni się zasadniczo od stosowanej w przeciętnym komputerze i wykorzystuje ideę sekwencyjnego przetwarzania danych, sformułowaną już w latach 30.

Doskonalszą koncepcją są superkomputery równoległe. Zadowalają się one nawet konwencjonalnymi procesorami za to w dużych ilościach - w skrajnych przypadkach są ich tysiące. Idea równoległego przetwarzania danych nie jest nowa. Tabliczki obliczeniowe sprzed 2000 lat, znalezione na greckiej wyspie Salamos, umożliwiają jednoczesne wykonywanie trzech operacji rachunkowych. Również wymieniony wcześniej projekt "ludzkiego komputera" Richardsona wykorzystuje tę ideę, wówczas niemożliwą do zrealizowania z przyczyn technicznych.

Najpotężniejszy komputer świata znajduje się w Nowym Meksyku (USA) i jest własnością Los Alamos National Laboratory. CM-5 firmy Thinking Machines kosztował 30 mln USD, ma 1024 procesory i osiąga moc 130 GFLOPS (operacje zmiennoprzecinkowe na sekundę). Już w 1986 r. szef firmy "Myślące Maszyny" Daniel Hillis przedstawił pierwszy model Connection Machine (CM). CM-5 może mieć maksymalnie do 65 536 procesorów (skąd my znamy tę liczbę?); wielkość ta ma jednak charakter czysto teoretyczny.

Zdarza się również, że pod pojęciem "procesor" ukrywa się jednobitowy arytmometr co oznacza, że 32 takie jednostki liczące można porównać z jednym "normalnym" procesorem 32-bitowym. I tak CM-5E, zbudowany ze 128 procesorów Supersparc firmy Sun, osiąga moc obliczeniową porównywalną z CM-5 w Los Alamos. Komputer ten przeszedł obszerne testy w Ames Research Center (NASA) wygrywając współzawodnictwo z podobnymi maszynami konkurentów:

- T3D (Cray)

- SP1 (IBM)

- Paragon (Intel)

- KSR2 (Kendall Square).

Poza wymienionymi firmami na rynku superkomputerów równoległych istnieje jeszcze kilku innych producentów odgrywających mniejszą rolę - DEC, Inmos, Wavetracer, Parsytec, Meico Scientific czy wywodząca się z Bulla francuska firma ACRI. W tej dziedzinie Japończycy znaczą jeszcze niewiele, ale może to ulec szybkiej zmianie - bardzo zaawansowane są projekty takich gigantów jak Mitsubishi, NEC, Matsushita, Fujitsu, Sanyo czy Sharp.

Do czołówki należy z całą pewnością współpracująca z ORACLE firma nCUBE Corporation. Firma ta stosuje klasyczną dla komputerów równoległych topologię HYPERCUBE. Podstawowym składnikiem takiej struktury jest "węzeł", będący w najprostszym przypadku pojedynczym procesorem. Tak jest w maszynie Craya Tera 3D wykorzystującej procesory Alpha (DEC). Z kolei węzeł Paragona zawiera do 5 procesorów i860XP-RISC oraz do 64 MB pamięci, co pozwala osiągać moc 150 MFLOPS na węzeł.

Teoretycznie można przyjąć, że moc superkomputera to suma mocy jego węzłów - ta liczba znajduje się najczęściej w materiałach reklamowych (peak perfomance). Bardziej miarodajna jest wydajność osiągana dla konkretnego oprogramowania (sustained performance). Istnieje wiele wzorów wiążących szybkość komputera z liczbą jego rocesorów. W idealnym przypadku jest to zależność liniowa - dwa razy więcej procesorów to dwa razy większa szybkość. Najbardziej pesymistyczne oszacowanie Minsky'ego operuje formułą:

log(n), gdzie n - liczba procesorów.

A jak jest w rzeczywistości? Współcześni projektanci komputerów równoległych mają do czynienia z następującą kwestią organizacyjną: jeżeli jedna kucharka ugotuje zupę w ciągu pół godziny, to czy sześć kucharek zrobi to przez pięć minut? Bez odpowiedniego programowania, z fizycznego łączenia wielu procesorów niewiele wynika. Wszak w globalnych sieciach komputerowych pracują miliony konfiguracji, a sumować ich moc można jedynie dla celów statystycznych.

Praktyka wskazuje, iż komputery równoległe wykorzystują zaledwie kilka procent swej mocy (konwencjonalne superkomputery ok. 30%). Przypomina to działanie ludzkiego mózgu. Czyżby nasz "program" (sposób myślenia) był zbyt mało "równoległy"? Być może jednak mózg człowieka w krytycznych sytuacjach potrafi osiągać znacznie wyższą wydajność w krótkim czasie. Nie jest więc przypadkiem, że doświadczenia biologii wykorzytuje się w informatyce tworząc komputerowe sieci neuronowe. W ten sposób również zbliżamy się do, zapowiadanego na najbliższe 2 lata, zbudowania maszyny cyfrowej liczącej z prędkością jednego teraflopa.