ベクトル計算機のための一次回帰演算の高速アルゴリズムとその並列化

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/5699
File
Title
ベクトル計算機のための一次回帰演算の高速アルゴリズムとその並列化
Title Alternative
Fast Execution of Linear Recurrences on Vector Computers and Its Parallelization
Author
氏名 川端 英之
ヨミ カワバタ ヒデユキ
別名 KAWABATA Hideyuki
氏名 湯之上 康一
ヨミ ユノウエ コウイチ
別名 YUNOUE Koichi
氏名 津田 孝夫
ヨミ ツダ タカオ
別名 TSUDA Takao
Abstract

本論文では,線形一次回帰演算のベクトル計算機向け高速化手法を提案する.この手法はベクトルレジスタを有効に利用する方法で,余分なベクトルロードおよびストア命令を排除するとともにスカラ処理が必要となる部分を削減することによって高速性能を実現する.従来,線形回帰演算のベクトル処理手法としては,計算量やベクトル長の観点から,ループアンローリングに基づく手法(アンローリング手法)が有効であるとされてきた.商用ベクトル計算機を単純化したモデルによる比較では,我々の手法はわずかなコード記述量であるにもかかわらず理想的なアンローリング段数(一般には非常に大きい段数)によるアンローリング手法と同等の演算性能であることが分かった.NEC SX-4を用いた線形回帰演算の実測では,モデルによる予測結果どおり理論最大性能の1/4に達する演算速度が観測され,モデルの妥当性と提案手法の有効性がいずれも高いことが確認された.また,提案手法の自然な拡張による並列化の試みでは,8プロセッサを用いて5.9倍の台数効果を得た. / In this paper, we propose a new technique to calculate fast first-order linear recurrences on vector computers. Our method is intended to reduce redundant vector load and/or store operations. The objective is accomplished by restructuring recurrent loops with information such as the length of vector registers in mind, not relying on automatic strip-mining by vectorizing compilers. Although it has been said that unrolling approach is suitable for linear recurrences to run fast on vector computers, appropriateness of the unrolling factor hasn't been mentioned specifically in general. We construct a simple model of a vector machine to compare ordinary unrolled code and code created by our method. On the model, it is explained that codes by our method can perform as well as unrolled codes with optimal (typically unrealistically large) unrolling factors. Experimental results on the NEC SX-4 show that our code runs 1/4 times as fast as the peak performance of the machine, which is also predicted by the model. The results confirm that our method is efficient and our model of a vector processor is proper. In addition, we show that our method can be easily parallelized. Speedup ratio of 5.9 on 8 processors has been observed.

Description Peer Reviewed
Journal Title
情報処理学会論文誌
Volume
43
Issue
4
Spage
971
Epage
985
Published Date
2002-04-15
Publisher
社団法人情報処理学会
ISSN
0387-5806
NCID
AN00116647
NAID
110002726264
Language
jpn
NIIType
Journal Article
Text Version
出版社版
Rights
ここに掲載した著作物の利用に関する注意:本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan.
Relation
isVersionOf:http://ci.nii.ac.jp/naid/110002726264
Relation URL
Old URI
Set
hiroshima-cu