Views

Biuletyn nr 18

From KDMwiki

Jump to: navigation, search
Biuletyn KDM
1 | 2 | 3 | 4 | 5
6 | 7 | 8 | 9 | 10
11 | 12 | 13 | 14
15 | 16 | 17 | 18
19 | 20 | 21 | 22
23 | 24 | 25 | 26
27 | 28 | 29 | 30
31 | 32
Lista biuletynów

Biuletyn nr 18 (8 stycznia 2007).

Spis treści

Wydarzenia: Listopadowa lista TOP500.

Autor: Maciej Cytowski

W listopadzie ubiegłego roku została ogłoszona nowa lista TOP500, pieciuset najmocniejszych superkomputerów świata. Lista TOP500 ogłaszana jest dwa razy w roku (czerwiec, listopad) na stronie http://www.top500.org. W zeszłym roku aktualny jej stan został opisany przez Maćka Szpindlera (Biuletyn nr 6). Od tamtego czasu zaszły na liście oczywiście pewne zmiany. Wśród nich najważniejsza to brak komputera Earth Simulator w TOP10.

Obecna lista

Pierwszych 10 pozycji listy TOP500:

Pozycja Lokalizacja Komputer Liczba procesorów Max wydajność [TFlops/s] Poprzednia pozycja
1 DOE/NNSA/LLNL

USA

BlueGene/L - eServer Blue Gene

IBM

131072 280,6 1
2 NNSA/Sandia National Laboratories

USA

Red Storm - Sandia/ Cray Red Storm, Opteron 2.4 GHz dual core

Cray Inc.

26544 101,4 -
3 IBM Thomas J. Watson Research Center

USA

BGW - eServer Blue Gene

IBM

40960 91,3 2
4 DOE/NNSA/LLNL

USA

ASC Purple - eServer pSeries p5 575 1.9 GHz

IBM

10240 63,4 3
5 Barcelona Supercomputer Center

Hiszpania

MareNostrum - BladeCenter JS21 Cluster, PPC 970, 2.3 GHz, Myrinet

IBM

10240 62,6 -
6 Sandia National Laboratories

USA

Thunderbird - PowerEdge 1850, 3.6 GHz, Infiniband

Dell

9024 53 6
7 Commissariat a l'Energie Atomique (CEA)

Francja

Tera-10 - NovaScale 5160, Itanium2 1.6 GHz, Quadrics

Bull SA

9968 52,8 -
8 NASA/Ames Research Center/NAS

USA

Columbia - SGI Altix 1.5 GHz, Voltaire Infiniband

SGI

10160 51,9 4
9 GSIC Center, Tokyo Institute of Technology

Japonia

TSUBAME Grid Cluster - Sun Fire x4600 Cluster, Opteron 2.4/2.6 GHz and ClearSpeed Accelerator, Infiniband

NEC/Sun

11088 47,4 -
10 Oak Ridge National Laboratory

USA

Jaguar - Cray XT3, 2.6 GHz dual Core

Cray Inc.

10424 43,5 -

Zmiany

Pierwsza 10 listy TOP500 zwykle mówi nam wszystko o tendencjach panujących w całej długiej liście, czy wogóle w całym superkomputerowym świecie. W aktualnej edycji TOP500 w pierwszej dziesiątce królują instalacje firmy IBM (aż 4) i rzeczywiście udział tej firmy w całej liście to aż 47.20%. Trzy komputery z pierwszej dziesiątki oparte są na komunikacji Infiniband - technologii, która coraz skuteczniej wypiera starsze Gigabit Ethernet oraz Myrinet. Udział technologii Gigabit Ethernet oraz Myrinet w liście TOP500 spadł w porównaniu z poprzednim rokiem o ok. 11%. Technologia Infiniband zaliczyła natomiast znaczny wzrost tego udziału, bo aż o ok. 10%. Do największych zmian w aktualnej edycji listy należy bezdyskusyjnie zaliczyć brak komputera Earth Simulator w pierwszej 10 (aktualnie miejsce 14). Ta prawdziwa już japońska legenda świata komputerowego znajdowała się w TOP10 przez ponad 4 lata (w tym ponad 2 lata na pierwszej pozycji). Od listopada 2004 komputer ten był sukcesywnie spychany na dalsze pozycje głównie przez amerykańskie instalacje. Oto ciekawa statystyka:

Edycja listy Pozycja Earth Simulatora

w TOP500

Liczba lepszych

instalacji USA

06/2002 1 0
11/2002 1 0
06/2003 1 0
11/2003 1 0
06/2004 1 0
11/2004 3 2
06/2005 4 3
11/2005 7 6
06/2006 10 6

W momencie pojawienia się Earth Simulator'a na liście TOP500 w czerwcu 2002, komputer ten był 5 razy szybszy od drugiego największego w tym czasie superkomputera na świecie (nawiasem mówiąc amerykańskiego IBM ASCI White). Od tamtego czasu osiągi instalacji firmy NEC były intensywnie gonione na całym świecie. Ta gonitwa doprowadziła do powiększenia mocy obliczeniowej najszybszego komputera na świecie o rząd wielkości (obecnie Blue Gene\L ma ponad 280 TFLOPs). Firma NEC ma jednak nadal swojego przedstawiciela na liście TOP500, jest nim ulokowany w Japonii TSUBAME Grid Cluster oparty na procesorach Opteron i sprzętowych akceleratorach .

Do wypchnięcia komputera Earth Simulator z pierwszej 10 przyczyniły się również dwa komputery firmy Cray Inc. - oparte na procesorach Opteron systemy Cray XT3 (Red Storm oraz Jaguar). Na uwage zasługuje przede wszystkim pierwszy z nich, który zajmuje wysoką drugą pozycję. Tak wysokiej lokaty na liście TOP500 komputery firmy Cray Inc. nie zajmowały od listopada 1998. Czy oznacza to wielki powrót Cray'ów? W roku 1998 udział Cray Inc. w TOP500 był na poziomie 15%, dwa lata temu wynosił on zaledwie 1,8%, obecnie utrzymuje się natomiast na poziomie 3%.

Bezkonkurencyjnym liderem udziału w TOP500 jest firma IBM mająca na swoim koncie 236 instalacji (ponad 47%). Na drugim miejscu pod tym względem znajduje się firma Hewlett-Packard mająca na koncie 158 instalacji (ponad 31%). Można jednak zauważyć bardzo istotną różnicę pomiędzy tymi dwoma producentami. Ponad 82% komputerów Hewlett-Packard z listy TOP500 to komputery z miejsc 200-500. Firma IBM natomiast ma ponad 40% własnych instalacji z TOP500 w pierwszej dwusetce.

Najpopularniejsze procesory to Pentium 4 Xeon (ponad 23%), Xeon EM64T (ponad 15%) oraz dwurdzeniowe Opterony (ponad 15%).

Kryteria oceny

Do testowania wydajności maszyn używany jest tzw. Linpack Benchmark. Należy jednak pamiętać, że obecne trendy porównywania wydajności maszyn dopuszczają Linpack Benchmark tylko jako jeden z wielu testów wydajności. Bardzo dobrym przykładem jest benchmark HPCChallenge.

Czy wiesz, że?

  • Wystarczy mieć 40 procesorów, żeby znaleźć się w TOP500

Komputery SR11000 firmy Hitachi nie potrzebują wielu procesorów by zyskać dużą moc obliczeniową. Na 156 miejscu listy znajduje się taki właśnie, wyposażony w 40 procesorów, system. Najlepiej notowanym komputerem firmy Hitachi jest 60 procesorowy SR11000-K1, który zajmuje miejsce 69. Można zadać sobie naturalne pytanie jak to możliwe? Otóż każdy procesor firmy Hitachi to tak naprawdę konstelacja 16 procesorów Power5+ z dodatkowym procesorem systemowym umożliwiającym automatyczne zrównoleglanie.

  • Jeden z producentów superkomputerów produkuje również odkurzacze

Firma Hitachi.

  • Najwyżej notowany komputer typu Self-made ma na swojej obudowie ponad 1560 jabłek

Ulokowany w Huntsville w stanie Alabama komputer MACH5 to składak wykonany w całości z komponentów firmy Apple. Cały system to 40 raków, każdy po 39 węzłów obliczeniowych Apple XServe. Na każdym węźle widnieje logo firmy. Komputer znajduje się na wysokiej 28 pozycji listy (ponad 16 TFLOPs).

  • Tylko 5 komputerów na liście TOP500 to tzw. składaki

..i trzy z nich to składaki Apple. Ile to razem jabłek?

  • Ponad 75% komputerów z listy TOP500 to systemy posiadające od 513 do 2048 procesorów

Jednak gdy zsumujemy te wszystkie procesory razem to da nam to tylko ok. 42% sumy wszyskich procesorów z listy. Dlaczego? patrz dalej..

  • Tylko jeden komputer na liście ma ponad 64 000 procesorów

Znajdujący się na pierwszym miejscu listy BlueGene/L ma ich 131072. Stanowi to ok. 12% sumy wszystkich procesorów z listy. Im więcej tym lepiej.

Teoria: Prawo Amdahla

Autor: Michał Łopuszyński

Wprowadzenie

Z każdym rokiem komputery z czołowych miejsc listy TOP500 zawierają coraz więcej procesorów (patrz poprzedni artykuł). Obecnie nikogo nie dziwią maszyny posiadające tysiące jednostek obliczeniowych. Pozostaje jednak pytanie - czy taką rozproszoną między kilka tysięcy CPU moc obliczeniową można łatwo wykorzystać? Problem nie jest nowy. Nad efektywnością obliczeń równoległych zastanawiano się od dawna. Jedną z najbardziej fundamentalnych, a jednocześnie bardzo prostych obserwacji sformułował Gene Amdahl (jeden z pionierów techniki komputerowej) już w latach 60 ubiegłego stulecia.

Co to jest prawo Amdahla?

Zastanawiając się nad teoretycznymi ograniczeniami dotyczącymi korzyści ze zrównoleglalnia Amdahl rozważył następujący modelowy problem. Wyobraźmy sobie, że mamy testowy program, który na jednym procesorze wykonuje się przez czas T. Amdahl założył, że program ten można podzielić na dwie rozłączne części - równoległą R i sekwencyjną S. Obliczenia wykonywane w części R programu dają się w idealny sposób podzielić między N procesorów. Znaczy to, że jeśli na jednym procesorze wykonanie fragmentu R zajmuje czas T*F, to po uruchomieniu naszego programu na dwóch procesorach czas potrzebny na część R zmaleje do T*F/2, jeśli wykorzystamy trzy jednostki obliczeniowe dodatkowo zmniejszymy ten wyniki do T*F/3 itd. W przypadku części sekwencyjnej S Amdahl przyjął, że jej wykonania nie da się przyspieszyć przez rozdzielenie pracy między wiele CPU. Czas potrzebny na część S rozważanego kodu, niezależnie od liczby użytych procesorów, wynosi T*(1-F).

Na podstawie powyższych rozważań można w łatwy sposób otrzymać wzór na czas wykonania opisanego modelowego programu w zależności od liczby użytych procesorów:

Parser nie umiał rozpoznać (Missing texvc executable; please see math/README to configure.): T(N)=T(1-F) + \frac{TF}{N} .

Na tej podstawie można też wyznaczyć tzw. przyspieszenie (ang. speedup), czyli stosunek czasu wykonania na 1 CPU do czasu wykonania na N CPU:

Parser nie umiał rozpoznać (Missing texvc executable; please see math/README to configure.): P(N)=\frac{1}{(1-F) + \frac{F}{N}} .

Ten wzór nosi nazwę prawa Amdahla.

No dobrze, ale co z tego wynika?

Aby lepiej zrozumieć otrzymany wynik warto popatrzeć na wykresy. Przyjrzyjmy sie najpierw zależność czasu wykonania od liczby użytych procesorów, dla przykładowego programu z F=0.8. Dla większej czytelności czasy wykorzystane przez cześć sekwencyjną S i równoległą R zostały zaznaczone różnymi kolorami:

Prawo Amdahla - Zależność czasu wykonania od liczby procesorów

Widzimy, że posiadanie dużej liczby procesorów to tak naprawdę tylko część sukcesu. Istotniejszym problemem jest znalezienie dobrego algorytmu, w którym część sekwencyjna będzie tak krótka, jak to tylko możliwe. Jeszcze dobitniej przedstawia to wykres zależności przyspieszenia P(N) od liczby użytych procesorów:

Prawo Amdahla - Zależność przyspieszenia od liczby procesorów

Na powyższym obrazku łatwo zauważyć, że o ile tylko współczynnik zrównoleglenia F jest mniejszy od 1.0, otrzymane przyspieszenia szybko odbiegają od wyidealizowanego liniowego wzrostu. Co więcej, od pewnego momentu zysk z dalszego zwielokrotniania liczby użytych procesorów staje się niewielki. Wąskie gardło stanowi tu właśnie część sekwencyjna. Decyduje ona też o maksymalnym możliwym przyspieszeniu, które łatwo wyznaczyć:

Parser nie umiał rozpoznać (Missing texvc executable; please see math/README to configure.): P( N \to \infty) = \frac{1}{(1-F)}

Na zakończenie, jako ilustrację problemu, dociekliwemu czytelnikowi proponujemy rozwiązanie prostego zadania domowego.

Zadanie: Załóżmy, że chcemy przeprowadzić obliczenia na komputerze BlueGene/L. Administratorzy pozwolili nam wykorzystać do rachunków całą maszynę (N=131072 procesorów). Program, który przygotowaliśmy, spełnia założenia prowadzące do prawa Amdahla. Z otrzymanego superkomputera chcemy uzyskać przyspieszenie P minimum 50000 (skromnie), co pozwoli nam uporać się z projektem w przydzielonym przez administratorów czasie. Jak dużą część programu F musi stanowić kod idealnie zrównoleglający się?

Podsumowanie

Modelowe rozważania Amdahla pokazują, że komputery masywnie równoległe, zawierające tysiące CPU, nie stanowią łatwego i uniwersalnego rozwiązania dla dużych problemów obliczeniowych. Sensowne wykorzystanie takiej architektury stanowi poważne wyzwanie dla twórców algorytmów. Na zakończenie warto też podkreślić, że model Amdahla nie uwzględnia mnóstwa istotnych czynników, występujących przy tworzeniu aplikacji równoległych np. opóźnień związanych z komunikacja/synchronizacja poszczególnych jednostek obliczeniowych, problemów z równym podziałem pracy między CPU (ang. load-balancing) itp. To już jednak tematy na zupełnie osobne artykuły...

Narzędzia: Jak wygenerować film z serii obrazów?

Autor: Łukasz Bolikowski

Zadanie

Mamy serię plików z obrazkami "klatka po klatce", chcemy wygenerować z nich film. Korzystamy z systemu UNIX.

W wersji A pliki nazywają się tak:

 klatka1.png klatka2.png ... klatka120.png

W wersji B tak:

 klatka001.png klatka002.png ... klatka120.png

Chcemy, aby wygenerowany film był w tempie 5 klatek na sekundę (jedna na 200 ms).

Pokażemy, jak to wykonać przy pomocy kilku alternatywnych pakietów. Wszystkie pakiety dostępne są na serwerze rekin. Jeśli czytelnicy znają inne sposoby wykonania tego zadania, zapraszamy do podzielenia się z nami!

Rozwiązanie 1: ffmpeg

Mając do dyspozycji pakiet ffmpeg wykonujemy następujące polecenia. Wersja A:

 ffmpeg -r 5 -i klatka%d.png film.avi

Wersja B:

 ffmpeg -r 5 -i klatka%03d.png film.avi

Rozwiązanie 2: mencoder

Mając do dyspozycji pakiet mencoder wykonujemy następujące polecenia (tylko wersja B):

 mencoder 'mf://klatka*.png' -fps 5.0 -ovc lavc -o film.avi

Jeśli kodek wideo o nazwie lavc nie jest dostępny, należy go doinstalować, lub wybrać inny. Listę dostępnych kodeków otrzymamy wykonując polecenie:

 mencoder -ovc help

Rozwiązanie 3: ImageMagick

Mając do dyspozycji pakiet ImageMagick wykonujemy następujące polecenia (tylko wersja B):

 convert -delay 20 klatka*.png film.mpeg

Dodatek: Zmiana klatka1.png -> klatka001.png

Nazewnictwo plików w wersji B jest wygodniejsze z tego względu, że w tej wersji napis klatka*.png jest w UNIXie rozwijany zgodnie z numeracją klatek. W wersji A, natomiast, pliki rozwijane są tak:

 klatka100.png
 klatka101.png
 ...
 klatka10.png
 ...
 klatka120.png
 ...
 klatka1.png
 ...
 klatka20.png
 klatka21.png
 ...
 klatka2.png
 ...
 klatka9.png

ponieważ UNIX rozwija w kolejności "alfabetycznej" względem "alfabetu":

 0 1 2 3 4 5 6 7 8 9 [...] a b c d [...] x y z [...] .

Aby temu zaradzić, możemy zmienić nazwy plików tak, aby zawsze zawierały trzy cyfry. W powłoce bash wykonamy to przy pomocy następującego polecenia:

 for i in `seq 1 99` ; do ii=`printf "%03d" $i` ; mv klatka$i.png klatka$ii.png ; done

W powłoce tcsh wydajemy następujące polecenia:

 foreach i ( `seq 1 99` )
   set ii=`printf "%03d" $i`
   mv klatka$i.png klatka$ii.png
 end

Pliki z numerami od 100 wzwyż nie wymagają zmiany nazwy.

W wyniku napis klatka*.png będzie rozwijany do:

 klatka001.png
 klatka002.png
 ...
 klatka009.png
 klatka010.png
 ...
 klatka020.png
 klatka021.png
 ...
 klatka100.png
 klatka101.png
 ...
 klatka120.png

Oczywiście jeśli jest taka możliwość, warto od razu tworzyć pliki z właściwymi nazwami (czyli w wersji B).