Monday, September 28, 2009

トルコの口笛族

今朝NHKラジオで聞いた話。トルコのある地域では小鳥がさえずるような口笛で会話がおこなわれる。数字も伝えられる。200メートル離れても会話できる。山が多い地域なのだろう。遠くに離れた人同士で話すのに使われているとのこと。でも最近の若者は携帯を使ってしまうので口笛会話がすたれつつある。

番組でも地名が紹介されていたが、覚えられなかった。という話をtwitterに書いていたら、調べてくれた人がいた。これによると、Kuskoyという場所のようだ。クシュコイと読むらしい。鳥の村という意味だそうだ。

番組で紹介されていた会話では、「今年のヘーゼルナッツの相場はどうかね」「まだ安いから倉にしまっておいた方がいいよ」というような例が紹介されていたが、私には鳥がないているだけのように聞こえた。

Saturday, September 12, 2009

Page replacement. 2Q

遠方にあるディスクに対して、SSDを使ったキャッシュを作れないかなと思っていた。

device-mapperを使ったdm-cache
http://users.cis.fiu.edu/~zhaom/dmcache/index.html
なるものがあり、私が欲しいのもこんな感じのものだ。
メインラインにマージはされていないが、このURLを見ると
比較的最近のカーネルに追従しているようだし、LKMLへパッチも送られた形跡がある。

欲しいものには近いのだが、SSDを使う場合、IOサイズを気にする必要がある。今時のRAIDに比べると
SSDのシーケンシャル性能は同等かひょっとすると悪いくらいで、得意なのはランダムREAD。サイズの考慮なしにシーケンシャルREADのデータでランダムREADデータを追い出してしまうとすごく損してしまう。
しかしdm-cacheのアルゴリズムは単純なLRUらしい。だからSSDではうまく行かないことが予想される。


さらに探していると、Rik van Rielのページに、
DmCache
http://kernelnewbies.org/KernelProjects/DmCache
というプロジェクトの説明を見つけた。名前がdm-cacheと似ていてまぎらわしい。
言っていることは大体私の希望どおりで、大きな単位のIOはキャッシュしない、などのアイディアが書いてある。
このプロジェクト、今どうなってるのかなあ。待っていてよいのだろうか。

この説明の中に、2Qというアルゴリズムを使う、と書いてあるのが気になっていた。
聞いたことがなかったが調べてみると、有名なもののようだ。元の論文にあたってみたので、メモを書いておこう。

最近まで全く知らなかったが、データベースの世界ではページ置換のアルゴリズムの研究というものが盛んなようだ(今でも?)。考えてみれば当然でしょうね。いままでデータベースといえばraw diskを自分で管理して、OSのキャッシュなんて使わなかったわけだから。しかし最近のデータベースはファイルサーバの上にデータを置いてしまったりする、という話を聞く。

話がすこし脇道にそれるけど、そういえば、この夏のSan DiegoのUSENIXで聞いた話の中で、もっとも感心したのが、
IBMの人のWriteキャッシュの話だった。

STOW
http://www.usenix.org/events/usenix09/tech/full_papers/gill/gill_html/index.html

同じ人の以前の仕事にやはりWriteキャッシュについての以下のものがあった。
WOW
http://www.usenix.org/events/fast05/tech/gill.html

おなじくIBMのARCはもうちょっと一般にも有名なのかもしれない。
やっている人の名前を見るとそれぞれ関係しあっているようだ。

http://www.usenix.org/events/fast03/tech/megiddo.html
http://www.almaden.ibm.com/cs/people/dmodha/arc-fast.pdf

このへんのものに、比較の対象として2Qが取り上げられている。
SolarisにL2ARCという名前で実装がある。たしかIBMの特許に引っかからないように実装したという
話だったと思う。

DmCacheのページに2Qと書いてあるのは特許の問題があるからなのだろう。


2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
Theodore Johnson, Dennis Shasha

http://portal.acm.org/citation.cfm?id=672996

1994のVery Large Data Basesの論文。
著者のDennis Shashaの方は、「サイエンティフィックアメリカン」の数学パスルのページを書いている人。実は私は同じ職場にいたことがある。といっても向こうは全然おぼえていないと思うけど。私の丁稚奉公先がDennisのいた会社で、同じフロアの人だったというだけ。しかもこの論文の当時のことだ。NYUの先生をしていることは聞いていたが、こんなことやっている人だとすら知らなかった。背が高くて上品な感じの人だった。


Readデータのキャッシュの方法にLRUが使われてきたが、それを改善する。

LRU
一本のキューを用意する。
新しいエントリを追加する時には最後尾から一個捨てて、新しいエントリは先頭に追加。
キューの中にあるものに再度アクセスが来たら先頭に移す。


LRUの問題点。
使用頻度の低いエントリをLRUに追加してしまうと、LRUが一周するまでの間、使われないエントリを持ち続けることになる。

最近使ったかどうかということと、使用頻度は別で、使用頻度は低いが、最近使われたということがあるし、逆に、全体をとおして見れば使用頻度は高いが、他のものと比較して最近つかわれていない、ということがあり得る。滅多に読まないデータをスキャンしてLRUに乗ってしまったりすると、大事なデータが追い出されるという問題が起こる筈だ。ARCはその両方を折衷した構造になっていた。


LRU/K ( K=2がLRU/2) というアルゴリズムがあって、これを改善しようとしているが、プライオリティキューの操作のオーバヘッドが大きい。

以下が2Qの説明。2QとはQueueが2つあるという意味。


簡単な方から。
Simplified 2Q:

2つのキュー、A1とAmを用意する。
新しいエントリはA1に追加する。
A1にあるものに対して2度目のアクセスがあると、Amに移す。

A1はFIFOで、あふれると、古いものから捨てて行く。
Amは従来のLRUと同じ。


Simplified 2Qの問題点。
チューニングが難しい。A1の量が小さすぎるとすぐにA1から追い出されてしまう。
つまり頻度に対する条件が厳しく、Amに入れないことになる。
A1を大きくしすぎると、Amの量が減ってしまう。

また、アクセスパターンによる問題がある。現実の負荷では一時的にアクセスされやすいページが多い。
アクセス頻度が多いのでAmに入れたが、そのあと全然アクセスされないということが起こる。


この問題を改善したのが、以下の2Q。

2Q:

A1をA1inとA1outに分ける。A1outはページのアドレスを覚えておくだけ。
インデクスだけを覚えるので、メモリ領域はあまり消費しない。

新しいエントリはA1inに追加。
A1inで古くなるとメモリは解放して、A1outに入れる(つまりインデクスだけ覚えておく)。
A1inのものが再度アクセスされても、そのまま。
A1outに入っているものが再度アクセスされると、メモリを獲得してAmに入れる。
A1outは古い順に捨てる。
AmはLRUとして使う。


つまり、
一時的アクセスはA1inに滞在する間だけで処理される。
A1に入っていたことがある、というのは頻度に関する情報としてとっておく(A1out)。
A1inは比較的いそがしく入れ替わり、Amに入ったものはゆっくり流れて行くイメージかな。

このやり方でも頻度については、高いか低いかという2つの状態しかないように思える。というのでARCを考えたのだろう。まるで分かったように書いたが、ARCのこともちゃんと理解してないので、あとで勉強する。

Tuesday, January 13, 2009

2平方数の和

ある素数pを
p = a^2 + b^2
の形に表そうという問題があります。
p = 1 (mod 4)の時に解があるということは知っていましたが、解き方はしりませんでした。総当たりで解いていたのです。どうやらこれは非常に効率の悪い方法だったようです。

本ってすばらしいですね。その方法が書いてありました。a^2+b^2=kpとなるa,bからスタートしてkを1まで減らすという作戦です。

1. a^2 = -1 (mod p) となるaを求める。
 フェルマーの定理と乱数を利用。

2. a^2 + 1^2 = 0 (mod p) なので、b = 1とおけば、a^2+b^2 = kp。k=1なら終了。

3. u = a (mod k), v = b (mod k)とする。u^2+v^2 = a^2+b^2 (mod k)となる。
  q = (u^2+v^2)/kとする。
 
4. 定義より(u^2+v^2)(a^2+b^2) =qkkp
  また式の変形で、(u^2+v^2)(a^2+b^2) = (ua+vb)^2 + (va-ub)^2

5. それぞれの項がkで割れる筈なので
a = (ua+vb)/k
b = (va-ub)/k
k = q
として2に戻る。

こんな計算方法、よく見つけたなあ。すごい。
これはかなり速いんですね。以下、私のコード。


from random import randint

def square_mod(p):
while True:
a = randint(2, p - 1)
b = pow(a, (p - 1) / 4) % p
if (b*b) % p == p - 1:
return b

def two_square_sum(p):
if p % 4 != 1: return [0, 0]

a = square_mod(p)
b = 1
k = (a * a + b * b) / p

while k > 1:
u, v = a % k, b % k

# abs(u) <= k/2
# abs(v) <= k/2
if u > k / 2: u -= k
if v > k / 2: v -= k

# u * u + v * v = 0 (mod k)
q = (u * u + v * v) / k

# (u * u + v * v) * (a * a + b * b) = (u * a + v * b)^2 + (v * a - u * b)^2 = (q * k) * (k * p)
c, d = (u * a + v * b) / k, (v * a - u * b) / k

# next turn
a, b = c, d
k = q

return [abs(a), abs(b)]


実際にやってみましょう。


for i in xrange(5, 10000, 4):
if is_prime(i):
x, y = two_square_sum(i)
print i, x, y

5 2 1
13 3 2
17 4 1
29 5 2
37 6 1
41 5 4
53 7 2
61 6 5
73 8 3
89 5 8
97 9 4
101 10 1
109 10 3
113 8 7
137 11 4
.....


この本で読みました。

Sunday, January 04, 2009

組み合わせを作るアルゴリズム#3

以前、k-subsetのことを書きました。Pythonで書きましたがC言語に直訳できそうな書き方でした。私のPythonの書き方はいつもそれで、たぶんPythonらしくないのでしょう。ダサイ書き方なんですよね。昨日某所にて同じことを以下のように書いているのをみてそう感じました。


def ksubset2(n, k, pos):
if k > 0:
for i in xrange(pos, n - k + 1):
for s in ksubset2(n, k - 1, i + 1):
yield [i] + s
else:
yield []


すごいなあ。格好いい。私がやってもこういう風には絶対ならないですね。これはジェネレータなのでksubset2(5,3,0)に前と同じ組み合わせが入っていることになります。

しかし、自分でやるとしたら、やっぱりCに置き換えやすい書き方をしておきますかね。Pythonで遅ければCに直すという理由で。つまりジェネレータは使わないのです。

ちなみに、某所でみたのは上のようにnで上限を渡すのではなくて、同じことではありますが以下のようにseqに元の集合を入れて渡すものでした。

def ksubset3(seq, k):
if k > 0:
for i in xrange(0, len(seq) - k + 1):
for s in ksubset3(seq[i+1:], k - 1):
yield [seq[i]] + s
else:
yield []