IoT機器に適した FPGAを用いた文字列分割の高速化

IoT 機器に 適し た FPGA を 用いた 文字列分割の高速化
大和 一洋 ∗
ミ ラ ク ル・ リ ナッ ク ス 株式会社
2016/12/1
概 要
本稿は、 IoT ゲート ウ ェ イ やデータ セ ン タ ーのサーバーに 適する FPGA を 用いた文字列分割の高速化に つい
て の研究成果を 報告する 。 ザイ リ ン ク ス 社の高位合成コ ン パイ ラ を 用いた プロ ト タ イ プは、 200MHz で動作し 、
ク ロ ッ ク 毎に 最大 32 の ASCII 文字を 処理する 。 そ れは、 PCI Express イ ン タ ーフ ェ イ ス を 介し て 、 ホス ト コ ン
ピュ ータ と FPGA ボード 間でデータ 転送を 行う ために OpenCL と 自製のフ レ ーム ワ ーク (Volvox) のいずれかを
利用する 。 評価では、 Volvox を 使っ たプロ ト タ イ プに よ る 処理が、 CPU に よ る 処理よ り も 約 10 倍高速である こ
と が示さ れた 。
1
はじ めに
IoT (Internet of Things) 機器の数は、 2020 年ま でに 208 億台に 達する と 予想さ れて いる [1]。 膨大な 数の機器
を 扱う た めのキ ーと な る コ ン ポーネ ン ト のひと つは、 IoT ゲート ウ ェ イ であ る 。 そ れは、 データ を 機器から 収集
し て イ ン タ ーネ ッ ト サーバーに 転送する こ と に 加え て 、 集約、 フ ォ ーマ ッ ト 変換、 不要な データ の破棄な ど の前
処理も 行う 。 IoT ゲート ウ ェ イ は、 データ セ ン タ ー以外に も 様々 な 場所に 設置さ れる こ と が想定さ れる 。 多く の
機器から のト ラ フ ィッ ク を 処理し な け ればな ら な いに も かかわら ず、 そ こ では、 設置ス ペース 、 冷却、 電力な ど の
制約はよ り 厳し い。 ネ ッ ト ワ ーク ・ プロ ト コ ルやフ ォ ーマ ッ ト に は HTTP や JSON のよ う に テキ ス ト 形式のも の
が多く ある ので、 ト ラ フ ィッ ク に はそ れら テキ ス ト 文字列が含ま れる 。 ま た、 近年、 小型機器でも 動作する 軽量プ
ロ グラ ム 言語 (例え ば、 Python や Ruby) を IoT 機器に 用いる 場合、 入出力に テキ ス ト を 使用する ケ ース も ある 。
そ のため、 効率的な テキ ス ト 処理は、 優れた IoT ゲート ウ ェ イ の重要な 要件のひと つと な る 。
一方、 データ セ ン タ ーでも IoT 機器から の大量のト ラ フ ィッ ク を 処理し な け ればな ら な い。 ま た 、 テ キ ス ト を
使用する 機会も 多い。 例え ば、 (Hadoop [2] を 用いたよ う な ) 収集データ の分散バッ チ処理、 自然言語の構文解析、
AI (Artificial Intelligence) と の対話、 多量のサーバーのロ グ解析な ど である 。
FPGA (Field Programmable Gate Array) は、 こ れら の課題に 対する 有効な 解決策のひと つと 考え ら れる 。 イ
ン テ ル社は、 2020 年ま でに 1/3 のク ラ ウ ド を 構成する サーバーに FPGA が搭載さ れる と 述べて いる [3]。 FPGA
を 使う と 、 ユーザーは自身で目的に 応じ て 回路を 構成でき る 。 良好な 設計がな さ れる と 、 高い性能と 電力効率が
得ら れる [4]。 し かし な がら 、 一般的な ソ フ ト ウ ェ アエン ジニアや運用管理者がそれら を 使いこ な すこ と は難し い。
な ぜな ら 、 そ の設計に は、 デジタ ル回路の知識を はじ め、 シス テム バス や OS な ど のコ ン ピュ ータ に 関する 広範な
知見が必要だから である 。 加え て 、 ア プリ ケ ーショ ン プロ グラ ム が、 構築さ れた FPGA 内の回路を 使用する よ う
に 新規開発ま たは修正を 行う 必要も ある 。
我々 は、 GNU C Library (glibc) [5] のよ う な 基本的な ラ イ ブラ リ から FPGA を 透過的に 使用する OS を 提供す
る こ と で、 こ れら の課題を 解決する こ と を 計画し て いる 。 こ の方式の優位点は、 ア プリ ケ ーショ ン の修正が不要
な こ と である 。 ま た、 最近の CPU と FPGA を 統合する ト レ ン ド に よ っ て 、 こ のコ ン セ プト は Intel プラ ッ ト ホー
ム で ARM でも 実現可能であ る 。 イ ン テ ル社は、 FPGA 技術の先進的な 企業であ る ア ルテ ラ 社の買収が完了し た
と ア ナウ ン ス し た [6]。 も う ひと つの主要な 企業である ザイ リ ン ク ス 社は、 ARM ベース のプロ セッ サと FPGA に
よ る 構成可能な 機能を ひと つに し た SoC (System on Chip) である Zynq を 販売し て いる 。 ARM 社のオーナーで
ある ソ フ ト バン ク の CEO は、 IoT のために ARM ベース のプロ セッ サを 活用する こ と に 積極的な 姿勢を 表明し て
いる [8]。
我々 は、 計画実現の第一歩と し て 、 テ キ ス ト 処理のも っ と も 基本的な 機能のひと つであ る 文字列の単語へ分解
を 行う 分割器のプロ ト タ イ プを 開発し た。 本稿ではそ のア ーキ テク チャ と 評価結果に ついて 述べる 。
∗ Email:
[email protected]
1
プロ ト タ イ プ
2
2.1
全体構成
プロ ト タ イ プは、 図 1 に示し たよ う にホスト コ ン ピュータ と 、 PCI Express イ ン タ ーフ ェイ スで接続さ れた FPGA
ボード (表 1 参照) で構成さ れる 。 図中のコ ン ポーネ ン ト は、 3 つのレ イ ヤ ーに 分類でき る 。 下位レ イ ヤ ー (灰色の
背景） は、 ハード ウ ェ アであり 、 その機能は固定である 。 中間レ イ ヤ ー (青い背景) は、 DMA 転送や割り 込み処理
な ど 様々 な ア プリ ケ ーショ ン で共通し て 使われ、 下位と 上位レ イ ヤ ーの橋渡し を 行う 。 上位レ イ ヤ ー (赤い背景)
は、 ア プリ ケ ーショ ン に 固有の処理を 持つ。
図 1: 全体構成
も っ と も 主要な 役割を 担う 分割器のカ ーネ ル (Tokenizer kernel)
1
を 2.2 節で説明する 。 中間レ イ ヤ ーに 2 つの
異な る フ ーレ ム ワ ーク、 OpenCL と Volvox を 用いて 、 そ れぞの場合に ついて 評価を 行っ た 。 こ れら を 2.3 と 2.4
節で説明する 。 上位レ イ ヤ ーでのホス ト ア プリ ケ ーショ ン に ついて は 2.5 節で解説する 。
FPGA ボード
FPGA デバイ ス
最大レ ーン 幅
最大リ ン ク 速度
DDR
2.2
表 1: FPGA ボート と 関連する 諸元
ALPHA DATA ADM-PCIE-7V3 [11]
Xilinx Virtex-7 XC7VX690T-2
×8
8 GT/s
2 つの 8GB ECC-SODIMM, 速度は最大 1333MT/s
分割器のカ ーネル (Tokenizer kernel)
分割器のカ ーネ ルは、 各行ごと に 、 入力さ れる 文字列の全て の単語に 対し て 、 開始と 終端位置の組を 算出する 。
現在のプロ ト タ イ プの諸元を 表 2 に 示す。 分割器は、 最大 L 行 (表 4 参照) を 一度に 処理する 。 分割器は、 C++で
記述さ れ、 ザイ リ ン ク ス 社の Vivado (HLS) 2016.1 に よ っ て 合成さ れて いる ので、 そ の入出力は表 3 に 示すと お
り C 言語の関数のよ う に 定義さ れる 。
図 2 に 、 2 つの行 ‘MIRACLELINUX’ と ‘Corporatecolorisgreen.’ ( はス ペース を 表す ) の分割
を 例示する 。 入力パラ メ ータ num lines と total length は、 そ れぞれ、 1 回のカ ーネ ル実行での処理さ れる 行
数と そ れら の合計長を 示す。 lengths は各行の長さ を 格納する 配列であ る 。 そ の配列長は、 num lines と 同一で
ある 。 配列 lines は、 処理さ れる 文字列を すべて 含み、 そ れら に はパディ ン グや改行を 示すコ ード は含ま れな い。
‘\n’ が含ま れて いて も 、 そ れは単な る 文字のひと つと し て 扱われる 。
1 FPGA
内に 構成さ れる 処理機構を カ ーネ ルと 呼ぶ。 Linux カ ーネ ルと は異な る ので混同に 注意。
2
区切り 文字
表 2: 分割器のカ ーネ ルのプロ ト タ イ プ諸元
半角ス ペース
マ ルチバイ ト 文字
非対応
連続し た区切り 文字
1 行の最大長
ひと つの区切り 文字と し て 扱う
65535
表 3: 分割器のカ ーネ ルの入出力
ビッ ト 幅
種類
プロ ト コ ル
パラ メ ータ
I/O
要素数/チャ ン ク
num lines
IN
32
scalar
AXI slave (register)
N/A
total length
lines
IN
IN
32
8
scalar
array
AXI slave (register)
AXI master
N/A
32
lengths
markers
IN
OUT
16
32
array
array
AXI master
AXI master
16
8
positions
OUT
16
array
AXI master
16
出力パラ メ ータ markers は、 長さ num lines+1 の配列である 。 その要素は、 対応する 行の分割結果を 格納する
領域の先頭を 指す。 最後の要素は、 positions の次の要素を 指す。 配列 positions は、 単語の開始と 終端の位置
の組を 含む。 そ の配列長は、 入力文字列に よ っ て 変わり 、 markers の最後の要素を 使っ て 次のよ う に 算出でき る 。
Np = Z/Bp
(1)
こ こ で Np , Z と Bp は、 そ れぞれ、 positions の要素数、 markers の最後の値、 positions の要素の大き さ であ
る 。 同様に 単語数 Nt は次のよ う に 得ら れる 。
Nt = Np /2
(2)
カ ーネ ルのブロ ッ ク 図を 図 3 に 示す。 入出力のためのポート は、 実際に はデータ 幅 WD ビッ ト のひと つの AXI
マ ス タ ーイ ン タ ーフ ェ イ ス な ので、 配列中の複数の要素が一度に 読み書き さ れる 。 そ の単位を チャ ン ク と こ こ で
は呼ぶ。 チャ ン ク 中の要素数を 表 3 の ‘要素数/チャ ン ク ’ 列に 示す。
Reader は、 ま ず lengths の全て の要素を 、 続いて lines を 読み出す。 こ の方式は、 メ モリ を シーケ ン シャ ル
に ア ク セ ス し 、 AXI のバース ト リ ード を 引き 起こ す。 バース ト リ ード /ラ イ ト は、 1 回の手続き で連続し たア ド レ
ス の複数のデータ を 転送する こ と に よ り 高いス ループッ ト を 実現する 。 バース ト 転送を 行う こ と は、 高速な デー
タ 入出力のための最も 重要な ポイ ン ト のひと つである 。 Dispatcher は、 読み出さ れた lines のチャ ン ク を 循環的
に ひと つの Splitter に 送り 出す。 Splitter は、 ク ロ ッ ク 毎に 1 文字 (8 ビッ ト ) を 解析し 、 そ の繰り 返し 間隔は
WD /8 ク ロ ッ ク であ る 2 。 繰り 返し 間隔と 同じ 数 Ns 個の Splitter を 配置する こ と で、 合計 Ns 文字が 1 ク ロ ッ
ク で処理さ れる 。 Splitter は、 いく つかのチャ ン ク に 分割さ れたも ののひと つを 解析する ので、 行の中の完全な
位置を 算出する のは不可能であ る 。 そ のた め、 完全な 位置を 後段のブロ ッ ク で計算出来る よ う に 、 いつく かの変
数も 算出する 。 Linearizer は、 循環的に Splitter から 解析結果を 集めて 、 再度ひと つのデータ ス ト リ ーム を 生
成する 。 Unifier は、 以前の結果と 組み合わせて 完全な positions と markers を 計算する 。 こ のア ーキ テク チャ の
表 4: 分割器のカ ーネ ルの構成パラ メ ータ
概要
パラ メ ータ
値
L
WD
8192
256
分割器が 1 度に 処理でき る 最大行数
NS
QW
p
32
64
Splitters の数
positions に 対する バース ト ラ イ ト 長
2 チャ ン ク 中に
AXI マ ス タ ーイ ン タ ーフ ェ イ ス のデータ 幅
16 を 超え る 単語がある 場合、 よ り 大き いク ロ ッ ク 数を 要する
3
図 2: 単語分割の例。 markers と positions は、 見やすく する た めに 実際のビッ ト 幅よ り 小さ く 表示さ れて いる
こ と に 注意。
利点は、 レ イ テン シ (処理時間) が入力さ れる 行の長さ の分布に 依存せず、 主と し て 全体の大き さ に 比例する こ と
である 。
算出さ れた positions と markers は、 そ れぞれ、 Positions formatter と Marker formatter に 送ら れる 。 そ
れら のブロ ッ ク は、 送ら れて く る データ 要素から WD ビッ ト 長のチャ ン ク を 生成する 。 QW
p 個の positions が準
備でき る 度に 、 Writer はそ れら を 書き 出す。 一方、 markers は、 すべて の positions が書き 出さ れる ま で Marker
formatter 内に 蓄積さ れる 。 markers の要素数は最大でも L + 1 な ので、 一時的に こ れら を 保持する こ と はそ れ
ほど 困難ではな い。 こ の手法も バース ト ラ イ ト を 引き 起こ すために 用いら れて いる 。
表 5 のよ う に AXI マスタ ーイ ン タ ーフ ェイ スのパラ メ ータ を 調整し ている 。 上述のと おり positions と markers
のバース ト 長は、 そ れぞれ、 QW
p と L + 1 である 。 な お、 こ こ でのバース ト 長は、 memcpy() ま たは、 for 文の中
で使用さ れる 値のこ と であ る 。 こ れは、 AXI イ ン タ ーフ ェ イ ス のパラ メ ータ のひと つであ り 、 デフ ォ ルト 値 (15)
のま ま であ る AWLEN と 異な る 点に 注意のこ と 。 表中の値は試行錯誤的に 決めら れた 。 こ れら のパラ メ ータ な し で
は、 バース ト ラ イ ト と 次のバース ト ラ イ ト の間隔が、 Vivado HLS の C/RTL co-simulation の結果から 期待さ れ
る 値よ り 長く な っ た。
表 5: 明示的に 指定し た AXI イ ン タ ーフ ェ イ ス パラ メ ータ
パラ メ ータ latency max read burst length
lines
lengths
0
0
32
32
markers
positions
0
0
default (16)
default (16)
分割器のカ ーネ ルは 200MHz で動作する よ う に 設計さ れて いる 。 こ れは、 FPGA ボード ADM-PCIE-7V3 で
OpenCL を 使う 場合の変更でき な い要件であ る 。 Vivado HLS の co-simulation に よ る と 、 1 つのチャ ン ク
3 サイ ズが
Ns バイ ト 以下
4
3
が入
図 3: 分割器のカ ーネ ル (Tokenizer kernel) のブロ ッ ク 図
力さ れた場合のレ イ テン シは 179 であり 、 Ns バイ ト ごと に 増加する 。
2.3
OpenCL フ レ ームワ ーク
OpenCL は、 The Khronos Group [10] に よ っ て 標準化さ れて いる フ レ ーム ワ ーク であ る 。 開発者は、 CPU、
GPU、 FPGA や専用ア ク セ ラ レ ータ な ど 種々 のデバイ ス を C 言語を ベース に し た 1 つの API セ ッ ト で使用でき
る 。 そ の API は、 ホス ト と デバイ ス の両方に 対し て 定義さ れて いる 。 加え て 、 ザイ リ ン ク 社の OpenCL 開発環境
である SDAccel では、 OpenCL C のみな ら ず、 pragma 指示子を 用いた C と C++で FPGA のカ ーネ ルを 記述す
る こ と ができ る 。 我々 は、 分割器のカ ーネ ルを SDAccel を 使っ て C++で記述し た。
図 4 に OpenCL を 使う 場合のデータ の流れの一例を 示す。 OpenCL は、 ‘Host application’ お よ び ‘OpenCL
framework on Host’ と 名付け ら れたボッ ク ス間のイ ン タ ーフ ェ イ ス (API) を 定義する ので、 厳密な シーケ ン スは、
そ のラ イ ブラ リ 実装に 依存する 。 図は仕組みを 容易に イ メ ージする ための補助である 。
ラ ベルの先頭の丸括弧の中の数字は、 それら が使用さ れる 典型的な 順序を 示す。 ラ ベルはそれら と 関連のある コ
ン ポーネ ン ト の近く に配置さ れて いる 。 図ではデータ が一旦 FPGA ボード 上の RAM を 経由し て いる が、 実際のホ
ス ト と FPGA ボード 間の転送方法は、 上述のと おり 実装依存である 。 開発者は、 目的固有の処理のみを OpenCL
C (も し く は C/C++) を 使っ て 設計すればよ く 、 PCI Express や DDR RAM のよ う な ハード ウ ェ ア の詳細を 知る
必要がな い。 こ れは OpenCL を 使う も っ と 有益な 点のひと つである 。
図 4: Volvox フ レ ーム ワ ーク を 使っ たデータ の流れの例
2.4
Volvox フ レ ームワ ーク
Volvox フ レ ーム ワ ーク は、 自製のソ フ ト ウ ェ ア と FPGA のためのグルー・ ロ ジッ ク で構成さ れる 。 こ れを 開発
し た理由は次の 2 つである 。 ひと つは、 OpenCL の API セ ッ ト が様々 な プラ ッ ト ホーム で種々 の目的のために 設
5
計さ れて いる こ と 。 すな わち 、 そ れは本研究の目的に 対し て 最良と は限ら な いこ と 。 他の理由は、 SDAccel がま
だ正式版でな い (β 版な ) ので、 そ れを 使っ た結果に はま だ改善の余地がある かも し れな いためである 。
分割器のカ ーネ ル自身は、 何ら 変更な し に OpenCL と Volvox フ レ ーム ワ ーク で共通し て 使用でき る 。 し かし 、
ホス ト 側では、 出来る 限り の性能を 提供する ために 、 上位レ イ ヤ ーと のイ ン タ ーフ ェ イ ス は OpenCL のそ れと は
非互換である 。 Volvox の特徴のひと つは、 分割器のカ ーネ ルが、 図 5 に示すよ う にアプリ ケ ーショ ン・ プロ グラ ム
のメ モリ 空間に マ ッ プさ れて いる バッ フ ァ に 対し て 直接読み書き する こ と である 。 ま た、 FPGA ボード 上の DDR
RAM は使用さ れず、 Linux カ ーネ ルと ア プリ ケ ーショ ン プロ グラ ム 間のデータ のコ ピ ーも な い。
図 5: Volvox フ レ ーム ワ ーク でのデータ の流れ
2.4.1
FPGA 内のグルー・ ロ ジッ ク
図 6 に 、 分割器が FPGA に 搭載さ れて いる ハード ウ ェ ア ブロ ッ ク を 使っ て PCI Express イ ン タ フ ェ ース に ア ク
セ ス する ためのグルー・ ロ ジッ ク を 示す。 分割器を 除く コ ン ポーネ ン ト はすべて LogiCORE と 呼ばれる ザイ リ ン
ク ス 社の IP であ る 。 そ れら は、 ×8 レ ーン ・ 8GT/s の PCI Express から のト ラ フ ィッ ク を 処理する た めに 、 256
ビッ ト の AXI イ ン タ ーフ ェ イ ス の RDATA およ び WDATA を 用いて 250MHz で動作する 。
AXI Bridge for PCI Express Gen3 は、 AXI と PCI Express 間でリ ード およ びラ イ ト 操作を 転送する 。 言い換
え る と 、 分割器のカ ーネ ルの AXI イ ン タ ーフ ェ イ ス での 1 つのバース ト リ ード (ラ イ ト ) 操作は、 PCI Express で
のバースト リ ード (ラ イ ト ) を 引き 起こ す。 こ のアーキテク チャ では、 分割器がホスト メ モリ へアク セスする DMA
エン ジン と し て 動作する 。
割り 込みコ ン ト ロ ーラ は、 次の 2 つの目的に 使用さ れる 。
(1) レ ベル割り 込みを エッ ジ割り 込みに 変換。 分割器の割り 込みピ ン は、 Vivado HLS に よ っ て 自動的に 生成さ
れ、 開発者はそ の仕様を 変更でき な い。
(2) AXI Bridge のク ロ ッ ク に 同期し た割り 込み信号を 生成。
表 6 に 配置配線後 FPGA のリ ソ ース を 示す。 使用率の点から は、 分割器内の並列度 (Splitter の数) を 増やす
こ と は可能である 。 し かし な がら 、 分割器のカ ーネ ルの論理的な 最大ス ループッ ト は、 すでに PCI Express の最
大転送レ ート に ほぼ匹敵し て いる 。 そ のため、 こ れ以上の並列性は性能に ほと んど 寄与し な い。
6
図 6: Volvox のグルー・ ロ ジッ ク
表 6: 分割器と グルー・ ロ ジッ ク のリ ソ ース
コ ン ポーネ ン ト
LUT
LUTRAM
FF
分割器と グルー・ ロ ジッ ク
2.4.2
20%
7%
11%
BRAM
4%
ホスト コ ン ピ ュ ータ のソ フ ト ウ ェ ア
Volvox フ レ ーム ワ ーク のホス ト 側でのコ ン ポーネ ン ト は、 Linux 用のロ ーダーブルカ ーネ ルモジュ ールのみで
ある 。 そ れは、 サイ ズがそ れぞれ 4MiB である DMA バッ フ ァ 用の 2 つのメ モリ 領域を 2 組確保する 。 各領域は、
そ れぞれ FPGA へのデータ、 およ び、 FPGA から のデータ を 格納する 。 2 組の領域を 使う こ と で、 ホス ト ア プリ
ケ ーショ ン は、 １ つの組を 使っ て 処理が行われて いる 間に 、 次のカ ーネ ル実行のための入力データ を 準備し たり 、
すでに 処理が完了し たデータ に ア ク セ ス 出来る 。 結果と し て 、 こ の機構も 性能の向上に 寄与する 。 Volvox のカ ー
ネ ルモジュ ールは、 mmap シス テム コ ールを 通じ て 、 ホス ト ア プリ ケ ーショ ン に 領域を マ ッ プする 。
カ ーネ ルモジュ ールは、 分割器から の割り 込みを 受け と っ た時に、 ホスト アプリ ケ ーショ ン を 起床する 機能を 持
つ。 し かし な がら 、 割り 込みの使用はオプショ ン である 。 分割器のカ ーネ ルは、 処理状態を 示すビッ ト を 含むレ ジ
ス タ を 提供する ので、 ホス ト ア プリ ケ ーショ ン はそ のレ ジス タ のポーリ ン グに よ り 処理の完了を 知る こ と ができ
る 。 カ ーネ ルモジュ ールは、 Linux の streaming DMA API [12] に 基づく DMA バッ フ ァ の同期機能を 提供する 。
ホス ト ア プリ ケ ーショ ン は、 そ の機能に よ り RAM のキ ャッ シュ のフ ラ ッ シュ や無効化を 行わな け ればな ら な い。
2.5
評価のためのホスト ア プリ ケ ーシ ョ ン
性能評価のた めに 表 7 に 示す 6 つのホス ト ア プリ ケ ーショ ン を 開発し た 。 そ れら は、 2.5.1 と 2.5.2 節で解説さ
れる 2 つのグループに 分類さ れる 。
2.5.1
実性能測定ためのホスト ア プリ ケ ーシ ョ ン
ひと つ目のグループの目的は、 実性能を 測定する こ と である 。 ア プリ ケ ーショ ン FOa と FVa は、 (a) 入力フ ァ
イ ルを 読み込み、 (b) そ の内容を 分割器のカ ーネ ルが利用でき る 形式に 変換し て 、 (c) バッ フ ァ に 書き 込み、 (d)
FPGA 内のカ ーネ ルの処理を 開始する 。 フ ァ イ ルの行数が L を 超え る 場合、 上記の (c)(d) が繰り 返さ れる 。 ア プ
7
リ ケ ーショ ン Ca は、 CPU を 用いて 同様の処理を 行う 時間を 知る ために 作成さ れた。 FOa と FVa と 異な り 、 そ れ
は 1 行ごと に 文字列分割を 行う 。
こ れら のア プリ ケ ーショ ン は、 最初のデータ の準備終了から 分割器のカ ーネ ルの実行完了ま での時間を 測定す
る 。 入力フ ァ イ ルを 読み込む時間の遅延を 低減する ため、 すべて の文字列は、 一旦ア プリ ケ ーショ ン 内のバッ フ ァ
に 予めコ ピ ーさ れる 。 こ の時間は測定に は含ま れな い。
2.5.2
コ ン セプト 実証のためのア プリ ケ ーシ ョ ン
も う 一方のグループの目的は、 C ラ イ ブラ リ (glibc) の関数のひと つである strtok() に相当する 機能を 実現し 、
その性能を 調べる こ と である 。 本稿では、 その機能を strtok v() と 記す。 アプリ ケ ーショ ン FOs と FVs (Cs ) は、
単位時間あたり 何回 strtok v() (strtok()) を 呼び出すかを 測定する 。 1 節で述べたよ う に我々 の目的は、 FPGA
を 透過的に 利用する OS を 提供する こ と であ る 。 こ れは、 そ のコ ン セ プト のひと つのデモン ス ト レ ーショ ン であ
る 。 ただし 、 現在の実装では、 呼び出し 元のア プリ ケ ーショ ン の修正を 不要と する ま での完全な 透過ではな い。
分割器のカ ーネ ルは、 複数の行を 一度に 処理する こ と が想定さ れて いる 。 1 行のみを 取り 扱う こ と はでき る が、
そ の場合、 3.4.1 節で議論する よ う に いく つかのオーバーヘッ ド に よ り 、 不十分な 結果に な る 。 そ れ故、 処理さ れ
る 複数行に 、 そ れら が strtok v() に 渡さ れる 前に ア ク セ ス でき る 必要がある 。 と はいえ 、 こ の制約があっ て も 、
例え ば、 大量のロ グのバッ チ処理な ど に 応用する こ と は可能である 。
ア プリ ケ ーショ ン FOs と FVs は、 ま ず、 複数行に ついて の positions と markers を そ れぞれ FOa と FVa の方
法で得る 。 その後、 それら は、 char *strtok v(char *str) の呼び出し 毎に、 NULL タ ーミ ネ ータ ーを パラ メ ー
タ と し て 与え ら れた文字列に埋め込む。 引数 str は、 本来の strtok のそれと 同じ く 分割さ れる 文字列である 。 返
り 値のポイ ン タ も 、 本来のそ れと 同じ 意味を 持つ。 オリ ジナルの strtok と の違いは、 区切り 文字が固定であり 指
定でき な いこ と である 。 アプリ ケ ーショ ン Cs は、 単純に strtok() を 入力行ごと に呼び出す。 Ca の分割エン ジン
に ついて は我自身々 で作成し たが、 こ ち ら は第三者に よ っ て 開発さ れ、 誰でも 容易に 使用でき る GNU C Library
の一部である 。
ア プリ ケ ーショ ン
表 7: ホス ト ア プリ ケ ーショ ン
FOa
FVa
Ca
FOs
目的
デバイ ス
フ レ ーム ワ ーク
実性能
FPGA
OpenCL
FPGA
Volvox
CPU
N/A
FVs
Cs
strtok() 相当の機能
FPGA
FPGA CPU
OpenCL Volvox N/A
評価
3
3.1
ホスト マシ ン
表 8 に 評価に 用いたホス ト マ シン の諸元を 示す。
CPU
表 8: ホス ト マ シン の諸元
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
RAM
OS
8 GB ×4
CentOS 6.8 (x86 64)
Max payload size on PCIe
128
8
3.2
入力データ
英語文書から 構成さ れる 10 から 109 の 9 つのサイ ズの入力データ を 用いた。 表 9 に、 それら に含ま れる 単語と 行
の数を 示す。 図 7 と 8 に 、 単語長と 連続し た区切り 文字の反復数の分布を 示す。 最頻出の語長は 3 である 。 90%と
99%の単語は、 そ れぞれ、 9 文字と 13 文字よ り 小さ い。
入力データ サイ ズは、 入力単語の組わせに 依存し 、 入力行数が同じ だと し て も 当然異な る 。 入力行数が最大 (す
な わち L) の場合のおおよ そ サイ ズは数百キ ロ バイ ト である 。
サイ ズ (Bytes)
10
102
表 9: 入力データ の単語数と 行数
103
104
105
106
107
単語数
2
1
18
3
154
43
1579
247
17194
1831
171422
17390
1743974
194936
109
17237031
1988957
172432363
19911073
Frequency
行数
108
0
5
10
15
20
Word length
Frequency
図 7: 入力データ の単語長分布
108
107
106
105
104
103
102
101
0
5
10
15
20
25
30
35
40
45
The number of consecutive separators
図 8: 入力データ 中の区切り 文字の反復数分布
3.3
ア プリ ケ ーシ ョ ン
最大の性能を 得る ために 2.5 節に 記載のア プリ ケ ーショ ン を ポーリ ン グモード で使用し た。 割り 込みを 使っ た場
合、 おおよ そ 5 から 10µs の追加的な 遅延が分割器のカ ーネ ルの実行毎に 発生し た。
処理時間は、 ア プリ ケ ーショ ン 内に 配置さ れた clock gettime(CLOCK MONOTONIC) を 使っ て 測定さ れた。 こ の
関数は測定毎に 2 回呼び出さ れる 。 報告 [13] によ る と 、 こ の関数自身の遅延は約 50ns であり 基本的に無視でき る 。
3.4
3.4.1
結果と 議論
実性能
図 9 に 、 入力データ サイ ズ A に 対する 処理時間 T を 示す。 黒、 青、 赤のマ ーカ ーは、 そ れぞれ、 ア プリ ケ ー
ショ ン FOa 、 Ca およ び FVa を 用いた測定結果を 表す。 Ca の処理時間 (TCa ) は、 A . 103 では最小である 。 一方、
FVa (TF Va ) は、 A & 104 で Ca のそ れよ り 小さ い。 比率 TCa /TF Va と 、 1 秒あ た り に 処理さ れる データ サイ ズで
ある ス ループッ ト F Vs は、 そ れぞれ、 10 およ び 4.13 × 109 B/s である 。
9
Ca の処理時間は、 お お よ そ 入力データ サイ ズに 比例し て いる
4
が、 FVa のそ れは、 A . 103 でほぼ一定で約
7µs である 。 我々 は、 A = 10 での処理時間の内訳を 調べた。 FVa に は、 以下の 3 つの工程がある 。
(1) DMA バッ フ ァ への入力データ の書き 込みと 分割器カ ーネ ルのレ ジス タ 設定。
(2) DMA バッ フ ァ の同期。
(3) 分割器のカ ーネ ルの実行。
そ れぞれの時間は、 そ れぞれ、 約 1、 4、 およ び 2 µs であっ た。 工程 (1) と (3) は、 入力サイ ズと と も に 増加する
が、 工程 (2) はほぼ一定であっ た。
(3) の時間に 関し て 、 2.2 節で述べたよ う に 設計 (C/RTL co-simulation) 上の分割器の最小レ イ テン シは 179 で
ある が、 実際のそ れは、 ク ロ ッ ク 周波数が 200MHz な ので約 400 である こ と を 意味し て いる 。 そ の違いは、 ホス
ト RAM から データ を 得る た めの遅延時間に 起因する 。 図 10 に 、 分割器の AXI イ ン タ ーフ ェ イ ス のいく つかの
信号を 示す。 そ れは、 FPGA 中の実信号のロ ジッ ク ・ ア ナラ イ ザである ILA (Integrated Logic Analyzer) [14] を
用いて 取得さ れた。 最初の ARVALID の立ち 上があり (読み込み要求の開始) から 、 対応する RVALID の立ち 上が
り (要求データ の到着) ま での間隔は、 約 100 ク ロ ッ ク である 。 分割器のカ ーネ ルは lengths と lines のために 、
2 度のバース ト リ ード を 行う ので、 そ の約 100 ク ロ ッ ク の 2 倍の遅延が、 設計上想定さ れる 値に 加算さ れる 。 仮に
lengths と lines の両方を 含むひと つの配列を 使え ば、 遅延時間は減る であ ろ う 。 し かし 、 そ れは可読性と 保守
性の低下を も たら す懸念がある 。
FOa の結果は、 A < 107 に おいて 、 10− 3 . T . 100 の広い 処理時間の分布を 持ち 、 そ の平均時間は、 A = 10
に おいて 、 FVa と Ca に 対し て 、 そ れぞれ、 104 およ び 105 倍である 。 こ の理由は現在不明で、 根本原因を 探る こ
と は OpenCL の実装がプロ プラ イ エタ リ である ために 困難である 。 し かし な がら 、 そ の影響は大き いサイ ズの入
力 (A > 108 ) を 処理する 場合、 無視でき る 。
102
FPGA with OpenCL
CPU
FPGA with Volvox
1
10
100
Process time (Sec.)
10-1
10-2
10-3
10-4
10-5
10-6
10-7
10-8
101
102
103
104
105
106
107
108
109
Input data size (Bytes)
図 9: 入力データ サイ ズに 対する 処理時間。 マ ーカ ーは平均時間を 示す。 エラ ーバーは、 結果の 90%が含ま れる 区
間を 表す。
3.4.2
strtok 相当関数の呼び出し 回数
図 11 は、 1 秒間の呼び出し 回数の測定結果を 示す。 全体的な 結果は、 実性能のそ れと ほぼ合致する 。 Cs に 対す
る FVs の呼び出し 回数の比率は、 約 7 であり 、 前節で議論し た実性能の比率である 約 10 (TCa /TF Va ) よ り 小さ い。
4 入力データ サイ ズが小さ いと こ ろ での非線形性は、
3.3 節で言及し た clock gettime() に 起因する と 考え ら れる 。
10
図 10: 10 バイ ト の文字列を 使用し た場合の分割器の AXI イ ン タ ーフ ェ イ ス の信号
こ れは、 strtok v() の呼び出し と NULL タ ーミ ネ ータ ーの書き 出し のために CPU に よ る 処理が増え たためと 考
え ら れる 。
一般的に 分割さ れた 単語に 対し て 、 さ ら な る 処理が行われる 。 例え ば、 数値型への変換、 大文字化、 そ れら を
使っ た新し い文字列の作成など である 。 次の複数行の処理を 分割器のカーネ ルが処理し て いる 間に、 こ れら を CPU
で行う こ と ができ る ので、 CPU 負荷の観点から は分割処理がな く なっ たよ う に見え る 。 と にかく 、 こ の結果は我々
のコ ン セ プト が実現可能である こ と を 示し て いる 。
CPU
FPGA w/ OpenCL
FPGA w/ Volvox
0
5x108
The count of calls per 1 second
1x109
図 11: strtok() と 相当する 関数 strtok v() の呼び出し 回数の比較。
4
まとめ
本稿では、 急速な 増加が予想さ れて いる IoT 機器に 向け た FPGA を 用いた文字列分割の研究結果に ついて 報告
し た。 ザイ リ ン ク ス社の高位合成コ ン パイ ラ を 用いたプロ ト タ イ プは、 200MHz で動作し 、 最大 32 の ASCII 文字
を ク ロ ッ ク 毎に 処理する 。 評価結果は、 本目的のために 作成さ れた自製フ レ ーム ワ ーク Volvox と 、 注意深く 調整
さ れたバース ト 転送のためのパラ メ ータ を 用いたプロ ト タ イ プに よ る 処理が CPU に よ る 処理よ り 約 10 倍高速で
あっ た 。 我々 のゴ ールは、 1 節で述べた よ う に FPGA を 透過的に 活用する OS を 提供する こ と であ る 。 今後、 他
の文字列処理機能と 、 FPGA 上でそ れら を 組み合わせた処理を 実現し て いく 。
ザイ リ ン ク ス 社に 対し て 、 OpenCL 開発環境であ る SDAccel の β 版を ラ イ セ ン ス し て 頂いた こ と に 感謝する 。
OpenCL を 用いた結果に は不可解な 部分も ある も のの、 協力し て そ れら を 明ら かに し て いき たい。
参考文献
[1] Gartner’s press release, Gartner says 6.4 Billion Connected ”Things” Will Be in Use in 2016, Up 30 Percent
From 2015.
11
[2] http://hadoop.apache.org/
[3] http://simplecore.intel.com/newsroom/wp-content/uploads/sites/11/2016/03/Intel-Investor-ConferenceCall-Deck.pdf
[4] https://www.xilinx.com/products/technology/power.html
[5] https://www.gnu.org/software/libc/
[6] https://newsroom.intel.com/news-releases/intel-completes-acquisition-of-altera/
[7] https://www.xilinx.com/products/silicon-devices/soc/zynq-7000.html
[8] http://www.armtechcon.com/from-trilobites-to-a-trillion-chips-the-iot-explosion/
[9] http://www.xilinx.com/products/design-tools/vivado/integration/esl-design.html
[10] https://www.khronos.org/
[11] http://www.alpha-data.com/dcp/products.php?product=adm-pcie-7v3
[12] https://www.kernel.org/doc/Documentation/DMA-API-HOWTO.txt
[13] http://btorpey.github.io/blog/2014/02/18/clock-sources-in-linux/
[14] https://www.xilinx.com/products/intellectual-property/ila.html
12