著者

森 明子 須田 礼仁 杉原 正顯

出版者

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

雑誌

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

巻号頁・発行日

vol.1999, no.38, pp.49-54, 1999-05-14

参考文献数

9

---

1986年にOrszagはLegendre多項式変換を含むSturm?Liouville固有関数変換の評価計算に対する高速算法を提案した。彼の算法は固有関数のWKB近似を用いて計算の一部でFFTを利用することにより、直接計算でO (^) かかる計算量がO ( log^2N/log log) に改善できるというものである。しかし彼の算法は計算の無駄が多く、精度も悪く実用的ではない。我々はLegendre多項式変換の場合についてこのOrszagの算法を改良したので報告する。アルゴリズムの改良により計算量はO ( log ) に改善され、高精度近似公式の採用により、単精度程度の精度でN&ge;128,倍精度程度の精度でN&ge;256で直接法よりも高速となることがわかった。In 1986 Orszag proposed a fast algorithm for Sturm-Liouville eigenfunction transform including the Legendre polynomial transform. His algorithm, which exploits the high speed of FFT through the WKB approximation, runs in time O (N log^2 N/log log N), while the direct computation requires O (N^2) time. His algorithm is, however, not practical because of its low precision and algorithmic unsophisticatedness. We improve Orszag's algorithm in the case of the Legendre polynomial transform. The improved algorithm runs in time O (N log N), and the Stieltjes's higher order approximation formula enables high precision. Our scheme is faster than the direct method for N &ge; 128 with the error tolerance ε=10^<-6> and for N &ge; 256 with ε=10^<-12>.

著者

石田 翔太郎 須田 礼仁

雑誌

研究報告ハイパフォーマンスコンピューティング(HPC) (ISSN:21888841)

巻号頁・発行日

vol.2015-HPC-152, no.5, pp.1-18, 2015-12-09

---

計算機上で整数一様乱数を生成する方法については,これまで多くの論文が発表されてきた.一方で,浮動小数点数一様乱数を生成する方法 (または整数一様乱数から浮動小数点数一様乱数への変換法) については,多くの場面で整数一様乱数を定数で割る方法 (rand()/232など) が用いられてきた.しかしながら,この方法では特定の形式の浮動小数点数しか生成されず,ほとんどの浮動小数点数は生成されない.これに対して,Moler は [2-53,1-2-53] の範囲にある全ての浮動小数点数を生成可能な一様乱数生成器を提案し,その後 Thoma により,その範囲は (0,1) にまで拡張された.しかしながら,Thoma により提案された手法は,浮動小数点数の丸めモードによっては,隣り合う浮動小数点数の出現確率が 3 倍程度異なる箇所が生じるといった,不自然な挙動を取ることが実験的及び理論的な検証から分かった.そこで,本論文はこの不自然な挙動を修正することを目的とした上で,まずは正しい浮動小数点数一様乱数生成器について議論し,続いてそのような生成器を提案すると共にその正当性を示し,最後に,提案された生成器の性能を実験により示した.

著者

須田 礼仁

出版者

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

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.47, no.18, pp.92-114, 2006-11-15

被引用文献数

8

---

高速ネットワークの普及にともない,ヘテロな計算機から構成されるネットワーク計算環境が現出しており,ヘテロ並列計算環境に適した並列化手法の必要性が高まっている.本稿ではタスク並列パラダイムにおける主要な問題であるスケジューリングアルゴリズムについて,ヘテロ並列計算環境に関した研究のサーベイを行う.大規模アプリケーションを想定して目的関数をスケジュール長(makespan)に絞るが,divisible load theoryやマルチプロセッサタスクも含める.Network computing environments with heterogeneous computers have emerged as results of speedups of computer networks, and needs of parallelization technologies for heterogeneous parallel computing environments are increasing. This paper surveys scheduling algorithms, which are the major issue of parallelization in the task parallel paradigm, for heterogeneous parallel computing environments. The objective is limited to the schedule length (makespan) assuming large scale applications, but divisible load theory and multiprocessor task are included.

著者

ゴメス クロード 須田 礼仁

出版者

一般社団法人日本応用数理学会

雑誌

応用数理 (ISSN:09172270)

巻号頁・発行日

vol.19, no.1, pp.47-51, 2009-03-25

著者

石黒 貴之 服部 啓太 須田 礼仁 杉原 正顯

出版者

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

雑誌

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

巻号頁・発行日

vol.1999, no.66, pp.1-6, 1999-08-02

被引用文献数

2

---

球面上のPoisson方程式は地球の大気の運動をシミュレーションする上で欠かせない方程式である.従来,気象学の分野では球面上のPoisson方程式の数値解法として,球面調和関数を用いたスペクトル法及び,差分法等が一般的に利用されてきた.しかし前者はスペクトル範囲以内では正確に計算できるが,計算速度が遅い,逆に後者は高速に計算できるが精度が悪い.そこでYeeによって高速Fourier変換(F)を用いた高精度かつ高速な二重Fourier級数展開法が提案された.本報告ではYeeの方法で解析が不完全なところを補い,さらに改良を加えた.その結果,我々の手法でば,Yeeの方法の精度を保ちつつ,2倍程度の計算速度の向上を実現した.In meteorology, the spectral and finite difference methods are commonly used as the numerical solutions of the Poisson equation on a sphere. Nevertheless the former, being highly accurate, is slow, whereas the latter, being fast, is lowly accurate. To improve this situation, Yee has recently proposed a fast and highly accurate method based on the FFT, which is called truncated double Fourier series. In this report we make up for incomplete point of Yee's report and improve Yee's scheme. As a result our scheme achieves doubled performance with keeping the same level accuracy.

著者

加藤 誠也 須田 礼仁 玉田 嘉紀

雑誌

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

巻号頁・発行日

vol.2012, no.5, pp.1-11, 2012-05-25

---

近年 GPU は計算能力において目覚しい発展を続けており,NVIDIA の CUDA C に代表される演算用の言語の導入などによって,科学技術計算分野において重要な役目を担うようになっている.その一方で,CUDA のプログラミングモデルである SIMT (Single Instruction Multiple Threads) の特徴として,ダイバージェンスと呼ばれる問題があり,GPU の実行率が低下するため,GPU は CPU に比べると条件分岐の影響を受けやすい.そのため,条件分岐の最適化がより重要になっている.本論文では,GPU のダイバージェンスを削減し,実行率を向上させるための手法として,動的割り付け・分岐統一化の 2 つの手法を提案する.動的割り付けは主にデータごとに長さの異なるループが実行されるカーネルに対して適用可能である.これは,CUDA におけるブロック単位でデータを割り当て,ブロック内で各スレッドに動的にデータを割り当てることで,各スレッドに割り当てられるデータの処理量を均等にし,GPU の実行率を高める手法である.分岐統一化はデータに応じた条件分岐によって処理の大半が分かれているカーネルに対して適用可能である.これは,各スレッドに複数のデータを割り当てて,ある分岐方向の処理を行う際に,各スレッドが自分の持つデータの中からその方向に分岐するデータを選んでそれに対して処理を行うようにすることで,各スレッドに各条件分岐の実行中に実行するデータがあるようにして,GPU の実行率を上げることができるという手法である.これらの手法の有効性は,サンプルコードを用いた実験によって確認した.Recently, GPUs have progressed tremendously in computational power. Thus, the role of GPUs has become important in the field of computational science with the introduction of programing languages for GPU computation such as NVIDIA CUDA C. On the other hand, a problem called branch divergence has appeared as the feature of the programming model of CUDA called SIMT (Single Instruction Multiple Threads). Because of this, GPUs are more likely to be affected by conditional branch instructions than CPUs. Therefore, optimization of conditional branch is very important on GPUs in order to utilize the entire computational power. This paper proposes two techniques for reducing branch divergence on GPUs. Dynamic work assignment is applicable when almost every part of the kernel is a loop whose number of iterations is different with respect to input data. This technique increases the GPU execution rate by assigning data to each CUDA block and assigning data to each thread dynamically in the block so that the amount of computation of each thread becomes equal to others in the block. Branch path unification is applicable when almost every part of the kernel executes the different branch path by a conditional branch depending on data. This technique increases the GPU execution rate by assigning multiple data to a thread and exchanging the order of data assigned to threads so that the same branch path is executed by as many threads as possible and all the branch paths are executed one after the other. The effectiveness of these techniques has been confirmed by the experiments with the sample codes.

著者

本谷 徹 須田 礼仁

雑誌

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

巻号頁・発行日

vol.2012-HPC-133, no.30, pp.1-8, 2012-03-19

---

連立一次方程式の反復解法として広く使われている共役勾配法を大規模に並列化した際に律速となるのは,頻繁に現われる内積計算の通信遅延である.内積計算は計算機全体の集団通信を必要とすることから,大規模なアーキテクチャでの通信遅延は大きくなる.また強スケーリングにおいては計算粒度が小さくなり,通信遅延は相対的が大きくなってしまう困難を抱えている.物理的制約を超えての通信遅延削減は不可能なため,アルゴリズム側のアプローチによる通信遅延の削減が必要とされている.本稿では,共役勾配法の k+1 反復分の内積計算に必要な通信を 1 回で済ませることで集団通信を回避し,通信遅延を削減するk段飛ばし共役勾配法を提案,実装した.

著者

須田 礼仁 小柳 義夫

出版者

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

雑誌

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

巻号頁・発行日

vol.1997, no.37, pp.31-36, 1997-05-09

被引用文献数

1

---

可変長指数部浮動小数点数表現形式とは指数の大きさによって指数部の長さが変化することにより、通常の浮動小数点数よりも高い精度や広い表現範囲が実現できる浮動小数点数の諸形式である。本論文では従来の方式の問題点を考察し、誤差解析やハードウェアへ実装などを考慮して、表現形式の設計基準の中に()変換にシフトが不要である ()指数部のビット長の変化が最大1であるの2点を盛り込むことを提案する。そしてこの基準を満たす表現形式をいくつか提示し、従来のものをも含めて精度や表現範囲を比較検討した。また、Kraftの不等式を用いた二重指数分割方式に関するいくつかの理論的な結果を示した。Some researchers proposed floating point number formats that attain higher precision and wider representation range than the usual formats by varing the length of the exponent. This paper consider the problems of those formats, and proposes to require that (1) encoding and decoding need no shifter and (2) the length of the exponent increases by at most one bit. Some new formats that meets those requirements are presented, and their precisions are evaluated. Some analytical results obtained from the Kraft's in equation about the double exponential cut formats are also presented.

著者

須田 礼仁 小柳 義夫

雑誌

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

巻号頁・発行日

vol.1997, no.37(1997-HPC-066), pp.31-36, 1997-05-09

---

可変長指数部浮動小数点数表現形式とは指数の大きさによって指数部の長さが変化することにより、通常の浮動小数点数よりも高い精度や広い表現範囲が実現できる浮動小数点数の諸形式である。本論文では従来の方式の問題点を考察し、誤差解析やハードウェアへ実装などを考慮して、表現形式の設計基準の中に()変換にシフトが不要である ()指数部のビット長の変化が最大1であるの2点を盛り込むことを提案する。そしてこの基準を満たす表現形式をいくつか提示し、従来のものをも含めて精度や表現範囲を比較検討した。また、Kraftの不等式を用いた二重指数分割方式に関するいくつかの理論的な結果を示した。

著者

須田 礼仁 小柳 義夫

出版者

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

雑誌

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

巻号頁・発行日

vol.64, pp.19-24, 1996-12-12

参考文献数

2

---

最小自乗最小ノルム解を求める解法としては特異値分解やQR分解がよく用いられるが,LU分解を用いて解を得る方法も存在する.本論文ではLU分解による最小自乗最小ノルム解法を紹介し,LU分解とQR分解における誤差と速度について評価をおこなう.誤差はLU分解の方が大きいと考えられるが,QR分解も決して安定というわけではない.特に疎行列ではLU分解の方が絶対的に速く,誤差もfill-inを抑えればそれほど悪くないのでLU分解による方法が有利な場合も十分にあると考えられる.

著者

須田 礼仁

出版者

一般社団法人日本応用数理学会

雑誌

応用数理 (ISSN:09172270)

巻号頁・発行日

vol.21, no.2, 2011-06-24

著者

須田 礼仁

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.59, pp.1-6, 2007-06-08

被引用文献数

1

---

Multi-master divisible load は著者らが提案してきたタスク再分散のためのモデルである.本稿の第1のテーマは,これまでに提案してきた手法の性能解析である.問題は 3 つのクラスに分けられ,それぞれタスク量 $T$ に対して最適解との性能比が $1 + O(\sqrt T)$ $1 + O(\log T/T)$ $1 + O(1/T)$ となることが示された.第2のテーマはこれまでに提案してきた手法で得られたスケジュールの改良である.通信時間の定数項や必須のアイドル時間を考慮し,各プロセッサがほぼ同時に計算を終了するようにスケジュールを改良した.その結果,近似解と最適解との差を 1/2 から 1/3 にすることができた.Multi-master divisible load is a model for task redistribution. This paper first discusses a performance analysis of our scheme. The problems are classified into three classes, and the relative performance against the optimum solution is $1 + O(\sqrt T)$, $1 + O(\log T/T)$, and $1 + O(1/T)$, respectively, where $T$ is the total task size. Second the schedules are improved, where the constant terms of the communication times and inevitable idle times are considered, and the completion times of the processors becomes nearly the same. The difference of the approximation and the optimum solutions is reduced into 1/2 or 1/3.