第4章 練習問題 3-19
3 並列フィボナッチ
{Fib 30}同士を比較した。単位はミリ秒。並列のほうが遅い。まあ、シングルプロセッサですし。
local S = {Property.get 'time.total'} in
{PFib 30 _}
{Show '---'}
{Show {Property.get 'time.total'}-S}
end
- 直列 - 410
- 並列 - 4980
また、Fib(n)が生成するスレッドの数をT(n)とすると、
T(1) = 1 T(2) = 2 T(n) = 1+T(n-1)+T(n-2)
ここで、S(n)=T(n)+1とすると、
T(n) = 1+T(n-1)+T(n-2) => T(n)+1 = (T(n-1)+1)+(T(n-2)+1) => S(n) = S(n-1) + S(n-2)
するとS(n)はフィボナッチ数になるので、
T(n) = Fib(n)-1
となる。Fib(n)はO(2^n)であるので、生成されるスレッドはO(2^n)となる。
id:selvaggioに教えてもらった。
4 順序一定並列性
declare A B C D in
thread D=C+1 end % (1)
thread C=B+1 end % (2)
thread A=1 end % (3)
thread B=A+1 end % (4)
{Browse D}
- スレッドの起動は上から順番に行なわれる: 1->2->3->4
- 加算はデータフロー変数によって制限される: 3->4->2->1
- 結果は4
- 直列の場合は、上から順番に。結果は4
5 Wait操作
- ifは条件部が決定状態ない場合は、決定するまで待機する
- A==Bは、AとBの等・不等が分かるまでブロックする
そのため、この操作はXが決定されるまでブロックするため、Waitとして用いることができる。
6 スレッドのスケジューリング
fun {Skip1 Xs}
case Xs of X|Xr then
if {IsDet Xr} then {Skip1 Xr} else Xs end
[] nil then nil end
end
fun {Sum Xs A}
case {Skip1 Xs} of
X|Xr then {Sum Xr A+X}
[] nil then A end
endGeneraterの走るスレッドをG、Sumの走るスレッドをSと省略する。
- G: リストを1|2|3|Xに束縛する
- S: 1|2|3をSkipする。Xを待つ
- G: X=4|5|6|Y
- S: A=0+4。そして5|6をSkipし、Yを待つ
- G: Y=7|8|9|Z
- S: A=4+7。そして、8|9をSkipし、Zを待つ
を繰り返すため、合計が本来よりも少なくなる。
7 高階プログラミンングを使うプログラムされたトリガ
fun {DGenerate N}
fun {$} N#{DGenerate N+1} end
end
fun {DSum F A Limit}
if Limit > 0 then
X#G = {F}
in
{DSum G A+X Limit-1}
else
A
end
end
local F S in
thread F = {DGenerate 0} end
thread S = {DSum F 0 150000} end
{Browse S}
end
8 並列状況におけるデータフロー的振る舞い
(a)
ブロックする。Aが未束縛のため、caseで待機状態に入るため。
(b)
表示される可能性があるのは、以下の2通り。
- _: Filterが一度も実行される前にShowが実行された場合。
- 5|_: Filterが一度以上、実行された後にShowが実行された場合。
また、変数は常に一通りの値に束縛されるため非決定性を持たない。
(c)
少なくとも、自分の環境では5|_が表示された。_が表示されないとは言いきれない。
Delay中に他のスレッドが走っている。
(d)
"[5 6 4]"が表示される。A=6によりFilter内のcaseが待機状態から脱けるため。
9 ディジタル論理シミュレーション
nビット数を以下のように表現することにする。
[x0 x1 x2 ..] % e.g. 0x001 => [1 0 0]
するとnビットの加算器は以下のようになる。
fun {NAdder Xs Ys}
C
in
{FullAdder Xs Ys 0|C C}
end
% 0b101 + 0b001 = 0b110
{Browse {NAdder 1|0|1|_ 1|0|0|_}}
% 0b001 + 0b001 = 0b010
{Browse {NAdder 1|0|0|_ 1|0|0|_}}
% 0b100 + 0b100 = 0b000
{Browse {NAdder 0|0|1|_ 0|0|1|_}}
10 遅延の基礎
次のような呼び出すたびに、値の代る式を書くことができるので。(宣言的でない場合、問題が生じるので)
fun lazy {LazyTime} {Time.time} end
11 遅延性と並列性
振る舞いの説明
- (X+Y)+Zが実行される場合は、まずXとYが必要とされる。なので、x,yが即座に表示される。
- XとYが束縛されるのは6秒後なので、その後Zが必要とされる。なので、zが6秒後に表示される
- Zが束縛されるのがさらに9秒後なので、15が表示される
X+(Y+Z)の場合
- 即座にy,zが表示される
- 9秒後にxが表示される
- 12秒後に6が表示される
theard X+Y end + Zの場合
- 即座にx,y,zが表示される
- 9秒後に6が表示される
速いプログラム
thread X+Y end +Zのように全てthreadで包むと、すべての変数が同時に必要となる。なので、これが最速となる。
(thdead ... (thread (thread (thread I1+I2 end) + I3 end) + I4 end) + ... ) + In
12 遅延性と漸増性
並列を使うプログラムは、Generateが先行して入力ストリームを生成する。
一方、遅延を使うプログラムは、Sumが必要として部分だけをGenerateが生成する。
また遅延と並列を一緒に使っても、主に遅延によって制御されているので大差はない。
fun lazy {Generate N}
N|{Generate N+1}
end
fun {Sum Xs A Limit}
if Limit>0 then
case Xs of X|Xr then
{Sum Xr A+X Limit-1}
end
else
A
end
end
local Xs S in
thread Xs={Generate 0} end
thread S={Sum Xs 0 60} end
{Browse S}
end
13 遅延性と一枚岩関数
振る舞いは同じ。Revでリストを最後までたどるので、遅延の意味はない。
遅延になった分効率が悪いはずなので、Reverse2のほうが効率が悪い。
14 遅延性と反復性
ByNeedを使って書き直すと次のようになる。反復的に見えるが、違うのかなぁ?
proc {LAppend As Bs ?R}
{ByNeed fun {$}
case As
of nil then Bs
[] A|Ar then
X Xr
R = X|Xr
in
X=A
{LAppend Ar Bs R}
end
end}
end
15 遅延性の性能
% 性急版
fun {Generate N Limit}
if N =< Limit then
N|{Generate N+1 Limit}
else
nil
end
end
fun {Sum Xs}
case Xs
of X|Xr then X+{Sum Xr}
[] nil then 0 end
end
% 遅延版
fun lazy {Add X Y} X+Y end
fun lazy {LSum Xs}
case Xs
of X|Xr then {Add X {LSum Xr}}
[] nil then 0 end
end
fun lazy {LGenerate N Limit}
if N =< Limit then
N|{LGenerate N+1 Limit}
else
nil
end
end
% 速度の測定
fun {Bench F}
Now = {Property.get 'time.total'}
in
{F}
{Property.get 'time.total'}-Now
end
{Browse {Bench proc{$} {Browse {Sum {Generate 0 100000}}} end}}
{Browse {Bench proc {$} {Browse {LSum {LGenerate 0 100000}}+0} end}}
16 by-need実行
待機状態に入らず、値を要求する処理が思いつかなかった。そこで、別スレッドで待機するようにした。
proc {Need X}
thread {Wait X} end
end
17 ハミング問題
% 素数生成のための関数群
fun lazy {LFilter L F}
case L
of nil then nil
[] X|L2 then
if {F X} then X|{LFilter L2 F} else {LFilter L2 F} end
end
end
fun lazy {Generate N}
N|{Generate N+1}
end
fun lazy {Sieve Xs}
case Xs
of X|Xr then X|{Sieve {LFilter Xs fun {$ Y} Y mod X \= 0 end}} end
end
% 4.5.6より。元の問題で使った関数群
fun lazy {Times N Xs}
case Xs of X|Xr then N*X|{Times N Xr} end
end
fun lazy {Merge Xs Ys}
case Xs#Ys of (X|Xr)#(Y|Yr) then
if X<Y then X|{Merge Xr Ys}
elseif X>Y then Y|{Merge Xs Yr}
else X|{Merge Xr Yr}
end
end
end
% 本題
fun {Hamming K}
Prime = {List.take {Sieve {Generate 2}} K}
H
X Xr
in
X|Xr = {Map Prime fun {$ P} {Times P H} end}
H = 1|{FoldL Xr Merge X}
H
end
% テスト
proc {Touch N H}
if N>0 then {Touch N-1 H.2} else skip end
end
H = {Hamming 5}
{Touch 20 H}
{Browse H}
18 並列性と例外
static analysis errorによりコンパイルできない:D。というのは冗談として、以下のように番号を振る。
local U=1 V=2 in
try
thread
try
U=V % (1)
finally
{Browse bing} %(2)
end
end
finally
{Browse bong} %(3)
end
endそして、1と2の間には前後関係が存在しているので、
- bong->例外発生->bing->例外を再raise
- 例外発生->bong->bing->例外を再raise
- 例外発生->bing->bong->例外を再raise
- 例外発生->bing->例外を再raise->bong
という順序が存在する。
19 宣言的並列性の限界
Megreは3つのストリームを一つづつ読むという風に順番が決定的であった。しかしサーバの場合は先に到達したものから読むという非決定性が必要となるため宣言的モデルでは実現できない。
