著者

石坂 一久 中野 啓史 八木 哲志 小幡 元樹 笠原 博徳

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.4, pp.958-970, 2002-04-15

被引用文献数

19

---

主記憶共有型マルチプロセッサシステムは幅広く使われているが,プロセッサ数の増加にともないその最大性能と実効性能の差が拡大してきている.このような問題を解決するためには,従来のループ並列処理に加えて,粗粒度タスク並列性,近細粒度並列性などのマルチグレイン並列性の利用が重要な技術である.また,プロセッサ技術の進歩とともに,プロセッサとメモリの速度差が顕在化し,その速度差を補うためのメモリ階層,特にキャッシュの有効利用は,マルチプロセッサシステムの性能向上に重要な要因となっている.本論文では,ループ並列化に加えプログラムを基本ブロック,ループ,サブルーチンといった粗粒度タスク(マクロタスク)に分割し,それらの間の並列性を効果的に利用するとともに,従来OSCAR型マルチプロセッサアーキテクチャにおけるローカルメモリおよび分散共有メモリ用に提案されていたデータローカライゼーション手法を主記憶共有型マルチプロセッサ上のキャッシュ最適化用に発展させたデータ分散・ダイナミックスケジューリング手法を提案する.本手法はOSCARマルチグレインコンパイラ上で実現され,逐次FORTRANプログラムを入力すると,共有メモリマシンにおける標準APIであるOpenMPを用いて複数マクロタスク間でキャッシュ上の共有データを再利用する並列化コードを自動生成する.本手法の評価を商用SMPマシンであるIBM RS/6000 604e High Node,Sun Ultra80上でspec95fpベンチマークのtomcatv,swim,mgridを用いて行った結果,IBM RS/6000上ではIBM XL FORTRAN version 6.1コンパイラの自動ループ並列化を行った場合の最小実行時間に対して本手法は最大5.8倍の性能向上を示し,Sun Ultra80上ではSun Forte 6 update 1コンパイラの最小時間に対して最大3.6倍の性能向上が得られることが確かめられた.In multiprocessor systems,the gap between peak and effective performance has getting larger.To cope with this performance gap,it is important to use multigrain parallelismin addition to ordinary loop level parallelism.Also, effective use of memory hierarchy is importantfor the performance improvement of multiprocessor systemsbecause the speed gap between processors and memories is gettinglarger.This paper describes coarse grain task parallel processingthat uses parallelism among macro-tasks like loops and subroutinesconsidering cache optimization using data localization scheme.The proposed scheme is implemented on OSCAR automatic multigrainparallelizing compiler. OSCAR compiler generates OpenMP FORTRAN programrealizing the proposed scheme from an ordinary FORTRAN77 program.Its performance is evaluated on IBM RS6000SP 604e High Node 8 processors SMP machine and Sun Ultra80 4 processors SMP machine.In the evaluation,OSCAR compiler gives us up to 5.8 times speedup againstthe minimum execution time of IBM XL FORTRAN compiler on IBM RS/6000 and up to 3.6 times speedup against Sun Forte 6 update 1 compileron Sun Ultra80.

著者

稲石 大祐 木村 啓二 尾形 航 岡本 雅巳 笠原 博徳

雑誌

全国大会講演論文集

巻号頁・発行日

vol.56, pp.303-304, 1998-03-17

著者

稲石 大祐 木村 啓二 藤本 謙作 尾形 航 岡本 雅巳 笠原 博徳

雑誌

全国大会講演論文集

巻号頁・発行日

vol.58, pp.177-178, 1999-03-09

著者

稲石大祐 木村 啓二 藤本 謙作 尾形 航 岡本 雅巳 笠原 博徳

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告計算機アーキテクチャ(ARC) (ISSN:09196072)

巻号頁・発行日

vol.1998, no.70, pp.31-36, 1998-08-05

被引用文献数

2

---

従来のコンパイラによる単一プロセッサ用キャッシュ最適化は個々のループを対象としているため、プログラム全体に比べると局所的な最適化が多く、プログラム全域を対象としたキャッシュ最適化は行われていない。そこで本稿では、最早実行可能条件解析を利用した単一プロセッサ上でのFORTRANプログラムのキャッシュ最適化手法を提案する。OSCAR FORTRANマルチグレイン自動並列化コンパイラは、FORTRANプログラムをループ・サブルーチン・基本ブロックの3種のマクロタスク(MT)に分割し、各MTに最早実行可能条件解析を行いマクロタスクグラフ(MTG)を生成する。MTGは制御依存及びデータ依存に基づくMT間の実行順序制約、及びMT間で授受されるデータに関する情報を表現する。本手法ではこのMTGを用いて、先行MTによってアクセスされたデータにアクセスする後続MTが先行MTの直後に実行されるよう大域的なコード移動を行い、キャッシュヒット率を向上させる。本手法は、OSCAR FORTRANマルチグレイン自動並列化コンパイラ中に、最適化された逐次型FORTRANを出力するプリプロセッサ機能として実現されている。CG法プログラムを用いた本キャッシュ最適化手法の性能評価結果を行ったところ167MHz UltraSPARC上で最高62%の速度向上が得られた。Cache optimizations by a compiler for a single processor machine have been mainly applied to a singlenested loop. On the contrary, this paper proposes a cache optimization scheme using earliest executable condition analysis for FORTRAN programs on a single processor system. OSCAR FORTRAN multi-grain automatic parallelizing compiler decomposes a FORTRAN program into three types of macrotasks (MT), such as loops, subroutines and basic blocks, and analyzes the earliest executable condition of each MT to extract coarse grain parallelism among MTs and generates a macrotask graph (MTG). The MTG represents data dependence and extended control dependence among MTs and an information of shared data among MTs. By using this MTG, a compiler realizes global code motion to use cache effectively. The code motion technique moves a MT, which accesses data accessed by a precedent MT on MTG, immediately after the precedent MT to increase a cache hit rate. This optimization is realized using OSCAR multi-grain compiler as a preprocessor to output an optimized sequential FORTRAN code. A performance evaluation shows about 62% speed up compared with original program on 167MHz UltraSPARC.

著者

笠原 博徳 小幡 元樹 石坂 一久

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.42, no.4, pp.910-920, 2001-04-15

被引用文献数

12

---

本論文では,共有メモリ型マルチプロセッサシステム上での粗粒度タスク並列処理のワンタイム・シングルレベルスレッド生成を用いた実現方式について提案する.粗粒度タスク並列処理は,現在のループ並列性の限界を超え,シングルチップマルチプロセッサからハイパフォーマンスコンピュータに至る広範囲のマルチプロセッサシステムの性能改善のために,重要な技術である.提案する粗粒度タスク並列処理実現手法では,まずFortranプログラムを粗粒度タスクに分割し,最早実行可能条件解析を用いてタスク間の並列性を解析した後,スタティックに粗粒度タスクをプロセッサに割り当てるか,実行時に粗粒度タスクをプロセッサに割り当てるダイナミックスケジューリングコードを埋め込んだOpenMP並列化Fortranプログラムを生成する.生成されるOpenMP並列化プログラムでは,階層的に粗粒度タスク並列処理を,プログラム開始時の一度だけのスレッドforkと,終了時の一度だけのjoinで低オーバヘッドで実現できる.本論文では,提案手法の有効性を8プロセッサからなる共有メモリマルチプロセッサIBM RS6000 SP 604e High Node上で評価する.本評価では,Perfect Club BenchmarksにおけるARC2D,SPEC 95fpのSWIM,TOMCATV,HYDRO2D,MGRIDを用い,提案する粗粒度タスク並列処理方式で生成したOpenMPコードをIBM XL Fortran compilerでコンパイルする.評価の結果,8プロセッサを用いた場合,提案する粗粒度並列処理手法は,XL Fortran単独によるループ自動並列化性能を1.5から3倍改善できることが確認できた.This paper proposes an implementation methodnamed ``one-time single level thread generation''for a coarse grain task parallel processing schemeon an off the shelf shared memory multiprocessor system.The coarse grain task parallel processing is importantto improve the effective performance of wide range of multiprocessor systemsfrom a single chip multiprocessor to a high performance computerbeyond the limit of the loop parallelism.The proposed scheme decomposes a Fortran programinto coarse grain tasks, analyzes parallelism among tasks by ``Earliest Executable Condition Analysis''considering control and data dependencies,statically schedules the coarse grain tasks to processorsor generates dynamic task scheduling codes to assign the tasks to processorsand generates OpenMP Fortran source codefor a shared memory multiprocessor system machine.The thread parallel code using OpenMP generatedby OSCAR compiler forks threads only onceat the beginning of the program and joins only once at the endeven though the program is processed in parallelbased on hierarchical coarse grain task parallel processing concept.The performance of the proposed scheme is evaluatedon a 8-processor shared memory multiprocessor system machine,IBM RS6000 SP 604e High Node,using a newly developed OpenMP backend of OSCAR multigrain compiler.The evaluation shows that OSCAR compiler with IBM XL Fortran compilergives us 1.5 to 3 times larger speedupthan native IBM XL Fortran compiler for SPEC 95fpSWIM, TOMCATV, HYDRO2D, MGRID and Perfect Benchmarks ARC2D.

著者

小幡 元樹 前川 仁孝 若尾 真治 小貫 天 笠原 博徳

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.1997, no.75, pp.13-18, 1997-08-19

---

現在、超電導モータ等の電気機器の開発にあたっては、発生する電磁界の解析が必須となっている。この電磁界解析手法として従来、有限要素法(E)あるいは境界要素法(E)が広く用いられている。有限要素法は、一般的に非線形性を含む不均一な領域の解析に適しており、境界要素法は均一な無限領域の解析を得意とする。しかし電磁界解析においては、磁性体のような非線形領域と周りの空気領域のように無限に広がる領域を含むため、解析時間を短縮し、さらに精度向上を目指し、著者らはFEMとBEMの長所を組み合わせた有限要素・境界要素併用法を提案している。この併用法により、FEM,BEMのみを用いた場合と比べ、計算時間は大幅に短縮されるが、本手法を用いても、大規模問題に対しては依然として長時間の解析時間を要する。そこで、本論文ではこの解析時間を短するための並列処理手法を提案し、NEC Cenju?3上で手法の性能評価を行った結果について述べる。現在、超電導モータ等の電気機器の開発にあたっては、発生する電磁界の解析が必須となっている。この電磁界解析手法として従来、有限要素法(E)あるいは境界要素法(E)が広く用いられている。有限要素法は、一般的に非線形性を含む不均一な領域の解析に適しており、境界要素法は均一な無限領域の解析を得意とする。しかし電磁界解析においては、磁性体のような非線形領域と周りの空気領域のように無限に広がる領域を含むため、解析時間を短縮し、さらに精度向上を目指し、著者らはFEMとBEMの長所を組み合わせた有限要素・境界要素併用法を提案している。この併用法により、FEM,BEMのみを用いた場合と比べ、計算時間は大幅に短縮されるが、本手法を用いても、大規模問題に対しては依然として長時間の解析時間を要する。そこで、本論文ではこの解析時間を短するための並列処理手法を提案し、NEC Cenju?3上で手法の性能評価を行った結果について述べる。Recently, for development of electrical appliances like super conductive motors, analysis of a generated electro-magnetic field is required. As a method of the electro-magnetic field analysis, the Finite Element Method (FEM) and the Boundary Element Method (BEM) have been widely used. The FEM is suitable for analysis of infinitely extending fields. The electro-magnetic field to be analyzed for electrical appliances, however, includes non-linear and infinite subfields. Taking into consideration these factors, the authors have been proposing a hybrid FE and BE method to take full advantages of these two method. Though analysis time by the hybrid FE and BE method compared with the FEM or BEM is significantly reduced, high precision analysis for large scale needs a large analysis time. To reduce analysis time, this paper proposes parallel processing scheme for a distributed many multiprocessor and evaluate its performance on NEC Cenju-3.