SC13 - Micronの超高速サーチエンジン「Automata」

SC13においてMicronは、「Automata」と呼ぶサーチや解析を超高速で実行する非ノイマン型のプロセサを発表した。

「Automata」は、その名の通り、有限状態オートマトンで、入力されるシンボル(文字やDNAのアミノ酸の種類など、一区切りのデータ)に応じて内部状態を変えていく順序回路である。

オートマトンを使って、構造を持たない(ただ、文字が並んでいるだけの)文章から目指す文字列を見つけるという研究は古くから行われており、1981年に、現在は九州大学の総長である有川先生が論文を発表している。そして、富士通は、この技術を使って「瞬索」というサーチソフトを開発し、1995年から発売している。

また、オートマトンを、FPGAを使ってハードウェアとして実装するという研究も多く発表されている。しかし、MicronのAutomataは、専用のアーキテクチャのチップであり、FPGAに比べて高性能を実現できるという。また、大きなFPGAはかなり高価であるが、AutomataはDRAMプロセスで作られており、チップも小さく、低コストにできるとのことである。

シンボル列のサーチは、単に文章の中から条件に合う文字列を見つけるという用途だけでなく、DNAのシーケンスの中から目的の遺伝子や断片のストリングを見つけたり、メールの添付ファイルからウイルスの特徴となるストリングを見つけるなど、色々な用途に使える。

Micronが開発した第1世代のAutomataチップはDDR3 DRAMと同じインタフェースを使っており、一見するとDRAMチップのように見える。この写真のAutomataボードの中央に載っている金属光沢のチップは制御用のFPGAで、Automataチップは左右の4つのドーターボードに載っている。この写真では、各ボードに4個ずつ載っているように見えるが、実はそれぞれのボードは3重になっており、12個のAutomataチップが載り、全体では48個のチップが搭載されている。

1個のAutomataチップは、毎秒6.6兆回の状態遷移の判断ができるという。そしてチップ間のバスを通して連携することができ、48個のAutomataチップを搭載するこのボードは、2.35Mbitの状態を持ち、321T回/秒の判断ができる。

Automataは、非決定性有限オートマトン(Non-deterministic Finite Automata:NFA)という方式を使っている。決定性有限オートマトン(Deterministic Finite Automata:DFA)は、現在の状態と入力に応じて次の状態が決まるが、NFAは入力だけでは次の状態が決まらず、その後の入力が次の状態に影響する場合がある。原理的には、NFAと等価な機能をDFAで実現することができるが、必要な状態数が指数関数的に増大する。従って、Automataは、ハードウェアを小さくできるNFAを使っている。

UnixやLinuxのシェルやEmacsカルチャーの読者は、正規表現(Regular Expression)での文字列のサーチを良くご存知と思うが、aと書けばaという文字とマッチするが、^aと書くとa以外のすべての文字とマッチする。また^a-zと書くとaからzまでの文字以外の文字とマッチする。8ビットで表現できる文字は256個しかないのであるが、このような複数の文字を組み合わせる表現では2256通りのパターンがあり得る。

Automataチップの内部構成は次の図のようになっていて、8ビットの入力文字をデコードして256行×49512列のDRAMアレイを読み出す。この1列にはマッチする文字に対応するビットには1、マッチしない文字に対応するビットには0を書き込んでおく。そうすると、マッチした文字が入力されると1、マッチしない文字が入力された場合は0が読み出される。この部分はMicron得意のDRAMの技術を使っており、FPGAなどでの実現に比べてチップサイズを小さくする効果が大きい。

前述のようにマッチする文字は2256通りのバリエーションがあり得るが、実際にはそれほど多くのパターンが使われることはないので、48Kのパターンを扱えれば十分である。

そして、入力文字と各列とのマッチ情報はルーティングマトリクスに送られる。ルーティングマトリクスは、各状態ビットを変化させるロジックに必要な列のマッチ情報を接続するという機能を持っている。

ロジックは、自分の列のマッチ情報やルーティングマトリクスからの他の列のマッチ情報を組み合わせて状態ビットを変更して、状態遷移を実現する。

ルーティングマトリクスの接続とロジックのファンクションはプログラムすることができ、各オートマトンがどのような文字列を見つけるのかをプログラムすることができる。なお、このプログラミングは固定ではなく、入力文字列の途中でダイナミックに変更することもできるようになっている。

状態ビットは各列に対応して存在するので、Automataチップは、最大では249512状態を持つことができるが、実際にはこのような巨大な状態を持つ単一のオートマトンを作るのでなく、状態ビットを分割して、サーチするストリングを見つける小さなオートマトンを多数作り、それらのストリングが入力文字列に出てくるかどうかを並列に監視するという使い方になる。また、複雑なストリングを見つける場合は、簡単なサブストリングに分解してサーチし、それらのサブストリングの検出を入力とするオートマトンを作ればよい。

Automataチップに収まる範囲では複数の対象ストリングがあっても、入力文字列を1回入力すれば、並列にサーチができる。そして、複数のAutomataチップに、違う対象ストリングを見つけるオートマトンを作り同じ文字列を入力すれば、さらに多くの対象ストリングの出現を見つけることができる。

それから、Automataチップは、状態ビット以外にカウンタという状態記憶エレメントを持っている。ある文字が512個続いたらという条件を普通のオートマトンで作ると、1個出現、2個続いた、3個続いた、...と512個の状態が必要になるが、ある文字が出現しているという条件でカウンタをカウントアップし、カウンタが512に達したら、条件を満たしたと判定すれば、必要な状態数は大幅に減少する。これはNFAを使えば、DFAに比べて状態数を大幅に減らせるという1つの例である。

MicronのAutomataは、このようなサーチをオートマトンを使って効率的に行えることを目指した専用アーキテクチャのチップであり、文字列だけでなく、遺伝子などのバイオの情報や、添付ファイルの中に含まれている可能性のある多種類のウイルスを検出するなど、多くの実用的な処理を行うことができる。高価な大型FPGAでの実現に比べても高性能で、小さいチップで実現できるので、低コストで色々なサーチやパターンマッチに基づくデータの解析が低コストで実現できる可能性が開ける。

Micronは、Automataチップのプログラミングのために「ANML(Automata Network Markup Language)」を開発しており、2014年の前半にSDK(Software Development Kit)を公開する予定であるという。

AutomataチップでOSやコンパイラが走るわけではないが、サーチなどの用途では、汎用プロセサに比べて非常に高い性能を実現でき、コプロセサとして使われるようになると思われる。インタフェースがDDR3 DRAMと同じであり、メモリマップのデバイスとしてCPUに接続して使えるので、容易に接続できるというメリットもある。