慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp クラスタ  慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp.

Slides:



Advertisements
Similar presentations
情報ネットワークと教育 通信と情報ネットワーク プロトコル LAN The Internet. 通信とその歴史 通信とは 電信 (1835 、モールス ) 電話 (1876 、ベル ) ラジオ (1895) 、テレビ (1925) 情報通信ネットワークへ.
Advertisements

IP over DVB-RCS の設計と実装 研究背景 DVB-RCS 衛星回線を用いて受信局から送信局への狭帯域な戻り回線を提供 Forward Link Return Link HUB Terminal.
インターネット プロトコル 情報教員のためのサーバ管理技法 3 日目 柴田 功. 情報教育の失敗事例 ホームページ作成でロゴの画像の ファイル名が他の生徒とかぶってし まった。 ホームページ作成でロゴの画像の ファイル名が他の生徒とかぶってし まった。 生徒には作品を FD に保存させていた が、データが消えてしまった。
研究目標 研究目標 提案手法 仮想ネットワーク上でのブロードキャスト、マルチキャスト通信の実現
イーサアドレスとはなにか? 情報塾( ) IPアドレスとの関係は? ARP,DHCP?
松谷 宏紀 (慶大) 鯉渕 道紘 (NII) 天野 英晴 (慶大)
第2回 プロセス管理 ジョブ、プロセスとは? プロセスの状態遷移 プロセス制御ブロック スケジューリング.
情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹
インターネットのプロトコル階層 ネットワーク層(IPアドレス)
コンピュータ基礎(10) 11章 通信ネットワーク.
ネットワーク技術II 第8.2課 イーサネット・スイッチング
Network-on-Chip 最前線 ~研究の始め方から最新動向まで~ 松谷@慶應
第4章 Internet Address.
仮想ブロードキャストリンクを利用した 片方向通信路の透過的経路制御 藤枝 俊輔(慶應義塾大学)
スケールフリーネットワークにおける 経路制御のためのフラッディング手法の提案と評価
2004年度 情報システム構成論 第2回 TCP/IPネットワーク
Rearrangeable NoC: 配線遅延を考慮した分散ルータ アーキテクチャ
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
発表の流れ 研究背景 マルチテナント型データセンタ 関連研究 IPマルチキャスト ユニキャスト変換手法 提案手法 性能評価.
WindowsNTによるLAN構築 ポリテクセンター秋田 情報・通信系.
tracert(トレースルート)コマンドによるルーティング表示
輪講: 詳解TCP/IP ACE B3 suzuk.
研究背景 クラウドコンピューティングサービスの普及 ユーザ数の増加に伴う問題 マルチテナント方式の採用 データセンタの需要が増加
Copyright Yumiko OHTAKE
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
ネットワーク機器接続 2SK 情報機器工学.
コンピュータ基礎(10) 11章 通信ネットワーク.
ノードの情報を動的に反映したオーバレイネットワークの構築
Ibaraki Univ. Dept of Electrical & Electronic Eng.
サーバ負荷分散におけるOpenFlowを用いた省電力法
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
京都大学大学院医学研究科 画像応用治療学・放射線腫瘍学 石原 佳知
Ibaraki Univ. Dept of Electrical & Electronic Eng.
大阪大学 大学院情報科学研究科 博士前期課程2年 宮原研究室 土居 聡
TCP/UDP プロセス間の通信のためのプロトコル TCP:信頼性高、処理時間大 UDP:信頼性低、処理時間小 ftp SMTP HTTP
岡村耕二 情報ネットワーク 補足資料 岡村耕二 情報ネットワーク.
DiffServにおけるクラスの新しい設定方法の提案
勉強会その5    2016/6/15 マルチコア/マルチプロセッサ キャッシュコヒーレンス 10 8分35秒.
予測機構を持つルータを用いた低遅延チップ内ネットワークに関する研究
松谷 宏紀 (慶大) 鯉渕 道紘 (NII) 王 代涵 (慶大) 天野 英晴 (慶大)
オーバレイ構築ツールキットOverlay Weaver
VM専用仮想メモリとの連携による VMマイグレーションの高速化
出典・・・基礎からわかるTCP/IPコンピューティング入門 村山公保著
仮想メモリを用いた VMマイグレーションの高速化
セキュリティ(2) 05A2013 大川内 斉.
チャネルの動的On/Off制御のための 先読みルータアーキテクチャ
ネットワークの性能 牧野ゼミ3年 足立龍哉.
演習第6回 情報通信技術論 インターネット工学
低遅延オンチップネットワークのための予測ルータの評価
IP over DVB-RCSの設計と実装
慶應義塾大学理工学部 天野英晴 共有メモリ型計算機  慶應義塾大学理工学部 天野英晴
仮想ネットワークを考慮した SoftIRQ制御によるCPU割当ての手法
第5回 メモリ管理(2) オーバレイ方式 論理アドレスとプログラムの再配置 静的再配置と動的再配置 仮想記憶とメモリ階層 セグメンテーション
マイグレーションを支援する分散集合オブジェクト
トラフィックプロファイラAGURIの設計と実装
情報実験 第五回 最低限 internet ~ネットワークの仕組みを知ろう~
卒業研究 JCSPを用いたプログラム開発  池部理奈.
九州大学のキャンパスネットワークを事例にL1~L3を学ぶ Study on L1,L2 and L3 with case of Campus Network of Kyushu Univ. 岡村耕二 Koji OKAMURA.
情報ネットワーク 岡村耕二.
アルゴリズムとデータ構造1 2009年6月15日
理工学部情報学科 情報論理工学研究室 延山 周平
衛星回線を含むネットワークにおける 動的経路制御に関する研究
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
異種セグメント端末による 分散型仮想LAN構築機構の設計と実装
nチャネルメッセージ伝送方式のためのjailによる経路制御
ネットワークプログラミング 05A1302 円田 優輝.
アルゴリズムとデータ構造 2010年6月17日
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
情報ネットワーク 岡村耕二.
Presentation transcript:

慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp クラスタ  慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp

NORA/NORMA 共有メモリを持たない 交信はメッセージのやりとりで行う 接続はGigabit EthernetやInfiniband MPIが主に使われる 接続はGigabit EthernetやInfiniband 最近は多出力のスイッチを用いる ハイラディックスネットワーク データセンターなどで要求レベル並列性を処理 クラスタコンピューティング

Beowulf クラスタ 1994年NASA T.Sterling 安価で簡単に大規模並列計算環境を作ろう コモディティのPCを利用 コモディティのネットワーク(Ethernet)を利用 コモディティのソフトウェア(Linux)を利用 PVMやMPI(来週紹介)などのメッセージパッシング型ライブラリでプログラム →現在のClusterの元祖となった 現在のClusterは、InfinibandなどのSANを使うものも多いが、基本的に上記の原則を守っている

Infiniband System (Storage) Area Network (SAN)用. 8b/10b コードを利用. 様々な接続形態に対応. マルチキャスト可能. SDR DDR QDR 1X 2Gbit/s 4Gbit/s 8Gbit/s 4X 16Gbit/s 32Gbit/s 12X 24Gbit/s 48Gbit/s 96Gbit/s

RHiNET-2 cluster

クラスタの接続網 直接網(direct/distributed) 間接網(indirect/centralized) ノード同士を直接つなぐ k-ary n-cubeが主に利用される 間接網(indirect/centralized) スイッチを経由してつなぐ Fat Tree, DragonflyなどHigh-radix系が流行っている パケットをどのように転送するかが重要

1.直接網 まずは基本的なもの Linear Central concentration Ring Tree Complete connection Mesh

直接網の評価基準(D and d) 直径(Diameter):D 次数(degree): d ネットワーク中の最も遠い2ノード間の最短ホップ数 次数(degree): d ノードに繋がるリンクの最大数 ASPL (Average Shortest Parth Length) 平均距離

直径の例 2(n-1)

二分バンド幅 bi-section bandwidth ネットワークを等分した際の 交信量→もっとも小さいものを 取る

Hypercube 0001 0000 0010 0011 0100 0111 0101 0110 1000 1001 1010 1011 1100 1101 1110 1111

Routing on hypercube 0101→1100 Different bits 0001 0000 0010 0011 0100 0111 0101 0110 1000 1001 1010 1011 1100 1101 1110 1111

hypercubeの直径 0101→1010 All bits are different → the largest distance 0001 0101→1010 0000 0010 0011 All bits are different → the largest distance 0100 0111 0101 0110 1000 1001 1010 1011 1100 1101 1110 1111

k-ary n-cube メッシュ、トーラスの一般化 n桁のK進数を各ノードに割り当てる。 それぞれの次元(桁)方向にリンクを順に設ける。 k-ary n-cube メッシュ、トーラスの一般化 n桁のK進数を各ノードに割り当てる。 それぞれの次元(桁)方向にリンクを順に設ける。 巡回するリンク(n-1→0)を持てば トーラス、そうでなければメッシュ 2次元、3次元メッシュ、トーラス、リング、直線状、hypercubeを含むファミリー

k-ary n-cube 0 1 2 0 1 2 3-ary 1-cube 3-ary 2-cube 0 1 2

k-ary n-cube 2 0 1 2 1 0 1 2 3-ary 3-cube 0 0 1 2 3-ary 1-cube 3-ary 3-cube 0 0 1 2 3-ary 1-cube 3-ary 2-cube

3-ary 4-cube 1*** 0*** 2***

3-ary 5-cube 0**** 1**** degree: 2*n Diameter: (k-1)*n 2****

6-次元 Torus Tofu

トレンドの移り変わり n k hypercube machines 1980’s 16 HW router Wormhole, VC Bandwidth requirement 10 5D/6D Mesh/Torus 2010’s 5 Optical links, Increasing size Low-latency requirement 3 2 2D/3D Mesh/Torus 90’s-2000’s 2 k 100 1000

2.間接網 等距離間接網 不等距離間接網 Multistage Interconnection Network (MIN) 最近はButterflyと呼ばれる 局所性が生かせないので大規模なシステムに向かない 不等距離間接網 base-m n-cube Fat Tree Dragon FlyなどHigh Radixネットワーク

Omega網 2x2のスイッチ素子を利用、Perfect Shuffleでステージ間を接続 000 001 010 011 100 101 110 111 2x2のスイッチ素子を利用、Perfect Shuffleでステージ間を接続

base-m n-cube (Hyper crossbar) router PU Used in Toshiba’s Prodigy and Hitachi’s SR8000

Fat Tree Myrinet-Clos はClosではなく Fat-tree

Myrinet-Clos(1/2) 128nodes(Clos128)

Flattened butterfly router (5×5) router (2×2) 2-ary 4-fly 24=16 node 2-ary 4-flat 24=16 node ルータがhigh-radixのものを使っている(ポート数が増えている) n-ary n-flat についてもう少し詳しく説明しよう ここまでのつながりがよろしくない 32-ary 2-flyの説明がほしい 行? A row of MIN is fused. High radix → High bandwidth Multiple paths can be formed 26

Dragonfly … … global channels … Intra-group int. network ... Rn-1 Inter-group int. network … … … terminal channels … G0 G1 Gg … … … P0 P1 Pk-1 Pk Pk+1 P2k-1 PN-k-1 PN-k PN-1

G1 G2 G8 …… An example of Dragonfly (N=72) G0 R0 R1 R2 R3 The interconnection of this part can be Flatten Butterfly P0 P1 P2 P3 P4 P5 P6 P7

k-ary n-cube 対 high radix スーパーコンピュータ k-ary n-cube high radix クラスタ・データセンター high radix k-ary n-cube チップ内(Network-on Chips:NoCs)

3.パケットの流し方 クラスタではパケットスイッチングを使う length,source,etc. Body 8bit~64bit destination Tailer: CRC etc. length,source,etc. 8bit~64bit Header Flit パケットスイッチング Flit: 転送の基本単位 配線のbit幅でない場合もある サーキットスイッチング クラスタではパケットスイッチングを使う

パケット転送手法 ストア・アンド・フォワード(Store-&-Forward) ウォームホール(Wormhole) パケット全体をノードのバッファに蓄えてから次のノードに送る TCP/IP は、これを使っている ウォームホール(Wormhole) フリット単位で先に進んでいける 先頭が進めなくなると全体が停止する バーチャル・カットスルー(Virtual Cut Through) 先頭のflitが進めなくなるとパケットの残りをノード中のバッファに格納する

Store and Forward パケット全体をバッファに格納してから進む ノード単位で再送が可能 しかし転送レイテンシィが大きい:D(h+b) バッファサイズも大きいものが必要 パケット転送、エラー時の再送制御などはソフトウェアで 可能→TCP/IPで使われる

Wormhole パケットのフリットはどんどん先に進める 転送遅延が小さい hD+b 4 4 3 2 3 2 1 1 パケットのフリットはどんどん先に進める 転送遅延が小さい hD+b   h: header, D:Diameter, b: body バッファ要求量も小さい(ヘッダが入ればいい) しかし、先頭が進めないと複数のノードにまたがって  パケットがストップしてしまう→混雑の原因に!  →仮想チャネルが有効 ハードウェアの専用ルータ(スイッチ)が必要

Wormhole 4 2 1 3 2 1

Wormhole 4 3 2 1

Wormhole 4 3 2 1

Virtual Cut Through Wormholeと同じくどんどん先に進める 先頭が進めなくなると、残りがバッファに入る 4 4 3 2 3 2 1 1 Wormholeと同じくどんどん先に進める 先頭が進めなくなると、残りがバッファに入る  →ノードにまたがってバッファを占領しない  →Wormholeほど混雑をおこさない。 Wormholeと同じ転送遅延時間 Store and Forwardと同じバッファが要求される ハードウェアルータが必要

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

Virtual Cut Through 4 3 2 1

仮想チャネル(Virtual Channel) 特にWormholeでは、パケットが複数のノードのバッファを占有 行先のバッファが空いていても、途中が占有されて先に進めない 独立したバッファとハンドシェーク線を用意することで、物理的な配線を増やさずに空いたバッファを有効活用 デッドロック回避(後程説明)にも有効

右に曲がりたいのだが、前がつっかえて曲がれない 仮想チャネル:混雑の回避 空いているのに もったいない 右に曲がりたいのだが、前がつっかえて曲がれない 右折レーンを付ければいい

仮想チャネルの実装 仮想チャネル(VC)は新しいレーンを作ること 物理的なワイヤを増やすのではないことに注意! VC#0 空いているのに もったいない 仮想チャネル(VC)は新しいレーンを作ること 物理的なワイヤを増やすのではないことに注意! [Dally,TPDS’92] VC#0 Packet (a) Packet (b) VC#1

バッファの空きを知らせる線が必要 NODE ハンドシェーク線 バッファ Link Crossbar ハンドシェーク線 バッファ MUX

デッドロック 互いに行先のバッファをブロックしてしまう

デッドロックの回避 バッファ間の依存関係が循環構造を形成しないようにする。 ネットワークに応じて様々な構造が提案されている 循環しない位多量にバッファを持たせる 構造化バッファ法 曲がる方向を制限する XY Routing (Dimension Order Routing) Turn model 仮想チャネルを使う ネットワークに応じて様々な構造が提案されている

まとめ 共有メモリを持たないクラスタは、最も簡単に大規模な並列コンピュータを構成できる 独立したジョブを扱うデータセンターなどに向いている ノード間のネットワークが重要 直接網 間接網 ルーチング手法 プログラムは、メッセージパッシングライブラリを用いてノード間のデータ交換を明示的に指定する →次回演習

演習 4-ary 8-cubeで、ヘッダサイズ1、ボディ16フリットのパケットをWormhole方式で、転送した場合、最大遅延は何クロックになるか? 1クロックに1フリット転送可能と考える パケットの衝突は考えない