(続)複数のスレッドを使って並列にソートする際に必要なスレッド数を計算する
複数のスレッドを使って並列にソートする際に必要なスレッド数を計算する - 計算機と戯れる日々の続き
配線が交わってもいいなら必要なスレッド数は少なくなる。
rubyを使って自動でgraphvizのソース作成しコンパイルするプログラムを作った。
結果は以下。
ソースは以下。
n=6
m=n/2
f=open("a.dot","w")
f.puts <<HEAD
digraph plus {
graph [rankdir=LR]
node [shape=circle]
HEAD
1.upto(n){|y|
f.puts " in#{y} [shape = box]"
f.puts " in#{y}->p1_#{(y.to_f/2).ceil}"
}
1.upto(m-1){|x|
1.upto(m){|y|
f.puts " p#{x}_#{y}->p#{x+1}_#{1>y-1?1:y-1}[label=\"\"]"
f.puts " p#{x}_#{y}->p#{x+1}_#{m<y+1?m:y+1}[label=\"\"]"
}
}
m.upto(m*2-1){|x|
1.upto(m*2-x){|y|
if 1>y-1 then
f.puts " out#{x-m+1} [shape = box]"
f.puts " p#{x}_#{y}->out#{x-m+1}"
else
f.puts " p#{x}_#{y}->p#{x+1}_#{y-1}"
end
if m*2-x<=y then
f.puts " out#{m*3-x} [shape = box]"
f.puts " p#{x}_#{y}->out#{m*3-x}"
else
f.puts " p#{x}_#{y}->p#{x+1}_#{y}"
end
}
}
f.puts "}"
f.close
puts `dot -Tsvg -o a.svg a.dot`
