ABSTRACT. 量子アニーリングは、組合せ最適化処理を高速かつ高精度に実行できると期待される計算技術である。量子アニーリングは自然計算の一種であり、物理学に基づく計算技術である。量子アニーリングの計算原理そのものを実行するハードウェアが現れてから、量子アニーリングの応用探索が活発に繰り広げられている。また、新しいタイプの量子アニーリングマシンの構築を見据え、理論的な研究も活発に進められている。本講演では、量子アニーリングの理論研究について紹介する。また量子アニーリングの応用探索に向けた最新の動向を述べる。

ABSTRACT. Range aggregation query is a fundamental operation in data analysis, which computes statistics such as maximum, average, and standard deviation of subset of records specified by the range condition of the query. Since data analysis has trial-and-error nature, data scientists repeatedly dispatch tons of range aggregation queries by changing range conditions, resulting in heavy workloads.

Partial aggregation methods accelerate such repetitive range aggregation queries by partitioning data into several groups, caching partial query result on each group, and answering queries by combining those partial results leveraging divide-and-conquer characteristic of aggregation operations. However, conventional partial aggregation methods have severe trade-off between the amount of cached aggregations and the performance; it needs to cache n aggregation values to avoid I/Os where n is the size of the domain of attributes in selection conditions.

Motivated by the issue, this paper presents Adaptive Partial Aggregation Tree (APA-Tree), which can reduce the number of cached aggregation values to arbitrary defined s. With this constraint, APA-Tree try to minimize the I/Os under the locality of reference assumption; APA-Tree finely computes aggregation values on frequently accessed data and coarsely on rarely accessed data. As a result, APA-Tree successfully accelerates repetitive aggregation queries with a small number of pre-computed aggregation values compared to conventional methods. Experimental results confirms that APA-Tree outperforms conventional partial aggregation methods in terms of the amount of I/Os especially in skewed workloads.

ABSTRACT. 複数のスレッドが同一のデータ構造に並行的 にアクセスしてREAD 処理とWRITE 処理を行 うとき，排他制御が必要になる．そのような排 他制御を実現するデータ構造は並行データ構造 と呼ばれる．データベースシステムにおいては TPC-C ベンチマークで見られるように，範囲 検索が頻繁に使われる．それゆえ範囲検索を効 率的に実行する並行データ構造が重要である． 古くはLehman とYao による並行B+木構造が 提案されてPostgreSQL で使われており，近年 はBronson らによる並行木構造が提案されてい る．Masstree はトライ木のノード部分にB+木 を格納する構造である．B+木，トライ木は，そ れぞれ一括挿入法による高速構築法が提案され てきた．一方，B+木とトライ木を混合した構造 であるMasstree の一括挿入法は我々の知る限り 存在しない．Masstree は16 並列アクセスまで 性能がスケールするが，それを上回る一括構築 法が存在すれば，運用開始時の待機時間を削減 でき，運用者の負担を削減させられる．我々は Masstree の一括挿入法を本論文で提案する．提 案手法ではMasstree がトライ木とB+木から構 成されている点に着目した．データを整列した 後，トライ木のレベルでのデータ分散を行い， 各トライ木においてB+木の構築を行った．整 列を高速に実行するために並列基数ソートを用 いた．トライ木構築は逐次的に実行し、B+木構 築は並列的に実行した．

ABSTRACT. 2016年にTCP BBRという新しいTCP輻輳制御アルゴリズムが提案された．これまでのTCP輻輳制御アルゴリズムは主にパケットのロスの検出に基づく手法(ロスベース手法)や，通信遅延時間に基づく手法(遅延ベース手法)，あるいはそれらを組み合わせた手法であったが，TCP BBRはKleinrockの輻輳モデルに基づいている．本稿では，新しい手法であるTCP BBRとこれまでのTCP輻輳制御アルゴリズムが同一ネットワーク内で競合したときの性能公平性について考察する．具体的には，TCP BBRと代表的な既存のTCPアルゴリズムであるCUBIC TCPが競合する環境における性能評価結果を示し，性能公平性が非常に低いことを示す．そして，OSのカーネルの改変により両TCPの振る舞いを示し，性能不公平の原因が輻輳ウィンドウの値にあることを示し，公平性改善に関する考察を行う．

ABSTRACT. 本研究では分散処理フレームワークMapReduceにおけるAll-to-All集団通信フェーズであるshuffleに関して，“skew”と呼ばれるMapReduce shuffleにおけるload imbalance問題に対処可能な集団通信の設計を行う．本研究ではshuffle対象のデータ本体 (block) とそのメタ情報 (meta-block) を単一のAll-to-All通信で交換するCSA (Coupled Shuffle Architecture)，blockとmeta-blockをそれぞれ別のAll-to-All通信によって交換するDSA (Decoupled Shuffle Architecture)，DSAにおいて各プロセスの消費メモリサイズを考慮してblockの配置を決定するDSA w/ SMS (Skew-aware Meta-Shuffle)，の3手法の提案及び比較を行う．また上記3手法に関して， InfiniBandに代表される高性能インターコネクトの性能を最大限活用するための実装方法を示す．評価実験では上記3手法を用いてskew度合いを変えながらshuffleワークロードを実行し，DSA w/ SMS方式のみが極度のskew状況下でもin-memoryでshuffleを実行できることを示す．またCSA，DSAの2手法のweak scaling性能の比較を通して，skew度合いに応じた両方式の挙動を詳細に調査する．

ABSTRACT. 近年，Deep Neural Network (DNN) において，重みパラメータや入力値のビット幅を削減して記憶領域やデータ転送コスト，計算コストを削減する研究が多く行われている．本稿では，ニューロン毎に異なる量子化ビット幅での最適化手法および提案手法で最適化したネットワークを高効率に処理するアーキテクチャを提案する．評価において，AlexNetの全結合層の重みパラメータサイズを32ビット浮動小数点数の13%，従来手法である層毎のビット幅最適化の63¥%に圧縮できることがわかった．また，Pruningを適用したネットワークにニューロン毎のビット幅最適化を実施することで，全結合層のパラメータサイズを32ビット浮動小数点数の0.65%とさらに大幅に圧縮可能であり，Pruningとの協調によってデータ転送量の削減効果が得られることがわかった．加えて，提案手法でビット幅を最適化したネットワークを提案のアーキテクチャで処理することにより，データ転送クロックサイクル数を従来の63%に削減できることがわかった．

ABSTRACT. 飛躍的な進歩を続けるニューラルネットワークは、実アプリケーションとして組み込まれるようになった。 推論処理に必要な計算量は大きいため、データ取得場所付近ではなく、データセンタに設置された潤沢な計算基盤をもつサーバで処理される。しかし、サーバやネットワークスイッチの膨大な消費電力やデータの一極集中によるトラフィック輻輳が問題となる。そこで、計算負荷の大きな畳み込み演算を削減するために、特徴抽出の役割を持つCNNを共有する分散推論の実行モデルを提案し、4つのモデルの精度の低下と削減可能な計算量を評価した。VGG16がベースとなるニューラルネットワークにおいて、タスクのドメインが同一であるモデルの 100クラス分類を解くニューラルネットワークの認識精度を測定した結果、元モデと比較して平均 12.3%だけ精度が低下した。一般物体検出を解くモデルでは、元モデルと比較して 0.8%精度が向上した。削減計算量の見積もりでは、Conv4-3までのニューラル ネットワークを共有したならば、従来手法と比較し65.79%の計算量が削減でき、高効率な推論処理が可能になることが分かった。

ABSTRACT. データセンタによるエネルギー消費は年々増加の一途を辿っている.ビッグデータブームに象徴されるよ うに，大規模データ分析基盤に対する IT 資源の投入は拡大を続けており，その省エネルギー化の重要性は高い. 本論文では，データ分析基盤の核であるデータベースシステムの省エネルギー化に向けて，プロセッサの省エネル ギー制御の観点から問合せ処理の性能・電力特性を明らかにする.即ち，分析指向問合せ処理の基本的な演算であ る全表走査を伴う処理を対象とし，プロセッサの動作モードが問合せ処理の性能及び消費電力に与える影響を解析 的にモデル化すると共に，当該モデルによって予測される性能・電力特性の傾向が実測値と合致することを示す.

ABSTRACT. トランザクション処理における必須の高性能化技法 としてグループコミットがある．これは複数のログレコードを一 括して永続的デバイスへ転送することで，トランザクション処理 を高性能化する．そのグループコミットは常に味方なのだろうか？ これが本研究の問いである．グループコミットは現代においても 深化を遂げ，トランザクション処理性能の劇的な向上に寄与して いる．そのため，グループコミットが味方であることを疑う者は いないだろう，我々を除けば．この問いに答えるために，我々は ハードウェアとしてNVRAM ならびにマルチコア・メニーコア環 境，トランザクション処理技術として，高性能楽観的並行制御法 TicToc と，並列ログ先行書込み法P-WAL を用いた．メニーコア 環境における実験において，グループコミットのグループサイズ が増えるほど性能が劣化する結果が観察された．即ち，グループ コミットは敵となり得ることが明らかになった．

ABSTRACT. 疎行列ベクトル積は科学技術計算において重要な計算カーネルの一つであり，その高速化が強く求められている．本論文では，DIA形式とCRS形式の2種類の疎行列格納形式を組み合わせたHybrid形式による疎行列ベクトル積を対象とし，疎行列ベクトル積の計算結果を書き込むベクトルに対するキャッシュブロッキング手法を提示する．また，キャッシュブロッキングを前提とした改良版Hybrid形式を提案する．そして，最新のマルチコアCPU及びメニーコアCPUを用いて性能評価を行い，本論文で示したキャッシュブロッキング手法や改良版Hybrid形式が有効となる疎行列が存在することを示す．

ABSTRACT. Algebraic block multi-color ordering is known as a paralleliza- tion method for a sparse triangular solver. In the previous work, we confirmed the effectiveness of the method in a multi- threaded ICCG solver for a linear system with a symmetric coefficient matrix. In this study, we enhance the method so as to deal with an unsymmetric coefficient matrix. We develop a multi-threaded ILU-GMRES solver based on the enhanced method and evaluate its performance in terms of both the runtime and the number of iterations.

ABSTRACT. ストリーム処理においてステートフルなデータを簡潔に処理するための解析基盤Phalanxを提案する． ストリーム処理ではイベントの到着順序が保障されないため、更新順序を考慮する必要があるステートフルなデータのあつかいが難しい．Phalanx ではCRDT のデータモデルに基づいて，ステートフルなストリーム処理を実現する．CRDT で用いられるデータ型は更新の順序を問わず結果整合性を保つことが可能なため，データの到着順序が保証されない状況でのステートフルなデータへの管理を簡素化できる．結果整合性をもつデータ型を利用することで，Phalanx ではイベントをCRDT の操作に対応付ける記述のみでステートフルなデータの変更を実現できる．

ABSTRACT. マーケティングデータなどのデータ分析を対象として, 近年,有用性の高い分析結果を自動的に検出する探索的データ分析の技術が注目されている．探索的データ分析では,多様なOLAPクエリあるいは多様な部分データを総当たりして有用性の高い分析結果を探索するため, 膨大な時間を要する問題がある．この問題に対して従来のクエリ最適化の技術として, 複数クエリの共有化手法および有用な分析結果の上位$k$件検索による探索空間の削減手法が存在するが, 前者はプランニング時の最適化技術であり実行プランが静的であることが必要であるのに対して, 後者は実行中の最適化技術であり動的に実行プランを変更する必要があるため, 両者の共存したものが存在していない．本稿では, プランニング時の最適化技術である複数クエリ共有化を実行中の探索空間の削減技術に複数クエリを同時実行する形で組み込み両立を図る.データをストリーム処理して複数クエリを同時に処理するとともに, 中心極限定理に基づいて有用性の低いデータキューブを推定して枝刈りするフレームワークを提案する．更に, 大規模データに対して異常検知の分析を行った結果を報告する．評価実験により,大域例外データを探索する場合, 最大で$2$倍の高速化が可能であることを確認した．

ABSTRACT. 1970 年代に Yacc が発明されてから,開発 されたパーサジェネレータの多くは出力される パーサの言語が限定されている.しかし,パーサ ジェネレータの文法仕様は LR(k),LL(k),PEG などの形式文法に基づいている.そのため,従 来のパーサジェネレータの言語限定は必要な い.本研究では,言語非依存のパーサ生成に ついて取り組む.まず,我々はアクションコー ド無しでパーサを生成できるように,形式文 法 PEG をベースとして宣言的拡張を行った. 次に,プログラミング言語に共通する機能で 記述できるように,パーサランタイムを単純 化した.最後に,テンプレートは出力する言語 を切り替えられるように実装した.我々は,こ のようなパーサジェネレータ NezCC を設計し た.NezCC は,C,Java,JavaScript,Python, Lua,Scala,Racket,F#といった,さまざま な言語で動作するパーサを生成できる.NezCC パーサは構文解析のための十分な機能 (柔軟な木 構築,拡張された文脈依存解析,効率的なパック ラット構文解析) を備えている.さらに,NezCC パーサの解析速度は十分に速い.我々の調査に よれば,Yacc や ANTLR のような既存のパー サジェネレータと比較して十分な構文解析速度 となった.

ABSTRACT. In high performance computing applications many per- formance problems are caused by the memory system. Such performance bugs are hard to identify precisely. Thus analysis tools play an important role in perfor- mance optimization. We present a specialized memory performance analysis tool which relies on Linux Perf to interface the hardware. Our tool design is simple, easy to use, easily extend-able and provides support for many existing and upcoming processors without signif- icant implementation effort. This tool is able to guide programmers towards the most promising optimization opportunities. It is able to report the location in the source code, the concerned objects and in most cases point out a specific performance problem occurring at this location. We demonstrate this in a number of case studies which include applications from PARSEC.