Rzeczywistość równoległa

Informatyków czeka zmiana warsztatu, narzędzi, technologii i akcentów w budowie systemów. Całe nasze myślenie o komputerach musi ulec zmianie.

Informatyków czeka zmiana warsztatu, narzędzi, technologii i akcentów w budowie systemów. Całe nasze myślenie o komputerach musi ulec zmianie.

Ostatnie cztery dekady to w informatyce czas nieustającego wzrostu mocy obliczeniowej w rytmie wyznaczanym przez prawo Moore'a. Od pierwszych procesorów i Intela 4004, poprzez królującą w latach 90. linię Pentium, aż po współczesne Core Duo - trwa nieustający wyścig megaherców i liczby tranzystorów. W ostatnich latach zauważyliśmy jednak ciekawe zjawisko. Wzrost częstotliwości w zasadzie zatrzymał się około 3 GHz. Producenci - Intel, AMD, Sun - konkurują na innych polach: zestawu instrukcji, rozmiaru pamięci podręcznej (cache) oraz liczby rdzeni. Dlaczego właściwie tak się dzieje? Dlaczego bariera 3 GHz okazuje się tak trudna do przeskoczenia?

Przyczyny są zasadniczo dwie: ciepło oraz czysto fizyczne ograniczenia związane z technologią półprzewodnikową i prędkością światła. A więc - ciepło wydzielane w układach scalonych opartych na krzemie od dawna przysparza coraz większych trudności - problemy z nim możemy "poczuć" przykładając rękę do otworu wentylatora w naszym komputerze domowym albo "usłyszeć", gdy komputer przenośny włącza dodatkowy wiatraczek, by ochłodzić procesor. Aby zrozumieć drugie ograniczenie, trzeba zastanowić się, co tak naprawdę znaczy 3 GHz. To 3 miliardy przełączeń zegara w ciągu sekundy. Jeden takt trwa jedynie 0,3 nanosekundy. Przez ten czas sygnał elektryczny przemieszcza się jednie o kilka centrymetrów. Czas ustalenia stanu bramki NAND wykonanej w technologii CMOS wynosi ok. jednej nanosekundy.

Widać więc, że dalsze podwyższanie częstotliwości zegarów procesora napotyka na czysto fizyczne ograniczenia, trudne do przezwyciężenia w obecnej (krzemowej) technologii. Dlatego od kilku lat rozwój architektur komputerów osobistych naśladuje ścieżkę rozwoju komputerów enterprise w kierunku powiększania liczby rdzeni procesora, nie zaś zwiększania częstotliwości zegara.

Tymczasem równoległe przetwarzanie informacji wnosi do informatyki (a w szczególności - do inżynierii oprogramowania) zupełnie nowe zagadnienia. W najbliższych latach informatyków czeka zmiana warsztatu, narzędzi, technologii oraz akcentów w budowie systemów. Zmiana ta zapewne potrwa ok. 10 lat, ale sprawi, że "na nowo zostaną rozdane karty" i wszystko na tym rynku jest możliwe.

Równoległe zagadnienia

Symbolem problemów z współbieżnością pozostaje tzw. prawo Amdahla. Mówi ono, że zdolność powiększenia mocy obliczeniowej systemu wieloprocesorowego jest istotnie ograniczona współbieżnością kodu wykonywanego przez ten system. Na przykład wykonanie na 10 procesorach programu, w którym 90% kodu może działać równolegle daje jedynie ok. pięciokrotny efektywny przyrost mocy obliczeniowej. Każdy dodatkowy procesor jest mniej efektywny, duży uzysk daje natomiast powiększanie odsetka kodu wykonywalnego równolegle.

Duża część aktualnie sprzedawanych komputerów osobistych zawiera mikroprocesory dwu- i czterordzeniowe. Jednak domowe systemy operacyjne nie zawsze potrafią w pełni je wykorzystać - stosują z reguły najprostsze możliwe rozwiązanie, alokując po prostu dany proces do danego rdzenia.

Problem zaczyna się wtedy, gdy komputer wykonuje jeden proces, za to intensywny obliczeniowo (a więc absorbujący dużą część czasu procesora) i powinien wykonać go równolegle na wielu jednostkach obliczeniowych. Jeśli wykonać test obliczeniowy na procesorze dwurdzeniowym okazuje się, że nie tylko nie działa on dwa razy szybciej od procesora jednordzeniowego, a czasami... w ogóle nie działa szybciej.

Problemy współbieżności znane są od czasów pierwszych wielozadaniowych systemów operacyjnych - czyli mniej więcej od czterdziestu lat. Także algorytmy równoległe są stare jak architektury wieloprocesorowe - czyli niewiele krócej. Na przestrzeni tego czasu dobrze opisano zagadnienia związane z wielozadaniowością. Ale niektóre kwestie (rywalizacja o dostęp, blokowanie wątków i danych, semafory, sekcje krytyczne, przesyłanie kolejek komunikatów) po raz pierwszy mają szansę zaistnieć w świecie popularnych systemów i aplikacji.

Walka z prawem Amdahla

Aby skutecznie walczyć z prawem Amdahla (czyli skalować efektywną moc obliczeniową komputera wraz ze zwiększaniem liczby rdzeni i procesorów), trzeba zupełnie inaczej budować systemy informatyczne na poziomie algorytmów i danych.

Klasyczny przykład ilustrujący inny paradygmat programowania to sumowanie zbioru liczb - zagadnienie powszechne niemal we wszystkich zastosowaniach, ale przede wszystkim w przetwarzaniu danych na potrzeby systemów finansowo-księgowych i szeroko pojętego ERP. W "normalnym" (tj. jednowątkowym) programowaniu zagadnienie takie realizowane jest przez sekwencyjne dodawanie kolejnych wielkości i utrzymywanie sumy kroczącej: pierwsza plus druga, dodać trzecia, dodać czwarta, itd. Tak napisanego algorytmu nie da się zrównoleglić, a tym samym dodanie dodatkowych procesorów nie przysporzy wydajności komputerowi, który realizuje takie zadanie.

Trzeba zastosować inne podejście: zbiór liczb podzielić na mniejsze części, każdy z procesorów wykona dodawanie swojego podzbioru, a następnie dodane zostaną wyniki każdego dodawania. Wszystko brzmi prosto do momentu, gdy zdamy sobie sprawę, że całe zadanie będzie wykonane tak szybko jak najwolniejszy z "kawałków". Co jeśli do dodawania zaangażowaliśmy 4 rdzenie, 3 już dawno ("dawno" w rozumieniu czasu mikroprocesora, oczywiście) zakończyły swoje zadanie, a czwarty dalej liczy? Decyzja, który robi co, podejmowana jest na początku - od niej więc zależy ostateczna wydajność całego algorytmu.

Jeszcze lepszym pomysłem jest zastosowanie bibliotek, w których podstawowe problemy zostały rozwiązane przez specjalistów od programowania równoległego i zamknięte w postaci gotowych do wykorzystania bibliotek algorytmów, uwzględniających architektury wielordzeniowe i wieloprocesorowe. Problem polega na tym, że takie biblioteki dostępne są na razie głównie na architektury superkomputerów, a ich ceny przeciętnego użytkownika komputera (a nawet przeciętnego producenta oprogramowania) przyprawiłyby o palpitację serca.

Problem odpowiedniego podziału zadań to dopiero pierwsze z wyzwań programowania równoległego. Drugie, ogromne zagadnienie, to dostęp do danych. Każdy, kto kiedykolwiek programował aplikacje bazodanowe, zetknął się z pojęciem blokad ("locków") na danych. Równoległy zapis do danych zawsze stwarza ryzyko niespójności i sposobem radzenia sobie z tym problemem jest blokowanie danych na czas zapisu i zarządzanie blokadami.