PARALELNÉ SPRACOVANIE - cvičenia - zadanie 2 - 2001/2002 - LS
Laboratórium D216, C+PVM+MPI

(Na konci textu sa nachádzajú linky.) Všeobecné podmienky (bodovanie, termíny) zadania nájdete tu.

Úlohu 2A si vyberiete zo skupiny úloh 2A, úloha 2B je tým určená (zo skupiny úloh 2B), s tým istým poradovým číslom. Teda napríklad ak ste si vybrali úlohu 2A2, tak máte automaticky pridelenú úlohu 2B2.
Úloha (implementácia) skupiny 2A je hodnotená max. 9-mi bodmi, úloha skupiny 2B je hodnotená max. 5-mi bodmi. Písomná dokumentácia, v ktorej budú uvedené obe úlohy, je hodnotená max. 5-mi bodmi.

Riešte v PVM aj MPI. Vstup je potrebné zadávať z klávesnice alebo menom súboru, nemá byť napevno zapísaný v zdrojovom kóde. Rozmer úlohy voľte tak, aby výpočet trval rádovo aspoň sekundy. Zmerajte dosiahnutý speed-up (prípadný slow-down treba vedieť zdôvodniť).


2A1. Problém obchodného cestujúceho. (max 9 bodov)

Daná je množina miest a vzdialeností dij medzi každou dvojicou i,j miest. Pre obchodného cestujúceho treba nájsť najkratšiu cestu z mesta napr. A, ktorá prechádza všetkými mestami práve raz a končí v A.

Napr. majme 5 miest A,B,C,D,E so vzdialenosťami podľa obr. Najkratšia trasa obchodného cestujúceho je :

   9     3     4     8     7      
A --- B --- C --- E --- D --- A

- Úlohu riešte na jednom počítači a sieti počítačov (PVM, MPI).
- Určte dobu riešenia úlohy na jednom počítači a sieti počítačov v závislosti od počtu uzlov - miest.
- Uvažujte aj neexistujúce cesty, keď vzdialenosť implementujete napríklad ako MAXINT.
- Rozmer úlohy voľte tak, aby výpočet trval rádovo aspoň sekundy.

 

2A2. Rozmiestnenie dám na šachovnici (max 9 bodov)

Na šachovnici nxn treba rozmiestniť n dám tak, aby sa vzájomne neatakovali. Nájdite všetky riešenia, vypíšte ich počet a jedno z nich.

Napr. šachovnica 5x5:
x    
  x  
    x
 x   
   x 

- Úlohu riešte na jednom počítači a sieti počítačov (PVM, MPI).
- Určte dobu riešenia úlohy na jednom počítači a sieti počítačov v závislosti od počtu dám - čísla n.
- Rozmer úlohy voľte tak, aby výpočet trval rádovo aspoň sekundy.

 

2A3. Najkratšie cesty z daného uzla (max 9 bodov)

Treba nájsť najkratšiu cestu z daného vrcholu V do všetkých ostatných vrcholov ohodnoteného orientovaného grafu.

Napr. Nech V = A
A-B 3 (A-C-B)
A-C 1
A-D 6 (A-C-B-D)
A-E 7 (A-C-B-D-E)

- Úlohu riešte na jednom počítači a sieti počítačov (PVM, MPI).
- Určte dobu riešenia úlohy na jednom počítači a sieti počítačov v závislosti od počtu vrcholov grafu.
- Rozmer úlohy voľte tak, aby výpočet trval rádovo aspoň sekundy.

 


ÚLOHY SKUPINY 2B (max 5 bodov)

Je daný neusporiadaný zoznam A = (a0, a1, a2,..., ai,... an-1). Zoznam treba usporiadať metódou:

2B1

2B2

2B3

shellsort

enumeration sort

odd-even sort

Ak ste si vybrali úlohu 2Ax, tak riešite úlohu 2Bx (x==x, jasné?)
- Úlohu riešte na jednom počítači a sieti počítačov (PVM, MPI).
- Určte dobu riešenia úlohy na jednom počítači a sieti počítačov v závislosti od dĺžky zoznamu A.
- Rozmer úlohy voľte tak, aby výpočet trval rádovo aspoň sekundy.


 

 

 

P O M Ô C K Y :


Ako odmerať čas v UNIXe - pozri sem.
Ladiace nástroje pre PVM, ktoré vám umožnia vidieť do paralelného vykonávania programu: PG_PVM a PG
Tu pozbieram nejaké odrazové linky, vhodné na inšpiráciu pri vypracovávaní zadania:
Obchodný cestujúci:
1
Dámy na šachovnici: 1
Najkratšie cesty: 1
stripped partitioning ku Dijkstrovmu algoritmu (oskenované strany) : 151 [14kB,36kB]   152 [37kB,86kB]


Poznámky:

1 - Obchodný cestujúci:
zlé je riešenie, keď každý worker hľadá cestu (metódou brute force) z iného vrcholu, a tak hľadajú vlastne tú istú -> duplicitná (nezmyselná) práca

2 N-dám:
potrebné je nájsť všetky riešenia, pričom je možné ich rozdeliť na originálne a ekvivalentné (otočenie o 90, 180, 270 stupňov, zrkadlenie horizontálne, vertikálne, diagonálne a antidiagonálne)

3 Najkratšie cesty (Dijkstra):
nezostať len pri 5 vrcholoch

Sort (odd-even): zamyslieť sa nad poradím komunikácia/lokálne triedenie, aby sa zbytočne nečakalo na lokálne dotriedenie, keď sused čaká na údaj a údaj je pritom k dispozícii