Message Passing Interface

Message Passing Interface (MPI, z ang., interfejs transmisji wiadomości) – protokół komunikacyjny będący standardem przesyłania komunikatów pomiędzy procesami programów równoległych działających na jednym lub więcej komputerach. Interfejs ten wraz z protokołem oraz semantyką specyfikuje, jak jego elementy winny się zachowywać w dowolnej implementacji. Celami MPI są wysoka jakość, skalowalność oraz przenośność. MPI jest dominującym modelem wykorzystywanym obecnie w klastrach komputerów oraz superkomputerach. Pierwsza wersja standardu ukazała się w maju 1994 r. Standard MPI implementowany jest najczęściej w postaci bibliotek, z których można korzystać w programach tworzonych w różnych językach programowania, np. C, C++, Ada, Fortran.

Historia

Różne środowiska przesyłania komunikatów dla potrzeb programowania równoległego były projektowane i rozwijane już na początku lat 80. XX wieku. Kilka z nich było budowanych dla specjalnych celów, na przykład dla maszyn takich jak Caltech N-cube. Niektóre były rozwijane dla sieci UNIX – Workstation. Były to między innymi PVM, Argonne’s P4 oraz PICL.

Ohio Superkomputer Center opublikował standard przesyłania komunikatów o nazwie LAM. Był to pakiet przygotowany specjalnie dla zastosowań w obliczeniach chemii kwantowej nazwany później TCGMSG. Powstał również wyprodukowany przez tę samą firmę komercyjny pakiet o nazwie Express, przeznaczony dla systemów N-cube.

Ponieważ autorzy tych licznych bibliotek w ramach swoich projektów dublowali podobną funkcjonalność, w październiku 1992 roku, podczas konferencji Supercomputing 92 uczestnicy doszli do porozumienia w sprawie opracowania wspólnego standardu przesyłu komunikatów, skupiającego i wykorzystującego na ile to możliwe wszystkie najlepsze rozwiązania z obecnych środowisk. W tym właśnie momencie narodził się także standard przesyłania komunikatów MPI.

Kilka bibliotek, takich jak ISIS implementowanych przez Cornell University, nie odpowiadało nieco sztywnemu modelowi proponowanemu przez uczestników konferencji. Ostatecznie biblioteki oparte na ISIS weszły w skład oprogramowania przeznaczonego dla systemów klastrowych firmy Microsoft, zwanego Wolfpack. ISIS był oparty na idei wirtualnej synchronizacji procesów. Dla zastosowań naukowych bądź komercyjnych biblioteka była nie do przyjęcia ze względu na duży spadek wydajności spowodowany koniecznością synchronizacji. Tymczasem w przypadku MPI synchronizacja nie była wymogiem krytycznym.

Obecnie występują 2 najpopularniejsze wersje: wersja 1.2 (tj. MPI-1, gotowy w maju 1994), która kładzie nacisk na przekazywanie wiadomości oraz jest zaopatrzona w statyczne środowisko uruchomieniowe oraz MPI-2.1 (MPI-2, ukończona w 1998), która zawiera kilka dodatków jak równoległe I/O, dynamiczne zarządzanie procesami oraz zarządzanie operacjami pamięci, Specyfikacja MPI-2 zawiera ponad 500 funkcji dla ANSI C, ANSI Fortran (Fortran90) oraz ANSI C++.

Warto zauważyć, iż MPI-2 jest głównie nadzbiorem MPI-1, mimo iż część funkcji została wymieniona. Programy napisane w standardzie 1.2 są kompatybilne z MPI-2. Po wprowadzeniu, nowszy standard nie cieszył się dużą popularnością, ponieważ rok wcześniej opracowano MPICH, w którym zaimplementowano część poprawek wprowadzanych w MPI-2. MPICH i LAM MPI to najczęściej stosowane implementacje standardu MPI.

Powstało też kilka specyficznych odmian MPI przystosowywanych przez producentów superkomputerów specjalnie dla tych maszyn. Firma SGI udostępnia na swoje platformy pakiet MPT (ang. Message Passing Toolkit) implementujący standard MPI.

Od czasu wypuszczenia w 1998 roku standardu MPI-2 wprowadzano w nim jeszcze długo korekty i jego pierwsza zaawansowana implementacja została przedstawiona dopiero w listopadzie 2002 roku.

W standardzie MPI-2 zdefiniowano równoległe operacje wejścia/wyjścia, które pierwotnie zostały zawarte w pakiecie MPI-IO rozwijanym specjalnie na potrzeby NASA, a następnie zmodyfikowane i przeniesione do nowego MPI-2.

Opis

MPI jest specyfikacją biblioteki funkcji opartych na modelu wymiany komunikatów dla potrzeb programowania równoległego. Transfer danych pomiędzy poszczególnymi procesami programu wykonywanymi na procesorach maszyn będących węzłami klastra odbywa się za pośrednictwem sieci.

MPI nie został usankcjonowany przez żaden z głównych standardów; mimo tego został de facto standardem komunikacyjnym pomiędzy procesami w programowaniu równoległym korzystającym z rozproszonego systemu pamięci. Główny model MPI-1 nie wspiera koncepcji współdzielonej pamięci, MPI-2 wspiera (w sposób ograniczony) rozproszony system pamięci dzielonej. Mimo tego programy MPI są bardzo często uruchamiane na komputerach o współdzielonej pamięci. Projektowanie programów zgodnie z modelem MPI posiada zalety architektur NUMA.

Mimo iż MPI należy do piątej (lub wyższych) warstw w modelu OSI, jego implementacje mogą pokrywać większość warstw modelu z gniazdem oraz TCP użytym jako warstwa transportowa. Większość implementacji MPI składa się ze specyficznego zestawu operacji, mogących zostać wywoływanymi z poziomu języków programowania.

Program w MPI składa się z niezależnych procesów operujących na różnych danych (MIMD). Każdy proces wykonuje się we własnej przestrzeni adresowej, aczkolwiek wykorzystanie pamięci współdzielonej też jest możliwe.

Zaletami MPI nad starszymi bibliotekami przekazywania wiadomości są przenośność oraz prędkość. Przenośność, ponieważ MPI został zaimplementowany dla każdej architektury opartej na rozproszonej pamięci. Prędkość, ponieważ każda implementacja jest zoptymalizowana pod sprzęt, na którym działa. Standard udostępnia zbiór precyzyjnie zdefiniowanych metod, które mogą być efektywnie zaimplementowane. Stał się on punktem wyjściowym do stworzenia praktycznego, przenośnego, elastycznego i efektywnego narzędzia do przesyłania komunikatów (ang. message passing). Standard MPI pozwala na jego zastosowanie zarówno w komputerach równoległych, jak i heterogenicznych sieciach stacji roboczych.

Standard nie zabrania, aby poszczególne procesy były wielowątkowe. Nie są też udostępnione mechanizmy związane z rozłożeniem obciążenia pomiędzy poszczególne procesy, z architekturą rozkładu procesorów, z dynamicznym tworzeniem i usuwaniem procesów. Procesy są identyfikowane poprzez ich numer w grupie w zakresie 0 .. groupsize – 1.

Główne własności MPI

  • umożliwia efektywną komunikację bez obciążania procesora operacjami kopiowania pamięci,
  • udostępnia funkcje dla języków C/C++, Fortran oraz Ada,
  • specyfikacja udostępnia hermetyczny interfejs programistyczny, co pozwala na skupienie się na samej komunikacji, bez wnikania w szczegóły implementacji biblioteki i obsługi błędów,
  • definiowany interfejs zbliżony do standardów takich jak: PVM, NX czy Express,
  • udostępnia mechanizmy komunikacji punkt – punkt oraz grupowej,
  • może być używany na wielu platformach, tak równoległych jak i skalarnych, bez większych zmian w sposobie działania.

Zalety MPI

  • dobra efektywność w systemach wieloprocesorowych,
  • dobra dokumentacja,
  • bogata biblioteka funkcji,
  • posiada status public domain,
  • przyjął się jako standard.

Wady MPI

  • statyczna konfiguracja jednostek przetwarzających,
  • statyczna struktura procesów w trakcie realizacji programu (dotyczy to implementacji opartych na MPI-1). Wersja MPI-2 (wspierana np. przez LAM 7.0.4) umożliwia dynamiczne zarządzanie strukturą procesów biorących udział w obliczeniach – MPI_Spawn(),
  • brak wielowątkowości.

Funkcje

Interfejs MPI ma na celu dostarczenie wirtualnej topologii, synchronizacji oraz zapewnienie komunikacji pomiędzy zestawem procesów (które zostały przypisane do węzłów/serwerów/instancji komputerów) w niezależny od języka sposób, przy podobnej do niego składni. Programy MPI zawsze współpracują z procesami, aczkolwiek programiści powszechnie odnoszą się do procesów jako procesorów. Zazwyczaj dla uzyskania maksymalnej wydajności, każdy CPU (lub rdzeń w wielordzeniowym procesorze) ma przypisany pojedynczy proces. Przypisanie to ma miejsce w czasie rzeczywistym przez agenta, który uruchamia program MPI (zazwyczaj nazywany mpirun lub mpiexec).

Biblioteka funkcji MPI zawiera (ale nie jest ograniczona do) operacji: punkt w punkt, typu randezvous oraz wysyłania/odbierania. Dostępne topologie logiczne to kartezjańska oraz oparta na grafie. Dane mogą być wymieniane pomiędzy parami procesów (operacje wysyłania/odbierania), występuje możliwość łączenia częściowych wyników obliczeń (operacje rozbijania i łączenia). Charakterystyczna jest tu również synchronizacja węzłów oraz identyfikacja używanego procesora, do którego jest przypisany proces, jak i dostępność sąsiadujących procesów w logicznej topologii. Operacje typu punkt w punkt obsługiwane są w trybach synchronicznym, asynchronicznym lub poprzez bufor.

Zarówno MPI-1 jak i MPI-2 wspierają implementacje, które dobrze sprawdzają się w komunikacji częściowej i obliczeniach. MPI również specyfikuje interfejsy bezpieczne pod względem wątków, tzn. takie, które zapewniają spójność oraz strategie zależności oprogramowania, co pozwala uniknąć manipulacji oraz ukrytego i niebezpiecznego stanu w obrębie interfejsu. Stosunkowo prostym jest pisanie w MPI kodu o charakterze wielowątkowym (punkt w punkt) – część implementacji wspiera taki kod. Wielowątkowa komunikacja zbiorowa jest najlepiej osiągalna poprzez użycie wielu kopii komunikatora.

Koncepcje

MPI oferuje bogaty wybór dostępnych dla użytkownika funkcji. Następujące pojęcia pomagają zrozumieć oraz zapewnić kontekst dla wszystkich możliwości oraz skutkują podjęciem decyzji przez programistę, którą z funkcji chce użyć w aplikacji.

Komunikator

Komunikatory są obiektami łączącymi, tj. grupującymi procesy podczas sesji MPI. W obrębie każdego komunikatora każdy zawarty proces ma niezależny identyfikator, zaś same procesy organizowane są w uporządkowaną topologię. MPI posiada również jawne grupy, ale są one głównie używane do organizacji oraz reorganizacji podzbiorów procesów przed utworzeniem innego komunikatora. MPI rozumie zarówno jedno jak i dwugrupowe operacje intrakomunikatorowe. W MPI-1 operacje jednogrupowe są dominujące, podczas gdy dwugrupowe odgrywają znaczącą rolę w MPI-2.

Komunikatory w MPI mogą być partycjonowane za pomocą kilku poleceń, które to zawierają algorytm kolorowania grafów nazywany MPI_COMM_SPLIT, który jest powszechnie używany do znajdowania topologicznych oraz innych logicznych podgrup w efektywny sposób.

Punkt – punkt

Szereg ważnych funkcji w API MPI dotyczy komunikacji pomiędzy dwoma określonymi procesami. Często używanym przykładem jest interfejs MPI_Send, który pozwala jednemu konkretnemu procesowi na wysłanie informacji do drugiego określonego. Operacje punkt – punkt są szczególnie użyteczne w nieregularnej komunikacji, np. w architekturze opartej na równoległości danych, w której każdy procesor stale wymienia regiony danych z innymi określonymi procesorami pomiędzy kolejnymi krokami obliczeń. Innym przykładem jest architektura master-slave, w której master wysyła nowe dane zadania do slave’a niezależnie od tego, czy poprzednie zostało ukończone.

Funkcje zbiorowe

Funkcje zbiorowe w API MPI dotyczą komunikacji pomiędzy wszystkimi procesami w grupie procesów. Typową funkcją jest MPI_Bcast call (skrót od „broadcast”). Funkcja ta pobiera dane z jednego, specjalnie oznaczonego węzła i wysyła komunikaty do wszystkich procesów w grupie. Odwrotną operacją jest MPI_Reduce, czyli pobieranie danych z wszystkich procesów z grupy, wykonanie operacji oraz finalnie przechowanie wyników w zadanym węźle. Wywołania te są często używane na początku lub końcu dużych rozproszonych obliczeń, gdzie każdy z procesorów operuje na części danych, po czym łączy je w wynik.

Istnieją również bardziej skomplikowane operacje, jak np. MPI_Alltoall, które przestawia n elementów danych z jednego procesora w taki sposób, iż n-ty węzeł dostaje określony element danych od każdego z procesorów.

Typy danych

Wiele funkcji MPI wymaga, określenia typu danych, jaki jest przesyłany pomiędzy procesorami. Dzieje się tak, ponieważ argumentami funkcji są zmienne, nie zaś typy definiowane. Jeśli typ danych jest standardowy, jak np. int, char, double itd., można użyć predefiniowanych w MPI typów takich jak: MPI_INT, MPI_CHAR, MPI_DOUBLE. Dane mogą być również w postać klas lub struktur danych. Można wykorzystywać pochodne typy danych z typów predefiniowanych.

Komunikacja jednostronna (MPI-2)

MPI-2 definiuje trzy operacje jednostronnej komunikacji: Put, Get i Accumulate, które to umożliwiają zapis do zdalnej pamięci, odczyt z niej oraz zmniejszają liczbę operacji pamięci dla wielu zadań. Definiowane są również trzy różne metody dla synchronizacji komunikacji – globalna, parami oraz przy wykorzystaniu zdalnych blokad – specyfikacja nie gwarantuje jednak, iż operacje te będą wykonywane aż do momentu punktu synchronizacji.

Dynamiczne zarządzanie procesami (MPI-2)

Kluczowym aspektem dynamicznego zarządzania procesami w MPI-2 jest zdolność procesów do tworzenia nowych procesów bądź ustanowienia komunikacji z procesami, które rozpoczęły się oddzielnie. Specyfikacja MPI-2 opisuje trzy główne interfejsy, przez które procesy mogą ustanawiać dynamiczną komunikację: MPI_Comm_spawn, MPI_Comm_accept/MPI_Comm_connect and MPI_Comm_join. Interfejs MPI_Comm_spawn pozwala procesom MPI na rozmnożenie liczby instancji nazywanych procesami MPI. MPI_Comm_spawn_multiple jest alternatywnym interfejsem, który pozwala różnym rozmnożonym instancjom być różnymi binariami z różnymi argumentami.

MPI I/O (MPI-2)

Równoległe I/O wprowadzone w MPI-2 jest często nazywane w skrócie MPI-IO oraz odnosi się do zbioru funkcji przeznaczonych do ułatwienia zarządzania I/O w systemach rozproszonych w sposób abstrakcyjny oraz umożliwienia łatwego dostępu do plików korzystając z istniejących typów pochodnych.

Pobieżne badania, jakie zostały przeprowadzone na MPI-IO, wskazują trudności w uzyskaniu zadowalających wyników.

Implementacje

'Klasyczne' implementacje dla klastrów oraz superkomputerów

Implementacja MPI jest różna dla różnych języków programowania. Większość z nich jest rodzajem kombinacji języka C, C++ oraz asemblera. Przeznaczone one są dla programistów C, C++ oraz Fortranu.

MPI został również szeroko rozpowszechniony w językach takich jak Python, Perl czy Java. Innym przykładem użycia jest MATLAB – korzysta on z różnych elementów MPI, jednakże w dalszym ciągu nie zapadły uzgodnienia odnośnie do standardów jego użycia.

Python

W chwili obecnej istnieje przynajmniej pięć implementacji MPI dla Pythona: pyMPI, mpi4py, PyPar, MYMPI (część Pydusa) oraz moduł MPI w ScientificPython. Godnym uwagi jest PyMPI, ze względu na fakt, iż jest to wariant interpretera Pythona. Z kolei PyPar, MYMPI, moduł ScientificPython wymagają importu, co oznacza, iż programista winien decydować gdzie i kiedy należy się odwoływać do MPI.

Java

Mimo że Java nie ma oficjalnej implementacji MPI, warto wymienić kilka prób połączenia Javy i MPI. Połączenia te różnią się stopniem końcowego sukcesu oraz kompatybilnością. Jedną z pierwszych prób była mpiJava Bryana Stolarskiego – zwłaszcza kolekcja wrapperów JNI odnoszących się do lokalnej biblioteki MPI w C.

Ten oryginalny projekt został nazywany również mpiJava API (zawierał także inne, późniejsze projekty Java MPI). Alternatywą, choć rzadziej używaną, jest MPJ API. Odznacza się on większym stopniem obiektowości oraz lepszym zbliżeniem do konwencji kodowania według Sun Microsystems. Biblioteki Java MPI mogą również bazować na lokalnych bibliotekach MPI bądź implementować przekazywanie wiadomości w Javie, zapewniając przy tym funkcjonalność P2P oraz pozwalając na wykonywanie operacji międzyplatformowych.

Najtrudniejsze elementy implementacji MPI w Javie wynikają z ograniczeń i osobliwości samej Javy – mała liczba jawnych wskaźników, liniowa przestrzeń adresów pamięci dla obiektów. Obejścia, których się zazwyczaj używa, umożliwiają przetransferowanie jednej linii w danym czasie i/lub wykonanie jawnej de-serializacji oraz konwersji typu przy wysyłaniu i odbieraniu, symulując tablicę C lub FORTRAN korzystając z jednowymiarowej tablicy i wskaźników do typów podstawowych, wykorzystując jednoelementowe tablice. W ten sposób otrzymane rezultaty są dalekie od konwencji języka Java.

Common Language

Istnieją dwa zarządzane CLI (.NET) implementacje MPI. Pierwszą z nich jest Pure Mpi.NET – obszerne, obiektowo zorientowane API dające się w łatwy sposób użyć w programowaniu równoległym. Bazuje na Windows Communication Foundation (WCF). SDK wykorzystuje zalety platformy .NET takie jak np. typy generyczne, delegaty, wyniki asynchroniczne czy rzutowanie wyjątków. Inną zarządzana implementacją jest MPI.NET, powstały na bazie licencji BSD, który jest kompatybilny z Mono.

Implementacje sprzętowe

Przeprowadzane są badania implementujące MPI bezpośrednio w sprzęt systemowy – operacje MPI są wykonywane w mikroukładach kości RAM. Ten rodzaj implementacji mógłby być niezależny od języka, systemu operacyjnego czy procesora, jednakże nie mógłby być łatwo aktualizowany. Drugie podejście jest oparte na sprzętowej akceleracji jednej lub wielu części operacji. Może zawierać sprzętowe przetwarzanie kolejek MPI lub używać RDMA do bezpośredniego transferu danych pomiędzy interfejsem sieciowym bez potrzeby interwencji CPU lub jądra.

Adaptacja MPI-2

Standard MPI-1.2 okazał się być uniwersalnym i obsługiwanym przez zdecydowaną większość klastrów obliczeniowych. Jednakże MPI-2.1 okazał się być bardziej limitowanym rozwiązaniem. Główne powody ku temu to:

  1. Podczas gdy MPI 1.2 oparty jest na wymianie wiadomości w stosunkowo prostym oraz statycznym środowisku, pełne MPI-2 zawiera I/O, dynamiczne zarządzanie procesami, a sam rozmiar pośredniczącej implementacji jest znacznie większy;
  2. Znaczna liczba programów MPI-1.2 została wydana do czasu, kiedy to na rynku pojawił się MPI-2. Zagrożenie potencjalnej straty przenośności korzystając z funkcji MPI-2 sprawia, iż programiści rezygnują z pisania w nowszym standardzie;
  3. Wiele aplikacji opartych na MPI-1.2 wykorzystuje jedynie podzbiór funkcji z tego standardu (16-25 funkcji), co porównawczo do MPI-2 jest niewielką ilością.

Zobacz też