Løsningsforslag til Øving 3: html versjon kommer senere. Oppgave 1 Fordeling 1: Tid med 1 prosessor: T_{1} = 1. Tid med n prosessorer:

T_{n} = ∑_{i=1}^{n} f_{i} · d_{i} = \frac{∑{n \atop i=1} \frac{1}{i}}{n}

Hastighetsøkningen blir dermed:

\underline{S} = \frac{T_{1}}{T_{n}} = \frac{n}{∑{n \atop i=1} \frac{1}{i}} ≤ \underline{\frac{n}{ln n}}

Fordeling 2: Tid med 1 prosessor: T_{1} = 1. Tid med n prosessorer:

T_{n} = ∑_{i=1}^{n} f_{i} · d_{i} = ∑_{i=1}^{n} \frac{i}{∑_{j=1}^{n} j} \frac{1}{i} = ∑_{i=1}^{n} \frac{1}{∑_{j=1}^{n} j} = \frac{2}{n(n + 1)}

Hastighetsøkningen blir dermed:

\underline{S} = \frac{T_{1}}{T_{n}} = \underline{\frac{n(n + 1)}{2}}

Fordeling 3: Tid med 1 prosessor: T_{1} = 1. Tid med n prosessorer:

T_{n} = ∑_{i=1}^{n} f_{i} · d_{i} = ∑_{i=1}^{n} \frac{n − i + 1}{∑_{j=1}^{n} j} \frac{1}{i} = ∑_{i=1}^{n} \frac{n − i + 1}{i} \frac{2}{n(n + 1)} = \frac{2}{n} ∑_{i=1}^{n} \frac{1}{i} − \frac{1}{n + 1}

Hastighetsøkningen blir dermed:

\underline{S} = \frac{T_{1}}{T_{n}} = \frac{1}{\frac{2}{n} ∑_{i=1}^{n} \frac{1}{i} − \frac{1}{n+1}} ≤ \frac{1}{\frac{2}{n} ln n − \frac{1}{n+1}} ≈ \underline{\frac{n}{2 ln n − 1}}

Plottet under viser hastighetsøkning (Speedup) som funksjon av antall prosessorer.

**kommer snaert**

Oppgave 2

1.

C_{0} = 2 ∗ 1024 + 2 ∗ \frac{1024 ∗ 1025}{2} = \underline{1051648}

2. “Tregeste prosessor” er prosessor #32, siden denne har flest addisjoner pr. I-verdi:

C_{1} = 2 ∗ 32 + 2 ∗ 32 ∗ 992 + 2 ∗ \frac{32 ∗ 33}{2} = 64608

Speedup = \frac{T_{1}}{T_{32}} = \frac{1051648}{64608} ≈ \underline{16.3}

3. For å balansere lasten, deler vi den ytterste løkken opp i 64 deler, slik at hver får 16 iterasjoner. Slik kan prosessor 1 få første og siste gruppe, prosessor 2 få andre og nest siste gruppe og så videre. Vi får dermed den modifiserte koden:

DOALL ℓ = 1, 32
DO 10 I = (ℓ-1) × 16 + 1, ℓ × 16

SUM(I) = 0 DO 20 J = 1, I

20 SUM(I) = SUM(I) + J 10 CONTINUE

DO 30 I = (64 - ℓ) × 16 + 1, (64 - ℓ + 1) × 16 SUM(I) = 0 DO 40 J = 1, I

40 SUM(I) = SUM(I) + J 30 CONTINUE

ENDALL 4. Vi ser bort i fra “overhead” fra kontrol-flyt. Antall sykler som trengs for beregning for en

prosessor ℓ, 1 ≤ ℓ ≤ 32, blir da:

C_{2} = ∑_{i=(ℓ−1)×16+1}^{ℓ×16}(2 × i + 1) + ∑_{i=(64−ℓ)×16+1}^{(64−ℓ+1)×16}(2 × i + 1)
= {[(ℓ − 1) × 16 + 2 + ℓ × 16 + 1] +

[(64 − ℓ) × 16 + 2 + (64 − ℓ + 1) × 16 + 1]} × 16

= 2054 × 16 = 32, 684.

Hastighetsøkningen sammenlignet med en-prosessor tilfellet blir da

Speedup = \frac{1051684}{32864} = 32.