strtok-count.eps

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]。

我々 は、 計画実現の第一歩と し て 、 テキスト 処理のも っ と も 基本的な 機能のひと つである 文字列の単語へ分解 を 行う 分割器のプロ ト タ イ プを 開発し た。 本稿ではそのアーキテク チャ と 評価結果について 述べる 。

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 節で解説する 。 表 1: FPGA ボート と 関連する 諸元

FPGAボード ALPHA DATA ADM-PCIE-7V3 [11]

FPGAデバイ ス Xilinx Virtex-7 XC7VX690T-2

最大レ ーン 幅 ×8 最大リ ン ク 速度 8 GT/s DDR 2つの 8GB ECC-SODIMM, 速度は最大 1333MT/s

2.2

分割器のカーネル (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’が含ま れて いて も 、 それは単な る 文字のひと つと し て 扱われる 。

表 2: 分割器のカ ーネ ルのプロ ト タ イ プ諸元 区切り 文字 半角スペース マ ルチバイ ト 文字 非対応 連続し た区切り 文字 ひと つの区切り 文字と し て 扱う 1行の最大長 65535 表 3: 分割器のカ ーネ ルの入出力 パラ メ ータ I/O ビッ ト 幅 種類 プロ ト コ ル 要素数/チャ ン ク

num lines IN 32 scalar AXI slave (register) N/A

total length IN 32 scalar AXI slave (register) N/A

lines IN 8 array AXI master 32

lengths IN 16 array AXI master 16

markers OUT 32 array AXI master 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 8192 分割器が 1 度に処理でき る 最大行数 WD 256 AXIマ スタ ーイ ン タ ーフ ェ イ スのデータ 幅 NS 32 Splittersの数 QW p 64 positionsに対する バースト ラ イ ト 長 2_{チャ ン ク 中に 16 を 超え る 単語がある 場合、 よ り 大き いク ロ ッ ク 数を 要する}

図 2: 単語分割の例。 markers と positions は、 見やすく する ために実際のビッ ト 幅よ り 小さ く 表示さ れて いる こ と に注意。

利点は、 レ イ テン シ (処理時間) が入力さ れる 行の長さ の分布に依存せず、 主と し て 全体の大き さ に比例する こ と である 。

算出さ れた positions と markers は、 それぞれ、 Positions formatter と Marker formatter に送ら れる 。 そ

れら のブロ ッ ク は、 送ら れて く る データ 要素から WDビッ ト 長のチャ ン ク を 生成する 。 QWp 個の 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 0 32

lengths 0 32

markers 0 default (16)

positions 0 default (16)

分割器のカ ーネ ルは 200MHz で動作する よ う に 設計さ れて いる 。 こ れは、 FPGA ボード ADM-PCIE-7V3 で

OpenCLを 使う 場合の変更でき な い要件である 。 Vivado HLS の co-simulation によ る と 、 1 つのチャ ン ク 3_が入

3_{サイ ズが N}

図 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 のためのグルー・ ロ ジッ ク で構成さ れる 。 こ れを 開発

計さ れて いる こ と 。 すな わち 、 それは本研究の目的に対し て 最良と は限ら な いこ と 。 他の理由は、 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: Volvox のグルー・ ロ ジッ ク 表 6: 分割器と グルー・ ロ ジッ ク のリ ソ ース

コ ン ポーネ ン ト LUT LUTRAM FF BRAM

分割器と グルー・ ロ ジッ ク 20% 7% 11% 4% 2.4.2 ホスト コ ン ピュ ータ のソ フ ト ウ ェ ア 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) が繰り 返さ れる 。 アプ

リ ケーショ ン 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 FVs Cs 目的 実性能 strtok()相当の機能

デバイ ス FPGA FPGA CPU FPGA FPGA CPU

フ レ ーム ワ ーク OpenCL Volvox N/A OpenCL Volvox N/A

3

評価

3.1

ホスト マシン

表 8 に評価に用いたホスト マ シン の諸元を 示す。

表 8: ホスト マ シン の諸元

CPU Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz

RAM 8 GB ×4

OS CentOS 6.8 (x86 64)

3.2

入力データ

英語文書から 構成さ れる 10 から 109 の 9 つのサイ ズの入力データ を 用いた。 表 9 に、 それら に含ま れる 単語と 行 の数を 示す。 図 7 と 8 に、 単語長と 連続し た区切り 文字の反復数の分布を 示す。 最頻出の語長は 3 である 。 90%と 99%の単語は、 それぞれ、 9 文字と 13 文字よ り 小さ い。 入力データ サイ ズは、 入力単語の組わせに依存し 、 入力行数が同じ だと し て も 当然異なる 。 入力行数が最大 (す な わち L) の場合のおおよ そサイ ズは数百キロ バイ ト である 。 表 9: 入力データ の単語数と 行数 サイ ズ (Bytes) 10 102 103 104 105 106 107 108 109 単語数 2 18 154 1579 17194 171422 1743974 17237031 172432363 行数 1 3 43 247 1831 17390 194936 1988957 19911073 0 5 10 15 20 Frequency Word length 図 7: 入力データ の単語長分布 101 102 103 104 105 106 107 108 0 5 10 15 20 25 30 35 40 45 Frequency

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 . 10 3 では最小である 。 一方、 FVa (TF Va)は、 A & 10 4_{で C} aのそれよ り 小さ い。 比率 TCa/TF Va と 、 1 秒あたり に処理さ れる データ サイ ズで ある スループッ ト F Vsは、 それぞれ、 10 およ び 4.13 × 10 9 B/sである 。

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 < 10 7 において 、 10−_{3 . T . 10}0の広い 処理時間の分布を 持ち 、 その平均時間は、 A = 10 において 、 FVaと Caに対し て 、 それぞれ、 104およ び 105倍である 。 こ の理由は現在不明で、 根本原因を 探る こ と は OpenCL の実装がプロ プラ イ エタ リ である ために困難である 。 し かし ながら 、 その影響は大き いサイ ズの入 力 (A > 108 )を 処理する 場合、 無視でき る 。 10-8 10-7 10-6 10-5 10-4 10-3 10-2 10-1 100 101 102 101 102 103 104 105 106 107 108 109

Process time (Sec.)

Input data size (Bytes)

FPGA with OpenCL CPU

FPGA with Volvox

図 9: 入力データ サイ ズに対する 処理時間。 マ ーカーは平均時間を 示す。 エラ ーバーは、 結果の 90%が含ま れる 区 間を 表す。 3.4.2 strtok相当関数の呼び出し 回数 図 11 は、 1 秒間の呼び出し 回数の測定結果を 示す。 全体的な結果は、 実性能のそれと ほぼ合致する 。 Csに対す る FVsの呼び出し 回数の比率は、 約 7 であり 、 前節で議論し た実性能の比率である 約 10 (TCa/TF Va)よ り 小さ い。 4_{入力データ サイ ズが小さ いと こ ろ での非線形性は、 3.3 節で言及し た clock gettime() に起因する と 考え ら れる 。}

図 10: 10 バイ ト の文字列を 使用し た場合の分割器の AXI イ ン タ ーフ ェ イ スの信号

こ れは、 strtok v() の呼び出し と NULL タ ーミ ネ ータ ーの書き 出し のために CPU によ る 処理が増え たためと 考 え ら れる 。 一般的に分割さ れた単語に対し て 、 さ ら な る 処理が行われる 。 例え ば、 数値型への変換、 大文字化、 それら を 使っ た新し い文字列の作成などである 。 次の複数行の処理を 分割器のカーネルが処理し ている 間に、 こ れら を CPU で行う こ と ができ る ので、 CPU 負荷の観点から は分割処理がなく なっ たよ う に見える 。 と にかく 、 こ の結果は我々 のコ ン セプト が実現可能である こ と を 示し て いる 。 CPU FPGA w/ OpenCL FPGA w/ Volvox 0 5x108 1x109

The count of calls per 1 second

図 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.

[2] http://hadoop.apache.org/ [3] http://simplecore.intel.com/newsroom/wp-content/uploads/sites/11/2016/03/Intel-Investor-Conference-Call-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