2011/06/24 連絡先：[email protected] 目次はじめに  Cell Broadband Engine  Cell APIを用いたプログラミング方法  課題：kmeans法のアルゴリズム  課題の進め方  注意事項  はじめに  マルチコアプロセッサ上でのプログラミング  プログラマはマルチコアであることを意識してプログラミングする ○ 例）pthread関数, OpenMP  Cell Broadband Engine  PlayStation3にも搭載されているヘテロジニアスマルチコアプロセッサ  ヘテロジニアス型ゆえに独自のプログラミングテクニック ○ Pthread + Cellプログラミング独自のAPI  課題：シングルコア用ソースコードをCell/B.E.用に改造して高速化してください  コンテスト形式で行うコンテスト環境天野研究室 YGM72の写真天野研究室 YGM72の構成 GbE Cell搭載サーバ global network コンテストで使用 x86 server BCU-100 BCU-100 BCU-100 BCU-100 16 PS3s 16 PS3s 16 PS3s 16 PS3s local network 8 PS3 Cell Broadband Engineの構成  非対称型マルチコアプロセッサ  PlayStation3等に搭載  制御用コアのPPE×１  MainMemory  1GB (BCU-100) 演算用コアのSPE×８２５６KB  PPEが持つメインメモリに直接アクセス不可 SPE SPE SPE SPE EIB SPE SPE SPE SPE  LocalStore(LS)  コア間はElement Interconnect Bus(EIB: 約４００Gbps)にて接続 PPE Cell/B.E. PPE・SPE間の通信API  PPE・SPE間通信APIには主に２種類ある SPE制御API （PPEが発行） データ転送API （主にSPEが発行）  SPEはメインメモリに直接アクセス不可 Cellプログラミングの流れメインメモリ PPE ①spe_image_open関数 ②spe_context_create関数 ③spe_program_load関数 SP E SP E SP E SP E SP E SP E SP E SP E ディスク ④spe_context_run関数 ■ spu_mfcdma64関数 ⑤spe_context_destroy関数 ⑥spe_image_close関数以上のようにして PPEがSPEを制御する課題：Kmeans法  クラスタリングの手法  今回の課題では、シングルコアのみで動作する関数として実装されている kmeans法をCell用に改変してもらいます Kmeans法のアルゴリズム(1/5) 初期状態：何色かの点(ノード)がランダムに散らばっている (この例では100ノード、5色) STEP1: 各色のノードの集合に関して重心を計算 (図のXがそれぞれの重心) とってもわかりやすい参考URL: http://d.hatena.ne.jp/nitoyon/20090409/kmeans_visualise Kmeans法のアルゴリズム(2/5) STEP2 各ノードの色を、もっとも近い重心と同じ色に塗り変える STEP1: 再度、重心をそれぞれの色ごとに計算する Kmeans法のアルゴリズム(3/5) STEP2: 再度、各ノードの色を、もっとも近い重心と同じ色に塗り変える STEP1: 再度、重心をそれぞれの色ごとに計算する Kmeans法のアルゴリズム(4/5) STEP2: またまた、各ノードの色を、もっとも近い重心と同じ色に塗り変える STEP1: またまた、重心をそれぞれの色ごとに計算する Kmeans法のアルゴリズム(5/5) STEP2: またまたまた、各ノードの色を、もっとも近い重心と同じ色に塗り変える終了条件：すべてのノードが、一番近い重心の色に属していて、もう色を塗り替える必要がない →終了課題の進め方 ssh でjikoku.cell.st.keio.ac.jpにログイン  kmeans.tar.gzをダウンロード、展開  kmeans内のサンプルコードを参考にしながら  課題１：PPEのみで実行しているプログラムを改変して、SPEを用いて演算できるようにする   主にcellkmeans.hを改変する  SPE用のプログラムspe.cを新たに作成する  課題２：さらに、SPEでの実行を高速化する  spe.cを改変する kmeansディレクトリについて  kmeansディレクトリの中身  cellkmeans.h : Kmeans法を記述しているファイル・       主にこれを改変する define.h : 必要に応じて改変可 main.c : 改変不可 spe.c : spe上で実行されるコード・新たに作成する check.c : OpenCVによる出力結果の描画 gen.c : inputファイル生成 Makefile  ただし、公平性のためコンパイルオプション等はこちらで指定したものを用いて最終的に評価しますサンプルコードについて  hello world  multiple_spe_ver: 複数SPEをpthreadで制御 ○ テンプレートとしてよければどうぞ ○ 比較用として  multiple_pthread_ver (PPEのみ)  single_pthread_ver (PPEのみ)  single_spe_ver  mfc  PPE-SPE間のデータ転送記述例高速なプログラムを目指して  並列化①：SPEを複数用いて演算 <- 必須  特に、STEP2は演算量が多いのでうまく並列化できないか ○ ノード数×色数の分だけユークリッド距離を計算して比較   並列化②：SPEにてSIMD(Single Instruction Multiple Data)演算を用いるその他：ループアンローリング、ダブルバッファリングなど  Cellプログラミングに関してさらに詳しい内容はFixstarsの webチュートリアルを参照 ○ http://cell.fixstars.com/ps3linux/index.php/Cell%E3%83%97%E3 %83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83% B3%E3%82%B0%E3%83%81%E3%83%A5%E3%83%BC%E3 %83%88%E3%83%AA%E3%82%A2%E3%83%AB 注意事項  まず、初めにやること  [email protected]にメール ○ 氏名を明記 ○ 折り返し、アカウントと初期パスワードを送ります  自動返信ではないので、返信まで少々時間を頂きます(遅くとも 24時間以内には返信します)  課題締切：2011年7月15日(金) 24:00 厳守！！  提出方法：~/comparch以下に置く  提出物：ソースコード、簡単なレポート連絡等があればウェブページにて行います。  トラブル・リクエスト等、何かあれば、 [email protected] まで。 