新HPCの歩み（第256回）－2007年(i)－

ISCにおいて、Burton Smithは今後の問題点として、The ILP wall, The Power wall, The Memory wallの3つを挙げ、いずれもが高度並列処理により解決されるだろうと述べた。Tom Sterlingは今年の特徴を「新しいムーアの法則としてのマルチコア」と位置づけた。Blue Gene/Pが発表された。

Advisory Board

三浦謙一(NII)、渡辺貞（理研）

Program Committee

佐藤哲也（地球シミュレータ）

Scientific Program Committee

三浦謙一(NII)

ISC Award Committee

関口智司（産総研）

順位

前回

設置場所

システム

コア数

Rmax

Rpeak

 1 

1

LLNL

BlueGene/L

  131072

280.60

367.0

 2

(10)

ORNL

Jaguar – Cray XT4/XT3

   23016

101.7

119.35

 3 

2

SNL

Red Storm

   26544

101.40

127.411

 4 

3

IBM Watson Lab.

BGW – BlueGene     

   40960

91.29

114.688

 5

–

BNL

New York Blue – BlueGene

   36864

82.161

103.219

 6 

4

LLNL

ASC Purple p5 575 1.9 GHz

  12208

75.76

92.781

 7

–

Rensselaer Polytechnic

BlueGene

  32768

73.032

91.75

 8

–

NCSA

Abe – PowerEdge 1955 2.33 GHz

   9600

62.7

89.5872

 9 

5

Barcelona S.C.

MareNostrum BladCenter JS21 Cluster

   10240

62.63

94.208

10

–

Leibniz RZ(ドイツ)

HLRB-II Altix 4700 1.6 Gz

    9728

56.52

62.2592

11 

6

SNL

Thunderbird – PowerEdge 1850 2.6 GHz

    9024

53.00

64.9728

12 

7

CEA（フランス）

Tera-10 – NovaScale 5160    

    9968

52.84

63.7952

13 

8

NASA Ames

Columbia – Altix 1.5 GHz     

   10160

51.87

60.96

14 

(9)

東工大

TSUBAME Grid Cluster – ClearSpeed    

   11088

48.88

78.7968

15

(12)

TACC（Texas大学）

Lonestar – PowerEdge 1955, 2.66 GHz

    5848

46.73

62.22

16

11

Maui HPC Center

Jaws – PowerEdge 1955 3.0 GHz

   5200

42.39

62.4

17

–

US Army Research L.

Michael J. Muuss Cluster

   4416

40.61

52.992

18

13

FZJ (ドイツ)

JUBL – BlueGee

  16384

37.33

45.875

19

–

LLNL

Atlas – Appro Xtreme Server

   9216

36.62

44.24

20

14

海洋開発研究機構

地球シミュレータ

   5120

35.86

40.96

　Top500に入るための最小性能は4.005 TFlopsであある。時間的な推移を見ると、Top1がTop500に落ちるまでの期間は6-8年、Top500の性能がパソコンで達成されるのに8-10年掛かっている。

　 (Gordon) Bellの法則によれば、コンピュータアーキテクチャの主流は約10年毎に変わる。これをTop500のリストから検証してみよう。たしかに、90年代前半まではベクトルやSIMDが主流であり、その後は2004年くらいまでcustom scalarの時代であり、その後はcommodity clusterが主流になっている。現在重要な問題は消費電力であり、BlueGene型のものが今後どのように主流になっているかが注目される。

　その意味で重要なのは、multi-coreとmany-coreである。我々はMooreの法則を安易に（安価に）乱用してきたので、システムの消費電力は膨大になっている。もはや、Mooreの法則のただ乗り(free lunch)はできない。消費電力を下げるために周波数を上げられないので、必然的に並列度が増大し、multi-coreが到来する。消費電力当たり最適なコアの大きさは、現在の贅沢なコアよりは小さいので、many-coreの時代がやってくる。

順位

前回

設置場所

システム

コア数

Rmax

Rpeak

14

(9)

東京工業大学

TSUBAME Grid Cluster

11088

48.88

78.7968

20

14

海洋研究開発機構

地球シミュレータ

5120

35.86

40.96

37tie

21tie

産総研CBRC

Blue Protein – BlueGene

8192

18.2

22.9376

37tie

21tie

高エネルギー機構

KEK/BG MOMO

8192

18.2

22.9376

37tie

21tie

高エネルギー機構

KEK/BG Sakura

8192

18.2

22.9376

51

－

東大

SR11000-J2

128

15.811

18.8416

59

33

海洋研究開発機構

Altix 4700 1.6 GHz

2560

14.598

16.384

75tie

51tie

日本原子力研究所

SGI Altix 3700 Bx2 1.6 GHz

2048

11.814

13.107

86

56

筑波大学

PACS-CS

2560

10.35

14.336

92tie

61tie

高エネルギー機構

KEK/BG UME

4096

9.433

11.4688

(1) 3つの壁

　トランジスタ数は年々増大しているが、クロック周波数やソケットのピン数は増えない。つまり単一プロセッサの性能は頭打ちである。従って並列処理が重要になる。しかし、命令レベル並列性は限界に来ている(the ILP Wall)。チップあたりの消費電力は耐え難いほど大きい(the Power Wall)。また、キャッシュメモリの効果は大きくない(the Memory Wall)。

　当分の間、ロジックの費用（ゲート数×周波数　当たりの費用）は下がりつつある。このようなハードウェアをどう使いこなせばよいか。

　新しい「キラーアプリ」が登場して、より大きな性能を必要とすることを期待している。たとえば、意味解析、検索、ヒューマンインタフェース、言語、画像、ゲームなど。

　マイクロプロセッサは今やマルチコアであり、マルチスレッドである。しかしこれまではアーキテクチャ的に同じものがたくさん並んでいるだけである。このようなシステムをどうプログラムしたらよいのか。

(a)   ILP Wall

　まず、ILP Wallについて考える。これまでILPへの二つのアプローチがあった。一つは、ベクトル命令や、SSEなどであり、もう一つはout-of-order実行、in-order retirement、レジスタリネーミング、分岐予測、投機的実行などである。しかしどちらのスキームも並列度を増やすことはできなかった、それは命令依存や、データ依存アドレス（ポインタを追跡するとか）などのせいである。実際のところ、クロックあたり2-3程度のILCしか実現できていない。ハイパフォーマンスには並列計算が必要である。

(b)   Power Wall

　次にPower Wallを考えよう。速度をσ倍にスケールするためには2つの方法がある。一つはコアの数をσ倍に増やすことであり、そうすれば消費電力もσ倍に増える。もう一つは、クロック周波数と電圧をσ陪にすることであり、そうすれば動的電力はσの3乗に比例し、静的な電力はσの1乗に比例する。平均はその中間であろう。つまり、σ＞1ならクロックのスケーリングはコアを増やすより悪い。しかし、σ＜1なら、逆にうまくいく。教訓は、「もしマルチプロセッサが完全に利用されているが熱すぎるとき、プロセッサ数ではなく電圧と周波数をスケールダウンせよ。」並列計算は電力を節約するためにも必要である。

(c) Memory Wall

　次はMemory Wallである。多くのトランジスタにより、より大きいキャッシュを作ることができるようになった。では、それで十分か、それともスケールアップに問題はあるか？　同一のDRAM合計バンド幅により性能を倍増するためには、キャッシュミス率は半分にしなければならない。では、キャッシュはどこまで大きくする必要があるか。密行列のかけ算やLU分解なら4倍、ソーティングやFFTなら前の2乗、疎行列や密行列とベクトルとのかけ算なら、考えるだけ無駄。クロック周波数がより高速になり、相互接続がより深くなると、キャッシュミスのレイテンシが増加する。すなわち、高性能にすればするほど、より大きいレイテンシは不可避になる。レイテンシとバンド幅は密接に関係している。入力から出力までデータをそのまま輸送するシステムでは、レイテンシ×バンド幅＝（必要な）並列度　となる。これは待ち行列理論でLittleの法則と呼ばれるものである。

(2) 並列処理

　Memory Wallを克服するにはどうすればよいか。

 (a) メモリバンド幅を増やすこと。DRAMの合計バンド幅をギガバイト単位で増やすこと。そしてチップのピンのバンド幅を増やすこと。

 (b) メモリレイテンシに対応するために、マルチスレッドのコアを使うこと。もしレイテンシが増えても、スレッド数を増やせばよい。これによりプログラミングモデルは大きくは変わらない。

 (c) バンド幅とレイテンシを改善するためにキャッシュを用いよ。コンパイラがより簡単に局所性を最適化できるようにせよ。キャッシュラインを短くし、投機のミスを防げ。

　結局メモリのバランスを保つためには並列計算が必要である。

　我々はフォン・ノイマンの前提に60年間依拠してきた。いまや、それ（とそれに付属するもの）は代えなければならない。逐次処理は変数がどんな値を取るかということでプログラムをスケジュールしているが、並列処理ではこのスキームは危険である。逐次プログラミングは並列プログラミングより簡単であるが、逐次プログラムは今や遅いプログラムである。だれでもうまくプログラムすることができるような並列プログラミングが必要である。我々の分野の懸賞金は高い。コンピューティングは再発明されなければならない。

　この問題をどう解決すればいいのか。マイクロプロセッサはものすごい勢いで高速化している。最近20年で1000倍以上になった。HPCは特殊化のスパイラルに落ち込んでいる。つまり、HPCの応用とはHPCシステムがうまく処理できるような応用のことを意味している。DARPA HPCSプログラムは、この傾向に棹を差そうとしている。並列システムに関する大学の研究は干上がっている。興味もない、アイデアもない、必要性もない、お金もない。しかし、並列計算への興味は必ず再起する。1970年から2000年までの国際会議の論文の分野を調べると、前半はマルチプロセッサが増えたが後半は減っている。

　過去から何を学ぶか。並列計算について多くのことはすでに知られている。たとえば、コンパイラ最適化、デバッグと性能チューニング、OS、アーキテクチャなど。これまでのほとんどの研究は、HPCを頭に置いてなされてきた。アイデアのなかには成功したものもしなかったものもある。また、技術的な成功は商業的な成功を意味するわけではない。

(3) 並列プログラミング

　まず並列プログラミング言語を取り上げる。現在のところ少なくとも二つのアプローチが成功しそうである。関数プログラミングとアトミックなメモリ・トランザクションである。どちらもそれ自身完全に満足はできるものではない。関数的プログラムはmutable state を許さないし、トランザクションのプログラムの依存性の実装法は汚い。データベースの応用はこの二つのアイデアを統合している。SQLは「最も関数的な」言語である。[データベースの]トランザクションはアトミシティとisolationを保ってデータの更新を行っている。多くの人は関数言語は効率が悪いと考えている。しかし、SisalやNESLはすばらしい反例である。Crayのシステム上で両者はFortranと十分競争できる。またある人々は、メモリ・トランザクションも効率が悪いと考えている。今のところそうかもしれない。やっと最適化を始めたところである。

　トランザクションと不変量(invariants)について考えよう。不変量はプログラムの保存則である。反復や再帰における量の間の関係であり、データ構造の統一性の法則である。もし文pとqが不変量Iを保存し、両者が干渉しないなら、並列合成{p||q}もIを保存する。もし、pとqがトランザクションのようにアトミックなら、両者は干渉しない。色々な操作は、状態について交換可能であることは少ないが、トランザクションは不変量についての可換性を与える。従って、もしコンパイラが不変量を利用することができればすばらしい。プログラマにそれを与えるよう要求できるか？

　並列性のスタイルについて考えよう。われわれは複数のプログラミングスタイルをサポートしなければならない。関数型もトランザクション型も、データ並列もタスク並列も、メッセージ・パッシングも共有メモリ型も、宣言型も命令型も、暗黙型も明示型も。これを実現するにはいくつかの言語が必要かもしれない。結局現在も複数の言語を用いている。言語間の相互通用性(.NETのような）は大いに助けになるであろう。本質的なことは、並列性がコンパイラに提示されることである。それにより、コンパイラがそれをターゲット・システムに適応できる。また、同じ理由で局所性もコンパイラに提示されることが重要である。

　並列性に対するコンパイラの最適化は可能か？　ある人は、自動並列化が失敗したことは実証済みであるという。そうではない、ベクトル化も並列化コンパイラも、正しいアーキテクチャに対して用いれば、非常に大きな成功を収めてきた。これによりマシン独立な言語を可能にした。なにをやったかというと、並列性のパッケージ化をやった。明示的な並列プログラムでさえそれが必要である。何が失敗だったかというと、それは並列性の発見である。大まかに言って依存性解析は主に局所的な成功にとどまった。大規模な局所性の発見も大変である。局所性解析は依存性解析の別名だからである。大規模な局所性パッケージングが可能かどうか、まだ判断がなされていない。

　では並列デバッギングやチューニングはどうであろうか。現在、デバッグには、1ステップずつの実行とprintf()に依存している。これはあまり有効な方法ではない。条件付きのデータ・ブレークポイントは有効であった。つまり、不変量が不変量でなくなったときに停止させるのである。アドホックなデータ精査も非常に重要である。これは一種のデータマイニングの応用である。逐次プログラムのチューニングは、プログラムカウンタが最もしばしば滞在する場所を見つけることである。その答は多くの場合サンプリングで見いだすことができる。それに対して、並列プログラムのチューニングは、並列性が不十分な場所を探そうとする。最も良いとされるアプローチは、タイムスタンプ付きのイベントのログを取ることである。

　では並列性に適したOSは何であろうか。まず、[並列]OSはプロセッサのスケジュールを止めなければならない。この仕事はプロセッサや他の資源の仕事である。また資源の変更は、ランタイムと交渉しなければならない。仕事はユーザレベルでスケジュールしなければならない。従って、特権を変更する必要はなく、局所性を保存することが望ましく、最適化はより可能になり、ブロック化された計算は一級になる[何を言いたいのか？]。用途によってはサービスの質が重要になる。このようなばあい、優先度よりデッドラインの方が重要である。ほとんどの並列アプリにおいてデマンド・ページングは悪い考えである。ページ・フォールトで待ちばかり起こってしまう。

(4) アーキテクチャ

　並列アーキテクチャについて述べる。並列性はハードウェアから始まった。しかしそれだからと言って、ハードウェアが進んでいるわけではない。じゃまなのはフォン・ノイマンの前提である。たとえば、割り込みとか。ほとんどは修復することは易しい。大きな問題は小粒度の並列性のサポートである。スレッドの粒度はスレッドあたりの状態の量に依存し、ブロックしたときそれをスワップするのにどのくらいの手間が掛かるかに依存する。もう一つの問題は、すべてのプロセッサが同一に見えるべきかどうかということである。異質性という選択はある。ヘテロなアーキテクチャや、ヘテロな実装である。その間で通信をするために共有メモリを用いることができる。しかし、同質のアーキテクチャのデータ型の方が性能は上がるであろう。最大の問題はシステムバランスをどうやって保つかということである。

(5) HPCはどうなるか

　以上の考察からHPCに対して何が言えるか。これまでHPCは、逐次処理の世界における、孤独な並列処理の前哨部隊であった。しかし今や並列計算はメインストリームである。HPCへの帰結は以下のようにまとめることができる。

(a) HPCの主流のソフトウェアの適応と利用

(b) 共有メモリとメッセージ・パッシングの実行時の結合

(c) プログラミング言語選択のスペクトルを広げること

HPC製品の提供が成功するためには

(a) 今後ますます登場する利用者のアプリとツールのHPC版

(b) 利用者のアプリを可能にし、加速するHPCのサービス

(c) 利用者の想定しているアーキテクチャのモデルをスケールアップできるHPCシステム

　HPCはその他すべてのものとともに再発明されなければならない。

(6) 結論

　結論として、われわれはいまや計算の基礎の多くを考え直さなければならない。やるべきことは山ほどある。私[Burton]はいくつかのテーマ、特にアプリの問題に触れなかった。それから、われわれは並列性に関して価値のある経験をたくさん持っている。その多くは今後も有用であろう。

　今までの私[Tom]の挙げた各年の標語を集めると、

              2004      Constructive Continuity

              2005      High Density Computing

              2006      Multicore to Petaflops

であった。今年の標語は、”Multicore: the Next Moore’s Law” である。

(1) 今年のトレンドのハイライト

a) BG/Lが今年も先頭

b) ペタフロップスへ向けて全開。2010年がターゲット

c) Multicoreは今や当たり前、そしてmanycoreが辞書に載るようになった。次はmyriadcoreか？

 d) ヘテロ構成、Cell, GPGPU などが噂になっている。ところで、プログラミングモデルは？

e) 他のアクセラレータも魅力的

f) LinuxとIBAのコモディティ・クラスタが進入中。

g) クロック周波数はほとんどフラットだが、少しは上昇中。

 h) ソフトウェアの進歩もゆっくりだが、重要な進歩もあり。

 i) アプリの広がり

j) 重要なテクノロジの進歩がムーアの法則を押し進めている。

k) Exaflops! Just when you thought it was safe to ignore the Top-500 List.

(2) まずトップマシンについて。まだ平ら。IBMのBG/Lは依然世界最速。

a) BG/Lの説明

b) Cray XT4の説明

c) MareNostrumの説明。

d) TSUBAMEの説明

(3) ペタフロップスへのスプリント

a) DARPA HPCS Phase III

b) DARPA HPCS — Cray Cascade

c) DARPA HPCS — IBM PERCS

d) NSF Cyber Infrastructure / Big Iron

d) IBM Blue Gene/P

(4) Multicore — the Next Moore’s Law

a) IBM POWER6

b) Dual-core Intel Itanium 2

c) Cell Components and Layout

(5) アーキテクチャの多様性の爆発

a) GPGPU

  グラフィックのための道具を、もっと広い範囲の応用に用いる。GPUのスレッドは非常に軽いので、スレッドの切り替えのコストはほとんどない。主要な制限は、配列のような規則的なデータ構造を一様に処理するようなものでなければならない。NVIDIAとATI (AMDのFusion)

b) Sun UltraSparc Niagara

c) IntelのTera-scale Processor

d) Roadrunner

e) IBM Cyclops-64 Multi-core Chip

f) TRIPS

  Tera-ops Reliable Intelligently adaptive Processing System, DARPAの予算でテキサス大学が開発。

(6) 標準的なHECシステム—2007年版

　これも恒例であるが、最後に今年の標準的な先端的システム像を示した。

    — コモディティ・クラスタ（トップはMPPか？）

    — Intel 64-bit x86 microprocessor (Woodcrest) （私[Tom]は、本当はOpteronが好きなのだが）

    — Hewlett-Packardがシステム統合

    — Dual Core

    — 2048 scalar Processors

    — 10 Teraflopsの性能(Top500の平均）

    — 2 TB main memory (1 GB/proc. core)

    — Infiniband interconnect

    — MPICH2

    — Linux

    — 8 racks