Merge Pathは何故うまく動くのかがわからない
1年以上ぶりの更新。
少し前からmoderngpuというCUDAライブラリのコードを読んでいます。github.com
と言っても全てではなくて、マージソートの部分。
そのコードの中でMergePathという関数が出てくる。そのコードは20行も無いくらいのコードなのだけれど、何故それが上手く動くのかがわからない。
ということで今日は、Merge Pathについて次の2本の論文を読んでいた。
http://www.cc.gatech.edu/grads/o/ogreen3/_docs/2012MergePath.pdf
http://www.cc.gatech.edu/~bader/papers/GPUMergePath-ICS2012.pdf
読みについての進捗は良くなく、2本とも中途半端なところまでしか読めてない。今の所、このアルゴリズムがうまく動くのかわかってない。
明日も論文を読むつもり。ちゃんと理解できるといいなぁ。