Views

Biuletyn nr 3

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 3 (23 sierpnia 2005).

Spis treści

Laboratorium użytkowników

Autor: Kerstin Kantiem

W sali 2167 w siedzibie ICM w gmachu Wydziału Geologii zostało uruchomione laboratorium dla użytkowników. Lab jest do dyspozycji użytkowników w godzinach otwarcia sekretariatu, czyli od 9:00 do 17:00. Klucze do labu znajdują się w sekretariacie. Obecnie lab jest wyposazony w trzy X-terminale, z których można logować się na komputery burza i rekin.


Wydarzenia: Relacja z konferencji "State of the art developments of real-space electronic sturcture techniques"

Autor: Michał Łopuszyński

Konferencja State of the art developments and perspectives of real-space electronic sturcture techniques in condensed matter and molecular physics zorganizowana przez Eduardo Hernandeza, Thomas Becka i Emillio Artacho pod patronatem instytutu CECAM (Centre Européen de Calcul Atomique et Moléculaire) odbywała się w Lyonie w dniach 20-24.06.2005. Na konferencji dominowały prezentacje dotyczące nowoczesnych metod obliczania struktury elektronowej ciał stałych z wykorzystaniem podejścia DFT (teorii funkcjonału gęstości elektronowej, ang. Density Functional Theory).

Obecnie w tego typu symulacjach dominują metody oparte na rozwinięciu elektronowych funkcji falowych w bazie fal płaskich. O tym podejściu i oprogramowaniu je wykorzystującym pisaliśmy dokładniej w poprzednim numerze biuletynu. Obecnie jest to standardowy sposób rozwiązywania zagadnień DFT w ciałach stałych, bardzo dobrze zbadany zarówno od strony teoretycznej, jak i technologicznej. Niestety posiada on również istotne ograniczenia. W szczególności dotyczą one maksymalnego rozmiaru badanych układów. Praktyczne możliwości sięgają tu symulacji zawierających najwyżej kilkaset atomów. Nawet wykorzystanie współczesnych superkomputerów/klastrów wyposażonych w setki, a czasem tysiące procesorów nie rozwiązuje problemu. Przeszkodą są tu trudności w efektywnej implementacji algorytmów, wykorzystywanych w tych tradycyjnych kodach DFT, na architekturach masywnie równoległych (w szczególności np. algorytmu szybkiej transformaty Fouriera - FFT). Dodatkowo użycie fal płaskich narzuca na badane problemy konieczność zastosowania periodycznych warunków brzegowych, co nie zawsze jest korzystne. Przykładowo w obliczeniach z zakresu nanotechnologii często mamy do czynienia z układami periodycznymi jedynie w jednym (nanorurki, druty kwantowe itp.) lub dwóch wymiarach (zjawiska powierzchniowe).

Konferencja w Lyonie poświęcona była alternatywnym metodom, pozwalającym w znaczącym stopniu wyeliminować powyższe trudności. Polegają one na zastosowaniu do teorii DFT typowych metod numerycznych dla równań różniczkowych cząstkowych tzn. metody elementu skończonego lub metody różnic skończonych. Techniki te określa się często mianem metod operujących w przestrzeni rzeczywistej (real-space). Do tej pory poświęcano im niewiele uwagi, gdyż w przypadku małych układów są one znacznie mniej wydajne niż metoda fal płaskich. Postęp w dziedzinie dostępnych mocy obliczeniowych spowodował jednak, że obszary, w których techniki real-space mogą okazać się efektywniejsze, stały się osiągalne technicznie. Dodatkowo metody te wydają się bardzo dobrze przystosowane do implementacji na komputerach masywnie równoległych. W związku z tym w ostatnich latach nastąpił znaczny wzrost zainteresowania tą dziedziną. Na konferencji przedstawiono liczne przykłady zastosowania i propozycje ulepszenia metodologii real-space, a także oprogramowania na niej bazującego. Mimo iż jest to dziedzina stosunkowo młoda dostępne są już pierwsze pakiety wykorzystujące tę technologię (np. oprogramowanie Mika lub GridPAW). Oczywiście nie osiągnęły one jeszcze niezawodności i uniwersalności właściwej tradycyjnemu podejściu fal płaskich. Sądząc jednak po dynamice prac na tym polu opisana sytuacja może szybko ulec zmianie.

Czytelników, których zainteresowała tematyka metod real-space, zachęcamy do przejrzenia abstraktów z konferencji umieszczonych na stronie WWW Warto też zajrzeć do artykułu przeglądowego w Rev. Mod Phys. 72, 1041 napisanego przez jednego ze współorganizatorów konferencji. Ze względu na rok wydania (2000) nie będzie on jednak zawierał najnowszych osiągnięć w dziedzinie, po które najlepiej sięgnąć do bieżącej literatury tematu.


Programowanie: Zrównoleglanie kodu - podstawy

Autor: Łukasz Bolikowski

Programowanie równoległe polega na napisaniu programu tak, aby można go było uruchomić na wielu procesorach równocześnie. Dokonuje się tego zazwyczaj przez modyfikację istniejącego kodu przeznaczonego pierwotnie na jeden procesor (mówimy wtedy o zrównoleglaniu kodu).

Zrównoleglając program należy szukać fragmentów, które mogą wykonywać się niezależnie od siebie. W przypadku obliczeń numerycznych, tego rodzaju równoległość związana jest zazwyczaj z występującymi w kodzie pętlami (DO w Fortranie, for w C).

Zrównoleglanie pętli

Przeanalizujmy dwa proste przykłady. W pierwszej pętli:

 DO I = 2, N-1
   TNEW(I) = 0.5*TOLD(I) + 0.25*TOLD(I-1) +0.25*TOLD(I+1)
 END DO

każda iteracja może być policzona niezależnie od pozostałych. Przykładowo, obliczenia dla iteracji I=5 nie zależą w żaden sposób od wyników obliczeń pozostałych iteracji, ani nie wpływają na wyniki obliczeń innych iteracji.

Taka pętla może więc być wspólnie liczona przez wiele procesorów: każdy procesor otrzyma pewien zakres iteracji do policzenia.

Druga pętla:

 F(1) = 1
 F(2) = 1
 DO I = 3, N
   F(I) = F(I-1) + F(I-2)
 END DO

nie może być niestety zrównoleglona w taki sposób, jak pierwsza. Iteracje muszą być obliczane jedna po drugiej, ponieważ np. obliczenia w iteracji I=5 zależą od wyników obliczeń iteracji I=3 i I=4. Wniosek: nie każdą pętlę można zrównoleglić.

Wiele programów z prawdziwego zdarzenia wykonujących obliczenia na siatkach dwu- lub trójwymiarowych zawiera fragment analogiczny do poniższego:

 TOLD(1:N, 1:M) = T(1:N, 1:M)
 DO I = 1, M
   DO J = 1, N
     ! tu obliczenia dla punktu TNEW(I, J)
     ! korzystajace z wartosci w punktach: TOLD(I, J),
     ! TOLD(I-1, J), TOLD(I+1, J), TOLD(I, J-1), TOLD(I, J+1)
   END DO
 END DO
 T(1:N, 1:M) = TNEW(1:N, 1:M)

Tego typu kod zrównolegla się z reguły w ten sposób, że siatkę dzieli się na podobszary (prostokąty lub równoległościany) i przydziela te podobszary procesorom.

Pamięć współdzielona i rozproszona

Bardzo ważnym czynnikiem wpływającym na konstrukcję programu równoległego jest budowa komputera, a dokładniej: sposób połączenia procesorów z pamięcią operacyjną. Omówmy więc w skrócie dwie najprostsze architektury wieloprocesorowe. Wybrane przykłady są nieco uproszczone, ich celem jest jedynie przedstawienie istoty sprawy. Proszę pamiętać, że w rzeczywistości sposób połączenia procesorów z pamięcią jest bardziej złożony.

Poniższa ilustracja przedstawia schematycznie dwie najbardziej typowe architektury komputerowe.

Połączenia procesorów z pamięcią

Pamięć rozproszona

Po lewej stronie przedstawiony jest przykład architektury o pamięci rozproszonej (distributed memory architecture), czyli architektury gdzie pamięć jest podzielona na fragmenty zarządzane przez poszczególne procesory (lub grupy procesorów).

Przykładem takiej architektury jest klaster IBM eServer (halo). Klaster składa się z 98 węzłów, każdy węzeł ma dwa procesory AMD Opteron i 2 GB pamięci operacyjnej. Warto sobie zdać sprawę, że klaster to 98 fizycznie odseparowanych komputerów połączonych jedynie wspólną siecią. Procesor w węźle X nie może więc bezpośrednio korzystać z pamięci umieszczonej w węźle Y. Zamiast tego, może on poprosić procesor z węzła Y o przesłanie mu fragmentu "swojej" pamięci (używając np. pary funkcji MPI_Send() i MPI_Recv() z biblioteki MPI).

Pamięć współdzielona

Schemat po prawej stronie to przykład maszyny o pamięci współdzielonej (shared memory architecture). W takich komputerach, jak sama nazwa wskazuje, wszystkie procesory współdzielą jedną i tę samą pamięć.

Dobrym przykładem jest tutaj nieco już starzejący się Cray SV1ex (tajfun), w którym 32 procesory mają do wspólnej dyspozycji 16 GB pamięci operacyjnej.

Pamięć fizycznie rozproszona, logicznie współdzielona

Ponadto, dostępne w ICM superkomputery Cray X1e (tornado) i SGI Origin 2000 (latimeria), choć posiadają cechy architektur o pamięci rozproszonej, są znacznie bardziej zespolone niż typowy klaster. Podstawowa różnica to globalne adresowanie pamięci, pozwalające na sięganie do odległej pamięci (należącej do innego procesora) bez konieczności absorbowania "właściciela". Bardziej wyrafinowane narzędzia, takie jak SHMEM, CAF czy UPC potrafią korzystać z tej możliwości. Mówi się, że pamięć w tych maszynach jest fizycznie rozproszona, logicznie współdzielona.

Inne możliwości

Możliwe są bardziej złożone sposoby łączenia procesorów i pamięci, np. rozwiązania hybrydowe, mające w sobie zarówno cechy pamięci współdzielonej, jak i rozproszonej. Przykładem takiej architektury jest Cray X1e (tornado). Szczegóły budowy tej maszyny omówimy w jednym z kolejnych biuletynów.

Wpływ architektury na zrównoleglanie

Aby zilustrować wpływ architektury na sposób zrównoleglania kodu, powróćmy na chwilę do ostatniej przykładowej pętli. Wyobraźmy sobie, że liczymy taki problem na siatce 16x12, korzystając z 12 procesorów. Załóżmy, że zdecydowaliśmy się podzielić obszar pomiędzy procesory w następujący sposób:

Podział obszaru pomiędzy procesory

Każdy procesor uaktualnia przydzielone mu węzły siatki. Przykładowo, procesor nr 6 uaktualnia węzły zaznaczone na fioletowo. Jednak w trakcie uaktualniania, musi on korzystać z węzłów "należących" do sąsiednich procesorów - na rysunku zaznaczonych kolorem błękitnym. Tę otoczkę, obszar z którego korzystamy, a który należy do sąsiednich procesorów, nazywany jest w programowaniu równoległym halo.

Tutaj dochodzimy do sedna sprawy: jeśli pracujemy na architekturze o pamięci rozproszonej, będąc procesorem, musimy poprosić sąsiednie procesory o przesłanie nam odpowiednich fragmentów "ich" pamięci, a także sami musimy reagować na żądania przesłania pamięci skierowane do nas od przez inne procesory. Co więcej, musimy wykonywać operacje wysyłania i odbierania w odpowiedniej kolejności, aby nie doszło do tzw. zakleszczenia: sytuacji w której procesor X czeka na dane od procesora Y, a procesor Y czeka na dane od procesora X. Dopuszczenie do takiej sytuacji jest bardzo poważnym błędem programistycznym.

Jeśli natomiast pracujemy na architekturze o pamięci współdzielonej, problem wymiany halo praktycznie nie istnieje: każdy proceror ma dostęp do całej pamięci i może bez problemu pobrać potrzebne mu wartości. Należy tylko uważać, aby pobierać wartości interesujących pól zanim sąsiedni procesor je uaktualni.

Podsumowanie

Jak widać, architektura komputera wieloprocesorowego, a dokładniej: sposób dostępu do pamięci operacyjnej przez poszczególne procesory wpływa na sposób zrównoleglania programu.

Pamięć współdzielona jest łatwiejsza w programowaniu i zazwyczaj pozwala na lepszą komunikację pomiędzy procesorami. Jest to jednak rozwiązanie drogie, a na dodatek liczba procesorów, które można połączyć wspólną jest bardzo ograniczona (maks. kilkudziesiąt).

Architektury oparte o pamięć rozproszoną są natomiast stosunkowo tańsze i pozwalają łączyć ze sobą do kilku tysięcy procesorów. Komunikacja między procesorami jest jednak zazwyczaj wolniejsza, a programowanie trudniejsze, niż w przypadku pamięci współdzielonej.


Programowanie: Zrównoleglanie kodu - narzędzia

Autor: Łukasz Bolikowski

Jest to jedynie pobieżny przegląd dostępnych narzędzi - bibliotek i języków - służących do zrównoleglania kodu. W kolejnych biuletynach planujemy umieścić artykuły opisujące dokładniej poszczególne rozwiązania.

OpenMP

OpenMP jest zbiorem tzw. dyrektyw służących do zrównoleglania kodu. Dyrektywy to fragmenty kodu wyglądające jak komentarze, jednak "wtajemniczone" kompilatory nie traktują ich jako komentarze, lecz jako wskazówki jak zrównoleglić następujący po nich fragment kodu (z reguły pętlę). Dyrektywy OpenMP stosuje się wyłącznie dla architektur o pamięci współdzielonej.

W ICM przy pomocy OpenMP można programować na:

  • tornado (ze względu na architekturę można uruchamiać na maks. 4 MSP lub 16 SSP)
  • tajfun (32 SSP lub 8 MSP)
  • latimeria (16 CPU)

Zobacz także:

MPI

MPI, czyli Message Passing Interface, to bardzo popularna biblioteka służąca do zrównoleglania kodów dla architektur o pamięci rozproszonej (m.in. klastrów). Można też używać biblioteki MPI na architekturach o pamięci współdzielonej, ale z reguły nie jest to najefektywniejsze rozwiązanie.

Dwie najważniejsze funkcje tej biblioteki to MPI_Send i MPI_Recv. Pierwsza wysyła określony fragment pamięci do określonego procesora, druga odbiera dane od określonego procesora i zapisuje w określonym miejscu w pamięci.

Mówi się, że do programowania przy użyciu MPI wystarcza w zupełności znajomość 6 funkcji: trzech inicjalizacyjnych (wywływanych raz na początku programu), jednej finalizującej (wywoływanej raz przy kończeniu programu), oraz MPI_Send i MPI_Recv. Dla tych, którym to nie wystarcza, standard MPI oferuje ponad 100 różnych bardziej wyspecjalizowanych funkcji.

W ICM przy pomocy MPI można programować na:

  • tornado (system kolejkowy pozwala uruchomić na maks. 12 MSP lub 48 SSP)
  • halo (system kolejkowy pozwala uruchomić na maks. 32 CPU)
  • tajfun (32 SSP lub 8 MSP)
  • latimeria (16 CPU)

Zobacz także:

SHMEM

SHMEM to rozwiązanie stosowane przez firmy Cray i SGI, opracowane z myślą o architekturach rozproszonych. Jej celem jest zapewnienie programiście komfortu znanego z architektur o pamięci współdzielonej. Można o niej myśleć jako o swego rodzaju "emulacji" architektury współdzielonej (stąd nieco myląca nazwa: SHared MEMory).

Dwie bardzo ważne funkcje SHMEM to shmem_get i shmem_put. Podstawowa różnica w stosunku do znanych z MPI MPI_Send i MPI_Recv polega na tym, że w przypadku SHMEM są to funkcje jednokierunkowe. Oznacza to, że wywołaniu shmem_get (pobierz dane z odległej pamięci) nie musi odpowiadać żadna "funkcja wysyłająca" na procesorze będącym "właścicielem" tej odległej pamięci. Podobnie, wywołaniu shmem_put (umieść dane w odległej pamięci) nie musi towarzyszyć "funkcja odbierająca".

Biblioteka SHMEM bardzo silnie korzysta ze specyficznych własności architektur superkomputerów Cray i SGI, nie jest więc dostępna na innych platformach. Co ważne, biblioteka SHMEM jest znacznie szybsza niż MPI, szczególnie na Cray X1e (tornado)!

W ICM przy pomocy SHMEM można programować na:

  • tornado
  • tajfun (tu SHMEM istnieje głównie dla kompatybilności

i nie jest, podobnie jak MPI, najlepszym wyborem)

  • latimeria

Zobacz także:

  • man intro_shmem na maszynach, gdzie SHMEM jest dostępny

Co-Array Fortran

Co-Array Fortran, lub w skrócie CAF, to rozszerzenie języka Fortran o dodatkowe konstrukcje pozwalające na łatwe zrównoleglanie programów. CAF powstał z myślą o architekturach rozproszonych. Najlepsze rezulataty uzyskuje się w przypadku architektur fizycznie rozproszonych, logicznie współdzielonych, takich jak Cray X1e.

Jest to zdecydowanie najbardziej efektywny sposób zrównoleglania programów. Generowany kod jest znacznie wydajniejszy niż w przypadku stosowania MPI czy SHMEM. Jednocześnie CAF jest znacznie łatwiejszy w użyciu, programy są znacznie bardziej czytelne niż np. w przypadku używania MPI.

Wprawdzie CAF obecnie nie jest jeszcze zbyt popularny, bo dostępny jest praktycznie tylko na nowszych superkomputerach Cray, ale planuje się, aby rozszerzenia CAF stały się częścią następnego standardu Fortranu (roboczo: Fortran 2008).

W ICM przy pomocy CAF można programować na:

  • tornado

Zobacz też:

Unified Parallel C

Unified Parallel C, lub w skrócie UPC, to rozszerzenie języka C o dodatkowe konstrukcje pozwalające na łatwe zrównoleglanie programów. Jest on bardzo podobny do rozszerzeń Co-Array Fortran, choć powstaje niezależnie. Podobnie jak CAF, jest to rozwiązanie dla architektur o pamięci rozproszonej.

W ICM przy pomocy UPC można programować na:

  • tornado

Zobacz też: