Párhuzamos algoritmusok

Dr. Olajos, Péter

Új Széchenyi Terv logó.

Miskolci Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Kivonat

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Póta József

Dobó István Gimnázium, Eger, középiskolai tanár

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

1. Alapfogalmak
1.1. 1.1. Bevezetés
1.2. 1.2. Párhuzamossági alapfogalmak
1.3. 1.3. Multiprocessors (megosztott memóriájú) architektúra
1.4. 1.4. Multicomputers (üzenet átadó) architektúra
1.5. 1.5. Párhuzamos programozás
2. Multipascal
2.1. 2.1. Bevezetés
2.2. 2.2. A multi-Pascal nyelv
2.2.1. 2.2.1. Bevezetés a Multi-Pascal használatába
2.2.2. 2.2.2. A FORALL utasítás
2.2.3. 2.2.3. A processz granularitása (felbontási finomsága)
2.2.4. 2.2.4. Egymásba ágyazott ciklusok (Nested loops)
2.2.5. 2.2.5. Mátrixok szorzása (Matrix multiplication)
2.2.6. 2.2.6. Megosztott és lokális változók
2.2.7. 2.2.7. Utasításblokkok deklarációval
2.2.8. 2.2.8. A FORALL indexek hatásköre (scope)
2.2.9. 2.2.9. A FORK utasítás
2.2.10. 2.2.10. Processz terminálás
2.2.11. 2.2.11. A JOIN utasítás
2.2.12. 2.2.12. Amdahl törvénye
2.3. 2.3. Mintafeladatok
2.4. 2.4. A multiprocessors architektúra
2.4.1. 2.4.1. Busz orientált rendszerek
2.4.2. 2.4.2. Cache memória
2.4.3. 2.4.3. Többszörös memória modulok
2.4.4. 2.4.4. Processzor-memória kapcsolóhálózatok
2.5. 2.5. Processz kommunikáció
2.5.1. 2.5.1. Processz kommunikációs csatornák
2.5.2. 2.5.2. Csatorna változók
2.5.3. 2.5.3. Pipeline párhuzamosítás
2.5.4. 2.5.4. Fibonacci-sorozat elemeinek meghatározása
2.5.5. 2.5.5. Lineáris egyenletrendszerek megoldása
2.5.6. 2.5.6. Csatornák és struktúrált típusok
2.6. 2.6. Adatmegosztás
2.6.1. 2.6.1. A spinlock
2.6.2. 2.6.2. A contention jelenség osztott adatoknál
2.6.3. 2.6.3. Spinlockok és Channelek összehasonlítása
2.7. 2.7. Szinkronizált párhuzamosság
2.7.1. 2.7.1. Broadcasting és aggregálás
3. PVM
3.1. 3.1. Elosztott rendszerek
3.2. 3.2. A PVM bevezetése
3.2.1. 3.2.1. A PVM rendszer szerkezete
3.2.2. 3.2.2. A PVM konfigurációja
3.2.3. 3.2.3. A PVM elindítása
3.3. 3.3. PVM szolgáltatások C nyelvű interfésze
3.3.1. 3.3.1. Alapvető PVM parancsok
3.3.2. 3.3.2. Kommunikáció
3.3.3. 3.3.3. Hibaüzenetek
3.3.4. 3.3.4. Buffer(de)allokálás
3.3.5. 3.3.5. Adatátvitel (küldés, fogadás)
3.3.6. 3.3.6. Processz-csoportok
3.4. 3.4. Példaprogramok
3.4.1. 3.4.1. Programok futtatása
3.4.2. 3.4.2. Hello
3.4.3. 3.4.3. Forkjoin
3.4.4. 3.4.4. Belső szorzat (Fortran)
3.4.5. 3.4.5. Meghibásodás (failure)
3.4.6. 3.4.6. Mátrixok szorzása (mmult)
3.4.7. 3.4.7. Maximum keresése (maxker)
3.4.8. 3.4.8. Egy dimenziós hővezetési egyenlet
4. MPI
4.1. 4.1. Bevezetés
4.2. 4.2. Történet és Fejlődés
4.2.1. 4.2.1. Miért használjunk MPI-t
4.3. 4.3. Az MPI használata
4.4. 4.4. Környezet menedzsment rutinok
4.4.1. 4.4.1. Parancsok
4.4.2. 4.4.2. Példa: környezet menedzsment rutinok
4.5. 4.5. Pont-pont kommunikációs rutinok
4.5.1. 4.5.1. Pont-pont műveletek típusai
4.5.2. 4.5.2. Pufferelés
4.5.3. 4.5.3. Blokkoló kontra nem-blokkoló
4.5.4. 4.5.4. Sorrend és kiegyenlítettség
4.5.5. 4.5.5. MPI üzenetátadó rutinok argumentumai
4.5.6. 4.5.6. Blokkoló üzenetátadó függvények
4.5.7. 4.5.7. Példa: blokkoló üzenet küldő rutinok
4.5.8. 4.5.8. Nem-blokkoló üzenetátadó rutinok
4.5.9. 4.5.9. Példa: nem-blokkoló üzenet átadó rutinokra
4.6. 4.6. Kollektív kommunikációs rutinok
4.6.1. 4.6.1. Minden vagy semmi
4.6.2. 4.6.2. Rutinok
4.6.3. 4.6.3. Példa: kollektív kommunikációs függvények
4.7. 4.7. Származtatott adattípusok
4.7.1. 4.7.1. Származtatott adattípusok függvényei
4.7.2. 4.7.2. Példák: származtatott adattípusok
4.8. 4.8. Csoport és kommunikátor kezelő rutinok
4.8.1. 4.8.1. Csoportok kontra kommunikátorok
4.9. 4.9. Virtuális topológiák
4.10. 4.10. Példaprogramok
4.10.1. 4.10.1. MPI array (mpi_array.c)
4.10.2. 4.10.2. Hővezetés egyenlete (mpi_heat2D.c)
4.10.3. 4.10.3. Hullámegyenlet (mpi_wave.c)
4.10.4. 4.10.4. Prímgenerálás (mpi_prime.c)
5. JCluster
5.1. 5.1. Bevezetés
5.1.1. 5.1.1. Telepítés, futtatás
5.1.2. 5.1.2. Alkalmazások indítása a Jclusterben
5.2. 5.2. Alkalmazások készítése
5.2.1. 5.2.1. PVM típusú alkalmazások
5.2.2. 5.2.2. MPI típusú alkalmazások
5.2.3. 5.2.3. „Hello World” program
5.3. 5.3. Példaprogramok
5.3.1. 5.3.1. RankSort (Multi-Pascal - Jcluster)
5.3.2. 5.3.2. Mmult (Multi-Pascal - Jcluster)
5.3.3. 5.3.3. Mmult2 (PVM - Jcluster)
Irodalomjegyzék

Az ábrák listája

1.1. Multiprocessors architektúra közös busszal.
1.2. Megosztott memória.
1.3. Multicomputers (üzenet átadó) architektúra.
2.1. Párhuzamos Ranksort algoritmus.
2.2. Processz létrehozása FORALL utasítással.
2.3. Egymásba ágyazott FORALL ciklusok.
2.4. Mátrixszorzás sémája.
2.5. A javított Ranksort program által adott helyes eredmény.
2.6. FORK utasítás hatása
2.7. Busz orientált rendszer.
2.8. Cache memória 1 processzoros gépen.
2.9. Cache memória multiprocessors-os gépen.
2.10. Szeparált modulok.
2.11. Lebegőpontos szorzás egyszerűsített pipeline algoritmusa.
2.12. A termelő-fogyasztó program.