第4回ASE研究会のお知らせ

日時：2009年3月27日（金）14時00分～17時00分
場所：東京大学　情報基盤センター　３階　大会議室（情報基盤センター案内地図）
主催：東京大学情報基盤センター　スーパーコンピューティング部門

【基調講演】

14時00分～15時00分

Speaker

　Julien Langou, University of Colorado Denver.

Title

　Communication Optimal and Tiled Algorithms for Dense Linear Algebra: Auto-Tuning Opportunities in this new Design Space

Abstract

　In this talk, we will first present recent communication-optimal and tiled algorithms for the LU factorization and the QR factorization introduced in [1,2,3,4]; then, we will motivate the need for performance auto-tuning in these algorithms and give some examples of opportunities in software auto-tuning. Our new communication-optimal and tiled algorithms represent a radical change with the current generation of linear algebra software (e.g. LAPACK and ScaLAPACK). They offer considerable advantage on a wide variety of platforms: sequential, multicore, parallel distributed, GPU acceleration. While we know that these algorithms are optimal in the big O sense, while we have proof-of-concept implementations of these algorithms, a lot remains to be done in finely tune these algorithms for a given (possibly heterogeneous) architecture. We believe the answer is in software auto-tuning.
　[1] James Demmel, Laura Grigori, Mark Hoemmen, and Julien Langou. "Implementing Communication-Optimal Parallel and Sequential QR Factorizations." arXiv:0809.2407
　[2] James Demmel, Laura Grigori, Mark Hoemmen, and Julien Langou. "Communication-optimal parallel and sequential QR and LU factorizations." arXiv:0808.2664
　[3] Alfredo Buttari, Julien Langou, Jakub Kurzak, and Jack Dongarra. "A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures." arXiv:0709.1272
　[4] Alfredo Buttari, Julien Langou, Jakub Kurzak, and Jack Dongarra. "Parallel Tiled QR Factorization for Multicore Architectures." arXiv:0707

【招待講演】

15時00分～16時00分

Speaker

　Shoji Itoh, Advanced Center for Computing and Communication, The Institute of Physical and Chemical Research（RIKEN）

Title

　Systematic Performance Evaluation for Numerical Algorithms of Linear Equations and Its Knowledge Discovery

Abstract

　Systematical performance evaluation method for numerical algorithms of linear equations is proposed. An introduced computational system generates a performance information data set for a range of iterative solvers and preconditioning using a lot of typical test problems, and presents data visually allowing the relationships between the various algorithms and problems to be compared.

16時00分～17時00分

講演者

　村上　弘（首都大学東京）

タイトル

　ブロック鏡映変換を用いたハウスホルダ型ブロック三重対角化法の、マルチコア及び小規模SMPシステム上での性能

概要

　大規模密な実対称行列の固有値問題の全体行列を、要素が小行列から成るブロック行列とみなし、ブロック化された鏡映変換に基づく直交変換により、（対称な）ブロック三重対角化を行うと、演算のほとんどは小行列ごとのレベル3 BLAS演算で組み立てられ、記憶の局所性と演算密度を高く保てるので、計算システムの高い性能を有効に引き出し易くなる。今回はマルチコア（4コア）のCPUによるPCと、小規模SMPシステム上での実験例を紹介する。ブロック三重対角化された行列の固有値問題は近年は分割統治法系統の方法が有望視されているが、今回はブロック三重対角行列を簡易な帯幅縮小処理の後に、村田帯ハウスホルダ法により（真の）三重対角化を行い、必要な範囲と個数の固有値をスツルム二分法で求めて、元の帯行列に対して逆反復法で各固有ベクトルを求める方法のコードを用いた。帯行列の固有ベクトルを元の行列の固有ベクトルに逆変換する過程で、元のブロック鏡映変換の逆が利用できる。（帯行列の望む範囲にある比較的少ない割合の固有値とそれに対する固有ベクトルを全て求めるには、帯行列のハウスホルダ三重対角化（演算量が行列次数N、 帯幅wに対してO（wN^2）になる）を経由しないで逆反復法を組み合わせたフィルタ対角化法などが有利になると考えられるが、今回はそれには立ち入らない。）ブロック鏡映変換の構成には、小行列を要素とするブロックベクトルのQR分解が必要で、それにはTS型行列専用のQR分解法が適している。

17時00分～

　T2Kスパコン見学（予定）

17時45分～

　懇親会（根津周辺）

---------------------------------------------------------------------
懇親会参加票（katagiri＠cc.u-tokyo.ac.jpまで）

日時：2009年3月27日（金）
　　　17時45分～
場所：根津周辺
会費：4000円程度

ASE研究会懇親会に参加します

お名前：
ご所属：
---------------------------------------------------------------------

• センターユーザに限定せず、研究会は一般公開とします。
• 参加費は無料で、基本的に事前登録は不要です。

また、今後の開催予定を確実に知りたい方は、メーリングリストへの登録をお願いします。登録依頼については、下記問い合わせ先までお願いします。

〒113-8658　東京都文京区弥生2－11－16
東京大学　情報基盤センター

ASE研究会幹事　特任准教授　片桐孝洋
E-mail：katagiri＠cc.u-tokyo.ac.jp
（”＠”を半角にしてからお送りください。）