1. 現在の位置 : ホーム
  2. 提供科目
  3. 2017年度の科目
  4. 計算科学演習A

計算科学演習AComputational Science, Exercise A

授業の概要・目的

大規模データに対する統計処理を通して、高速な逐次計算プログラムを作成する技法と並列計算の初歩を学ぶことを目的とする。数値計算と統計計算について簡 単に触れた後、計算機アーキテクチャの説明、キャッシュの有効活用などの話題を解説し、高速な逐次計算プログラムを作成する上での注意点を解説する。さら に、マルチコアCPUを搭載する計算機での代表的な並列計算技法であるOpenMPと分散メモリ型並列計算機のための並列化技法であるMPIについて学 ぶ。
実習では、最小二乗法の問題を解く為のコードを作成する。最小二乗法については、列フルランク行列の場合には、QR分解によって計算可能である。よって、 始めに、列フルランク行列の場合を仮定し、QR分解を行うための逐次計算のコードを、「逐次計算の高速化」の内容を意識して作成する。次に、そのアルゴリ ズムを基礎として、MPI並列計算用のQR分解法であるAll Reduce アルゴリズムを実装する。列フルランクでない行列については、ピボット選択付QR分解の後、特異値分解を用いてノルム最小二乗解を求めるのが一般的であっ たが、近年、それに代わるより簡便な新しい手法が提案されており、この授業では、その手法を実装する。さらに、作成した逐次計算のコードをOpenMPの 技法を用いた並列計算のコードへと拡張する。

The aim of this course is to obtain skills for high performance computing and basic parallel computing, through statistical processing for large-scale data. For this purpose, we give lectures and exercises as follows.
In lectures, we give a short introduction to numerical algorithm and statistical processing at first. Then we explain computer architecture and basics of high performance computing. Furthermore we lecture two major parallel computing techniques, OpenMP for computers with shared memory, and MPI for computers with distributed memory.
In exercises, students implement the code for solving least squares problems. In the case of column full rank matrices, least-squares problems can be solved using the QR decomposition. Thus, firstly, serial codes for the QR decomposition are implemented with basics of high performance computing. Next, by using the serial codes, students implement "All Reduce algorithms" which is an algorithm of the QR decomposition for computers with distributed memory by using MPI. In the case where matrices are not column full rank, in general, least squares problems are solved by using the singular value decomposition. But nowadays a new simple algorithm is proposed, thus students write codes of this algorithm. Then, their codes are parallelized by using OpenMP.

授業計画と内容

ガイダンス

情報学研究科の学生のためのスパコン利用ガイド

・数値計算と統計計算 (2回)
計算科学の重要な手法である数値解析・数値計算の基礎について講述する。
線形代数の知識について復習した後、計算機で統計計算を行う上で重要となるアルゴリズムを解説する。特に、連立一次方程式の解法であるLU分解、最小二乗法において基礎となるQR分解について解説する。

数値計算1(木村分)

数値計算2(木村分)

数値計算3(木村分)

BLAS&LAPACK(木村分)

最小二乗法

・逐次計算の高速化(1回)
計算機アーキテクチャの説明、キャッシュの有効活用、データの再利用、さらに演算器の有効活用、効率的なプログラムを作成する上での注意事項などハイパフォーマンスコンピューティングという分野の基本的な内容を解説する。

逐次処理の高速化(木村分)

・OpenMP 入門(2回)
OpenMP並列プログラミングの基本的な考え方と技法について解説する。簡単な課題を用いて実習を行う。

OpenMP(木村分)

・MPI入門(2回)
MPI並列プログラミングの基本的な考え方と技法について解説する。簡単な課題を用いて実習を行う。

MPI入門(スライド) プログラム例

・最小二乗法を行うためのC言語によるコードの作成 (8回)
最小二乗法については、列フルランク行列の場合には、QR分解によって計算可能である。よって、始めに、列フルランク行列の場合を仮定し、QR分 解を行うための逐次計算のコードを、「逐次計算の高速化」の内容を意識して作成する。次に、そのアルゴリズムを基礎として、MPI並列計算用のQR分解法 であるAll Reduce アルゴリズムを実装する。
列フルランクでない行列については、ピボット選択付QR分解の後、特異値分解を用いてノルム最小二乗解を求めるのが一般的であったが、近年、それ に代わるより簡便な新しい手法が提案されており、この授業では、その手法を実装する。さらに、作成した逐次計算のコードをOpenMPの技法を用いた並列 計算のコードへと拡張する。

All schedules are as follows.
・Lecture of numerical algorithm and statistical processing (2 times Lecture)
(1) LU decomposition for linear equations
(2) QR decomposition for least-squares problems
・Lecture of computational science (1 time Lecture)
(1) Speed-up of serial computation
・Lecture of introduction to OpenMP (2 times Lecture)
(1) Parallel computing techniques for computers with shared memory using OpenMP
・Lecture of introduction to MPI (2 times Lecture)
(1) Parallel computing techniques for computers with distributed memory using MPI
・Exercises to the implementation of the code for solving least squares problems (8 times Exercise)
(1) Implementation of serial codes for the QR decomposition with basics of high performance computing
(2) Implementation of "All Reduce algorithms" for computers with distributed memory by using MPI
(3) Implementation of serial codes for solving least squares problems in the case where matrices are not column full rank
(4) Parallelizing their codes by using OpenMP

履修要件
・課題実習では、学術情報メディアセンターのスーパーコンピュータを使用します。情報学研究科に所属の学生は事前に取得しているアカウントを使用します.他研究科履修生については本演習用に必要に応じてアカウントを配布します。
・実習用端末として、ノート型PCを持参してください。持参できるノート型PCがない場合には教員に申し出てください。

ECS-ID is required for all attendees prior to the exercise classes.
A laptop computer is used in this course. It is better to bring a laptop computer.
予備知識
最小二乗法について理解するための予習あるいは復習を期待する。プログラミング言語Cについては、その文法を習得していることを前提として演習を行う為、それについての予習と復習を授業と並行して行うことを期待する。さらに、各話題について、授業時間の制約の為、詳細に解説することが困難であるため、各自で、図書館等を利用して各話題についての深い知識を得ることを期待する。
成績評価の方法・基準
レポート試験の成績(80%) 平常点評価(20%)
「All Reduce アルゴリズムを実装した並列計算のコード」を作成するレポート課題を出題する(配点 40点)。
「OpenMPの技法を用いた並列計算のコード」を作成するレポート課題を出題する(配点 40点)。
それぞれプログラムを作成することを課題とするレポートであり、独自の工夫がみられるものについては、高い点を与えます。
平常点評価には、出席状況と質問など通した授業への積極的な参加を評価します。

Students submit two reports about "All Reduce algorithms" and "The code using OpenMP". In these reports, students implement these codes, and given high points for the codes are improved by students.

"All Reduce algorithms": it is worth 40 points.
"The code using OpenMP": it is worth 40 points.
Attendance and active participation through questions is worth 20 points.
教科書
講義資料を配布
特に定めない

Handouts to be distributed
Not specified
参考書等
授業中に紹介する
特に定めない

Not specified
URL
その他(授業外学習の指示・オフィスアワー等)
オフィスアワーについては担当教員の KULASIS 登録情報を参照すること。
木村欣司:kkimur@amp.i.kyoto-u.ac.jp
關戸啓人:sekido@amp.i.kyoto-u.ac.jp
授業時間外で、質問がある場合には、あらかじめ、上記のアドレスにメールをすること。

See KULASIS data for office-hour information.
Kinji Kimura : kkimur@amp.i.kyoto-u.ac.jp
Hiroto Sekido : sekido@amp.i.kyoto-u.ac.jp
Please send mail to the above-mentioned address to contact outside the class time.


※オフィスアワー実施の有無は、KULASISで確認してください 。

センター提供科目一覧に戻る