45214 Datamaskinarkitektur - Øvinger 1995

Øving 3

Oppgave 1

Hastighetsøkningen ved å bruke n prosessorer i stedet for 1 for å løse et beregningsproblem, er gitt ved:


      S = T(1) / T(n) .

hvor T(n) er gjennomsnittstiden for å løse et problem på en n-prosessor maskin. T(n) er gitt ved:


      T(n) = sum(i = 1..n, f(i) x d(i))

hvor f(i) er sannsynligheten for at problemet løses ved å fordele arbeidet likt på i prosessorer, og


     d(i) = 1 / i

er gjennomsnittlig arbeid pr. prosessor ved bruk av i prosessorer på denne måten.

Utfør beregningen når f(i) er:


     f(i) = 1 / n 
og
     f(i) = i / sum(j = 1..n, j),   i = 1..n 

og når den er

     f(i) = (n - i + 1) / sum(j = 1..n, j), i = 1..n

I det første tilfellet er det jevn fordeling av arbeid på prosessorene. I det andre tilfellet er det antatt størst sannsynlighet for at oppgaven blir tilordnet et større antall prosessorer, mens det i det tredje tilfellet antas størst sannsynlighet for at oppgaven kjøres på et mindre antall prosessorer.

Plott estimatene for hastighetsøkningen.

Hint: Bruk gnuplot til å plotte disse kurvene. Programmet er enkelt å bruke. Det er lagt ut et hjelpe-eksempel på filen ~dam/45214/ovinger/gnuplot. Se også manualsidene på Sun og Info-sidene i Emacs for mer informasjon.

Oppgave 2

Det følgende FORTRAN-programmet skal utføres på en en-prosessor maskin. En parallell versjon skal utføres på en delt-minne (Eng: shared-memory) multiprosessor.


     L1:    DO 10 I = 1, 1024
     L2:       SUM(I) = 0
     L3:       DO 20 J = 1, I
     L4: 20       SUM(I) = SUM(I) + J
     L5: 10 CONTINUE

Anta at setningene L2 og L4 tar to maskin-sykler hver. En maskin-sykel inkluderer både CPU-aktivitet og minne-aktivitet. Se bort i fra ``overhead'' p.g.a. løkkekontroll (setningene L1, L3 og L5) og andre faktorer, som f.eks. system ``overhead'' og ressurs-konflikter.

a)

Hva er den totale utførelsestiden til programmet på en en-prosessor maskin?

b)

Fordel I-løkken blant 32 prosessorer med ``prescheduling'' på denne måten:

Prosessor 1 utfører de første 32 instruksjonene (I = 1 til 32),

Prosessor 2 utfører de neste 32 iterasjonene (I = 33 til 64),

osv.

Hva er utførelsestiden og hastighetsøkningen sammenlignet med oppgaven i a)? (Merk at arbeidsmengden p.g.a. av J-løkken ikke er balansert på de forskjellige prosessorene).

c)

Modifiser programmet slik at lasten balanseres over alle de 32 prosessorene. Med en balansert last mener vi at alle prosessorene skal utføre et likt antall addisjoner med hensyn til begge løkker.

d)

Hva er den korteste utførelsestiden vi kan få med programmet som ble lagd i oppgave c)? Hva blir hastighetsøkningen sammenlignet med en-prosessor tilfellet?

Pauline Haddow(pauline@idt.unit.no)

Last modified: Mon Oct 16 16:41:27 1995