組合せスケジューリング(1)

多体問題で、GPUで計算するとどうしても質点同士の相互作用を2回計算をしてしまっていた。例えば、質点0と質点1について考えると、質点0に及ぼされる相互作用を計算するときに質点1から作用を計算し、質点1に及ぼされる相互作用を計算するときに質点0から作用を計算するが、それは方向が逆なだけで同じだから、計算がダブっていることになる。しかし、GPUではブロックやスレッドが別だと同じ配列の要素に代入できないので、どうしても計算がダブることになる。
しかし、スレッドが同じなら計算をダブらせなくても済む。ブロックは1つにして、スレッドは256個がいいらしいので、そうする。そして、例えば、質点0〜7と質点8〜15の64個の相互作用を計算する。このように8つずつの質点をグループにして、グループとグループの相互作用の計算を一度に256のペアについて行う。それを255回行って、全てのペアを網羅する。それと、そのグループ内の相互作用を計算して、1回の計算が完了する。これで計算のムダは本当に速くなる


ここで、そのグループのペアをうまく組み合わせることが問題になる。0〜511を組合わせて、511回ですべての組合せができるようにしたい。
とりあえず、511回より多くかかってもいいから、ペアのスケジューリングを考える。最も簡単なのは次のようなものだろう。4つのグループがあったとして、そのペアをすべて列挙すると、


[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]

となるので、この順番にパッキングしていく。まず、重ならないようにすると、


[0, 1]
[0, 2]
[0, 3]

となる。次の[1, 2]は、上から見ていって重ならないところに入れると、上2つはダメだから、


[0, 1]
[0, 2]
[0, 3], [1, 2]

となる。というようにやっていくと、結局、


[0, 1], [2, 3]
[0, 2], [1, 3]
[0, 3], [1, 2]

とうまくスケジューリングできた。
色々やっていくと、どうもグループ数が2のべきだとうまくいくようだ。よく見ると規則性がある。



class pair_set:
def __init__(self, n):
self.n = n
self.pair_table = [ ]
self.check_table = [ ]

def calc(self):
for p in self.pair_generator():
self.put_pair(p)

def put_pair(self, p):
for i in range(len(self.check_table)):
if self.is_empty(i, p):
self.set_pair(i, p)
return
self.append()
self.set_pair(len(self.pair_table) - 1, p)

def pair_generator(self):
for i in range(self.n - 1):
for j in range(i + 1, self.n):
yield [ i, j ]

def is_empty(self, i, p):
turn = self.check_table[i]
return not turn[p[0]] and not turn[p[1]]

def set_pair(self, i, p):
self.pair_table[i].append(p)
self.check_table[i][p[0]] = True
self.check_table[i][p[1]] = True

def append(self):
self.pair_table.append([])
self.check_table.append([ False for i in range(self.n)])

def __str__(self):
buff = ""
for pairs in self.pair_table:
for pair in pairs:
buff += pair.__str__()
buff += "\n"
return buff

ps = pair_set(16)
ps.calc()
print ps