著者

中野 啓史 石坂 一久 小幡 元樹 木村 啓二 笠原 博徳

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.76, pp.67-72, 2001-07-25

参考文献数

13

被引用文献数

3

---

近年のプロセッサの動作速度とメモリアクセスの速度差の拡大により,データローカリティを利用したキャッシュ最適化がますます重要となっている。また,マルチプロセッサシステム上での並列処理においては,従来のループ並列化のみの並列処理は限界を向かえつつある。そのため更なる性能向上を得るには粗粒度タスク並列処理の併用等マルチグレイン並列化が重要となっている。本稿では,Fortranプログラムをループ・サブルーチン・基本ブロックの3種類の粗粒度タスクに分割し,粗粒度タスク間の制御依存・データ依存を解析して並列性を抽出する粗粒度タスク並列処理において,粗粒度タスク間のデータ共有量を考慮してキャッシュ最適化を行う粗粒度タスクスタティックスケジューリング手法について述べる。本手法をOSCAR Fortranマルチグレイン並列化コンパイラに実装してSunUltra80(4プロセッサSMP)上で評価を行った結果,SPEC 95fpのswim,tomcatvにおいて,本手法により,Sun Forte HPC 6 update 1 の自動並列化に対してそれぞれ4.56倍,2.37倍の速度向上が得られ,本手法の有効性が確かめられた。Effective use of cache memory based on data locality is getting more important with increasing gap between the processor speed and memory access speed. As to parallel processing on multiprocessor systems, it seems to be difficult to achieve large performance improvement only with the conventional loop iteration level parallelism. This paper proposes a coarse grain task static scheduling scheme considering cache optimization. The proposed scheme is based on the macro data flow parallel processing that uses coarse grain task parallelism among tasks such as loop blocks, subroutines and basic blocks. It is implemented on OSCAR Fortran multigrain parallelizing compiler and evaluated on Sun Ultra80 four-processor SMP machine, using swim and tomcatv from the SPEC fp 95 benchmark suite. As the results, the proposed scheme gives us 4.56 times speedup for swim and 2.37 times for tomcatv respectively against the Sun Forte HPC 6 loop parallelizing compiler on 4 processors.

著者

小幡 元樹 白子 準 神長 浩気 石坂 一久 笠原 博徳

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.4, pp.1044-1055, 2003-04-15

被引用文献数

13

---

従来,チップマルチプロセッサからHPCまで幅広く使われている共有メモリ型マルチプロセッサシステム上での自動並列化コンパイラではループレベル並列処理が主に用いられてきたが,その並列化技術の成熟により,ループ並列化では今後大幅な性能向上は難しいといわれている.このループ並列性の限界を越えるために,現在ループ・サブルーチン・基本ブロック間の粗粒度タスク並列性,ステートメント間の近細粒度並列性を従来のループ並列処理に加えて利用するマルチグレイン並列処理が有望視されている.マルチグレイン並列処理において各種粒度の並列性を階層的に抽出し,効率良い並列実行を実現するためには,各々の階層(ネストレベル)の並列性に応じて,何台のプロセッサ,あるいはプロセッサのグループ(プロセッサクラスタ)を割り当てるかを決定する必要がある.本論文ではプログラム中の各階層の並列性を効果的に用いるための階層的並列性制御手法を提案し,本手法を実装したOSCARマルチグレイン並列化コンパイラによる階層的並列処理の評価では,SMPサーバIBM pSeries690 Regatta 16プロセッサシステム上にてSPEC95FPベンチマークを用いた結果,逐次処理に対して1.9?10.6倍の性能向上が得られることが確かめられた.A multigrain parallel processing is very important to improve effective performance beyond the limit of the loop parallelism on a shared memory multiprocessor system.In the multi-grain parallelization, coarse grain parallelism among loops,subroutines and basic blocks,and near fine grain parallelism among statements inside a basic block are exploited in addition to the conventional loop parallelism.In order to efficiently use hierarchical parallelism of each nest level,or layer, in multigrain parallel processing,it is required to determine how many processors or groups of processors should be assigned to each layer,according to the parallelism of the layer.This paper proposes a hierarchical parallelism control scheme for multigrain parallel processing so that the parallelism of each hierarchy can be used efficiently.Performance of the hierarchical parallelization using the proposed scheme implemented on OSCAR multigrain parallelizing compiler is evaluated on IBM pSeries690 Regatta SMP server with 16 processors using SPEC95FP benchmarks and the hierarchical parallelization using the proposed scheme gave us 1.9 to 10.6 times speed up against sequential processing.

著者

小幡 元樹

出版者

Waseda University

巻号頁・発行日

2003-03

---

制度:新 ; 文部省報告番号:甲1749号 ; 学位の種類:博士(工学) ; 授与年月日:2003/3/6 ; 早大学位記番号:新3512

著者

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

出版者

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

雑誌

情報処理学会論文誌 (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.

著者

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

出版者

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

雑誌

情報処理学会論文誌 (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.