Programowanie równoległe i rozproszone
Andrzej Karbowski, Ewa Niewiadomska-Szynkiewicz (red.)
rok wydania: 2009
format: B5
oprawa: miękka
stron: 426
wydawnictwo: Oficyna Wydawnicza Politechniki Warszawskiej
Tematem książki „Programowanie równoległe i rozproszone” jest wykorzystanie maszyn wieloprocesorowych oraz sieci maszyn (klastrów lub gridów) do rozwiązywania złożonych zadań obliczeniowych. Praca jest obszerną monografią zawierającą trzy zasadnicze wątki dotyczące: wstępnych definicji i pojęć, narzędzi programistycznych oraz algorytmów i metod obliczeniowych. Omawiane są nowe architektury sprzętowe do realizacji obliczeń równoległych i rozproszonych, miary efektywności obliczeń równoległych a także podstawowe paradygmaty programowania równoległego. Dwa najdłuższe rozdziały zawierają szczegółowe opisy mechanizmów i narzędzi programowania współbieżnego oraz narzędzi służących do realizacji zdalnych wywołań (architektura klient-serwer). Prezentowane są mechanizmy i techniki programowania z wykorzystaniem narzędzi z różnych klas. Ostatni rozdział zawiera opis wybranych algorytmów z dziedziny algebry liniowej i nieliniowej, w tym także optymalizacji, wraz ze sposobami ich dekompozycji, równoległej implementacji oraz analizą poprawności.
Książka jest przeznaczona dla pracowników naukowych różnych specjalności rozwiązujących duże zadania obliczeniowe, pracowników firm zajmujących się budową złożonych systemów informatycznych, studentów studiów magisterskich i doktoranckich na kierunkach informatycznych, zarówno politechnik jak i uniwersytetów, a także osób zainteresowanych zdobyciem wiedzy w dziedzinie mechanizmów zrównoleglania obliczeń, nowoczesnych metod numerycznych oraz ich realizacji na maszynach wielordzeniowych, wieloprocesorowych i w sieciach komputerów. Praca jest przewodnikiem wystarczającym do samodzielnego pisania aplikacji współbieżnych, równoległych i rozproszonych działających w omawianych środowiskach sprzętowych. Omawiane w książce programy są do pobrania ze strony WWW.
SPIS TREŚCI:
Przedmowa 9
1. Wprowadzenie 13
1.1. Pojęcia podstawowe 13
1.2. Przykłady zastosowania obliczeń równoległych 15
2. Miary efektywności zrównoleglenia 19
2.1. Współczynnik przyśpieszenia oraz wydajność. Prawo Amdahla oraz Gustafsona-Barsisa 19
2.2. Sprawność oraz skalowalność 23
3. Architektury maszyn równoległych 25
3.1. Najważniejsze trendy na rynku procesorów 25
3.2. Klasyfikacja maszyn równoległych 28
3.3. Maszyny typu SISD 30
3.4. Maszyny typu SIMD 31
3.4.1. Maszyny SM-SIMD 31
3.4.2. Maszyny DM-SIMD 32
3.5. Maszyny MIMD 33
3.5.1. Maszyny SM-MIMD 33
3.5.2. Maszyny DM-MIMD 37
3.5.3. Klastry i gridy 45
3.5.3.1. Klastry 45
3.5.3.2. Gridy 46
4. Wprowadzenie do programowania równoległego 51
4.1. Podstawowe narzędzia służące do zrównoleglania 51
4.2. Elementy programowania wektorowego oraz wykorzystującego karty graficzne (GPGPU) 53
4.2.1. Obliczenia z wykorzystaniem wektorowych jednostek wykonawczych 53
4.2.2. Obliczenia z wykorzystaniem kart graficznych 57
4.2.2.1. Wprowadzenie 57
4.2.2.2. Przykładowy program realizujący obliczenia z wykorzystaniem GPU 59
4.3. Elementy programowania równoległego specyficzne dla maszyn z pamięcią wspólną 60
4.3.1. Procesy i wątki 60
4.3.2. Mechanizmy komunikacji i synchronizacji między zadaniami 63
4.3.2.1. Wspólna pamięć 63
4.3.2.2. Zamek 64
4.3.2.3. Semafor 67
4.3.2.4. Bariera 68
4.3.2.5. Zmienne warunków i monitory 69
4.4. Elementy programowania równoległego specyficzne dla maszyn z pamięcią lokalną 70
4.4.1. Mechanizmy standardowe oparte na przesyłaniu komunikatów 70
4.4.2. Mechanizmy wirtualnej pamięci wspólnej 71
4.5. Elementy programowania równoległego specyficzne dla sieci komputerowych 73
4.5.1. Wstęp 73
4.5.2. Sieci lokalne 74
4.5.3. Sieć globalna 75
4.6. Podstawowe modele programów równoległych 76
5. Programowanie równoległe na komputerach wieloprocesorowych (wielordzeniowych) z pamięcią wspólną 78
5.1. Identyfikatory, uchwyty i nazwy obiektów 79
5.2. Funkcje systemowe systemu UNIX 83
5.2.1. Procesy 83
5.2.2. Potoki anonimowe – najprostsze narzędzie do komunikacji i synchronizacji 87
5.2.3. Potoki nazwane 90
5.2.4. Mechanizmy komunikacji międzyprocesowej (IPC) Systemu V 92
5.2.4.1. Pamięć wspólna 92
5.2.4.2. Semafory w systemie UNIX 94
5.2.5. Kolejki komunikatów 96
5.3. Funkcje systemowe systemu MS Windows 98
5.3.1. Procesy 99
5.3.2. Potoki anonimowe 103
5.3.3. Potoki nazwane 105
5.3.4. Wątki 113
5.3.4.1. Lokalne zmienne wątku 115
5.3.4.2. Obiekt „sekcja krytyczna” 116
5.3.5. Pamięć wspólna 116
5.3.6. Kolejki komunikatów 118
5.3.7. Semafory w systemie Windows 119
5.3.7.1. Zamek 121
5.3.7.2. Obiekt „zdarzenie" 122
5.3.7.3. Oczekiwanie na wiele obiektów 124
5.4. Biblioteka Pthreads 126
5.4.1. Wątki 129
5.4.2. Zmienne specyficzne, czyli prywatne zmienne wątków w pamięci globalnej 133
5.4.3. Wątki a sygnały 136
5.4.4. Zamek biblioteki Pthreads 137
5.4.5. Zamek czytelnicy–pisarze 142
5.4.6. Bariera 142
5.4.7. Zmienna warunku 144
5.4.7.1. Programy przykładowe 146
5.5. Wątki w języku Java 148
5.5.1. Synchronizacja wątków 151
5.6. Wątki w języku C# 157
5.6.1. Synchronizacja wątków 159
5.7. Dyrektywy zrównoleglające OpenMP 163
5.7.1. Zmienne środowiskowe 164
5.7.2. Dyrektywy środowiska OpenMP 165
5.7.3. Funkcje biblioteczne 175
5.7.4. Przykładowe programy wykorzystujące dyrektywy OpenMP 177
6. Programowanie równoległe na komputerach wieloprocesorowych z pamięcią lokalną oraz w sieciach komputerowych oparte na przesyłaniu komunikatów 186
6.1. Wprowadzenie 186
6.2. Mechanizm gniazdek 187
6.2.1. Przesyłanie danych bez tworzenia połączenia 189
6.2.2. Ograniczenia komunikacji bezpołączeniowej 191
6.2.3. Komunikacja przy użyciu połączeń 191
6.2.4. Komunikacja synchroniczna i asynchroniczna 193
6.2.5. Obsługa wielu gniazdek jednocześnie 193
6.2.5.1. Przepytywanie 194
6.2.5.2. Funkcja select 195
6.2.5.3. Użycie wielu procesów lub wątków 196
6.2.5.4. Komunikacja asynchroniczna 196
6.2.6. Wady biblioteki gniazdek 197
6.3. Interfejs MPI 198
6.3.1. Rozpoczęcie i zakończenie korzystania z MPI w programie 199
6.3.2. Komunikatory i grupy procesów 199
6.3.2.1. Operacje na grupach 200
6.3.2.2. Operacje na komunikatorach 202
6.3.2.3. Komunikatory zewnętrzne 203
6.3.3. Przesyłanie komunikatów 205
6.3.3.1. Funkcje komunikacji nieblokującej 208
6.3.3.2. Typy pochodne i pakowanie danych 211
6.3.3.3. Ocena sposobów komunikacji – rekomendacje 214
6.3.4. Komunikacja kolektywna 215
6.3.4.1. Synchronizacja za pomocą bariery 216
6.3.4.2. Wysyłanie komunikatu do grupy procesów 216
6.3.4.3. Rozsyłanie danych między członków grupy procesów 216
6.3.4.4. Zbieranie danych od grupy procesów 217
6.3.4.5. Komunikacja „wszyscy do wszystkich” 219
6.3.4.6. Operacje redukcji 219
6.3.5. Wirtualne topologie 221
6.3.6. Programy przykładowe 224
6.3.7. Podsumowanie 233
7. Programowanie rozproszone w środowiskach sieciowych oparte na wywołaniach zdalnych procedur 234
7.1. Wprowadzenie 234
7.2. Architektura klient–serwer 234
7.3. RPC 242
7.4. RMI (Java) 262
7.5. CORBA 282
7.6. Usługi sieciowe (Web Services) 313
7.6.1. Współdziałanie 315
7.6.2. Format WSDL 315
7.6.3. Protokół SOAP 320
7.6.4. Standard UDDI 324
7.6.5. Architektura REST 326
7.6.6. Zalety, wady i perspektywy 327
7.7. Narzędzia RPC w środowisku .NET 328
7.7.1. Serwer 329
7.7.2. Klient 332
7.7.3. Wybór metody przesyłania danych 335
7.7.4. Obiekty Singleton i dzierżawy 336
7.7.5. Obiekty aktywowane przez klienta 339
7.8. .NET Remoting a Web Services 340
7.9. Porównanie mechanizmów 341
8. Mechanizmy wirtualnej pamięci wspólnej 347
8.1. Co-Array Fortran 347
8.1.1. Kotablice i kowspółrzędne 348
8.1.2. Identyfikacja obrazów 349
8.1.3. Synchronizacja danych oraz sterowania w obrazach 350
8.1.4. Funkcje kolektywne 352
8.2. UPC – Unified Parallel C 353
8.2.1. Kompilacja i uruchamianie aplikacji 354
8.2.2. Deklaracja tablic dzielonych, ich partycja i alokacja 355
8.2.3. Zrównoleglanie pętli 357
8.2.4. Tryby kontroli pamięci 357
8.2.5. Synchronizacja 358
8.2.6. Wskaźniki 361
8.2.7. Kolektywne operacje wymiany danych 362
8.2.8. Kolektywne operacje obliczeniowe 364
8.2.9. Przykład sesji w klastrze 365
8.3. Dyrektywy zrównoleglające OpenMP w klastrach 368
8.4. Linda 369
9. Przykłady równoległych metod obliczeniowych 373
9.1. Równoległe algorytmy synchroniczne 373
9.1.1. Rodzaje zrównoleglania 373
9.1.2. Rozwiązywanie układów równań liniowych 374
9.1.2.1. Zrównoleglenie kodu – algorytm eliminacji Gaussa 374
9.1.2.2. Zrównoleglenie metody – algorytm eliminacji Gaussa-Jordana 375
9.1.2.3. Zrównoleglenie zadania – metoda blokowa 376
9.1.3. Rozwiązywanie układów równań nieliniowych 377
9.1.4. Zadania optymalizacji 378
9.2. Algorytmy asynchroniczne 379
9.2.1. Algorytmy całkowicie asynchroniczne 380
9.2.1.1. Odwzorowania zwężające w normie maksimum 383
9.2.1.2. Odwzorowania zachowujące porządek (izotoniczne) 389
9.2.2. Obliczenia częściowo asynchroniczne 391
9.2.2.1. Rozwiązywanie układów równań liniowych 392
9.2.2.2. Algorytm PageRank szeregowania linków w wyszukiwarce 393
Dodatek. Język Fortran 395
D.1. Wprowadzenie 395
D.2. Podstawowe elementy języka Fortran 90 i 95 396
D.2.1. Standardowe typy danych 397
D.2.2. Typy danych definiowane przez użytkownika 399
D.2.3. Dynamiczne struktury danych 400
D.2.4. Instrukcje sterujące 401
D.2.5. Podprogramy i moduły 405
D.3. Podstawowe elementy języka Fortran 2003 407
D.3.1. Obsługa danych i programowanie zorientowane obiektowo 408
D.3.2. Współdziałanie z językiem C 412
D.3.3. Wsparcie standardu IEEE dotyczącego liczb zmiennoprzecinkowych 417
Bibliografia 419
Skorowidz 422
