-
Notifications
You must be signed in to change notification settings - Fork 1
/
afl_4.tex
126 lines (103 loc) · 3.37 KB
/
afl_4.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
\documentclass[10pt,a4paper,danish]{article}
%% Indlæs ofte brugte pakker
\usepackage{amssymb}
\usepackage[danish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{todonotes}
\usepackage{algorithmic}
\usepackage{amsmath}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\rhead{\today}
\rfoot{\thepage}
\setlength{\parindent}{0pt}
% Opsæt indlæsning af filer
\lstset{
language=Python,
extendedchars=\true,
inputencoding=utf8,
linewidth=\textwidth, basicstyle=\small,
numbers=left, numberstyle=\footnotesize,
tabsize=2, showstringspaces=false,
breaklines=true, breakatwhitespace=false,
}
%% Titel og forfatter
\title{Aflevering 4 \\Algoritmer og datastrukturer\\Forår/Sommer 2011}
\author{Naja Mottelson (vsj465)\\Søren Pilgård (vpb984)}
%% Start dokumentet
\begin{document}
%% Vis titel
\maketitle
\newpage
%% Vis indholdsfortegnelse
\tableofcontents
\newpage
%% Rapport, baby!
\section{a}
\subsection{Algoritme}
Lader vi i og j være indicer til hhv. det første og sidste element i de arrays vi
arbejder med, kan vi skrive en multitrådet algoritme til at lægge arrays sammen således:
\\
\begin{algorithmic}[1]
\STATE SUM-ARRAYS$(A, B, C, i, j)$
\IF {$i == j$}
\STATE $ C[i] = A[i] + C[i]$
\ELSE
\STATE mid = $\lfloor \frac{(i + j)} 2 \rfloor$
\STATE spawn SUM-ARRAYS$(A, B, C, i, mid)$
\STATE SUM-ARRAYS$(A, B, C, mid + 1, j)$
\STATE sync
\ENDIF
\end{algorithmic}
\subsection{Paralellisme}
Work for denne algoritme kan beskrives ved rekursionsligningen
$$
T_1(n) =
\begin{cases}
\Theta(1) & \text{hvis } i = j \\
2T_1(\frac{n} {2}) + \Theta(1)& \text{hvis } i \neq j
\end{cases}
$$
\\
Vi ser at det første led bidrager med $\Theta(\text{lg }n)$ arbejde, hvilket
dominerer det konstante led fra basistilældet. Altså har vi $T_1(n) =\Theta(\text{lg} n)$.
Eftersom dybden af rekursive kald er logaritmisk, og de rekursive kald igen dominerer
den konstante faktor fra basistilfældet får vi at $T_\infty(n) = \Theta(\text{lg } n)$.
Parallelismen for SUM-ARRAYS ($\frac{T_1} {T_\infty}$) bliver således $\Theta(\frac{\text{lg n}} {\text{lg n}}) = \Theta(1)$.
\section{b}
Når vi sætter $grain-size$ til $1$ vil ADD-SUBARRAY udføre konstant arbejde eftersom
vi altid vil have at $j = i$. Work for SUM-ARRAYS' vil derfor blive
$$T_1(n) = \Theta(n) \cdot \Theta(1) = \Theta(n)$$
Det samme gælder ved udregningen af span, som således kan skrives som
$$T_\infty(n) = \Theta(n) + \Theta(1) = \Theta(n)$$
Vi får derved parallelismen
$$
\begin{aligned}
\frac{T_1} {T_\infty} &= \Theta(\frac{n} {n})\\
&= \Theta(1)
\end{aligned}
$$
\section{c}
Vi ser at for-løkken i SUM-ARRAYS' bidrager med $\Theta(r)$ arbejde og
at hjælperoutinen ADD-SUBARRAY bidrager med $\Theta(g)$ som $grain-size$ vokser.
Lader vi $g$ være $grain-size$ ser vi at en formel for SUM-ARRAYS' i termer af $n$ og $g$
kan skrives på formen $T_\infty = \frac{n} {g} + g$ (her ignorerer vi afgrænsningerne i den
oprindelige kvotient). For at finde den optimale værdi for $grain-size$ differentierer vi
$T_\infty$ med hensyn til $g$ og får
$$T_\infty'(g) = 1 - (\frac{n} {g^2}) $$
De optimale værdier for $g$ må da være nulpunkterne for $T_\infty'$:
$$
\begin{aligned}
1 - (\frac{n} {g^2}) &= 0 \\
1 &= (\frac{n} {g^2}) \\
n &= g^2 \\
g &= \sqrt[+-]{n}
\end{aligned}
$$
\end{document}