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

Ú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í d_ij 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.

- Ú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:

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 :

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