ABSTRACT. In recent years, among high-performance computing (HPC) systems with many processors, distributed memory type computers rather than shared memory type computers have been common. The interconnections between nodes are required for parallel computing. Among them, we consider the Infiniband connection, which is common for HPC. Infiniband has characteristics of low latency and high bandwidth compared to Ethernet, and we want to make the most of it. The MPI library exists as a de facto standard of communication libraries for HPC applications. In this study, however, we use the Infiniband Verbs API to control the communication more directly and hide the communication time.

In IP communication, a socket is used as an endpoint of the connection. On the other hand, in Infiniband, Queue Pair (QP) is used. Several types of communication can be handled by Verbs, among which Reliable Connection (RC) communication has retransmission control, and communicates with a specific partner for each QP. On the other hand, in Unreliable Datagram (UD) communication, acknowledgments are not required, although there is a possibility of data loss. In addition, since the destination can be specified for each transmission for the same QP, there is no need to generate QP for each communication partner. This enables a memory saving communication even when the number of nodes is very large. The existing practical MPI libraries use RC communication. In this study, however, we try to take advantage of the fact that data loss in UD communication is rare, so that we can utilize UD communication with a minimized number of acknowledgments.

Also, we focus on multiplexing communication, that is, take a strategy to do the same calculation in parallel and to communicate the results between nodes and to adopt the earliest arrival. In this experiment, we confirmed that the execution time could be stably reduced compared with the conventional method in the environment where jitter was intentionally generated.

ABSTRACT. We propose a wireless bus interface that connects chips integrated side by side wirelessly. By forming on-chip coils along the outer periphery of each chip and using horizontal inductive coupling between the coils, high-speed communication between multiple chips is enabled. By using the proposed technique, it is possible to realize a high-performance embedded system of a freely configurable merely by arranging small chips having different functions side by side. In this paper, we show a theoretical analysis of inductive coupling between horizontal coils, results of electromagnetic field simulations, and circuit simulation results. The circuit simulation assuming a 45 nm CMOS process revealed that high-speed communication of 14.3 Gb/s/link is performed with power efficiency of 0.55 pJ/b which is comparable to that of wired communication technology. Furthermore, evaluation results with a prototype board are shown. Data is transferred via the coil on the prototype board, indicating that the proposed technique is effective even in noisy real-world environments.

ABSTRACT. In the era of multi-/many-core processors, there are increasing needs for middleware of high-performance computing to exploit both inter-node and intra-node parallelism. To overlap communication and computation efficiently, many studies have focused on MPI+ULT, a combination of MPI for inter-node parallelism and user-level threads (ULTs) for intra-node parallelism. ULTs are more lightweight than kernel-level threads, and thread creation and context switching can be done with a smaller overhead. MPI+ULT systems are equipped with communication-computation overlap mechanism taking advantage of the flexibility of ULTs. However, there are mainly two problems in the existing implementations. First, the use of MPI_THREAD_MULTIPLE to invoke MPI functions from multiple threads causes a performance bottleneck. Second, some MPI+ULT systems focus on the use of non-blocking communication and programmers have to manage both the start and the end of communication explicitly. To solve these problems, we introduce the high-performance MPI+ULT implementation MPI+myth. MPI+myth focuses on implicit overlapping communication and computation without any code modifications to the applications. Furthermore, it can avoid the overhead of multi-threaded MPI invocations using a communication dedicated thread and adopts a new scheduling technique which achieves efficient load balancing by avoiding a situation that a core is occupied by blocking ULTs. In the evaluation, we demonstrate significant performance improvement compared with the existing hybrid programming methods using several microbenchmarks and one mini application miniFE. In addition, we illustrate that MPI+myth has the potential to overlap communication and computation and our new ULT scheduling technique can achieve load balancing more efficiently than existing ULT scheduling techniques.

ABSTRACT. Razor はタイミング障害の検出/回復のための代表的な手法である．本稿では，Razor をRISC-V コアの Rocket に適用する．Rocket は一種のアウトオブオーダースカラプロセッサであり，このことが Razor への適用において問題である．その問題点を明確にし，解決方法を示す．また，Razor 適用による性能の変化について評価する．

ABSTRACT. The benefits of low power consumption and cost reduction by miniaturization of semiconductors are fading away. Therefore, a paradigm shift towards computing infrastructures prioritizing low power and easy-to-estimate performance on the edge side is arising at the expense of programmability. Systolic array architecture is one of candidates for such types of still programmable accelerators. However, we have many issues such as (1) scalability to meet performance demand is required on the edge side without increasing the number of external memory buses for cost reduction; (2) straightforward 2D implementation leads to low frequency and low performance per area due to many long wires, and self-loop operations such as floating-point accumulation interfere pipeline execution; (3) accelerating innermost loops is insufficient for matrix multiplication or convolution operation with short vector length. In this paper, in order to improve the scalability and area efficiency of systolic arrays for edge side, (1) cascaded multichip structure as an AXI slave and intra-chip multi-bus structure ensuring scalability without increasing the number of external memory bus; (2) column multithreading for reducing the number of physical columns to avoid performance degradation due to long wires and self-loop accumulation; (3) multilevel loop controller and adaptive map shifter for reducing startup overhead; are proposed. We designed a systolic array with single column x 64 rows as AXI4 slave by Verilog HDL, estimated the operating frequency and performance by using a prototype system on FPGA, and evaluated the area with TSMC 28nm library and memory generator. We found (1) the execution speed of a matrix multiplication / a convolution operation / a light-field depth extraction with the size larger than the capacity of the local memory is 6.3x / 9.2x / 6.6x compared with conventional systolic array (EMAX); (2) the speed with four chips configuration is 19.6x / 16.0x / 8.5x; (3) the size of the single chip is 8.4mm^2 (0.31x of EMAX) and the basic performance per area is 2.4x.

ABSTRACT. STRAIGHTはオペランドをレジスタの名前ではなく命令間の距離で表すことにより，命令間に偽の依存が生じない命令セットである． これは偽の依存を除去するレジスタリネーミングを不要にするため，電力効率を改善しつつ従来より高い性能を出すことのできる． しかしオペランドを距離で表す制約により，STRAIGHTでは従来アーキテクチャと比べ30%程度実行命令数が増加する． これは，STRAIGHTでは長寿命なレジスタ値を保持するために定期的な命令実行が必要なことが原因である． 本稿では，STRAIGHTのレジスタリネーミングが不要という特徴を損なわないまま，寿命・使用用途ごとにレジスタを論理的に分割する命令セットアーキテクチャの改良を提案する． コンパイラが静的にレジスタ値の寿命を予測し適切なレジスタに割り付けることにより，長寿命なレジスタ値を保持するために実行命令数が増えることを避けることができる． まずこの命令セット向けの最適化コンパイラを実装し，STRAIGHTアーキテクチャと比べ実行命令数を削減できることを確認した． またプロセッサシミュレータによる初期評価を行ったところ，その性能はSTRAIGHTと比べ3-10%，従来アーキテクチャと比べた場合には20%程度高いことを示した．

ABSTRACT. テンソル分解は，複雑なデータを取り扱う手法として注目されている。本発表では，テンソル分解の代表例の一つである，ALS（Alternating Least Square）法を用いた密テンソルのCP分解に着目する。ALS法では，MTTKRP（Matricized Tensor Times Khatori-Rao Product）と呼ばれる処理が計算時間の大半を占めることが知られている。一方で，MTTKRPに関して，最近のマルチコアCPUの特徴を考慮した実装方法や性能特性については，現状，情報が乏しい。そこで，最近のマルチコアCPU上でALS法を実装し，MTTKRPの性能を中心に，その性能を分析する。そして，より効率的な実装に向けた検討を行う。

ABSTRACT. GPUは多数の計算ユニットを並列に動作させることによってパイプラインやメモリアクセスレイテンシを隠蔽し，CPUと比較して高いスループットを実現しているため，計算ユニットへ命令を割り当てるスケジューリングポリシーが重要である．そのため，近年様々なスケジューリングポリシーが研究されている．しかし，既存のGPUスケジューラは依存関係やメモリアクセスパターンなどの各プログラムが持つ様々な特徴を考慮せずにすべてのプログラムに対して同じスケジューリングポリシーを適用しているため，GPUの計算ユニットが常に使いきれているとは限らない．そこで本論文では，メモリアクセスに着目して静的解析を行い，その結果に基づき，プログラムごとにスケジューリングポリシーを選択する手法を提案する．提案手法では，コンパイラが出力するアセンブリコード内の同一アドレスに対する平均メモリアクセス回数から見積もったデータ局所性の大小に応じて，適切なスケジューリングポリシーを判定する．しかし，静的解析では，ループや条件分岐などによるアクセス回数の変動を追跡しきれない．そのため，ループや条件分岐内で発生するアクセスは，そのネストの深さに応じた重み付けをした上で平均アクセス回数をカウントする．更に，静的解析の結果に基づいてスケジューリングポリシーを切り替えるために，GPUスケジューラを拡張する．提案手法を用いて評価を行った結果，既存のGPUスケジューラと比較して34:2%の実行時間の削減を果たすことができた

ABSTRACT. Hierarchical matrix (H-matrix) is an approximated form to represent N*N correlations of N objects. H-matrix construction is done by partitioning a matrix into submatrices, followed by calculating element values of these submatrices. This thesis proposes implementations of matrix partitioning using task parallel languages, Cilk Plus and Tascell. Matrix partitioning is divided into two steps: cluster tree construction by dividing objects into clusters hierarchically, and block cluster tree construction by finding out all cluster pairs at the same level of the cluster tree that satisfy an admissibility condition. Because the two kinds of trees constructed and traversed in these steps are unpredictable unbalanced, it is expected that we can parallelize these both steps efficiently using task parallel languages. To obtain sufficient parallelism in the cluster tree construction, we not only execute recursive calls in parallel, but also parallelize the inside of each recursive step. In the block cluster tree construction, we assigned each worker its own space so that the workers can store the cluster pairs without using locks. As a result, comparing to a sequential implementation in C, we achieved up to 11.7-fold speedup using Cilk Plus and 12.6-fold speedup by Tascell for the cluster tree construction. For the block cluster tree construction, up to 39.1-fold speedup by Cilk Plus and 42.1-fold speedup using Tascell are achieved. In regard to the whole process of matrix partitioning, we achieved up to 12.5-fold speedup by Cilk Plus and 13.7-fold speedup using Tascell. All the experiments are executed on two 18-core Xeon processors with real data sets to generate coefficient matrices used in the surface charge method.

ABSTRACT. データベースシステムのトランザクション処理における並行実行制御(Concurrency Control, CC) プロトコルは，性能を高めるべくトランザクションを並行に実行しながらも，直列化可能性 (serializablility) を担保することを目的としている．その理論的枠組みとして，これまでにページモデルを用いたスケジュールおよび serializability の定式化がなされ，その結果のうち，特に複数バージョン(Multi-version) スケジュールを対象としたserializability の定義である MVSR やその部分空間である CSR は今でも実用的である．2PL プロトコルが生成するスケジュール空間は CSR に含まれることが分かっており，2PL は特に追加の判定等をする必要がないため広く使われてきた．一方，スケジュールが MVSR であるかどうかを判定するほぼ唯一の既存手法は，有向グラフ構造 MVSG に循環がないことを確かめることであり，必ずしも実用的な CC プロトコルにとって使いやすいとは言えない．また，メニーコアアーキテクチャを前提としたインメモリ DBMS 向けに近年提案されている CC プロトコルの一部は CSR よりも広いスケジュールを生成するが，具体的に MVSR のどの部分空間に含まれるかという解釈は難しかった．本稿では，MVSR やその部分空間と等価なスケジュール空間を表現する新たな serializability 判定手法として，時刻割り当てルール(Timestamp Mapping Rules, TMR) を提案する．TMR によるスケジュール空間の定義と既存の定義との等価性を示し，部分空間の包含関係を包括的に整理する．

ABSTRACT. NoSQL データベースは，高い性能やスケーラビリティによってソフトウェアのバックエンドとして広く使用されている．そして，そのスキーマ設計は性能を引き出すために非常に重要な課題である．しかし，手動での設計で性能を十分に引き出すことは困難であるため，スキーマ推薦フレームワークによる自動最適化が求められている．既存手法では対応できるスキーマが限られるため，更新処理のために正規化が必要な状況下においてクエリの応答時間が著しく増加する問題が生じる．本稿では Secondary Index の活用を考慮した NoSQL データベースのスキーマ推薦によりクエリ処理の高速化を図る．具体的にはクエリ処理に活用できる Column Family, Secondary Index を列挙し，それらを使用するクエリプランの最適解を整数線形計画法によって探索する．これにより，更新処理を効率的に行うためにスキーマの正規化が必要な状況下においても，頻度の高いクエリに対しては1つの Column Family により応答し，頻度の低いクエリに対しては Secondary Index を活用することでクエリ処理を高速化する．評価実験により，更新処理が多い場合に相当する厳しい容量制限下において，ワークロードのクエリへの応答時間の平均値を既存手法に対して73.5%低減可能であることを確認した．

ABSTRACT. イベントデータを取集、蓄積、分析を行うシ ステムにおいてデータ分析を行うさい、データ が持つ構造をスキーマとして定義し、データを 分析用にテーブル構造として配置、クエリーを 用いてアクセス、分析することが多い。ここで、 データ分析のためにはスキーマ情報が必要にな るが、データ収集から始まり、蓄積、分析に至 るまでのどの時点で分析用スキーマを適用する かについて、以下に示す戦略がある。 1.1 生データによる Schema-on-read では、 データ分析段階までスキーマ定義が要らないこ とから、データ構造に囚われずに多様なデータ を保存でき、また、データ分析ニーズの変化に 応じて柔軟に対応できる。さらに、スキーマ同 期などの管理が要らないため、システムをシン プルに構築することで運用コストを減らせるな どの利点がある。一方、データ利用時において、 データを分析用に変換する必要があり、性能の 面で問題がある。 1.2 カラムナフォーマットによる Schema-on- write では、スキーマを用いたカラムナフォー マットを用いて分析用にデータを調整すること で、CPU やメモリの利用効率を上げられる。 一方、生データを保管するための一次ストレー ジが必要である。また、データを蓄積する前に 分析用スキーマを決めることがむずかしく、ス キーマ変更や保存時と分析時のスキーマ同期な どの管理が必要となることから、システム設計、 導入、運用における障害となっている。 一般的には、データの変更頻度やデータ分析 用途に応じて上記のいずれかが用いられてきた が、それぞれ利点、欠点があった。これに対し て、我々は 1.3 カラムナフォーマットによる Schema-on-read を可能にする、スキーマレスカラムナフォーマット “Yosegi” を開発した。 これによって、カラムナフォーマットの利点と Schema-on-read の持つ利便性の両方を実現で きた。 本論文では、Yosegi の実現方法、既存カラ ムナフォーマットとの性能比較について述べた 後、Yahoo! JAPAN におけるデータ分析基盤 に適用した事例について紹介する。

ABSTRACT. STRAIGHTはオペランドをレジスタの名前ではなく命令間の距離で表すことにより，命令間に偽の依存が生じない命令セットである． これは偽の依存を除去するレジスタリネーミングを不要にするため，電力効率を改善しつつ従来より高い性能を出すことができる． しかしオペランドを距離で表す制約により，STRAIGHTでは従来アーキテクチャと比べ30%程度実行命令数が増加する． これは，STRAIGHTでは長寿命なレジスタ値を保持するために定期的な命令実行が必要なことが原因である． 本稿では，STRAIGHTのレジスタリネーミングが不要という特徴を損なわないまま，寿命・使用用途ごとにレジスタを論理的に分割する命令セットアーキテクチャの改良を提案する． コンパイラが静的にレジスタ値の寿命を予測し適切なレジスタに割り付けることにより，長寿命なレジスタ値を保持するために実行命令数が増えることを避けることができる． まずこの命令セット向けの最適化コンパイラを実装し，STRAIGHTアーキテクチャと比べ実行命令数を削減できることを確認した． またプロセッサシミュレータによる初期評価を行ったところ，その性能はSTRAIGHTと比べ3-10%，従来アーキテクチャと比べた場合には20%程度高いことを示した．

ABSTRACT. キャッシュ圧縮技術はキャッシュの容量を擬似的に数倍に増大させる手法だが, キャッシュ置換アルゴリズムと競合し得る. そこで, キャッシュ圧縮によって生じる余剰領域を, 追い出された後のキャッシュ・ラインを一時的に格納するビクティム・キャッシュとして利用し, 正規のキャッシュ置換アルゴリズムに干渉させない手法が提案されている. しかし, キャッシュ置換アルゴリズムによるキャッシュ・ラインの評価が正しければ, 余剰領域のキャッシュ・ラインが参照される可能性は低い. 一方, プリフェッチ技術は予測精度が高いと有効的な手法だが, キャッシュ・ポリューションを起こすことが知られている. そこで, 本研究ではキャッシュ圧縮によって生じる余剰領域を用いて, キャッシュ・ポリューションを防ぐ仮想的なプリフェッチ・バッファを実現する手法を提案する. RISC-V プロセッサ上に提案手法を実装してSPEC CPU2017をシミュレートした結果，非圧縮キャッシュに対して幾何平均でMPKIを約12％削減し, IPCを約15％向上することを示した. また, SPEC CPU2017でのプリフェッチによるキャッシュ・ポリューションを調査し, 約18％削減することを示した

ABSTRACT. 高性能なプロセッサでは，あらかじめ必要なデータを予測してキャッシュに挿入しておくために，プリフェッチャというハードウエアが設けられている．プリフェッチャはキャッシュの有効利用を促進することでプロセッサの性能向上に寄与するが，一方でキャッシュ・ポリューションや主記憶へのアクセスの帯域幅の占領といった，プロセッサの性能を低下させる事象を引き起こすことがある．この対策として，プリフェッチャを動的に制御するさまざまな手法が提案されている．本論文では，プリフェッチャを動的に制御する手法で用いられている指標からプリフェッチャの精度とカバレッジを取り上げ，これらがプリフェッチャを動的に制御するうえで必ずしも有用とはいえないことを示した．また，フェーズ検出を用いてプロファイルを作成し，それを利用してプリフェッチャの組み合わせを動的に切り替えるプリフェッチ制御手法を提案した．提案手法はSPEC CPU2006のベンチマークのうちいくつかのベンチマークにおいて有意にプリフェッチャの組み合わせを切り替えることができた．

ABSTRACT. マルチコア環境では一般に,ロックを用いて共有変数へのアクセスを調停する.しかし,ロックにはデッドロックの発生や並列度の低下などの問題があるため,ロックを代替・補完する並行性制御機構として,トランザクショナルメモリ( TM )が提案されている.この機構をハードウェア上に実装したハードウェア・トランザクショナルメモリ( HTM )では,トランザクション( Tx )同士を投機的に並列実行することで,ロックに比べ並列度が向上する. HTM におけるバージョン管理,および競合検出のための機構には,それぞれに Eager 方式と Lazy 方式が存在し,それらの組み合わせにより, HTM には 3 つのポリシーが存在する.これら 3 つのポリシーはそれぞれアクセス競合の解決方式に違いがあり,これが実行時間に与える影響を調査した結果,プログラム毎に最適なポリシーが異なることを確認した.本論文では,トランザクションのメモリアクセスパターンを解析して得た指標に基づき,プログラムの実行中にポリシーを最適なものに切り替える手法を提案する.評価の結果,評価に用いた全てのプログラムにおいて最適なポリシーを選択可能であることを確認した.

ABSTRACT. 近年，モバイル端末の普及に伴い，高速かつ省電力に動作するプロセッサが求められている．プロセッサの高速化にはSIMDやスーパスカラなどの命令間の並列性に着目した高速化手法が注目されてきた．並列化による高速化が注目される一方で，計算再利用に基づいた高速化手法を採用した自動メモ化プロセッサが提案されている．並列化と計算再利用は処理全体の総量が変化するか否かという点で異なる．計算再利用は実行自体を省略することで，処理に必要な消費エネルギーを削減でき，省電力化に対して有効となる可能性がある．以前にも自動メモ化プロセッサの省電力化の研究は行われてきたが，ベースアーキテクチャは単命令発行型を前提としており，現代の一般的なスーパスカラ型アーキテクチャとは異なる． そこで本論文では，スーパスカラ型自動メモ化プロセッサでの電力評価を行い，計算再利用が省電力に対して有効であるか検討した．その結果，メモ化を適用しない場合と比較して，スーパスカラ型自動メモ化プロセッサにおける消費エネルギーは，最大 5.0 減少，平均 19.6 ％増加という結果になり，計算再利用が省電力化に対するポテンシャルを有することが確認できた．

ABSTRACT. 防犯カメラなどの動画像データが活用されるようになってきたが，動画像解析に要する通信量や計算量，プライバシーに関する問題が介在している．また，ディープラーニング技術が画像認識や音声認識を始めとする様々な分野に応用されているが，正確な認識処理を行うためには大量のデータの収集，処理が必要となるため，リアルタイムに解析するのは非常に困難である．本研究では，動画像をリアルタイムに解析し，動作の識別を行うことを目標として，姿勢推定ライブラリOpenPoseとディープラーニングフレームワークKerasを用いた機械学習手法について考察した． 画像1枚から抽出した特徴量のみを使用した学習では，約80%の精度で動作を識別することが可能であることがわかった． 次に，同じ動画から取得した10枚の画像の時系列を考慮した特徴量データを使用して動作の識別精度を測定したところ，画像1枚の識別と比較して識別精度は低下した． 実験結果をもとに，その原因と識別精度を向上させる手法について考察する．

ABSTRACT. Partial differential equations (PDEs) are often used as mathematical models in various fields of science and engineering, and numerical solutions of PDEs are one of the most computation-intensive tasks in scientific and engineering applications. On the other hand, recently, deep-learning technique is widely used in many applications, e.g. computer vision, image recognition, natural language processing, computer games, robots, self-driving cars, etc. Solving PDEs by deep-learning technique has been also considered in various forms recently. Based on the previous studies, in this preliminary study, two kinds of applications (1. conventional convolutional neural network for a Poisson equation and 2. deep Galerkin method for some parabolic partial differential equations) of deep-learning technique to solving PDEs is examined. Predicted solutions by the neural network can roughly capture the feature of numerical solutions by finite-difference method which is regarded as true solutions.

ABSTRACT. 深層ニューラルネットワークの学習高速化の必要性に伴い、ラージバッチ学習と呼ばれるデータ並列型の分散深層学習が注目されているが、訓練データ以外のデータに対する汎化性能が劣化することが知られている。汎化性能改善のため、学習に用いるデータの拡張を行うData Augmentationなどの手法が用いられている。本研究では、2つの訓練データを線形補間し新しい1つの訓練データとして学習に用いるMixupと呼ばれる手法について着目する。MixupはData Augmentation手法の一種として汎化性能の改善のみが注目されているが、1つの訓練データは2つの訓練データから生成されているとみなせるため、反復数単位で高速な収束が期待できる。複数のモデル・データセットにおいて評価実験を行い検証を試みた。

ABSTRACT. Hierarchical matrix (H-matrix) is an approximated form to represent N*N correlations of N objects. H-matrix construction is done by partitioning a matrix into submatrices, followed by calculating element values of these submatrices. This thesis proposes implementations of matrix partitioning using task parallel languages, Cilk Plus and Tascell. Matrix partitioning is divided into two steps: cluster tree construction by dividing objects into clusters hierarchically, and block cluster tree construction by finding out all cluster pairs at the same level of the cluster tree that satisfy an admissibility condition. Because the two kinds of trees constructed and traversed in these steps are unpredictable unbalanced, it is expected that we can parallelize these both steps efficiently using task parallel languages. To obtain sufficient parallelism in the cluster tree construction, we not only execute recursive calls in parallel, but also parallelize the inside of each recursive step. In the block cluster tree construction, we assigned each worker its own space so that the workers can store the cluster pairs without using locks. As a result, comparing to a sequential implementation in C, we achieved up to 11.5-fold speedup using Cilk Plus and 12.6-fold speedup by Tascell for the cluster tree construction. For the block cluster tree construction, up to 37.7-fold speedup by Cilk Plus and 38.8-fold speedup using Tascell are achieved. In regard to the whole process of matrix partitioning, we achieved up to 12.2-fold speedup by Cilk Plus and 14.5-fold speedup using Tascell. All the experiments are executed on two 18-core Xeon processors with real data sets to generate coefficient matrices used in the surface charge method.

ABSTRACT. 静止画や動画像を扱う情報機器の普及に伴い，マルチメディアアプリケーションを開発する機会が増加している．これらのアプリケーションの実行を高速化するためには，実行環境のコア数，キャッシュサイズおよびSIMDレジスタのサイズ等を考慮してプログラムを記述する必要があり，プログラム開発コストの大きさが問題となっている． そこで本研究では動画像処理プログラムの開発に特化したフレームワークを提案する．提案するフレームワークは，高い抽象度を持つ専用言語とその言語からプログラムや実行環境の特徴に応じた最適化が施されたプログラムへと自動変換する専用コンパイラから構成される．このフレームワークを用いることで，プログラマは実行環境の性能を十分に引き出す高性能なプログラムを容易に記述することが可能になる．

ABSTRACT. Work stealing, which is a popular scheduling algorithm for task parallelism, has an efficient dynamic load balancing functionality; however, it tends to damage the data locality and doesn't scale on many-core architectures with memory-bound applications. On the other hand, deterministic scheduling algorithms (e.g., static parallel for loop) have good data locality, but they're intolerant to load imbalance emerged dynamically. This paper introduces Almost Deterministic Work Stealing (ADWS), which achieves both of these two requirements: good data locality and dynamic load balancing. ADWS consists of two parts: (i) the deterministic task allocation, which deterministically distributes tasks to workers based on the amount of work of each task, and (ii) the hierarchical localized work stealing, which compensates load imbalance emerged dynamically in a locality-aware way. In ADWS, programmers have to specify the amount of work of each task, but specifying work is not so hard for programmers if possible. The experimental results show ADWS is nearly 6 times faster than the traditional work stealing scheduler at maximum with memory-bound applications, and even if the work specified by programmers is not precise, the dynamic load balancing works well while maintaining most of the data locality.

ABSTRACT. Infiniband has characteristics of low latency and high bandwidth compared to Ethernet, and we want to make the most of it. The MPI library exists as a de facto standard of communication libraries for HPC applications. In this study, however, we use the Infiniband Verbs API to control the communication more directly and hide the communication time.

In IP communication, a socket is used as an endpoint of the connection. On the other hand, in Infiniband, Queue Pair (QP) is used. Several types of communication can be handled by Verbs, among which Reliable Connection (RC) communication has retransmission control, and communicates with a specific partner for each QP. On the other hand, in Unreliable Datagram (UD) communication, acknowledgments are not required, although there is a possibility of data loss. In addition, since the destination can be specified for each transmission for the same QP, there is no need to generate QP for each communication partner. This enables a memory saving communication even when the number of nodes is very large. The existing practical MPI libraries use RC communication. In this study, however, we try to take advantage of the fact that data loss in UD communication is rare, so that we can utilize UD communication with a minimized number of acknowledgments.

Also, we focus on multiplexing communication, that is, take a strategy to do the same calculation in parallel and to communicate the results between nodes and to adopt the earliest arrival. In this experiment, we confirmed that the execution time could be stably reduced compared with the conventional method in the environment where jitter was intentionally generated.

ABSTRACT. In the era of multi-/many-core processors, there are increasing needs for middleware of high-performance computing to exploit both inter-node and intra-node parallelism. To overlap communication and computation efficiently, many studies have focused on MPI+ULT, a combination of MPI for inter-node parallelism and user-level threads (ULTs) for intra-node parallelism. ULTs are more lightweight than kernel-level threads, and thread creation and context switching can be done with a smaller overhead. MPI+ULT systems are equipped with communication-computation overlap mechanism taking advantage of the flexibility of ULTs. However, there are mainly two problems in the existing implementations. First, the use of MPI_THREAD_MULTIPLE to invoke MPI functions from multiple threads causes a performance bottleneck. Second, some MPI+ULT systems focus on the use of non-blocking communication and programmers have to manage both the start and the end of communication explicitly. To solve these problems, we introduce the high-performance MPI+ULT implementation MPI+myth. MPI+myth focuses on implicit overlapping communication and computation without any code modifications to the applications. Furthermore, it can avoid the overhead of multi-threaded MPI invocations using a communication dedicated thread and adopts a new scheduling technique which achieves efficient load balancing by avoiding a situation that a core is occupied by blocking ULTs. In the evaluation, we demonstrate significant performance improvement compared with the existing hybrid programming methods using several microbenchmarks and one mini application miniFE. In addition, we illustrate that MPI+myth has the potential to overlap communication and computation and our new ULT scheduling technique can achieve load balancing more efficiently than existing ULT scheduling techniques.

ABSTRACT. GPUは多数の計算ユニットを並列に動作させることによってパイプラインやメモリアクセスレイテンシを隠蔽し，CPUと比較して高いスループットを実現しているため，計算ユニットへ命令を割り当てるスケジューリングポリシーが重要である．しかし，既存のGPUスケジューラは依存関係やメモリアクセスパターンなどの各プログラムが持つ様々な特徴を考慮せずにすべてのプログラムに対して同じスケジューリングポリシーを適用しているため，GPUの計算ユニットが常に使いきれているとは限らない．そこで本論文では，メモリアクセスに着目して静的解析を行い，その結果に基づき，プログラムごとにスケジューリングポリシーを選択する手法を提案する．提案手法では，コンパイラが出力するアセンブリコード内の同一アドレスに対する平均メモリアクセス回数から見積もったデータ局所性の大小に応じて，適切なスケジューリングポリシーを判定し，その結果に基づいてスケジューリングポリシーを切り替えるために，GPUスケジューラを拡張する．提案手法を用いて評価を行った結果，既存のGPUスケジューラと比較して34.2%の実行時間の削減を果たすことができた．

ABSTRACT. Domain Specific Language is a promising approach to achieve programmability and portability of scientific program codes and obtain reasonable performance. However, DLS platforms themselves are often lack portability. To solve this issue, we have been developing a platform to construct DSLs that optimize and adapt the scientific computation kernel codes recursively concerning the hierarchal structure of HPC systems. On our platform, the optimization and adaptation system is modularized as aspects, which is a type of objects on Aspect-oriented Programming, corresponding to each layer of HPC system(like node-level parallelism by MPI, thread-level parallelism by OpenMP, accelerator-level parallelism by OpenACC, and so on). Therefore system designers can construct the DSL platforms for their HPC system by combining the modules provided by DSL developers using our platform. In this poster, our platform demonstrated by constructing a simple DSL for stencil computation.

ABSTRACT. The Pfaffian is a homogeneous polynomial defined for a skew-symmetric matrix. The Pfaffian has similar characteristics to determinants and square of the Pfaffian of a skew-symmetric matrix corresponds to its determinant. In physics fields, such as quantum field theory with lattice model, variational Monte Carlo method and topological quantum number, computing the Pfaffian is especially meaningful, and rapid computation of the Pfaffian contributes to further development of physics. Despite demand, there is few numeric calculation library for computing the Pfaffian, and any library cannot sufficiently exert computer performance. PFAPACK is a Pfaffian calculation library which has already applied to various studies and implements an algorithm with better computational complexity. However, the implementation is not suitable for current computer performance because parallel computing and data arrangement with high efficiency of access is not sufficiently considered. Therefore, in this study, the author develops a Pfaffian computation library optimized for current computer systems. In the development, the author tries to improve the data access speed by optimizing data arrangement and considers of SIMD instructions and hierarchical cache. The performance of the library is verified in comparison to existing libraries.

ABSTRACT. We propose a mapping operator generation method for the subspace correction applied to a sequence of linear systems whose coefficient matrices are similar or identical. In our method, we automatically construct the operator using the information obtained in the preceding solution steps. The operator is generated with minimum additional memory requirement through the sampling of approximate solution vectors and the use of the Rayleigh–Ritz’s method. Numerical tests using electromagnetic field analysis demonstrate the effectiveness of the proposed method.

ABSTRACT. 近年、IoTとして、スマートフォンや監視カメラから情報を収集し、高度交通システムや AR ゲームなどで活用することが期待されている。これらのアプリケーションでは、各種センサ情報を低遅延で処理する必要があり、エッジコンピューティングが注目されている。このエッジコンピューティングにおいて、プライバシーに関わる情報を複数のアプリケーションで連携して取り扱うためには、適切なアクセス制御が必要となる。そこで本研究では、宣言的アクセス制御ルールを記述可能なエッジ環境向け分散オブジェクトデータストアを提案する。本システムでは、複数のアプリケーションがデータストア上でデータを共有しており、アプリ開発者はスキーマ上にルールを記述することで，レコードへのアクセス制御を定義できる。これにより、アプリユーザはアプリケーションの友人関係などのデータに基づいて、位置情報などの個人情報を閲覧・購読する権限を与えることができる。

ABSTRACT. イベントデータを取集、蓄積、分析を行うシ ステムにおいてデータ分析を行うさい、データ が持つ構造をスキーマとして定義し、データを 分析用にテーブル構造として配置、クエリーを 用いてアクセス、分析することが多い。ここで、 データ分析のためにはスキーマ情報が必要にな るが、データ収集から始まり、蓄積、分析に至 るまでのどの時点で分析用スキーマを適用する かについて、以下に示す戦略がある。 1.1 生データによる Schema-on-read では、 データ分析段階までスキーマ定義が要らないこ とから、データ構造に囚われずに多様なデータ を保存でき、また、データ分析ニーズの変化に 応じて柔軟に対応できる。さらに、スキーマ同 期などの管理が要らないため、システムをシン プルに構築することで運用コストを減らせるな どの利点がある。一方、データ利用時において、 データを分析用に変換する必要があり、性能の 面で問題がある。 1.2 カラムナフォーマットによる Schema-on- write では、スキーマを用いたカラムナフォー マットを用いて分析用にデータを調整すること で、CPU やメモリの利用効率を上げられる。 一方、生データを保管するための一次ストレー ジが必要である。また、データを蓄積する前に 分析用スキーマを決めることがむずかしく、ス キーマ変更や保存時と分析時のスキーマ同期な どの管理が必要となることから、システム設計、 導入、運用における障害となっている。 一般的には、データの変更頻度やデータ分析 用途に応じて上記のいずれかが用いられてきた が、それぞれ利点、欠点があった。これに対し て、我々は 1.3 カラムナフォーマットによる Schema-on-read を可能にする、スキーマレスカラムナフォーマット “Yosegi” を開発した。 これによって、カラムナフォーマットの利点と Schema-on-read の持つ利便性の両方を実現で きた。 本論文では、Yosegi の実現方法、既存カラ ムナフォーマットとの性能比較について述べた 後、Yahoo! JAPAN におけるデータ分析基盤 に適用した事例について紹介する。