Hiroki HONDA (本多 弘樹)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 14000000, indirect: -)
A high-performance software distributed shared memory (DSM) system with performance scalability, named Mocha, was implemented as an experimental prototype aiming at the usefulness of supercluster systems. The current version of Mocha works on a 32 node cluster on the Linux environment. The source program has been opened in public domain via web. A scheme for suppressing communication overhead, which is mainly caused by maintaining data consistency among shared data located at distributed memories, is proposed and slotted in Mocha. The effectiveness is evaluated by using some benchmark programs. A tool for performance debugging of application programs and constructing an efficient software DSM, named S-Cat, was implemented, which has such functions as showing visually communication locus among processors during execution process of an application program. S-Cat was used in efficient implementation of Mocha and performance tuning of application programs on Mocha.
The main research results are as follows:
1.Implementation of a low communication overhead software DSM, named Mocha
2.Comparison study of different software DSMs on the same cluster
3.Proposal of coarse-grain parallel processing on software DSM
4.Construction of a visualization tool for software DSM, named S-Cat
5.Proposal of parallel processing on graphic processor and off-the-shelf processor
Some technical issues toward realization of high-performance software DSMs for supercluster systems are made clear. "Hierarchical paradigm" for controlling multiple clusters was proposed, but its usefulness cannot be verified during this research period.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (A), Fund Type: -, Overall Grant Amount: - (direct: 26900000, indirect: 8070000)
We have studied the OpenMP programming environment for the next generation 64-bit high-performance clusters, by using software distributed shared memory (SDSM) system to enable OpenMP program to run on the cluster. We have also developed a programming support system for OpenMP, and numerical libraries using OpenMP.
1.We ported the SCore cluster system software to 64-bit processor architectures. We conducted the performance evaluation of SCASH DSM system which runs on SCore.
2.We have designed and implemented a very portable SDSM system, SCASH-MPI which uses MPI as its communication layer. MPI is the most portable communication library supported for many kinds of high-speed communication network, so that this approach provide highly portability It allows the users to make use of wide address space in 64-bit processor. We found that the overhead of this implementation is just 6% comparing to the original SCASH.
3.We have designed a new SDSM system, FDSM, by using the access pattern analysis of applications. The access pattern is detected by a hardware mechanism provided by IA64, and is used for efficient communication. It achieves more performance than SCASH.
4.We have studied the optimization of OpenMP program running a DSM system of heterogeneous clusters. We found that the performance can be improved by the combination of the loop re-partitioning and the page migration.
5.We have designed and implemented the interactive tool, OMP/iPat, to support the programmer for OpenMP program developments. It allows the programmer to develop his OpenMP program interactively using the information from parallelism analysis by the compiler.
6.We have conducted the performance evaluation by using the OpenMP benchmark, SPEC-OMP. We have designed and implemented an algorithm of parallel recursive FFT by using OpenMP for IA-64 shared memory multi-processors.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 13900000, indirect: -)
We aim to establish the fundamental technology of parallelizing compilers with a granularity tuning mechanism for efficient parallel processing. The parallelizing compiler generates a parallel object program, which will be executed in the shortest time on a parallel computer, by matching its hardware characteristics with parallel properties of a given application program. The main results are as follows :
1. A new static parallelizing scheme is proposed, in which apart of a target sequential program is divided into parallel tasks with optimal granularity by using the LogP model as an abstract parallel machine. Do loops, do across loops and recursive function calls are applied for granularity tuning, and evaluation studies are carried out on some different parallel computers.
An efficient execution mechanism for coarse-grain parallel processing is proposed for distributed memory parallel computers. The mechanism can be realized to transform a given sequential program into a coarse-grain task graph with execution start conditions as well as data reaching conditions as a function of parallelizing computers.
3. A parallelizing compiler with a coarse-grain parallel processing function is experimentally constructed. The conventional Open MP compiler is utilized to translate the coarse-grain task graph with Open MP primitives into an executable parallel C program.
4. A novel software distributed shared memory (SDSM) is proposed, which reduces memory consistency overhead by reflecting characteristics of application programs at a middleware level. The SDSM scheme is implemented in such parallel machine environment as a heterogeneous workstation cluster and an SMP-type personal computer cluster.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 奨励研究(A), Fund Type: -, Overall Grant Amount: - (direct: 2100000, indirect: -)
本研究は、本申請者がこれまでの研究で開発したFortranプログラム粗粒度タスクの並列処理方式を土台として、階層的並列処理実現に関する研究を行なったもので、以下の研究実績のとおりその目的を達成した。
1. 粗粒度並列処理の階層化の検討:
階層的並列処理は粗粒度タスクをプロセッサクラスタへ割り当て、プロセッサクラスタ内のプロセッサ群を利用して細粒度並列処理を行なうものである。細粒度並列処理においてはスタティックスケジューリングによりコンパイル時に静的にプロセッサに割り当てており、コンパイル時に割り当てが行なわれることを利用して、同期コードの挿入およびその最適化を行なっている。一方粗粒度並列処理においてはマルチプロセッサスケジューリングアルゴリズムを応用したダイナミックスケジューリング手法を用いることにより、実行すべきタスクが実行時に決定されるという問題に対処している。このため細粒度並列処理において必要となる同期情報をハードウェア同期機構に挿入することをプログラム実行時に動的に行なう必要がある。本研究ではone-PE同期機構、SBM同期機構、RBCQ同期機構を用いる細粒度並列処理と粗粒度並列処理を階層的に実現する手法を考案した。
2. 階層的並列処理を実現する自動並列化コンパイラの開発:
上記方式を実現する自動並列化コンパイラを作製した。本コンパイラでは逐次中間コードを生成の後、並列性解析を行ない、並列中間コードを生成する。また細粒度並列処理のための同期コードおよび粗粒度並列処理のためのダイナミックスケジューリングコードもコンパイラが生成する。これにより実行時ののオーバーヘッドを軽減することが可能となる。なお、本コンパイラは大規模なソフトウェアとなるため、PCを利用した複数人数による開発となるが、本補助金で購入した設備により開発した。
3. 実マルチプロセッサシステムの開発と性能評価:
本自動並列化コンパイラによる階層的並列処理を効率良く実現するハードウェア同期機構を実装した実マルチプロセッサシステムを開発しその上で本方式の有用性を検証した。
4. 研究成果のまとめと学会発表:
以上の一部をまとめ学会論文として発表した。

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 奨励研究(A), Fund Type: -, Overall Grant Amount: - (direct: 1000000, indirect: -)
本研究は、本申請者がこれまでの研究で開発したFortranプログラム粗粒度タスクの並列処理方式を土台として、階層的並列処理実現に関する研究を行なったもので、研究実績は次の通りである。
(1)細粒度並列処理と粗粒度並列処理の階層化の検討
階層的並列処理は粗粒度タスクをプロセッサクラスタへ割り当て、プロセッサクラスタ内のプロセッサ群を利用して細粒度並列処理を行なうものである。細粒度並列処理においてはコンパイル時に割り当てが行なわれることを利用して、同期コードの挿入を行なっている。一方粗粒度並列処理においてはダイナミックスケジューリング手法を用いることにより、実行すべきタスクが実行時に決定されるという問題に対処している。このため同期情報をハードウェア同期機構に挿入することをプログラム実行時に低オーバーヘッドに行なう必要がある。そこで本研究では同期情報の少ないRBCQ同期機構を考案した。
(2)階層的並列処理を実現する自動並列化コンパイラの開発
上記方式を実現する自動並列化コンパイラを作製した。対象プログラミング言語はC及びHigh Performance Fortranである。本コンパイラでは逐次中間コードを生成の後、並列性解析を行ない、並列中間コードを生成する。また細粒度並列処理のための同期コードおよび粗粒度並列処理のためのダイナミックスケジューリングコードもコンパイラが生成する。これにより実行時ののオーバーヘッドを軽減することが可能となる。なお、本コンパイラは大規模なソフトウェアとなるため、ワークステーションを利用した複数人数による開発となるが、本補助金で購入した設備により開発した。
(3)実マルチプロセッサシステム上での有効性評価
申請者が既に開発している実マルチプロセッサシステム上で本方式により各種アプリケーションプログラムを並列処理し、本自動並列化コンパイラによる階層的並列処理の有用性を検証した。
(4)研究成果のまとめと学会発表
以上の一部をまとめ学会に投稿し採録が決定した。
早川潔,本多弘樹「RBCQ同期機構およびその同期方式の提案と性能評価」並列処理シンポジウムJSPP '97論文集

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 7000000, indirect: -)
This research addresses to give granularity tuning mechanism for obtaining the maximum speed in parallel program execution on a distributed memory-type parallel computer. The mechanism requires to exploit parallelism in a program and divide the computation into subprograms (threads) of suitable granularity. Performance improvement can be achieved to allocate the suitable-size threads statically to each processing element of a parallel computer by efficiently utilizing its hardware's potential ability.
(1) Parallelizing compiler. We proposed a novel granularity tuning mechanism based on a LogP model, which is an abstract parallel computer model for analyzing execution time of a parallel program. The mechanism was experimentally installed in a SISAL compiler for a dataflow computer EM-X,and some evaluation study was carried out by executing benchmark programs with do-all loops and do-across loops.
(2) Performance debugging for parallel programs : A performance debugging system for a parallel program was developed, which shows an execution process of a parallel program as a form of a Gantt chart. A programr can find performance bottleneck by carefully checking the chart, and interactively change its execution sequence, as a result the parallel granularity, in order to obtain better performance. We proposed 3D animation technique based on a dynamical model, which is adopted to visualization of a process of parallel discrete event. A 3D visualization tool was developed and the utilization for parallel debugging was investigated.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 奨励研究(A), Fund Type: -, Overall Grant Amount: - (direct: 900000, indirect: -)
本研究は、本申請者がこれまでの研究で開発しFORTRANプログラム粗粒度タスクの並列処理方式を土台として、プログラム全域にわたる階層的並列処理実現に関する研究を行なったもので、研究実績は次の通りである。
(1)細粒度並列処理と粗粒度並列処理の階層化の検討
階層的並列処理は粗粒度タスクをプロセッサクラスタへ割り当て、プロセッサクラスタ内のプロッセッサ群を利用して細粒度並列処理を行なうものである。細粒度並列処理においてはスティックスケジューリングによりタスクをコンパイル時に静的にプロセッサに割り当てており、コンパイル時に割り当てが行なわれることを利用して、同期コードの挿入およびその最適化を行なっている。一方粗粒度並列処理においてはマルチプロセッサスケジューリングアルゴリズムを応用したダイナミックスケジューリング手法を用いることにより、実行すべきタスクが実行時に決定されるという問題に対処している。このため細粒度並列処理において必要となる同期情報をハードウェア同期機構に挿入することをプログラム実行時に動的に行なう必要がある。本研究ではone-PE同期機構ならびにSBM同期機構を用いる細粒度並列処理と粗粒度並列処理を階層的に実現する手法を考案した。
(2)階層的並列処理を実現する自動並列コンパイラの開発
上記方式を実現する自動並列化コンパイラを作製した。対象プログラミング言語はC及びHigh Performance Fortranである。本コンパイラでは逐次中間コードを生成の後、並列性解析を行ない、並列中間コードを生成する。また細粒度並列処理のための同期コードおよび粗粒度並列処理のためのダイナミックスケジューリングコードもコンパイラが生成する。これにより実行時ののオーバーヘッドを軽減することが可能となる。なお、本コンパイラは大規模なソフトウェアとなるため、ワークステーションを利用した複数人数による開発となるが、本補助金で購入した設備により開発した。
(3)実マルチプロセッサシステム上での有効性評価
申請者が既に開発している実マルチプロセッサシステム上で本方式により各種アプリケーションプログラムを並列処理し、本自動並列化コンパイラによる階層的並列処理の有効性を検証した。
(4)研究成果のまとめと学会発表
以上の成果をまとめて学会において発表を行なった。

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 一般研究(B), Fund Type: -, Overall Grant Amount: - (direct: 7100000, indirect: -)
主記憶共有マルチプロセッサシステム上でのFortranプログラムの並列処理では、従来よりマルチタスキングやマイクロカスキングなどの手法が用いられてきた.しかし,マルチタスキングでは,ユーザによる並列性指定が困難である,osコールなどによるスケジューリングオーバーヘッドが大きい等といった問題がある.マイクロタスキングは,最も広く用いられてきたループ並列化手法であるが,イタレーション間にまがる複雑なデータ依存やループ外への条件分岐によって並列化できないループが以前存在する.
これらに対して当研究者当は、マクロデータフロー処理手法を提案した.マクロデータフロー処理手法では,コンパイラがプログラムを粗粒度タスクへ分割し,粗粒度タスクの最早実行可能条件を解析することにより粗粒度のアスク間の並列性を自動抽出する.コンパイラが各ソースプログラム専用に生成したスケジューリングルーチンを用いることで,スケジューリングオーバーヘッドを抑えることができる.また,マクロデータフロー処理を行なう場合,各データをデータ転送を最小化するよう考慮し,各プロセッサ上のローカルメモリに配置(データローカライズ)することによって,より効率の良い並列処理が可能となる.
プロトタイプマルチプロセッサイステムOSCAR上での性能評価では,マクロデータフロー処理による粗粒度タスクの有効な並列処理を確認できた.また富士通VPP-500、Alliant FX/4、KSR1、NEC Cnju-3等,商用マルチプロセッサシステム上での性能評価でも,従来手法であるマルチタスキングおよびマイクロスタキングに比べ,マクロデータフロー処理の方が高い並列性の抽出が可能であることが分かった.さらに,それらの評価から従来手法に比べて低オーバーヘッドな処理を行なうことが可能で,プログラムの実行速度が向上することも確認された.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 奨励研究(A), Fund Type: -, Overall Grant Amount: - (direct: 900000, indirect: -)
本研究は、これまでの基礎研究で開発した細粒度と粗粒度タスクの並列処理方式を階層的に組み合わせた、プログラム全域にわたる階層的並列処理を実現する自動並列かコンパイラに関する研究を行ったもので、研究実績は以下のとおりである。
(1)細粒度並列処理と粗粒度並列処理の階層化方式の考案
階層的並列処理は粗粒度タスクをプロセッサクラスタへ割り当て、プロセッサクラスタ内のプロセッサ群を利用して細粒度並列処理を行なうものである。細粒度並列処理においてはスタティックスケジューリングによりタスクをコンパイル時に静的にプロセッサに割り当てており、コンパイル時に割り当てが行なわれることを利用して、同期コードの挿入およびその最適化を行なっている。一方粗粒度並列処理においてはマルチプロセッサスケジューリングアルゴリズムを応用したダイナミックスケジューリング手法を用いることにより、実行すべきタスクが実行時に決定されるという問題に対処している。このため細粒度並列処理において必要となる同期情報をハードウェア同期機構に挿入することをプログラム実行時に動的に行なう必要がある。本研究ではSBM同期機構を用いる細粒度並列処理のための同期方式を考案した。
(2)階層的並列処理を実現する自動並列化コンパイラの開発
上記方式を実現する自動並列化コンパイラを作製いた。対象プログラミング言語はC及びHigh Performance Fortranである。本コンパイラでは逐次中間コードを生成の後、並列性解析を行ない、並列中間コードを生成する。また細粒度並列処理のための同期コードおよび粗粒度並列処理のためのダイナミックスケジューリングコードもコンパイラが生成する。これより実行時ののオーバーヘッドを軽減することが可能となる。なお、本コンパイラは大規模なソフトウェアとなるため、ワークステーションを利用した複数人数による開発となるが、本補助金で購入した設備により開発した。
(3)実マルチプロセッサシステム上での有効性評価
申請者が既に開発している実マルチプロセッサシステム上で本方式により各種アプリケーションプログラムを並列処理し、本自動並列化コンパイラによる並列処理の有用性を検証した。
(4)研究成果のまとめと学会発表
以上の成果をまとめ学会において発表を行なった。このための出張費を本補助金により支出した。