Biuletyn nr 29 Numer Specjalny - Praktyki 2008

Spis treści

Fortress

Autor: Marek Grabowski *

Dlaczego nowy język

Potrzebę stworzenia nowego języka przeznaczonego do wysokowydajnego programowania dostrzegła, na początku XXI, wieku DARPA i w 2003 roku uruchomiła program High Productivity Computer Systems, w skrócie HPCS. Jego celem jest, ogólnie, poprawienie jakości procesu programowania superkomputerów i niezawodności programów.

W chwili obecnej zwiększenie mocy obliczeniowej osiąga się przez budowanie coraz bardziej skomplikowanych komputerów, mających coraz więcej procesorów i coraz bardziej rozbudowaną hierarchię pamięci. Niestety, powoduje to, że coraz trudniej jest pisać programy potrafiące wykorzystywać całą moc tychże komputerów. Najbardziej popularne języki w których dziś pisze się oprogramowanie naukowe to C, C++ i Fortran – wszystkie przeznaczone do programowania sekwencyjnego i nieposiadające wbudowanych mechanizmów zrównoleglających wykonywanie programów. Obecnie równoległość osiąga się głównie dzięki zastosowaniu biblioteki MPI (Message Passing Interface), która jest niskopoziomowym i raczej nieprzyjemnym w użyciu dodatkiem do wspomnianych wcześniej języków. Były inne próby prowadzenia wielowątkowości do sekwencyjnych języków, jak np. UPC, czy OpenMP, ale nie przyjęły się one na wystarczająco dużą skalę.

Ponadto nawet w przypadku zastosowań „biurkowych” wspomniane języki zostały już w dużej mierze wyparte przez inne. Świetnym przykładem nowoczesnego języka jest język Java -- programowanie w tym języku jest wydajniejsze, bo zarówno kod produkuje się szybciej, jak i jest on pozbawiony większej części błędów, które prawdopodobnie popełniłoby się pisząc go chociażby w C++. Co więcej programy napisane w Javie uruchamiają się właściwie na dowolnej maszynie, bez konieczności podmieniana bibliotek, czy zmian w kodzie.

Do pisania programów na superkomputery także chciałoby się mieć język wysokopoziomowy, w którym wygodnie osiągałoby się wielowątkowość programów. Tak samo jak w przypadku Javy dobrze by było gdyby programy napisane w tym języku działały na wszystkich, albo przynajmniej większości architektur obecnych i przyszłych, szczególnie, że powstaje coraz więcej Gridów, które nie są systemami jednorodnymi i przenośność kodu zaczyna być kluczowa. Poza tym w przeciwieństwie do długości życia superkomputerów, który wynosi kilka, powiedzmy 5, lat, okres życia programu obliczeniowego to kilkanaście, a nawet kilkadziesiąt lat (co można zaobserwować na przykładzie niektórych bibliotek Fortranu), więc możliwość przeniesienia programu na nową maszynę jest istotna.

W ramach projektu HPCS pracowano nad trzema językami mającymi odpowiedzieć na powyższe potrzeby. Do współpracy zaproszono trzy największe firmy zajmujące się superkomputerami, które pracowały nad trzema językami – IBM nad X10, Cray nad Chapel i SUN Microsystems nad Fortress. W tym artykule zajmiemy się ostatnim z nich. Jest on o tyle interesujący, że w 3 fazie projektu, wybrano dwa języki, które będą dalej sponsorowane przez DARPĘ i Fortress nie znalazł się wśród nich. Spowodowało to, że SUN zaczął rozwijać swój język jako projekt opensource'owy, a więc udostępnił zarówno specyfikacje jak i źródła prototypu kompilatora. Na końcu artykułu znajduje się link do materiałów dotyczących wszystkich 3 języków.

Pomysł

Mottem, które jest przytaczane na większości dokumentów dotyczących Fotress jest „To do for Fortran what Java did for C”, a nazwa Fortress miała wziąć się od „secure Fortran”. Te dwie rzeczy dobrze pokazują jaki pomysł na język miał SUN zaczynając pracę.

Każdy kto zetknął się zarówno z C (lub C++) jak i Java bardzo szybko wymieni kilka udoskonaleń jakie wprowadziła Java. Po pierwsze pojawiła się prawdziwa obiektowość, zniknęło samodzielne zarządzanie pamięcią, po drugie właściwie zniknęło rzutowanie typów, co pozwoliło ograniczyć liczbę błędów. Ponadto Java jest rzeczywiście przenośnym językiem i programy napisane raz można uruchamiać na dowolnej maszynie, na której zainstalowano JVM.

Oczywiście nic nie jest za darmo i istnienie JVM spowodowało, że programy napisane w Javie są zauważalnie wolniejsze od tych napisanych w C. Ponadto automatyczne zarządzanie pamięcią, owszem zmniejszyło liczbę błędów i spowodowało, że programowanie jest dużo prostsze, ale zmniejszyło także efektywność wykorzystywania zasobów komputera, co przy programowaniu wysokowydajnym jest bardzo bolesne. Poza tym część decyzji projektowych bardzo utrudnia wykorzystanie Javy jako języka do programowania superkomputerów, wystarczy wspomnieć niezgodność z najpopularniejszym standardem obliczeń podwójnej precyzji. Na części frontów Java cofnęła się trochę w porównaniu z C++, np. nie można przeciążać operatorów i nie istnieje wielodziedziczenie.

Drugą rzeczą, którą można wyczytać z motta jest chęć rozwinięcia, czy może zastąpienia Fortranu. Większość, a przynajmniej duża część, bibliotek numerycznych jest, ku rozpaczy młodszych informatyków, napisana właśnie w Fortranie, który to język już skończył 50 lat. Od tamtych czasów sposób programowania, a przede wszystkim wielkość programów bardzo się zmieniła. Z naszego punktu widzenia narzędzia powstałe w tamtym okresie są dość prymitywne. Co prawda starano się zmienić Fortran tak, aby uwzględnić takie rzeczy jak dowolny format kodu, czy brak konieczności używania „goto”, ale niestety wszystkie te próby miały jedno dodatkowe założenie – nowe kompilatory muszą rozumieć stare programy. Pełna wsteczna kompatybilność jest, oczywiście, pożądana, ale niestety uniemożliwia głębszą zmianę języka.

W tej chwili Fortran żyje już chyba wyłącznie dzięki swoim bibliotekom numerycznym i temu, że dużo programów używanych do tej pory jest w nim napisanych. Za to obszar zastosowania tego języka to już praktycznie wyłącznie obliczenia. Tak więc motto można odczytać jako chęć stworzenia języka dedykowanego do pisania oprogramowania obliczeniowego, w którym wygodnie będzie się pisać programy wykorzystujące wiele procesorów, który co więcej będzie przenośny i wydajny.

Założenia

Mając na względzie powyższą motywację możemy przejść do omawiania języka Fortress. Aby nadążyć z duchem czasu Fortress jest językiem obiektowym, co ani trochę nie dziwi. Jednak w odróżnieniu od Javy ma pozwalać na przeciążanie operatorów i funkcji, oraz na wielodziedziczenie.

Pierwszym, rzucającym się w oczy, oryginalnym pomysłem jest zastosowanie UTF-16 do pisania programów. Efekt jest taki, że w kodzie mamy dostęp do praktycznie wszystkich symboli matematycznych, od oznaczenia na liczby rzeczywiste, przez górne i dolne indeksy, do symboli całek, czy greckich liter. Jeśli weźmie się pod uwagę to, że głównym zastosowaniem Fortress mają być obliczenie, to ten pomysł jest fenomenalny – kod programu będzie wyglądał prawie jak wersja napisana przez matematyka na kartce!

Drugą zmianą, w stosunku do „normalnych” języków programowania, jest podejście do wielowątkowości. W tej chwili, pisząc programy wiemy, że będą się one wykonywać sekwencyjnie i jeśli chcemy używać więcej niż jednego wątku, to musimy to explicite kompilatorowi powiedzieć. SUN stwierdził, że w przypadku superkomputerów takie podejście jest złe, bo tam, ze względu na architekturę, właściwie wszystko powinno wykonywać się równolegle. W związku z tym postanowili wprowadzić domyślną równoległość do języka i zmuszać do wyraźnego zaznaczania, że coś ma być wykonywane sekwencyjnie.

Kolejnym, już nie tak rewolucyjnym pomysłem, jest stwierdzenie, że skoro nie da się napisać języka, który będzie potrafił wszystko co numerycy ze wszystkich dziedzin mogą chcieć, to należy wyrzucić wszystko co tylko się da poza kompilator, a całą funkcjonalność przerzucić do bibliotek, które każdy będzie mógł sobie pisać w miarę potrzeb. Tym samym ludzie zajmujący się jakąś konkretną dziedziną będą mieli bibliotekę dedykowaną dokładnie do niej, z nazwami funkcji, czy symbolami operatorów takimi jak się w danej dziedzinie przyjęło. Dużo bardziej rewolucyjna jest skala powyższego rozwiązania. Mianowicie wszystko co nie MUSI być w kompilatorze ma być udostępniane jako biblioteka, co ma pozwolić na zmienianie zachowania się programu w zależności od wymagań, czy architektury systemu (np. można samemu definiować siłę wiązania operatorów). W szczególności „równoległość” pętli nie jest osiągana przez automatyczne zrównoleglenie programu w miejscu wystąpienia słowa „for”, ale przez odpowiednie zaimplementowanie generatora kolejnych liczb naturalnych, który znajduje się w bibliotece, więc zawsze można go podmienić i otrzymać zwyczajne, sekwencyjne pętle.

Cechy szczególne

Jak już było wspomniane, kod programu napisany w Fortress ma wykorzystywać UTF-16 do wyświetlania formuł matematycznych. Naturalnie można także pisać programy w ASCII, a jeśli będzie się używało dialektu podobnego do LaTeXa, to będzie można wyświetlić kod w wersji UTF, a nawet przerobić na kod LaTeXowy za pomocą programu Fortify.

Przyjrzyjmy się teraz obiektowości w Fortress, zwłaszcza że jest ona rozwiązana inaczej niż w Javie. Poza obiektami występują w tym języku byty nazwane cechami (traits). Cechy są rozwinięciem idei interfejsów znanych z Javy, a różnią się od nich tym, że mogą implementować deklarowane metody. Za to tak samo jak interfejsy mogą dziedziczyć po innych cechach i nie mogą zawierać pól. Obiekty mogą dziedziczyć po wielu różnych cechach, zawierać pola i implementować metody. Efekt tego jest taki, że powstaje struktura drzewiasta, której liśćmi są obiekty, a cechy znajdują się wewnątrz.

Pomysł programowania obiektowego z cechami nie jest nowy i wydaje się naturalnym rozwinięciem standardowego podejścia. Różnica w modelowaniu rzeczywistości tymi dwoma metodami jest taka, że w przypadku klasycznyc języków obiektowych definiujemy kategorię rzeczy, a potem zawężamy ją do potrzebnej klasy, a w przypadku programowania z cechami definiujemy zbiór własności, a potem potrzebną klasę określamy jako coś, co ma interesujące nas zbiór cech. Różnicę tę najłatwiej zobaczyć na przykładzie:

Wersja obiektowa: Pojazd -> Pojazd Silnikowy -> Silnikowy Pojazd Czterokołowy -> samochód
Wersja z cechami: (Silnikowy, Czterokołowy, Służący do transportu) -> samochód

Jak widać w wersji z cechami hierarchia jest dużo bardziej płaska od wersji klasycznej. Każdy kto pisał duży projekt w Javie wie, że w przy obecnym podejciu hierarchia obiektów potrafi bardzo rozrastać się „do góry”.

Ciekawą rzeczą jest ukłon SUNa w kierunku języków funkcyjnych. Mimo, że Fortress jest imperatywny w tym znaczeniu, że istnieje instrukcja przypisania, to zdecydowano się na wprowadzenie pewnych elementów funkcyjności. Pierwszym widocznym efektem jest to, że wszystko jest wyrażeniem, czyli musi zwracać jakąś wartość (nawet np. pętla while()) -- w tym celu wprowadzono „zmienną” (), czyli void. Funkcyjność, w rozumieniu traktowania funkcji („typ strzałkowy” -- arrow type) tak jak wszystkich innych typów, a więc pozwalania na przekazywaniee jako parametry do innych funkcji, jak i zwracanie ich jako wartości bywa wygodna. Z jakiegoś powodu SUN nie chwali się tym i nie jest to nigdzie podkreślane. Powodem takiego zachowania może być mała popularność (w rozumieniu „mało ludzi zna”, a nie „mało ludzi lubi”) klasycznych języków funkcyjnych, które w założeniu mają bardzo rozrzutne gospodarowanie pamięcią. Z drugiej strony możliwość zwracana funkcji, a więc w rzeczywistości zmiany zachowania się programu w zależności od danych, w zastosowaniach HPC może być bardzo pożądana.

Funkcyjność języka wymaga bardzo silnego systemu typów. Jak już zostało zasygnalizowane, ma on pozwalać na przeciążanie funkcji, czyli rozpoznawanie którą należy wywołać po typie parametrów. Warto wyraźnie powiedzieć, że możliwość definiowania typów przez użytkownika powoduje, że kompilator będzie potrafił sprawdzić „typowanie się” wyrażeń matematycznych.

Programy napisane w Fortress składają się z komponentów, z których każdy ma udostępniać jakiś interfejs (np. funkcję run() dla programów wykonywalnych, albo API komponentów które mają być używanie przez inne). „Kompilator” ma mieć dwa tryby pracy – może być używany jako interpreter, lub jako prawdziwy kompilator (czego nie ma Java). W trakcie kompilacji komponety mają być optymalizowane, a następnie składowane w ukrytym cache'u Fortress.

Pamięć uruchomionego programu jest współdzielona przez wszystkie jego wątki, co jak wiadomo może powodować wiele złych efektów, takich jak data race condition, czy problemy z aktualnością pamięci. Jako, że programy w Fortress mają być z założenia wielowątkowe, to język musi udostępniać i udostępnia różne mechanizmy wspomagające zapewnienie integralności danych. Po pierwsze dostęp do zmiennych odbywa się na zasadzie tranzakcji, po drugie daje programiście możliwość wykonania części programu sekwencyjnie, zadeklarowania sekcji krytycznej, czy wykonania operacji atomowo.

W tym miejscu warto pokusić się o pewne podsumowanie. Rynek HPC jest dosyć konserwatywny i przywiązany do sprawdzonych rozwiązań, więc przekonanie go do nowego języka będzie trudne. Trudno powiedzieć, czy zrobienie przez SUNa z Fortress projektu otwartego wystarczy aby pokonać język, który zostanie ostatecznie wybrany z projektu HPCS, ale pewnie jest, że Fortranowi należy się już emerytura i potrzebny jest jakiś jego następca.

Na pewno część pomysłów SUNa, jak np. wyświetlanie kodu jak formuły matematycznej, programowanie z cechami, czy częściowe wprowadzenie funkcyjności jest ruchem w dobrą stronę. Inne pomysły, niestety, budzą mieszane uczucia. Pozwolenie na przeciążanie operatorów nie sprawdziło się w C++, więc nie wiadomo dlaczego w przypadku Fortress miałoby być inaczej. Owszem, dla osób zajmujących się konkretną dziedziną możliwość korzystania z własnych oznaczeń będzie przyjemna, ale dla informatyków, który później taki kod będą optymalizować może okazać się koszmarem. Tak samo domyślna równoległość programów jest pomysłem wartym rozważenia, ale trzeba wziąć pod uwagę przyzwyczajenie całego środowiska do sekwencyjnego pisania programów. Na lepsze spojrzenie na sytuacje trzeba będzie poczekać do 2010 roku, kiedy to ma się skończyć HPCS DARPA.

Przykład programu

Do prototypu kompilatora dostępnego na stronie projektu dodane jest kilka przykładowych programów. Pokażę tutaj dwie wersje tego samego programu obliczającego pi za pomocą igły Buffona. Pierwsza jest zwyczajnym kodem w ASCII, a druga tym samym kodem przerobionym na kod LaTeXa za pomocą Fortify i skompilowanym do pdfa.

component buffons

export Executable

run(args:String...):()=do

  needleLength = 20
  numRows = 10
  tableHeight = needleLength numRows
  var hits : RR64 := 0.0
  var n : RR64 := 0.0
  println("Starting parallel Buffons")
  recordTime(6.0)
  for i <- 1#3000 do
     delta_X = random(2.0) - 1
     delta_Y = random(2.0) - 1
     rsq = delta_X^2 + delta_Y^2
     if 0 < rsq < 1 then
        y1 = tableHeight random(1.0)
        y2 = y1 + needleLength (delta_Y / SQRT rsq)
        (y_L, y_H) = (y1 MIN y2, y1 MAX y2)
        if ceiling(y_L/needleLength) = floor(y_H/needleLength) then
                   atomic do hits += 1.0 end
        end
        atomic do n += 1.0 end
     end
  end
  probability = hits/n
  pi_est = 2.0/probability
  printTime(6.0)
  println("")
  print("estimated Pi = ")
  println(pi_est)
  end

end


Kod w wersji "matematycznej"

Status projektu

W tej chwili (koniec lipca 2008) Fortress jest projektem opensource. Opublikowana została wersja 1.0 specyfikacji języka i prototyp kompilatora jako klasa w Javie. Prototypowi temu jeszcze daleko do wersji nadającej się do normalnego użytku, gdyż np. nie akceptuje tabulatorów w kodzie, wymaga aby komponenty nazywały się tak jak pliki w których się znajdują, a prędkość działania pozostawia wiele do życzenia.

Dostępna jest też nakładka na Emacsa do pisania i wyświetlania kodu z wykorzystaniem niektórych symboli matematycznych, jest działający program Fortify do przerabiania kodu Fortress na kod LaTeXa.

Zobacz także

HPCS: The big picture – o programie HPCS DARPA [1]
Materiały o językach powstałych w wyniku programu HPCS [2]
Strona projektu Fortress (tu jest specyfikacja języka i prototyp kompilatora) [3]



O Autorze

* Marek Grabowski uczesniczył w praktykach studenckich organizowanych przez Centrum Obliczeniowe ICM w lipcu i sierpniu '2008. Tematem prakyk było programowanie komputerów w architekturze wielordzeniowej. Autor jest studentem informatyki i matematyki Wydziału Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Intel Threading Building Blocks

Autor: Kamil Lenartowicz **

Pomysł/Założenia

Biblioteka ma za zadanie implementować podobną funkcjonalność jak standard OpenMP jednak w modelu obiektowym dla języka C++. Biblioteka jest dostępna jako nagłówki oraz prekompilowane biblioteki dynamiczne. Biblioteka oferuje narzędzia mogące się najczęściej przydać w trakcie pisania programu w oparciu o pamięć współdzieloną, oferuje dość duże możliwości zarządzania podziałem pracy, wprost daje dostęp do zazwyczaj drzewiastej topologii propagacji pracy wśród wątków. Biblioteka jest dostępna na kompilatory Intel, Microsoft oraz GNU g++.

Cechy szczególne

Najważniejszą cechą tej biblioteki jest sposób implementacji zrównoleglanych programów, jeśli chcemy zrównoleglać pętle lub zajmować się zadaniami musimy zaimplementować klasy będące odpowiednikami wątków które zazwyczaj muszą potrafić się łączyć (zbierać wyniki wykonanych prac ze swoich dzieci albo poprostu mniejszych zakresów w przypadku zrównoleglania pętli) oraz rozdzielać (w przypadku pętli) lub też wywoływać podzadania. Ważną cechą biblioteki jest integracja z STL tam gdzie jest to sensowne co czyni biblioteke wygodniejszą w użytkowaniu.


Możliwości

Zrównoleglanie pętli z przykładem kodu

Pętlę zrównoleglamy przez zdefiniowanie obiektu który będzie potrafił podzielić swój przedział pracy na mniejsze przedziały (a tak naprawde realizujemy to przez implementacje konstruktora kopiującego - biblioteka sama zajmuje się dzieleniem przedziałów), będzie potrafił połączyć dwa wykonane już przedziały w jeden duży wykonany (czyli scalanie wyniku) oraz będzie potrafił wykonać prace na zdefiniowanym przedziale. Czyli mamy tutaj do czynienia z obiektami samoczynnie dzielącymi się od jednego do maksymalnego zrównoleglenia (struktura drzewiasta), specjalne operacje wykonują konieczne do zaimplementowania metody:


operator() - wykonuje zadany przedział (jednowątkowo)

konstruktor kopiujący - używany do dzielenia pracy

join() - łączenie wykonanych przedziałów


W trakcie działania sytuacja może wyglądać następująco (białe kwadraty oznaczają przedziały do zainicjowania, zielone przedziały zakończone, kolejce cyfry oznaczają wątki mogące działać równolegle).

TBB-Petla.jpg

Warto zwrócić uwagę, że kolejne gałęzie mogą się dzielić i wykonywać zupełnie niezależnie - dopiero w trakcie ich łączenia musi nastąpić synchronizacja.


Przykład: implementacja obliczenia \pi w OpenMP

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "omp.h"


int main(int arg, char ** argc) {
       
       if(arg < 2) exit (1);
       
       
       int n = atoi(argc[1]);
       double sum = 0;
       double h = 1. / (double) n;
       
       
       omp_set_dynamic(1);
       
       #pragma omp parallel
       {
               double pom;
               int i;
               
               #pragma omp single
               printf("watkow: %d\n", omp_get_num_threads());
               
               #pragma omp for reduction(+:sum)
               for(i = 0; i < n - 1; i++) {
                       
                       pom = 1. / (double) ((double) n + (double) i * (double)i * h);
                       
                       sum += pom;
               }
       }
       
       sum *= 4.;
       
       printf("pi = %lf\n", sum);

       return 0;
}

Czyli mamy tu łatwo zrównolegloną pętlę obliczającą kolejne wyrazy sumy.


Przykład: implementacja obliczenia \pi w TBB

#include "tbb/parallel_reduce.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/tick_count.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"

#include <cstdlib>

using namespace std;
using namespace tbb;

class Pi {

       public:
               double sum;
               const int n;
               const double h;
               
               void operator() (const blocked_range<size_t>& r) {
                       for (size_t i = r.begin(); i!=r.end(); ++i)
                               sum += 1. / (double) ((double) n + (double) i * (double)i * h);
               }
               
               Pi(Pi & x, split) : sum(0), n(x.n), h(x.h) {}
               
               void join(const Pi & y ) { sum += y.sum; }
   
               Pi(int _n, double _h) : sum(0), n(_n), h(_h) {}
};

double PiFoo(size_t n) {
       
       double h = 1. / (double) n;
       
       Pi pi(n, h);
       parallel_reduce(blocked_range<size_t>(0, n, 10001), pi );
       return pi.sum;
}



int main(int arg, char ** argc) {
       
       task_scheduler_init init;
       
       if(arg < 2) exit (1);
       int n = atoi(argc[1]);

       printf("pi = %lf\n", 4. * PiFoo(n));
       return 0;
}
  • Funkcja PiFoo oblicza \pi, w tym celu wywołuje parallel_reduce - jest to specjalna funkcja TBB której w parametrach trzeba podać zakres na jakim dane zadanie ma być wykonane oraz obiekt korzeń który będzię się potrafił dzielić na podzakresy, obliczać zakres oraz łączyć wykonane zakresy. W implementacji klasy Pi mamy operator() który w argumencie przyjmuje zakres na jakim ma sekwencyjnie obliczyć wartość sumy, warto zauważyć że obiekt klasy Pi przechowuje aktualną sumę na swoim przedziale (zmienna sum), odpowiednio ją inicjuje w konstruktorze (w szczególności w kopiującym ją zeruje!) oraz w metodzie join dokłada do swojej wartości wartość z obiektu dołączanego (odpowiednik redukcji z OpenMP).
  • Dzielenie pracy oczywiście nie może trwać w nieskończoność, kiedyś trzeba obliczyć dany fragment bez zrównoleglania, czasem nawet jeśli są jeszcze wolne rdzenie - dodatkowy 3 argument dla konstruktora klasy blocked_range definiuje długość zakresu którego nie opłaca się już dzielić. Jest również możliwość użycia heurystyki która sama wywnioskuje do kiedy opłaca się zrównoleglać, jak łatwo się domyślić trzeba wtedy podać specjalną taką klasę w pierwszym argumencie funkcji parallel_reduce (więcej w dokumentacji) jednak heurystyka nie zawsze się sprawdza.

Wsparcie dla zadań

To co narzuca się po obejrzeniu topologii zrównoleglania pętli to oczywiste przeniesienie struktury drzewa na zadania (tylko że tym razem zależności ojciec syn to zadanie główne i podzadanie którego ojciec potrzebuje). Biblioteka TBB daje nam możliwość definiowania zadań które np. w swoim kodzie wykonania utworzą nowe zadanie i przykładowo uruchomią je i będą czekać na jego zakończenie. Dobrze ilustruje to rysunek poniżej (spawn i wait for to oczywiście funkcje jakie będa odpowiedzialne za te operacje), uważny czytelnik zauważy, że jest to dokładnie to samo z czym mieliśmy doczynienia w przypadku zrównoleglania pętli.

TBB-Task.jpg


Przykład: obliczanie liczb Fibonacciego (z tutorial TBB)

long ParallelFib( long n ) {
    long sum;
    FibTask& a = *new(task::allocate_root()) FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    return sum;
}

Funkcja oblicza zadaną liczbę Fibonacciego, w tym celu uruchamia specjalny obiekt klasy FibTask, jego definicja mogła by wyglądać tak:


class FibTask: public task {
public:
   const long n;
   long* const sum;
   FibTask( long n_, long* sum_ ) :
       n(n_), sum(sum_)
   {}

  task* execute() { // Overrides virtual function task::execute
      if( n<CutOff ) {
          *sum = SerialFib(n);
      } else {
          long x, y;
          FibTask& a = *new( allocate_child() ) FibTask(n-1,&x);
          FibTask& b = *new( allocate_child() ) FibTask(n-2,&y);
          // Set ref_count to "two children plus one for the wait".
          set_ref_count(3);
          // Start b running.
          spawn( b );
          // Start a running and wait for all children (a and b).
          spawn_and_wait_for_all( a );
          // Do the sum
          *sum = x+y;
      }
      return NULL;
  }
};


  • Najważniejsza metoda execute nadpisująca domyślną zadania TBB tworzy nowe podzadania które z kolei obliczają potrzebne liczby Fibonacciego, uruchamia te zadania i czeka na ich zakończenie, (funkcja spawn jest nie blokująca, funkcja spawn_and_wait_for_all uruchamia i czeka na zakończenie wszystkich dzieci, funkcja set_ref_count ustawia ilość zadań na jakie będzie trzeba czekać - +1 ponieważ dochodzi zadanie czekające na dzieci które ma powiadomić ojca o ich zakończeniu.
  • Oczywiście ten sposób obliczania liczb Fibonacciego nie ma nic wspólnego z optymalnością.

Scalable allocator

TBB oferuje nam alokacje pamięci która nie wymaga synchronizacji między wątkami, jak wiadomo kiedy alokujemy pamięć w modelu SMP na przykład używając funkcji malloc z języka C jest to sekcja krytyczna, w przypadku dużej liczby wątków i wielu alokacji może to zacząć mieć znaczenie. Biblioteka oferuje prosty mechanizm omijania tego problemu, w praktyce wygląda to tak:

vector<int, scalable_allocator<int> > * v;
v = new vector<int, scalable_allocator<int> >(10);

W ten sposób zaalokowaliśmy wektor nie zależnie od innych działających wątków, warto zwrócić uwagę na intergracje z STL.

Cache aligned allocator

Biblioteka daje nam możliwość przeciwdziałania tzw. false sharing, w tym celu możemy zażyczyć sobie aby alokacja zawsze brała nową linię cache, oczywiście należy tego mechanizmu używać tylko wtedy kiedy trzeba, cache jest mały.

vector<int, cache_aligned_allocator<int> > * v;
v = new vector<int, cache_aligned_allocator<int> >(10);

Mamy pewność, że problem false sharing nie będzie dotyczył wektora v.


Inne narzędzia

TBB jest ogólnie rzecz biorąc zbiorem pomocnych narzędzi, znajdziemy tu np. kolejki, hashtablice, wektory bezpieczne na wielowątkowość, możliwość zdefiniowania pipelining, zmienne atomowe itp., więcej w dokumentacji.


Status projektu

Biblioteka jest w pełni działająca, są wersje produkcyjne. Można również pobrać kod zródłowy. Obecnie biblioteka jest rozprowadzana jako zbiór nagłówków oraz bibliotek dynamicznych co ułatwia nam instalacje.


Zobacz także

  • http://www.threadingbuildingblocks.org/ - strona domowa, można pobrać aktualną wersję biblioteki oraz bardzo dobrą dokumentację podzieloną na:
    • wstęp,
    • tutorial - opis możliwości biblioteki,
    • manual - opis konkretnych funkcji.

O Autorze

** Kamil Lenartowicz uczesniczył w praktykach studenckich organizowanych przez Centrum Obliczeniowe ICM w lipcu i sierpniu '2008. Tematem prakyk było programowanie komputerów w architekturze wielordzeniowej. Autor jest studentem informatyki Wydziału Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego.

X10

Autor: Magdalena Zakrzewska ***

Pomysł

X10 to experymentalny nowy język programowania rozwijany przez IBM we współpracy z ośrodkami akademickimi. Jest on częścią projektu IBM PERCS (Productive Easy-to-use Reliable Computer Systems), który to ma za zadanie stanąć naprzeciw wymaganiom nowych systemów opartych na wielowątkowych aplikacjach. PERCS skupia się sprzętowo-programowej współpracy. Jego zadaniem jest zintegrować możliwości nowych mikrotechnologii, architektur, systemów operacyjnych i kompilatorów, aby zwiększyć wydajność i skalowalność współbieżnych programów.

X10 stara się sprostać tym wymaganiom. Projekt ten tworzy nowy model programowania wraz z kilkoma narzędziami dostępnymi pod Eclipsem, który ulepsza optymalizację programów w zarządzanym przez siebie środowisku pracy.

Jednak najważniejszym celem X10 było stworzenie języka prostego, przenośnego, niezależnego od architektury - takiego jak Java. Ale języka jednocześnie korzystającego z możliwości sprzętu, na którym działa.

Główne założenia

X10 jest nowoczesnym, współbieżnym językiem obiektowym, łatwo zrozumiałym dla użytkowników Javy. Jest przede wszystkim tworzony dla przyszłych systemów operacyjnych działających na superkomputerach - gdzie węzły są wielordzeniowe z symetrycznym dostępem do pamięci, a całość ma budowę klastra. X10 należy do grupy języków traktujących wspólną przestrzeń adresową pamięci jako podzieloną lokalnie między procesory (PGAS -Partitioned Global Address Space).

Oprócz nowego języka X10 propunuje także narzędzia pomocne programistom. Chodzi tu o X10 Development Toolkit (X10DT), który może być zainstalowany jako wtyczka do Eclipsa. X10DT ułatwia kodowanie: wspiera edytowanie, przeglądanie, debugowanie, uruchamianie programów. Ma on prosty w obsłudze interfejs i funkcjonalnośc znaną użytkownikom Eclipsa: m.in. wyskakujące okienka z podpowiedziami.

Sposób działania

X10 to tak naprawdę podzbiór języka Java rozbudowany o nowe rozwiązania. Program napisany w X10 jest tłumaczony na kod Javy, z dodatkowymi klasami z X10. Potem może być uruchomiony przez wirtualną maszynę X10 (JVM + J2SElibraries + X10 libraries + X10 Multithreaded Runtime).


Kompilacja i uruchamianie


X10 przydziela globalną przestrzeń adresową procesu poszczególnym procesorom(rdzeniom). Dzięki temu możliwe jest współbieżne wykonywanie operacji. Nową funkcjonalność X10 uzyskuje dzięki specyficznym dla siebie klasom : Place, Point, Region, Dist, Array, Clock oraz nowym pojęciom: activity, future, finish.

Współbieżność programów zapewniają tablice (klasa Array), które mogą być rozdystrybuowane między różne miejsca. Tam będą równolegle wykonywane operacje na danych fragmentach tablicy. Miejsca z kolei (klasa Place) mają wykorzystywać architekturę maszyny, czyli jej wieloprocesorowość.

Podstawowe pojęcia

Activity i Place

Activity - to dynamiczne wykonanie fragmentu kodu powiązane ze zmiennymi i miejscem wykonania

Place - miejsce przechowywania danych. Przestrzeń adresowa jest dzielona między miejsca, które są tworzone podczas uruchamiania programu na podstawie zmiennych środowiskowych.


Future i finish

Future - konstrukcja używana do równoległego wyliczenia wyrażenia jako nowe działanie (podobne do fork() w C)

Finish - czekanie na zakończenia działania wywołanego przez future

Przykład użycia konstrukcji future. Wywołania fib(n-1) i fib(n-2) wykonują się współbieżnie:

public class TutFuture1 {
    static int fib(final int n) {
        if ( n <= 0 ) return 0;
        else if ( n == 1 ) return 1;
        else {
            future<int> fn_1 = future { fib(n-1) };
            future<int> fn_2 = future { fib(n-2) };
            return fn_1.force() + fn_2.force();
        }
    } // fib()‏
    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
    } // main()‏
} // TutFuture1


Regiony i dystrybucje

Point - klasa reprezentująca wektor wartości typu integer

Region - dowolny zbiór punktów

Dist - dystrybucja, czyli zamapowanie regionu w miejsca

Ateach - pętla, która dla każdej iteracji tworzy nowe działanie.

Przykład użycia konstrukcji ateach:

public class TutAteach1 {
    public static void main(String args[]) {
        finish ateach( point[i] : dist.factory.unique() ) {
            System.out.println("Hello from " + i);
        } 
    } // main()‏
} // TutAteach1

ateach( point[i] : dist.factory.unique() ) - rozdziela punkty z domyślnego regionu równomiernie między miejsca i dla każdego punktu tworzy nowe działanie.

Domyślnie są cztery miejsca.

Wynik na ekranie:
Hello from 1
Hello from 0
Hello from 3
Hello from 2

Array - tablice w X10 są wielowymiarowe. Można je rozdzielić między miejsca

Każdy dostęp do dzielonych danych (czyli fragmentu tablicy) musi się odbywać poprzez działanie w miejscu, gdzie są te dane. Bezpośredni dostęp do danych w innym miejscu jest niedozwolony.

Clock

Clock - zegary pozwalają na synchronizację równoległych obliczeń

Przykład użycia:

        finish async {
            final clock c = clock.factory.clock();
            foreach (point[i]: [1:N]) clocked (c) {
                while ( true ) {
                    int old_A_i = A[i]; int new_A_i = Math.min(A[i],B[i]);
                    if ( i > 1 ) new_A_i = Math.min(new_A_i,B[i-1]);
                    if ( i < N ) new_A_i = Math.min(new_A_i,B[i+1]);
                    A[i] = new_A_i;
                    next;
                    int old_B_i = B[i]; int new_B_i = Math.min(B[i],A[i]);
                    if ( i > 1 ) new_B_i = Math.min(new_B_i,A[i-1]);
                    if ( i < N ) new_B_i = Math.min(new_B_i,A[i+1]);
		  B[i] = new_B_i;
                    next;
                    if ( old_A_i == new_A_i && old_B_i == new_B_i ) break;
                } // while
            } // foreach 
        } // finish async

next - bariera synchronizacyjna

Status projektu

W chwili obecnej X10 to tylko język symulujący wykorzystanie możliwości architektury wieloprocesorowej. Wszystkie programy są tłumaczone na Javę i mogą być uruchomione na każdym komputerze z Javą 5.0. X10 nie ma wsparcia ze strony warstwy pośredniczącej między sprzętem, a programem. Inaczej mówiąc: X10 nie korzysta z faktu, że działa na konkretnej maszynie - to programista daje procesowi informacje, na jakim sprzęcie działa. Tworzy się jedynie iluzja, że program wykorzystuje wydajnie zasoby komputera.

Na razie X10 skupia się na funkcjonalności, nie wydajności. W przyszłości projekt ma stworzyć dodatkową warstwę, które pozwoli wykorzystywać możliwości sprzętowe komputerów. Ponadto narzędzie programistyczne X10DT będzie rozbudowane o nową funkcjonalość wspierającą pisanie programów współbieżnych.

Zobacz także

Strona domowa: [4]
Na tej stronie są wszystkie potrzebne informacje: dokumentacja, tutorial, przykłady.

O Autorze

*** Magdalena Zakrzewska uczesniczyła w praktykach studenckich organizowanych przez Centrum Obliczeniowe ICM w lipcu i sierpniu '2008. Tematem prakyk było programowanie komputerów w architekturze wielordzeniowej. Autorka jest studentką informatyki i matematyki Wydziału Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Intel Ct

Autor: Filip Balejko ****

Nowe możliwości, nowe wyzwania

Trendy w nowo powstających architekturach

Architektury procesorowe ewoluują w stronę udostępniania programiście coraz to większych możliwości w programowaniu równoległym. Widoczne są wyraźnie dwa trendy: wiele rdzeni wraz ze wzbogaconym zbiorem instrukcji SIMD oraz udostępnianie procesorów graficznych (GPUs) do ogólniejszego użytku.
Trendy te stwarzają dwa poważne wyzwania. W jaki sposób udostępnić programistom złożony model programowania równoległego? Po drugie, jak zapewnić zgodność między zwiększającą się liczbą rdzeni oraz instrukcji SIMD?

Intel postanowił sprostać obu tym wyzwaniom tworząc Ct. Jest to deterministyczny model programowania równoległego stworzony po to, aby efektywnie wykorzystać modele programowania GPGPU (general-purpose GPU) oraz CPU. Ct różni się od innych modeli wszechstronnością, dając programiście elastyczność w pisaniu kodu na wiele architektur. Dla porównania, większość modeli programowania GPGPU podlega ograniczeniom wynikającym ze specyfiki architektury, dla której kod będzie stworzony.

Programowanie w architekturach Tera-Scale

Niezależni producenci oprogramowania są podekscytowani teoretycznymi maksymalnymi osiągnięciami przyszłych architektur, ale jednocześnie obawiają się trudności jakie może przynieść pisanie dedykowanego dla nich kodu. Używanie wątków i instrukcji wektorowych dostarcza ogromnej elastyczności programiście, lecz znacząco wpływa na produktywność oraz przenośność i skalowalność aplikacji. Co więcej, ewoluujące wielkości wektorów i zwiększająca się liczba rdzeni przysparza problemów ze skalowalnością. Wsteczna kompatybilność tworzonego kodu gwarantuje poprawność lecz nie wykorzystuje nowych możliwości jakie niosą ze sobą nowe technologie, co może prowadzić do regresu wydajności wraz z rozwojem architektur...

Producenci sprzętu i oprogramowania GPU starają się rozwiązać te problemy. Języki dla GPU zwalniają programistę z myślenia o wątkach albo instrukcjach SIMD dzięki modelom programowania takim jak DirectX. W tym modelu pojedynczy element danych (piksel) jest przetwarzany niezależnie od sąsiadujących elementów. Ten prostszy model obliczeń odzwierciedla leżącą u podstaw architekturę i jest często nazywany strumieniową równoległością danych (streaming data parallelism).

Na modele programowania GPU narzucone są ograniczenia, dzięki którym kompilator oraz środowisko uruchomieniowe potrafi wnioskując na podstawie kodu automatycznie zrównoleglić aplikację. Przykładami są DirectX, CUDA i Cg. Jeżeli programista jest w stanie przepisać aplikację tak aby działała zgodnie z tymi ograniczeniami, kompilator/środowisko potrafi zrobić resztę automatycznie. Najczęściej jednak przepisanie aplikacji i podporządkowanie się tym ograniczeniom wymaga od programisty dużego nakładu pracy i może odzwierciedlić się w znaczącym spadku efektywności algorytmów. Na przykład trudno jest wydajnie operować na listach czy też skompresowanych strukturach, a więc aplikacje, które naturalnie korzystają z tego typu algorytmów, muszą zostać przeformułowane tak, aby używały algorytmów lepiej wspieranych przez modele GPGPU.

Intel Ct jest architekturą ogólniejszego użytku niż GPU czy też inne architektury oparte o koprocesory. W przeciwieństwie do GPU, architektura Intela posiada:

  1. Wewnątrzrdzeniową komunikację poprzez spójną i efektywną hierarchię cache
  2. Wydajną i posiadającą małe opóźnienia synchronizację wątków na przestrzeni całej macierzy procesorów
  3. Mniejszą efektywną liczbę strumieni danych SIMD

Sprzęt ogólnego użytku pozwala architekturze Intela na uruchamianie szerszej klasy algorytmów (na przykład stosujących listy). Pomimo, że architektura Intela jest w stanie uruchamiać aplikacje oparte na modelu programowania GPU, aplikacje te są bardziej ograniczone niż jest to konieczne. Oczywiście ma sens zdefiniowanie ograniczonego modelu programowania aby kompilator i środowisko uruchomieniowe było w stanie zrównoleglić aplikację. Jednakże pożądany jest model, który jest mniej ograniczony niż modele GPGPU tak, aby aplikacje nie musiały być zasadniczo przeformułowywane. Celem Ct jest stworzenie przenośnego modelu programistycznego, który efektywnie wykorzystuje popularne architektury.

Zagnieżdżona równoległość danych

Często wygodne dla programisty jest myślenie o zasobach wielordzeniowych procesorów jako o silniku dla równoległych obliczeń na danych. Podstawową ideą są aplikacje dostarczające równoległych operacji na kolekcjach danych. Abstrahowanie od niskopoziomowej implementacji wątków, liczby rdzeni oraz zbiorów instrukcji wektorowych i rozważanie problemu w pojęciach operacji na kolekcjach danych znacząco ułatwia wyrażenie równoległości w sposób niezależny od platformy. Ct dostarcza abstrakcje zagnieżdżonej równoległości danych wspierając równocześnie nieregularne algorytmy które:

  1. Wymagają dynamicznych typów danych takich jak rzadkie macierze, listy czy drzewa
  2. Zależą od efektywności rywalizacji o zasoby podczas operacji takich jak redukcja czy sumy prefiksowe
  3. Posiadają skomplikowane, zagnieżdżone pętle i instrukcje warunkowe
  4. Posiadają funkcje rekurencyjne

Intel twierdzi, że Ct realizuje te wymagania efektywnie (w przeciwieństwie do GPU) oraz, że z systemów dual- i quad-core skaluje się do tera-scale.

API Ct w procesie rozwoju aplikacji
Jak Ct jest kompilowane

Znaczenie determinizmu

Determinizm zapewnia, że zachowanie programu jest identyczne zarówno na jednym jak i na wielu rdzeniach. To w gruncie rzeczy eliminuję cała klasę błędów programistycznych biorących się z niedeterministycznej kolejności dostępu do danych - data races. Ct dostarcza również przewidywalny model programowania wysokiego poziomu, dzięki czemu przeciętny programista może używać operatorów Ct posiadając jedynie podstawową wiedzę o ich koszcie i skalowalności. Jest to trudne do osiągnięcia w modelach programowania równoległego, które nie narzucają na programistę odpowiednich ograniczeń.

Model programowania Ct realizuje to trudne zadanie połączenia wydajnych oraz dających wiele możliwości struktur i mechanizmów z całkowicie deterministycznym zachowaniem. Jest to niezbędne w modelach programowania tera-scale i umożliwia tworzenie programów, które są zarówno wydajne jak i łatwe do napisania.

Ct API

Ct Vectors: TVECs

Podstawowy typ wektorowy w Ct.

  • Równoległy wektor przechowywany w osobnym segmencie pamięci (zapewnienie bezpieczeństwa wykonywanych na nim równoległych operacji).
  • Do wektorów TVEC można stosować jedynie operatory Ct.
  • TVECs są przekazywane przez wartość aby zapewnić bezpieczeństwo operacji równoległych oraz umożliwić agresywną optymalizację.
  • TVEC może przechowywać standardowe typy: I32 (32-bit integer), I64 (64-bit integer), F32 (Float), F64 (Double), Bool (Boolean) oraz struktury i tablice zdefiniowane przez programistę.
TVEC<I8> Red;
TVEC<F32> Xes;
Red = copyin(CRed, Height*Width, I8); // Red ← CRed
copyout((void*)CXes,Xes);             // Cxes ← Xes

C = [[a],[],[b,c,d],[e,f]]            // C[2,1]==c
D = [(0->a),(2->b),(8->c),(_->d)]     // D[8]==c, D[5]==d

Operatory Ct

Z punktu widzenia programisty operatory Ct nie posiadają efektów ubocznych – operator logicznie zwraca nowy TVEC. Wykorzystano również przeciążanie operatorów aby kod był bardziej przejrzysty.

 ScaledRed = Red*0.5; // ScaledRed ← a new TVEC 

Operatory zbiorowe

Są to redukcje oraz inne operacje na całych zbiorach. W językach funkcyjnych nazywane operacjami fold lub homomorfizmami list. Operacje te dzielą się na redukcje i sumy prefiksowe (scans).

addReduce([1,2,3,4]) 			 // [10]
addPrefix([1,0,2,-1,4]) 		 // [0,1,1,3,2]
Pack([a,b,c,d,e,f],[0,1,1,0,1,0])      // [b,c,e]
Permutacje
ShiftRight([a,b,c,d,e,f],[1],i)   // [i,a,b,c,d,e]
RotateLeft([a,b,c,d,e,f],[2])     // [c,d,e,f,a,b]

Inteligentne operatory

Poniższy kod wykonuje “inteligentne” dodanie dwóch wektorów, niezależnie od ich długości, wymiarowości czy regularności.

 TVEC<F32> A = B + C; 

W przypadku zagnieżdżonych struktur operatory zachowują się tak jak można by się tego spodziewać:

 
add([[a,b],[c,d,e,f]],[[g,h],[i,j,k,l]])  // [[a+g,b+h],[c+i,d+j,e+k,f+l]] 
addReduce([[1,2],[3,4,5]]) 		    // [3,12]
addReduce([(1->1),(2->1),(1->2)])         // [(1->3),(2->1)]

Przykład programu

TVEC<F64> ctQsort(TVEC<F64> Keys)
{
  TVEC<F64> pivot, lowerKeys, 
			 pivotKeys, upperKeys;
  TVEC<Bool> pivotFlags;
  I32 pivot;

  if (length(Keys) == 0)
    return Keys;
 
  pivot = extract(Keys, 0);
  pivotFlags = lessThan(Keys, Pivot);
  lowerKeys = pack(Keys, pivotFlags);
  pivotFlags = equal(Keys, Pivot);
  pivotKeys = pack(Keys, pivotFlags);
  pivotFlags = greaterThan(Keys, Pivot);
  UpperKeys = pack(Keys, pivotFlags);
  return cat(ctQsort(lowerKeys), cat(pivotKeys,ctQsort(upperKeys));
}

Status Projektu

Na dzień dzisiejszy (wrzesień 2008) Ct jest projektem badawczym i nie jest w żaden sposób udostępniony do ściągnięcia i użycia.

Zobacz także

Strona domowa Ct: [5]
White Paper [6]

O Autorze

**** Filip Balejko uczesniczył w praktykach studenckich organizowanych przez Centrum Obliczeniowe ICM w lipcu i sierpniu '2008. Tematem prakyk było programowanie komputerów w architekturze wielordzeniowej. Autor jest studentem informatyki Wydziału Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego.