Open Data Structure の日本語訳

TL;DR

  • Open Data Structures というフリーのデータ構造の教科書を翻訳している
  • サンプルコードを新たにRubyで書き、Ruby版を英語に逆輸入する予定である
  • 翻訳品質を上げるために資金あるいは手を提供してくれる方を募集している

Open Data Structuresというプロジェクトをご存知だろうか。 これはPat Morin氏が立ち上げたプロジェクトで、 大学のコンピュータサイエンス系の学部ならほぼ皆が最初に学ぶデータ構造に関する教科書をフリーで公開するものである。

「大学で」「皆が」「最初に」学ぶということは

  • 一般性・普遍性があり
  • だれでも使う
  • いつでも使う

ということを示唆しており、この分野、そしてこのプロジェクトの意義深さを端的に示しているだろう。

僕自身、大学の専門課程における最初の学期にこの教科書でデータ構造を学んだ。 先月のことだが、この教科書の日本語訳がまだないことにふと気づき、Patに連絡を取ってみた。 翻訳は歓迎してくれるそうだ。他の日本語翻訳やってるという話も聞いていないとのこと。(もしやってる方いたら連絡ください。) そして、この魅力的な分野への入門をかつてサポートしてくれた教科書を翻訳することにした。

なぜ翻訳をするのか

まず、本を英語から日本語に翻訳する意味はあるのだろうか?

個人的には英語よりも日本語を読む方がかなり早い。 しかし、専門書を読むときはついつい翻訳は避けてしまう。 品質のばらつきが大きく、読みにくいものも多いと感じるのが自分の場合は主な原因だ。

しかし、この教科書は入門書である。 前提知識は中学高校レベルの数学をほんの少しだけである。 (簡単なプログラミング経験があった方が、実感が持てて、有り難みがわかり、楽しく読めるとは思うが。) 日本語で読める無料の教科書は、分野の裾野を広げ、楽しくプログラムを書ける・効率的なプログラムが書ける人を増やしてくれるだろう。

母国語で大学レベルの教科書が読める国は多くない。 より専門的な内容はもっぱら英語で読むことになるのだから、さっさと崖から突き落とせという意見ももちろんあるだろう。 自分自身も大学に入った頃は「英語で読む」のに抵抗があった。(「英語を読む」ところまでは幸い受験で慣れた。) この抵抗を可及的速やかに取り除くのが、アクセス可能な知識を押し拡げるためには極めて重要だろう。 大学生になっても日本語で教科書が読める恵まれた環境が、日本人の英語アレルギーを支えている可能性はある。

しかし、この教科書は専門への橋渡しの、その初っ端に位置している。 この教科書を読むための前提知識は多くない。これに英語を加えるのは、対象読者を制限することになるだろう。 母国語でこのような入門書が読める、少なくともその選択肢があるのは望ましいことだと思う。

この教科書は、300ページ程度ながら、丁寧にゆっくりと、それでいて実用的な題材を納めている。 より本格的な教科書も出版されており、その中には翻訳されているものもある。 内容は素晴らしく、僕自身今でも度々読み返す。 少なくとも自分の持っている二冊は翻訳の質も良かった。(Algorithm DesignIntroduction to Algorithms) ただし、文量は大判1000ページ程度、価格は10000円程度と、気軽なものではない。 こういった専門家向けの入門書や、あるいはより専門的な書籍への橋渡しであるこの教科書を、日本語で・フリーでアクセスできるようにするのがこの翻訳の目的である。

Ruby版の開発

もう一つやろうと思っていることがある。

現在ODSには擬似コードC++Java版がある。 日本語版のサンプルコードはRubyで書こうと思っている。

自分がはじめて触ったプログラミング言語Rubyで、今でも一番愛着を持っているのはRubyである。 昨年Google Summer of Codeで、Rubyの人たちにRubyの中身をいろいろ教えて頂き、とても楽しかったのでその恩返しをしたいという気持ちもある。

というわけで、Ruby版を開発する予定だ。 まずは本文を訳すのに集中することにしたので、ひとまず擬似コードを入れている。 日本語版で上手くRuby版が書けたら、英語版の本家への逆輸入もしたいと思っている。

スケジュール

一ヶ月ほど翻訳作業をしており、現在14章中の9章を翻訳している途中である。 今のところ予定通りに進行していて、このままスケジュールに沿えば7月20日に(試訳が)完成することになっている。

日本語版のビルドやRuby擬似コードの開発まで含め、8月前半にリリースしたいと思っている。

ご協力のお願い

先に述べたように、翻訳はしばしば読みにくくなってしまう。 本書がそうなるのはもちろん本意でない。 より良いものを公開できるよう、この教科書の意義に共感して頂ける方の支援を募りたい。

翻訳作業は既に中盤に差し掛かっており、苦でもないためこのまま自分が行えると思う。 しかし僕は翻訳の専門家でもないし、英語に特別な強みを持っているわけでもない。 試訳も限られた空き時間で、まずは完成させることを目指し進めている。 そのため、初稿の品質は必ずしも高くはないと思う。 そこで教科書の品質を高く保つためのご協力いただければと考えている。

次のような3種類のやり方を考えている。

  • 気軽なフィードバック:GithubからでもメールでもTwitterでも、誤りの指摘や、修正案などを送っていただきたい。
  • 校正・校閲・査読:章単位での通読をお願いし、校正・校閲・査読いずれの形でもまとまったフィードバックをお願いしたい。上の気軽なフィードバックとくらべて、まとまった時間を投資していただける方向けの選択肢である。
  • 校正・校閲・査読のための資金援助:これらの作業を依頼するための資金援助を募りたい。これはクラウドファンディングを利用することを考えている。直接的な支援のみならず、SNSでシェアもぜひお願いしたい。

2つ目と3つめの方法で、全体を校正・校閲・査読していただければ、一定の品質保証になるのではないかと思っている。

ご協力頂いた方々には本書の謝辞でお礼を述べさせていただきたい。(クラウドファンディングで、広告権売るのはどうかなぁとか。未来のプログラマーの卵たちがはじめに読む本に広告打てるの結構アツくないですか?)

SoCS 2017 掲載論文の解説

SoCS 2017: The 10th Annual Symposium on Combinatorial Searchに、IDA* 探索を GPU を利用して高速化する手法に関する論文が採択された。

論文のタイトルは「Block-Parallel IDA* for GPUs」であり、以下のリンクから閲覧できる。

これは修士学生の頃の研究成果を、卒業後に投稿したものである。 採択は5月4日で、会議は6月16-17日に Pittsburgh で行われた。 自分は既に働いているので会議には参加せず、発表は共著者である元指導教官にお願いした。

概要

日本語で検索しても辿り着けるよう、概要を書いておく。 (かなり端折っているので、詳しくは論文を読んでいただきたい。)

IDA*

グラフ探索やIDA*の説明は、Wikipediaや元所属研究室の有志が2015年に書いてくれたAdvent Calendarに譲る。

掻い摘むと、IDA*とは問題についての知識をうまく利用しながら先読みをし、最適な行為の列を見つけるアルゴリズムであって、解の長さに対しメモリ使用量が指数的には大きくならないものである。 (余談だが、IDA*の提案者Richard E. Korf先生は、自分の元指導教官の元指導教官である。)

主な応用としては、色々なパズル、カーナビ、タンパク質の構造決定などがある。

先日少しバズっていた深層学習を超えた手法とは何かで書かれているように、巷で大流行の機械学習に、自動行動計画・先読み・探索・推論を組み合わせるのが一種のトレンドになるような予感がある。(もうなっている?) IDA*はこの探索における基礎的な技術のうちのひとつである。(ちなみに自動行動計画は自分の元所属研究室の主要なテーマであった。)

背景

本研究の主要な成果は、GPUでIDA*を効率的に実装する方法を提案したことだ。 GPUA*の並列化を行った先行研究としてChou, 2015があった。 しかしA*では、解の長さに対しメモリ使用量は一般に指数的に大きくなる。 例えばCPUでの直列A*でも、数GBのメモリをふつう1分以内程度で使い切る。 そのため、GPUの性能を使って本当に解きたい大規模な問題が解けないのである。 一方、IDA*では解の長さに対してメモリ使用量は線形程度に抑えられる。 そのため、メモリ使用量の制約からA*が解けない大規模な問題を解ける可能性がある。

GPUを使ってIDA*を並列化するとき、肝となるのは処理の分割方法である。 幅優先探索深さ優先探索などの単純な探索では、探索木の対称性が高く、素朴な方法で仕事を均等に分配できる。 一方IDA*では、探索木の形状の対称性は低く、実際に探索するまでこの形状はわからない。

IDA*の探索処理をどう分割し、並列化するかに関する研究は古くからある。 しかしその大部分は、CPUまたはSIMD計算機の並列化に関するものである。 GPUの実行モデル(NVIDIAはSIMTと呼んでいる)は、また違った特徴を有する。 過去の研究成果を元に、いくつかの手法を再実装してみたところ、GPUを前提に設計されていないため発生する種々の問題から、十分な性能が得られなかった。

Block-parallel IDA*

そのため本研究では、IDA*をGPUを利用して効率的に実装する手法としてBlock-parallel IDA*を提案した。

一般的なIDA*の並列化では、初期状態から少しだけ探索を行い、そうして得られる探索途中のノードを各スレッドに割り当てていた。各スレッドは割り当てられたノードを初期状態とし、探索の続きを行う。各々が探索する部分木の大きさは未知なので、処理の量にばらつきが出る。これを動的に調整するためのメカニズムにより処理が複雑化していた。

これに対して、提案手法Block-parallel IDA*では、各ノードはスレッドではなくブロックに割り当てられる。 これはオセロのゲーム木探索にGPUを利用する研究(Rocki and Suda, 2010)に着想を得たものである。 本論文ではIDA*の並列実行において、ブロック内のスレッドが明示的な同期を取らずに処理を行える方法を示した。 また、ブロック間のノードの分配はGPUのハードウェアスケジューラを利用できるため、ここでもやはり明示的な同期が不要である。 明示的な同期や処理の動的な再分配が不要なため、実装は非常にシンプルである。

実験

実験的に以下のことを確認した。

  • 1536コアのGPUにおいて、直列処理と比べて並列処理は約660倍高速である
  • 処理の均等な分割がほぼ完全に達成されている
  • CPUでの直列処理と比べて、1536コアのGPU1枚での並列処理は約5倍(ある補正をすると約7倍)高速である

所感とやり残し

GPUを使って5倍(あるいは7倍)高速化というのはさほどインパクトが大きくないかもしれない。しかし、一見GPUには向かない処理をうまく変換し、それなりの高速化を達成したという意味で価値のある成果だと思っている。

手法としては複数GPUの場合もほぼそのままでスケールするのではないかと思っている。しかし、これを実際に確認するまでは手が回らなかった。 また、もしGPU100枚や1000枚の規模になると、きっとまた一味違った困難が発生するのではないかとも考えている。

より多様な問題で性能評価を行うことも有意義だろう。 Block-parallel IDA*は問題にほぼ依存しないよう設計したつもりである。 しかし問題によっては、GPUの共有メモリに探索に必要な情報が収まらないなどの小さな困難は少なくとも発生するだろう。(この問題に関しては、教科書的にグローバルメモリから共有メモリに適当にprefetchすることで対処できるだろうと考えている。) 有効な問題の範囲を明らかにし、困難が発生する場合にはその対処方法を開発することは残された課題である。

Call for V100

GPUプログラミングわりと楽しかったので、探索技術に興味のある石油王の方が見ていたらV100(1699万円?)買ってください。