Loop-Call Context Treeを用いたランタイムデータフロー解析

超並列マルチコア CPU やさらにアクセラレータを組み合わせた高度な並列処理に代表されるように、発熱やエネルギー浪費の原因となるプロセッサの動作周波数を増加させることなく処理性能を向上させる技術が急速に普及しつつある。しかしながら、現状では並列処理を効率的に行うためにはプログラマがアプリケーション全体の構造を正確に理解し効率的にハードウェアリソースに合わせて並列化することが必要であり、非常にコストのかかる経験的な作業であるといえる。さらに、アプリケーションプログラムは年々その規模と複雑さを増してきているため、大規模・複雑化するアプリケーションプログラムを生産的かつ効率的に並列化する手法を確立することが求められている。本稿ではループ階層構造に着目し大規模・複雑化するアプリケーションプログラムの生産的な並列化の支援を目的として、実行時にループ階層単位のデータ依存関係を示すデータフローを Loop-Call Context Tree を用いてモニターする機構を提案する。ループはプログラム中に様々な粒度で出現する構造であり、年々大規模・複雑化するアプリケーションにおいてもプログラムを適確かつ効率的に並列処理するための重要な手掛かりである。そこで、本研究においては、コンパイル後のバイナリコードからプログラム中に現れるループ構造を抽出すると同時にメモリを介したデータ依存をプログラムの実行時に抽出する機構を動的バイナリトランスレーション技術を用いて構築する。評価環境を構築し評価を行った結果、バイナリコードを入力として実行時にループ階層構造およびループ領域毎のメモリを介したデータ依存関係を抽出可能であることを確認した。Advances in parallel processing techniques such as a combination of massively parallelized multicore CPUs and accelerators make it possible to keep performance improvements. However, programmers must fully understand all of program structures across an application in order to perform effective parallel processing, and these said to be emprical and time-consuming processes for them. Additionally, since current application programs become large and complex year by year, we need to realize a productive and effective mechanism that can parallelize large and complex application programs. In this paper, we present a mechanism that monitors runtime data flow using Loop-Call Context Tree. Here, we focus on loop nesting structures which are one of the primary hints for finding parallelism. Using pre-compiled binary codes as an input, we extract loop nesting structures, and at the same time monitor data dependencies through memory access using dynamic binary translation system. We implement our mechanism and evaluated it. From the results, we confirm that we can extract loop nest structures and data depencencies among loop regions.