2. Bestem for hvilken meldingstørrelse som MPI_Send bytter
fra å buffre meldingen til å vente på at den kommer frem.
3. Merge sortering foregår ved at man først sorterer to og to elementer. Deretter fletter man sammen to og to sorterte lister av lengde 2 til en sortert liste av lengde 4. Dette fortsetter man med til alle tallene er sortert.
Eks:
Steg 0. 4 2 1 5 8 7 3 9
Steg 1. (2 4)(1 5)(7 8)(3 9)
Steg 2. (1 2 4 5)(3 7 8 9)
Steg 3. (1 2 3 4 5 7 8 9)
Kjøretiden er O(nlogn).
Lag et MPI program som foretar en parallell merge sort av n tall
på p prosessorer. I starten har hver prosessor n/p
dataelementer, i hvert steg samles to sorterte lister på en prosessor
som fletter de sammen. Sluttresultatet skal være på prosessor
0. For enkelhets skyld kan du la både n/p og p være
potenser av 2.
Analyser kjøretiden til programmet og sammenlign med praktiske
eksperimenter. Hvordan endrer kjøretiden seg når du holder
n fast og øker p? Beregn speedup.
Hint:
Dersom programmet kjører for fort til at du kan ta tiden på
det så kjør det flere ganger i
en løkke.
subrutine kallet
call random_number(tab(1:n))
i Fortran90 lager n tilfeldige tall i tabellen tab. Merk at tab må være av type real.