Dlaczego komputery są tak szybkie?

Wstęp

Do obliczeń dużych problemów naukowych i inżynierskich często używamy tak zwanych „superkompumputerów”. Sa to zespoły połączonych wielu procesorów i innych elektronicznych elementów, które współpracują wykonując duże i trudne obliczenia.

Szybkości superkomputerów są mierzone ilością operacji zmiennoprzecinkowej arytmetyki na sekundę. Obecnie mamy superkomputery których szybkość jest w granicach kilku do kilkuset petaflopów. Jeden petaflop oznacza 10 do potęgi 15 zmiennoprzecinkowych obliczeń na sekundę.

W tym eseju rozpatrzymy fascynujące pytanie: dlaczego superkomputery osiągają taką szybkość? Esej nie jest naukowym artykułem i jego celem jest tylko zachęcenie czytelników do dalszego studiowania tematu. Czytelnicy mający podstawy informatyki zareagują inaczej niż ci mający wykształcenie humanistyczne. Postaram się, aby obie grupy miały pożytek czytając informacje o superkomputerach, które rozwiązują najtrudniejsze problemy naukowe i inżynierskie. Superkomputery są obecnie głównym narzędziem badan fizyki, chemii, biologii, genetyki, astronomii, mechaniki, ekonometrii i wielu innych nauk oraz dyscyplin inżynierii. W niektórych zastosowaniach superkomputer symuluje fizyczny eksperyment. Na przykład zamiast testów skrzydła samolotu w aerodynamicznym tunelu superkomputer symuluje aerodynamikę używając matematyczny model. Maszyna musi być bardzo szybka.

Dlatego warto wiedzieć nieco na czym polega sekret szybkości super maszyn. Tym sekretem jest nie tylko szybkość przepływu prądu. Sekret jest trochę bardziej subtelny, choć doskonale zrozumiały dla niemal każdego człowieka. Po przeczytaniu eseju czytelnik pomyśli: oczywiście, ja też tak myślałem. Odpowiedz na pytanie ma dwie części. Jedną łatwiejszą i jedna trochę trudniejszą, ale nie na tyle aby uczeń dziesiątej klasy nie mógł chwycić sensu koncepcji.

Superkomputery

Zacznijmy od części łatwiejszej. Każdy z nas wie, że duże projekty takie jak budowanie domu, statku lub samolotu są wykonywane przez wielu robotników pracujących równocześnie. Techniczna nazwa takiego stylu pracy jest “równoległe wykonanie zadań projektu”. Używamy słowa „równolegle” w znaczeniu „równocześnie”. Po angielsku parallel. Rozwiązanie trudnego problem na komputerze też można uważać za project i może być podzielone na niezależne obliczenia wykonywane równolegle.

Wszystkie superkomputery są równoległymi maszynami. To znaczy składają się z wielu liczących elementów, które działają równolegle. Każde zadanie projektu (programu) jest wykonywane przez jeden element superkomputera. Oczywiście te elementy maszyny muszą być koordynowane aby poprawnie policzyć wszystkie zadania. Nie mogą liczyć chaotycznie. Ta konieczność koordynacji wymaga czasu i często opóźnia obliczenia. Jest to cena jaką płacimy za szybkość równoległości. Nic nie jest za darmo.

A teraz poprzeczka idzie wyżej, bo opiszę drugą, trudniejszą cześć sekretu szybkich obliczeń. Okazuje się, że w obliczeniach naukowych i inżynierskich bardzo często używamy wektory. Wektor to zbiór liczb które są ponumerowane. Na przykład a(1) znaczy pierwszy element wektora “a” który może mieć tysiące składników. Prostym obliczeniem wektorowym jest suma dwóch wektorów c(i)=a(i)+b(i) dla wszystkich numerów i, na przykład, od i=1 do i=100000. Zwykły mikroprocesor, aby dodać dwie liczby musi wykonać 9 elementarnych instrukcji. W naszym przykładzie 900000 instrukcji. To jest za wolne. Musimy więc wykorzystać dwa fakty, aby przyspieszyć obliczenia. Fakt nr 1, czyli to, że wiemy, że wszystkie operacje są jednakowe np dodawanie. Oraz fakt nr 2, czyli to, że wiemy iż będą dodawane element wektorów umieszczonych w przyległych komórkach pamięci. Możemy więc umieścić cały wektor w specjalnej szybkiej pamięci zwanej registers. Taka technika nazywa się “vector computing” – obliczenia wektorowe. Są one znacznie szybsze niż tak zwane zwykle (skalarne) obliczenia używające 9 instrukcji dla dodania jednej pary liczb.

Podsumowując możemy teraz powiedzieć, że znamy sekret szybkości superkomputerów. Jest nim równoległość i wektorowe obliczenia. Przykładem komputerów które liczyły wektorowo były już w 1970tych i 1980tych latach komputery Cray. Obecnie przykładem jest superkomputer zwany TITAN w Oak Ridge National Laboratory w USA. W Polsce jest ośrodek z superkomputerem zbudowanym przez HP w Gdańsku. Nosi nazwę TASK (Trójmiejska Akademicka Sieć Komputerów). Maszyna TASKU jest w pierwszej setce najszybszych superkomputerów świata. Ma numer około 90. W kilku krajach świata jest kilka lub kilkanaście superkomputerów. Wśród nich są takie państwa jak USA, Chiny, UK, Niemcy, Japonia, Południowa Korea, Włochy, Francja, Kanada, Holandia i inne przemysłowo i naukowo wysoko rozwinięte kraje.

O autorze wpisu:

Janusz Kowalik jest emerytowanym profesorem matematyki i informatyki na Washington State University oraz byłym kierownikiem organizacji badań informatyki w firmie lotniczej Boeing Company w Seattle. Adres internetowy Janusza: j.kowalik@comcast.net

  1. Instrukcje wektorowe jako SIMD są dziś dostępne w każdym procesorze, a typowe architektury wektorowe skończyły się w latach 90. Więc wektorowe przetwarzanie nie decyduje już dziś o mocy superkomputerów tylko czysty paralelizm. To, że superkomputer dziś działa na takiej samej architekturze jak mój laptop to ogromna zaleta, a programowanie równoległe jest wciąż na tyle problematyczne, że większość programów jest daleka od optymalnego wykorzystania mocy superkomputerów. Ale to się powoli zmienia na lepsze. Bardzo podobają mi się eksperymenty z HPC z kartami graficznymi i CUDA i to że każdy może sobie dziś odpalić dziesiątki tysięcy rdzeni na amazonie za parę dolarów na godzinę.

  2. Trzeba ostroznie wyjasniac kwestie szybkosci.
    Superkomputery skladaja sie z procesorow ktore wykonuja wektorowe obliczennia i sa przyspieszana przyspieszaczami ENVIDIA lub Intel ktore dzialaja na zasadzie wektorowego liczenua. To wlasnie dlatego superkomputery sa szybkie .Inaczej mowiac rownoleglosc jest na kilku poziomach. Jeden poziom to
    architektura wieloprpocesorowej maszyny a inny poziom to poziom nizszy wektorowego liczenia przez procesory lub przyspieszacze.To jest dokladnie powod szybkosci.Jak nie krecic kota ogonem obliczenia SIMD(Single Instruction Multiple Data) to tez rownoleglosc tylko tyle ze jest to najprostrzy przypadek. Wyzsza forma rownoleglosci to SPMD (Single Program Multiple Data) ktore wymagaja wielu procesorow. Publikpowane doswiadczenia i moje wlasne wskazuja ze wektorowe obliczenmia sa szybsze okolo 100 razy od scalarnych wykonanych przez te same procesory.
    Aby czytelnik to poprawnie rozumial rozpatrzmy obliczenie typu Saxpy co jest suma dwoch wektorow x i y dlugosci na przyklad 1000 elementow z ktorych jeden jest mnozony przez liczbe a.
    Kontrastem jest obliczenie dodania tysiaca par liczb rozrzuconyc pamieci.Te dwa obliczenia roznia sie szybkoscia pomimo tego ze obie operacje w sensie matematycznym sa jednakowe. Roznica jest spowodowana tym ze Saxpy jest obliczeniem wektorowym jesli programista nie wylaczy operacji wektorowej.
    Trzeba rozumiec ze superkomputery sa najszybsze od setek Teraflops do setek PetaFlops ale jeden procesor z wieloma rdzeniami jest tez wzglednie szybki.
    Uwaga ze mozna za kilka dolarow liczyc z szybkoscia superkomputera jest przesada. Przyspieszacze kosztuja tysiace dolarow. NP jeden procesor wektrorowy Intela Phi z 60 rdzeniami kosztowal 2,500 USD.Taka maszyna z jednym procesorem jest zwana kieszonkowym superkomputetrem. Wektorowo 1 TersaFlops.Scalarnie znaczie wolniej .

  3. 4 teraflopy zoptymalizowane pod kątem zastosowań równoległych (instancja P2) kosztują dziś mniej niż dolara za godzinę. Za 150 dolarów na godzinę można mieć 70 teraflopowy klaster – 40 tysięcy rdzeni.
    .
    Pisanie kodu wykorzystującego wektoryzację SIMD jest dziś bardzo problematyczne. Software jest dziś oderwany od konkretnych centr obliczeniowych i mało kto będzie się bawił w optymalizację na poziomie assemblera w czasach kiedy sieci neuronowe zaczynają odpalać niemal wszyscy, a kompilatory sobie na razie z generowaniem kodu wektorowego same nie radzą. Więc praktyka jest taka, że w open sourcowych projektach np modeli pogodowych albo modeli oceanograficznych nie robi się takich optymalizacji bo ważniejszy jest uniwersalizm bazy kodu.

  4. Pisalem ze pierwsze komputery wektorowe byly w latach 1970-1980 Cray 1, Cray XMP,Cray YMP .Obecnie nastapila druga fala tej technologii lecz realizowana inaczej. Sa jednak podobienstwa, Na przyklad uzycie szybkiej pamieci registers.
    Natomiast idea przyspieszaczy NVIDIA jest nowa poniewaz przyspieszacze sa dodatkowym instrumentem do klasycznego komputera. Przyspieszacze nie sa niezalezne dzialajace samodzielnie.Przyspieszacze wspieraja procesor i wykonuja obliczenia wektorowe na rozkaz procesora.Intela procesor Phi scisle mowiac nie jest przyspieszaczem (accelerator) lecz coprocessor czyli stowarzyszony procesor ktory musi miec kompana
    w postaci multiple core procesora. Ale luzno mowiac mozna go zaliczyc do klasy accelerator poniewaz jego dlowna rola to szybkie wektorowe obliczenia. Podsumowujac mozna powiedziec ze dobrze sie sklada iz matematyka obliczeniowa obfituje w wektorowe operacje. Bez tego obliczenia byly by znacznie wolniejsze.

  5. W tym eseju pisze o dwoch roznych poziomach rownoleglosci. Rownoleglosc na poziomie architektury wieloprocesorowego komputera oraz rownolegle obliczenia przez kazdy porocessor ktory moze liczyc kilka watkow(threads) rownoczesnie.
    Do tych dwoch typow rownoleglosci mozemy dodac jeszcze jedna .W wielu obliczeniach mozna rozpatrywac rozne niezalezne alternatywy ,Na przyklad inzynier moze obliczac aerodynamike kilku wersji skrzydla samolotu. Te obliczenia sa niezalezne i moga byc liczone rownolegle tym samym programem lecz z innymi danymi dla kazdej wersji (SPMD).
    Taka metoda jest nazwana alternative parallelism.
    Z punktu widzenia programowania mozna rozroznic SPMD oraz SIMD(obliczenia wektorowe) ktore opisalem w jednym komentarzu.
    Metoda OpenMP uzywa SIMD bezbolesnie tworzac kilka lub kilkanascie watkow liczonych rownoczesnie.
    Rownoleglosc w PC nie jest kluczowa bo procesory sa szybkie i rozwiazuja male problemy w krotkim czasie. Dla problemow duzych np aerodynamika samochodu konieczne sa wieloprocesorowe superkomputery kieszonkowe lub prawdziwe super z tysiacami procesorow i rdzeni.

  6. OpenMP nie używa SIMD bezboleśnie – dopiero w OpenMP 4.0 niedawno pojawiły się instrukcje to jawnej wektoryzacji, wcześniej trzeba było pomagać hintami w kompilacji, cała sprawa jest na razie eksperymentalna. A w pełni automatyczna kompilacja SIMD w C albo Fortranie to wciąż pieśń przyszłości. Żyjemy w czasach, gdzie pełna optymalizacja jeżeli nie jest automatyczna na poziomie kompilatora nie jest opłacalna bo hardware jest tani w stosunku do potrzebnych nakładów pracy, czasu niszowych specjalistów i rezultatu w postaci przywiązanego do architektury, trudnego w utrzymaniu kodu. Może poza szczególnymi przypadkami kiedy nawet superkomputery to za mało typu symulowanie mechaniki kwantowej.

  7. Jarku
    OpenMP jest w uzyciu okolo 10 lat ,w USA dluzej. Na Uniwersytecie Gdanskim studenci uzywali OpenMP od okolo 2006 roku.
    Cala idea to uzycie fork-join do wykonamia petli przez multiple threads.OpenMP ma dwie opcje :jedna SIMD w ktorej kazda pletla jest jednakowa oraz bardziej ogolny przypadek kiedy rozne obliczenia Tasks sa wykonane przez threads. Ja moge powiedziec bez przesady ze OpenMP byl od wielu lat najlatwiejszym do nauczenia i uzycia narzedziem parallel computing. Moj asystent na UG nigdy nie nie powiedzial mi ze studenci mieli trudnosci. Uczylem OpenMP oraz MPI (Message Passing Interface) w ciago jednego 30 godzinnego kursu.
    Uzywalismy lokalne hardware :shared memory do OpenMP i kluster do MPI od kokolo 2006 roku.
    Slowo bezbolesny dokladnie opisuje latwosc uzycia OpenMP. Jesli masz konkretny problem to moge korespondencyjnie Ci poradzic jak napisac program.
    Moj adres jest j.kowalik@comcast.net

  8. Do Jarka D.
    Nie wiem jakie masz podrecznikki lub zrodla informacji o OpenMP
    ale ja mam dwugodzinny wyklad w Power Point na temat tego systemu.Moge wyslac Ci plik.Jest tam kilka przykladow, oraz wstep do architektury wspolczesnych procesorow. Ten wyklad jest oparty na ksiazce Using OenMP ktora redagowalem w 2008 roku.Ksiazke opublikowal The MIT Press.

  9. Janusz, nie wiem czy się rozumiemy i czy mówimy o tym samym, bo ja nie sugeruje, że OpenMP jest trudnym, albo złym narzędziem. Mówię tylko o bardzo konkretnych problemach związanych z wektoryzacją. Parę linków dla naprowadzenia:
    .
    http://www.hpctoday.com/hpc-labs/explicit-vector-programming-with-openmp-4-0-simd-extensions/
    .
    „Wide vector registers and SIMD instructions – Single Instructions operating on Multiple Data elements packed in wide registers such as AltiVec [2], SSE, AVX [10] and MIC [9] – pose a compilation challenge that is greatly eased through programmer hints. While many applications implemented using OpenMP [13, 17], a widely accepted industry standard for exploiting thread-level parallelism, to leverage the full potential of today’s multi-core architectures, no industry standard has offered any means to express SIMD parallelism. Instead, each compiler vendor has provided its own vendor-specific hints for exploiting vector parallelism, or programmers relied on the compiler’s automatic vectorization capability, which is known to be limited due to many compile-time unknown program factors.”
    .
    http://delaat.net/awards/2014-03-26-paper.pdf
    .
    „We observed that it is rather
    easy to get functional code and start benchmarking, but the
    first performance numbers can be far from satisfying. Our
    experience indicates that a simple data structure and mas-
    sive parallelism are critical for Xeon Phi to perform well.
    When compiler-driven parallelization and/or vectorizatio
    nfails, programming Xeon Phi for performance can become
    very challenging.”

  10. Na UG uzywalismy prostego zespolu procesporow multicore Intela .Jak pisalem OpenMP pracowal bez problemu.
    Coprocesor Phi jest stosunkowo nowy (2012) i byc moze ze automatyczna wektoryzacja przez kimpilator nie jest idealna.Ale mozna latwo wektoryzowac uzywajac OpenMP.
    Uzycie Phi jest jeszcze niezbyt dobrze znane.

  11. Do RAFALA Dobre pytanie.
    Dobre pytanie
    Dodajemy dwie liczby floating point.
    Policzmy instrukcje
    Wyjmij z pamieci a oraz b 2 instrukcje
    porownaj wykladniki 1 instrukcja
    wyskalij liczy aby mozna je dodac 2 instrukcje
    Przersun przecinek po dodasniu 1
    Wloz wybik do pamieci 1 instrukcje
    dwie dodatkowe to przeliczxenie z systemu dziesiatkowego na binarny na poczatku. input jest dziesietny a operacja i pamiec bonarna.

    1. Dzięki.
      Myślę, że zrozumiałem, ale chciałbym wiedzieć czy na pewno rozumiem jak wygląda ten proces, więc napiszę przykład i byłbym wdzięczny jakby napisał Pan czy dobrze myślę i ewentualnie naprostował mnie jeśli nie. W przykładzie gwiazdka * będzie oznaczać mnożenie a znak ^ potęgowanie.
      Oto przykład:
      Chcę dodać liczby 3,25 i 16,25.
      Dwie pierwsze operacje- przekształcenie z dziesiątkowego na binarny. Otrzymuję 11,01+10000,01, czyli inaczej 0,1101 * 10^(10) + 0,1000001 * 10^(101). Kolejna instrukcja-porównuje wykładniki: 10<101.
      Teraz następna: skalowanie. I tu nie wiem czy dobrze zrozumiałem o co chodzi. Przyjąłem, że chodzi o to aby doprowadzić w obu liczbach podstawę do tego samego wykładnika. Mam więc 0,0001101 * 10^(101) + 0,1000001 * 10^(101). Tylko, że tu wystarcza jedna instrukcja (zeskalować wystarczy jedną z liczb) a nie dwie- chyba że źle rozumiem co to jest skalowanie. Otrzymuję wynik 0,1001110 * 10^(101).
      Przesuwać przecinka tu nie trzeba, ale rozumiem, że w innym przykładzie byłoby to konieczne.
      Włożenie wyniku do pamięci- jasne.

  12. Jarek,
    Naiusz jakie Ty masz konkretnie trudnosci z wektoryzacja Podaj jezyk programowania,
    i opis petli ktore chcesz policzyc rownolegle.
    Wazne sa Twoje problemy a nie innych uzytkownikow.

  13. Do RAFALA
    KIedy pisalem ostatni moj komentarz byla burza i swiatlo migalo
    wiec tekst zostal nieco uszkodzony . Jesli masz jakies pytanie to ja z wielka przyjemnoscia bede z Toba korespondowal bezposrednio Internetem lub poprzez Racjonaliste.

  14. Do RAFALA
    Bardzo dobrze rozumiesz caly proces
    Przyklad jest poprawny.
    Skalowanie znaczy ze musimy przesunac mantysy tak aby wykladniki byly te same
    bo inaczej nie mozemy dodac mantys.
    Tutaj zrobie jedna uwage:jezeli dwie liczby ronia sie rzedem wielkosci zbut duzo to mniesza liczba staje sie zerem to znaczy nie jest dodana poniewaz jest poza dokladnoscia single lub double prcision.Taka liczba nazywa sie machine zero.
    Dziekuje Rafal za pytanie i przyklad. Zycze wszystkim czytelnikom aby tak reagowali na kazdy publikowany esej.
    Thank you for a good example. Perfect job.

  15. Dodatkowa informacja dla Rafala Rardiana.
    Definicja machine zero jest :najwieksza liczba epsilon dla ktorej maszyna liczy
    1+epsilon= 1.W matematyce epsilon jest zerem. W arytmetyce zmiennoprzecinkowej jest to mala liczba.
    Jesli dodajemy a do b i b jest znacznie mniejsze to moze sie tez zdarzyc ze koncowa czesc b nie zmiesci sie w przestrzeni mantysy i dodamy do a tylko czesc liczby b.Dobre kimpilatory informuja uzytkownika ze tak sie stalo.
    Przyklad latwy do sprawdzenia.
    Dodaj 1000,000 odwrotnosci liczb 1/x gdzie x zmienia sie od 1 do 1000,000.
    Dodaj w kolejnosci od x=1 do 1000,000 a potem oblicz to samo w odwrotnej kolejnosci .
    Wyn\iki beda rozne. W pierwszym wypadku dodajemy na koncu obliczen male liczby do duzych czesciowych sum.. W drugim obliczeniu dodajemy wieksze liczby na koncu.
    Dlatego trzeba uwazac z sodawaniem i odejmowaniem na komputerze.

  16. Innym przykladem niebespiecznego obliczenia jest wyrazenie M*(a-b) gdzie M jest duza liczba a a oraz b sa prawie jednakowej wielkosci.Roznica a-b jest malo wartosciowa poniewaz najwazniejsze czesci a i b zostaly usuniete .Roznica reprezentuje numeryczny odpadek .
    Ta malo wartosciowa liczba po pomnozeniu przez M staje sie duzym odpadem.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *