並列プログラムの作り方メモ

「並列プログラムの作り方」を西那須野町図書館経由宇都宮市立図書館より借りました。返す前にメモを残そうと思います。(その後、結局手元に置きたくなって購入しました。)

Rinda2

並列プログラムの作り方

How to write Parallel Programs - A First Course

並列プログラムの作り方 N. Carriero/D.Gelernter 共立出版

読んだことないけど気になる本

おすすめがあったら教えて下さいな。

協調作業のための基本パラダイム

パラダイム

結果並列法 (result parallelism)
手順並列法 (agenda parallelism)
専門家並列法 (specialist parallelism)

プログラミングの方法

メッセージパッシング
ライブデータ構造
分散データ構造

基本データ構造

基本分散データ構造体

ロック、セマフォ

# カウンティングセマフォ
ts.write(['sem']) # n回実行
ts.take(['sem'])

# タスクのバッグ
ts.write(['task', 'task-description'])
ts.take(['task', nil])

Rinda::TupleSpaceにはevalがありません。速度を気にしなければThreadで代用できなくもない。

# eval??
10.times do |n|
  Thread.new(n) { |x| ts.write(['this loop', x]) }
end
10.times do |n|
  ts.take(['this loop', n])
end

名前によってアクセスされる構造体

# [name, value]
ts.read(['name', nil])
# 更新
ts.take(['name', nil])
ts.write(['name', 'new value'])

# bariier-37でバリア同期
ts.write(['barrier-37', n])

name, value = ts.take(['barrier-37', nil])
ts.write(['barrier-37', value - 1])

位置によってアクセスされる構造体。分散配列。

10.times do |n|
  tuple = ts.read(['A', i, n, nil])
  row_band[n] = tuple[3]
end

inストリームとrdストリーム

消費して行く方がinストリーム。rdストリームは読んでも減らない。読む位置をずらすだけ。

ストリーム'strm'はこんなタプル群

['strm', 1, value1]
['strm', 2, value2]
...

最後の要素のインデックスはtail tuple

['strm', 'tail', 14]

'strm'に要素を追加するには…

tuple = ts.take(['strm', 'tail', nil])
index = tuple[2]
ts.write(['strm', 'tail', index+1])
ts.write(['strm', index, 'new element'])

inストリームには先頭(head tuple)も必要

tuple = ts.take(['strm', 'head', nil])
index = tuple[2]
ts.write(['strm', 'head', index+1])
tuple = ts.take(['strm', index, nil])
value = tuple[2]

readストリームにはhead tupleは必要ない

ライブデータ構造体

writeのかわりにeval(はないのでThread.new)を使う。promise, futureとかそんなの?

require 'rinda/tuplespace'

$ts = Rinda::TupleSpace.new

n = 100

$ts.write(['live stream', 0, 1])
(1..n).each do |i|
  Thread.new(i) do |x|
    tuple = $ts.read(['live stream', x-1, nil])
    $ts.write(['live stream', x, tuple[2] * x])
  end
end

p $ts.read(['live stream', n, nil])

詳細をすべてまとめると

結果並列法による素朴な作戦。優雅だけど効率悪いよ

require 'rinda/tuplespace'

$ts = Rinda::TupleSpace.new

def is_prime(n)
  return true if n == 2
  limit = Math.sqrt(n.to_f) + 1
  i = 2
  while (i < limit) 
    tuple = $ts.read(['primes', i, nil])
    return false if tuple[2] && (n % i == 0)
    i += 1
  end
  return true
end

def main(n)
  (2..n).each do |i|
    Thread.new(i) do |x|
      $ts.write(['primes', x, is_prime(x)])
    end
  end

 (2..n).each do |i|
    tuple = $ts.read(['primes', i, nil])
    puts(i) if tuple[2] 
  end
end

str = ARGV.shift || '10'
main(str.to_i)

協調されたプログラム

なんとなくOOPでないコード。かっこわる。

require 'rinda/tuplespace'

class Phil
  def initialize(ts, size)
    @ts = ts
    @size = size
    @status = []
  end

  def periodic
    while true
      sleep(0.5)
      p @status
    end
  end

  def think(i)
    sleep(rand(5))
  end

  def eat(i)
    @status[i] = '|@|'
    sleep(rand(5))
  end

  def phil(left)
    right = (left + 1) % @size
    while true
      @status[left] = '<O>'
      think(left)
      @ts.take(['room ticket'])
      @status[left] = ' o '
      @ts.take(['chopstick', left])
      @status[left] = '|o '
      @ts.take(['chopstick', right])
      @status[left] = '|o|'
      eat(left)
      @status[left] = '|O|'
      @ts.write(['chopstick', left])
      @status[left] = ' O|'
      @ts.write(['chopstick', right])
      @status[left] = ' O '
      @ts.write(['room ticket'])
    end
  end

  def start
    Thread.new { periodic }
    @size.times do |i|
      Thread.new(i) { |x| phil(x) }
    end
    @size.times do |i|
      @ts.write(['chopstick', i])
      @ts.write(['room ticket']) if i < @size-1
    end
  end
end

Phil.new(Rinda::TupleSpace.new, 10).start
gets

感想

基本パラダイムのように整理して考えたことなかったので、勉強になりました。

inしてoutすることでアトミックな操作を実現できるんだなぁ、としみじみ思うのでした。

car, cdr, consを実装しよう！という演習問題もありました。

参考資料

並列プログラムの作り方 N. Carriero/D.Gelernter 共立出版
<URL:http://www.hlla.is.tsukuba.ac.jp/%7eyas/sie/pdsoft-2001/2001-12-06/> - 並列プログラミングスタイル
Rinda2