トップ 新規 編集 差分 一覧 Farm ソース 検索 ヘルプ PDF RSS ログイン

Cell Challenge 2009

[Cell]

ここは?

SACSIS2009併設企画 Cell Challenge 2009に関する情報共有の場

大会スケジュール

現時点での予定です。予告なく変更になることがあります。ご了承ください。
2008/12/01
規定課題概要公開,参加受付開始,ツールキット(試用版)公開
2009/01/05
規定課題詳細,ツールキット公開
2009/01/21→28
参加受付〆切,予選ラウンド開始
2009/02/27
規定課題 予選ラウンド終了,自由課題終了
2009/03/06
規定課題 決勝ラウンド開始
2009/03/20→21
規定課題 決勝ラウンド終了
2008/05/28〜
SACSIS2009 にて表彰

課題

Cell Challenge 2009 の規定課題は「文字列の編集距離計算」です.

共有ファイルはbluebaseの /home/doc/document/CellChallenge2009 にでも保存しましょう。

ツールキット

ドキュメント

処理の流れ(toolkit ver.0.1版。正式版は異なる。)

  1. main_ppe.c(エントリプログラム)
    1. 【初期化処理】2つの入力文字列を読み込む(110--144)
      1. buf1, num1: 文字列1とその文字数
      2. buf2, num2: 文字列2とその文字数
    2. 【PPEで計算】編集距離をPPEで求めて、ppe_resに格納(144--145)
    3. 【SPEの実行】7つのSPEへ計算要求、終了まで待つ(149--199)
      1. 全てのsc[i].{buf1,buf2}は、入力文字列へのポインタ(ここでは同一文字列を指しているが、main_spe.cでローカル変数にコピーする)
      2. sc[i].{num1,num2}には、入力文字列の文字数
      3. 最終的にSPEプログラムは、sc[i].buf4[0]に計算結果を格納する
      4. buf3とbuf4[1-31]は未使用なので、各PEの通信に使える?
    4. 【計算結果の比較】SPEプログラムの終了処理後、PPEの計算結果(ppe_res)とSPEの計算結果(buf4[0])を比較し、正しいか評価する(201--236)
  2. main_spe.c(main_ppe.cから呼び出される)
    1. 入力をローカル変数scへコピーする
    2. spe_caldst()関数を呼び出す(spe1.cで定義)
  3. spe1.c(ここを考える)

toolkit0.1をps3a.yuba.is.uec.ac.jpでコンパイルするには

$ tar xvzf toolkit01.tgz
$ cd toolkit0.1
$ cp Makefile Makefile.orig         # Makefileのバックアップ
$ vi Makefile                       # Makefileの編集
$ diff Makefile Makefile.orig       # 編集内容は以下
4,6c4,6
< USERNAME = USERNAME
< IDIR     = /export/home/$(USERNAME)/toolkit0.1
< EXE_FILE = /export/home/$(USERNAME)/toolkit0.1/main
---
> USERNAME = matsum
> IDIR     = /home/$(USERNAME)/src/cell2009/toolkit0.1
> EXE_FILE = /home/$(USERNAME)/src/cell2009/toolkit0.1/main
14c14
< PPE_CC  = /opt/cell/toolchain/bin/ppu-gcc
---
> PPE_CC  = /usr/bin/ppu-gcc
21c21
< SPE_CC  = /opt/cell/toolchain/bin/spu-gcc
---
> SPE_CC  = /usr/bin/spu-gcc
$ cp spe.h spe.h.orig               # spe.hをバックアップ
$ vi spe.h                          # spe.hを編集
$ diff spe.h.orig spe.h             # spe.hの編集内容は以下
6c6
< #define EXE_PATH "toolkit0.1/"
---
> #define EXE_PATH ""
$ make

この方法だとコンパイルと実行はできるが、途中でフリーズする。main_ppe.c:191--193 で止まっているので、SPEの方とうまく同期が取れていない模様。要調査。

↑SPEの数を7と設定しているのが問題。spe.h:4を

#define NUM_SPE 6

などのように6以下の数にしたら解決。

toolkit0.5 for ps3a.yuba.is.uec.ac.jp

ps3a.yuba.is.uec.ac.jpで簡単に動かせるようにちょっと変えたtoolkit0.5をおいておきます。展開してmake run1とかやればすぐ動きます。

お役にたてば幸いです(もうすぐ正式版もリリースされますが)。

toolkit0.5_for_ps3a.tar.gz(9)

$ tar zxvf toolkit0.5_for_ps3a.tar.gz
$ cd toolkit0.5_for_ps3a/
$ make run1

toolkit1.0.x for ps3a.yuba.is.uec.ac.jp

例にならってツールキットver.1.0.xのps3a版。どうぞ。

toolkit102_for_ps3a.tar.gz(9)

  • toolkit1.0.3 for ps3a のつくりかた

改善案

不要なDMA転送をしないようする

主な修正点

  • (spe1.c)直前に計算したデータが使えるならdmaget関数を呼ばないように修正
  • (ppe.c)キューをSPEに割当てる際、単純に暇なSPEへ割当てず、直前にその隣を計算していたSPEに優先的に割当てるように修正

ソースコード: cell2009-dma.tar.gz(7)

修正前と性能比較を行った

  • プラットフォーム: ps3a
  • 比較元とするプログラム: ツールキットver.1.0.2をps3a用に修正したプログラム
  • NUM_SPE: 6
  • データ: run1、run2、run3の3種類
  • 50回計算を行い、平均の計算時間を得る
run1 run2 run3
修正前 0.0759861 0.264899 1.01769
修正後 0.0757417 0.262961 1.01597
比率(後/前) 0.9967836 0.9926840 0.9983098

およそ0.16〜0.73%の性能向上が見られた。

(2009/2/2追記)

  • 良くなる要因
    • DMA転送量が減る(dmaget()関数を呼ぶ回数が減る)
  • 悪くなる要因
    • PPEはすぐにSPEに仕事を割り振らず、キャッシュの使えるSPEを探してから割り振る。なので、その間に止まり続けるSPEが少なくとも1つある。
    • SPEはキャッシュが使えるかどうかを判定してからDMA転送する。条件分岐による遅延があるかもしれない。

前回の結果が微々たる変化だったので、本当に性能向上してるか疑わしい。同じ検証を何度か繰り返したところ、性能が低下することも何度かあった。

キャッシュを利用してDMA転送を省略する回数をrun3を用いて調べたところ、ばらつきはあるが1/500(=50回/25600回)程度の割合だった。そのために、良くなる要因が活きないと考えられる。

ブロックサイズをデータにあわせて変更する

ソースコード: cell2009-block.tar.gz(7)

主な修正点

  • 文字列の長さnum1が20480以上である場合、ブロック数bnum1を(num1/64)とする。bnum2も同様。
  • ブロックサイズ変更のプログラムは、本ページの「ブロックサイズの変更による性能変化」を元にしている。

修正前と修正後の計算時間を以下の条件で比較した

  • プラットフォーム: ps3a
  • NUM_SPE: 6
  • サンプルデータ: 文字列長10KBから100KBまでのデータの組を、それぞれ25サンプルずつ
  • 各データについて、25組の計算時間の平均を算出
文字列長(KB) 10 20 30 40 50 60 70 80 90 100
修正前 0.26352 1.01204 2.25604 3.99963 6.23406 8.96826 12.19890 15.92690 20.12620 24.84790
修正後 0.46743 1.81033 4.04892 7.18661 11.20650 16.12660 21.94310 28.64930 36.25210 44.74780
性能比(後/前) 1.77379 1.78879 1.79470 1.79682 1.79762 1.79819 1.79878 1.79880 1.80124 1.80087

77%から80%計算時間が長くなってしまっている。

考えられる原因は

  • ブロックサイズを固定長から可変長にしたことによるオーバーヘッドが大きすぎる
  • ブロックサイズを可変長にしてもそれほど性能向上に寄与しない

キューの改良

ソースコード: ppe.c.que(8)

修正点

計算できないキューは通常通りenqueueするが、計算できるキューは次にもう一度取り出せるように戻す(push)。

$ diff ppe.c ppe.c.que
36a37,46
>   else if(qu->head == QUEUE_SIZE-1 && qu->tail == 0) qu->state = QUEUE_FULL;
>   else                         qu->state = QUEUE_IDLE;
> };
>
> void queue_enq_tail(UINT32 in, queue* qu){
>   if(qu->tail != 0) qu->tail--;
>   else              qu->tail=QUEUE_SIZE-1;
>   qu->entry[qu->tail] = in;
>   if(qu->head == qu->tail-1)   qu->state = QUEUE_FULL;
>   else if(qu->head == QUEUE_SIZE-1 && qu->tail == 0) qu->state = QUEUE_FULL;
197c207
<           else queue_enq(blk_id, &bqueue);
---
>           else queue_enq_tail(blk_id, &bqueue);

検証

修正前と性能比較を行った

  • プラットフォーム: ps3a
  • 比較元とするプログラム: ツールキットver.1.0.2をps3a用に修正したプログラム
  • NUM_SPE: 6
  • データ: run1、run2、run3の3種類
  • 50回計算を行い、平均の計算時間を得る
run1 run2 run3
変更前 0.0762162 0.263384 1.01217
変更後 0.0758743 0.263053 1.01186
性能比 0.9955140 0.998743 0.99969

ほとんど変わりません!

SIMD化に向けて

配列構成を変えて分岐を減らしまくってみた by大島

基本戦略は,並列性を出すため斜め処理.

  • プラットフォーム: ps3a
  • NUM_SPE: 6
  • 10回平均

base
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock 0.065496541 0.224973417 0.860779858 0.009840107 0.016973569

分岐殺し
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock 0.065909316 0.225414945 0.861314582 0.009354425 0.017369651

あれ,ほとんど変わらないぞ……Cellって分岐が多くても特に問題無いんだっけ?まぁここからSIMD化しますが.

SIMD化してみた(大島)

SIMDブロックはSIMDしかしないようにした
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock 0.049584794 0.16122849 0.60564053 0.009776615 0.017309379
run4が速度低下しているけど,それ以外は速度向上してる.なるほど.

もうちょっとがんばった気がする
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock 0.04737742 0.152813006 0.573273038 0.009255575 0.016686201
でかい問題は高速化されやすい?

さらにがんばってみた.めぼしいところはSIMD化し終わったつもり.細かいチューニングはしたいけど.
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
min eclock 0.03829122 0.12328815 0.45604086 0.008605 0.01335502

配列の扱い方をちょっと変えてみた.allresult
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
min eclock 0.02381802 0.05993605 0.20824814 0.00823998 0.01174903
max eclock 0.02599597 0.066715 0.21189213 0.01112199 0.01541519
一つ前よりだいぶ速くなった.問題サイズが小さいものについては微妙だが.

配列のデータ構造を斜め(/方向)に変更

ソースコード: spe1.c-skew-v1.tar.gz(8)

SPEが内部に持つ128x128の配列を、次のような斜め方向の順番で保持するように変更した。

大島さんのSIMD化と久米君のmin関数の改善案を参考にしている。

- - - - - - -
0 1 3 ・・・ 7878 8001 8128
2 4 7 ・・・ 8002 8129 8256
5 8 ・・・ 8130 8257 8353
・・・
8000 8126 8253 ・・・ 16378
8127 8254 8381 ・・・ 16379 16381
8255 8382 8508 ・・・ 16380 16382 16383

実行時間の比較を行った。(ps3a, NUM_SPE 6, 100回平均)

- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock(修正前) 0.0758221985 0.263651738 1.0164351747 0.009846897 0.0197983389
eclock(修正後) 0.0649134754 0.2220238635 0.8476732353 0.0099163937 0.0182811546
修正後/修正前 0.856 0.842 0.833 1.007 0.923

大体で実行時間が短くなった。SIMD用のAPIはまだ使ってないが、イタレーション内の並列性が増したのでうまく最適化してくれてるのかも。

(2009/2/18追記) CellOpenCafeで動かしたところ、改善が見られなかった。

配列のデータ構造を斜め(/方向)に変更(その2)

ソースコード: spe1.c-skew-v2.tar.gz(11)

  • SIMD化した
  • cell open cafeで動かした
  • 7SPEs, 10回試行

修正前
run1 run2 run3 run4 run5
最小値 0.18418884 0.38558602 1.18953204 0.01631117 0.12288499
最大値 0.28284383 0.55217814 1.28819895 0.01645517 0.17086101
平均 0.246108 0.424345 1.23789 0.0163678 0.128192

修正後
run1 run2 run3 run4 run5
最小値 0.18483210 0.38571405 1.18967891 0.01629901 0.12291908
最大値 0.28067994 0.48550391 1.29043913 0.01645422 0.17128301
平均 0.245113 0.429357 1.21361 0.01635 0.133016

最小値と最大値の幅が100msec程度あり、ps3aに比べて非常に大きい。性能向上は1%から2%程度みられた。(少ない…)

ためしにSIMD化する前のものをOpenCafeで動かしたが、性能向上は見られなかった。ps3aでよくなっても、必ずしもOpenCafeで同じように改善するとは限らないようだ。

配列のデータ構造を斜め(/方向)に変更(その3)

ソースコード: skew2-v2.1-spe1.c(15)

  • 保持するデータ構造を全面的に修正した
  • cell open cafeで動かした
  • 7SPEs, 10回試行
old run1 run2 run3 run4 run5
min 0.18371391 0.38603997 1.19146013 0.01619697 0.12282300
max 0.28271604 0.52395988 1.27221704 0.01694894 0.12507701
avg 0.24412980 0.43096967 1.22462003 0.01635971 0.12811401
new run1 run2 run3 run4 run5
min 0.18409395 0.38549685 1.18995595 0.01615596 0.12285399
max 0.28060198 0.49126792 1.24070883 0.01643491 0.12368011
avg 0.22955408 0.44401028 1.21008711 0.01624906 0.12337446

ps3aでも簡単に比較したところ、その2よりさらに性能向上していた。(run3: 0.80sec→0.65secぐらい)

ただしソースの可読性は反比例して悪くなった。

(2009/2/26追記)

もう少しがんばった版:skew2-v2.2-spe1.c(9)

10回試行 on ps3a
run1 run2 run3 run4 run5
min 0.04037499 0.13529015 0.50844812 0.00858593 0.01570392
max 0.04904294 0.14000988 0.51873779 0.01215291 0.02204108
avg 0.04449601 0.13736057 0.51259952 0.00992448 0.01846075

run3: 0.65sec→0.50secぐらいまで向上した。

PPEにも計算させる

ソースコード: ppecalc-1-ppe.c(11)

  • PPE上で計算するスレッドを1つ走らせる。(SIMD化していないプリミティブな計算方法)
  • ps3a, 6SPEs, 10回平均
  • SPE-SIMD化はskew2-v2.1-spe1.c(15)のやつ、PPE計算はppecalc-1-ppe.c(11)のやつ
run1 run2 run3 run4 run5
修正前 0.075078509 0.075078509 1.013955735 0.010421109 0.021378232
SPE-SIMD化 0.050538112 0.050538112 0.614989974 0.010416389 0.018289113
PPE計算 0.100525474 0.100525474 0.985107399 0.009664129 0.068906307
SPE-SIMD化 & PPE計算 0.114116454 0.114116454 0.659179879 0.010578108 0.029006720

あまり有効でないようだ。

検証

toolkit ver.0.1とver.1.0の比較

どれくらい高速になったかを簡単に調べた。(ps3a上でNUM_SPE=6)

$ cd toolkit0.1
$ make run2
./main ./file5 ./file6
strnum(a)= 10240
strnum(b)= 10240
str1 : 10240 : blk 80
str2 : 10240 : blk 80
[SPE_] : 9581
[PPE_] : 9581
eclock  : 1.48276401
dec_cnt : 1.18090959
SUCCESSFUL.
$
$ cd ../toolkit1.0
$ make run2
./main ./file5 ./file6 9581
answer = 9581
strnum(a)= 10240
strnum(b)= 10240
[SPE_] : 9581
[PPE_] : 9581
eclock  : 0.26406312
SUCCESSFUL.

プロセッサ数が6倍で、計算時間は約0.178倍(逆数は5.6程度)なのでかなり良い並列化ができている。ver.1.0より大幅に高速化することは難しそう…。

ブロックサイズの変更による性能変化

SPEが計算する部分行列は128x128がデフォルトだが、そのサイズを変更したら性能はどのように変化するかを調べた。

ソースコード: cell2009-flexible-block.tar.gz(9)

主な修正点

  • (spe.h): spe_ctrl(sc)のメンバに、ブロックサイズ数bsize1およびbsize2を新たに追加
  • (spe1.c): 部分行列(buf)をグローバル変数として持たないようにした

検証の概要

  • ブロックの大きさを16x16, 32x32, 64x64, 128x128, 256x256, 512x512の6段階に変化させる
  • run1(5120x5120), run2(10240x10240), run3(20480x20480)の3種類のサンプルデータで実行
  • ブロックサイズ、サンプルデータの組合せごとに50回ずつ実行し、平均の計算時間を算出
block-size run1 run2 run3
16x16 0.185 0.698 2.750
32x32 0.140 0.524 2.060
64x64 0.129 0.477 1.875
128x128 0.129 0.466 1.823
256x256 0.131 0.466 1.807
512x512 0.157 0.493 1.826

この結果を見ると、最適なブロックサイズはサンプルデータによらず、1600分割(40x40分割)〜6400分割(80x80分割)あたりに良いブロックサイズがあるように見える。

  • SPE*6のrun1〜5でも測定してみた(大島)
    • ps3aで10回の最小時間をとった
    • カーネルはSIMD化してない初期状態

32
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
min eclock 0.08827114 0.32413697 1.26304507 0.01139593 0.01489592

64
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
min eclock 0.07560897 0.27491903 1.06912303 0.01002717 0.01387

128
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
min eclock 0.07364488 0.2619729 1.00781989 0.00834394 0.01664901

run4あたりは小さい方が速いんじゃないかと思ったけど,全然意味ないねこれ.計算量が小さすぎるのかなあ?

SPE数を変更したときの性能変化

  • 環境はps3a
  • ツールキットver.1.0.2を使用
  • NUM_SPEを1から6まで変化させ、make run3を行った。
  • 50回上記を繰り返し、平均の計算時間を算出
SPE数(n) 平均計算時間(a(n)) a=1との性能比(p(n)=a(n)/a(1)) a=1と比較したときのオーバーヘッド(p(n)*n)
1 5.999 1.000 1.000
2 3.009 0.501 1.003
3 2.007 0.334 1.003
4 1.509 0.251 1.006
5 1.210 0.201 1.008
6 1.012 0.168 1.013

結果を見ると、

  • 当然ながら、計算時間aはSPEの数nにほぼ反比例している
  • オーバヘッドはn^2に比例していると予想すると、NUM_SPE=7のときのオーバーヘッドは1.8%程度である
    • a(7) < a(1) / 7 * 1.017 (上記のデータなら0.871秒)

細かい改善 and etc...

'09/2/5

ちょっと書き方を変えたやつをspe1_kume_20080204_01.c(9)におきました.

  • spe_LD(): 分岐が時間がかかると勝手に仮定し,分岐(if)をなくすよう努力
  • min(): これの考え方→min()って変えて良かったのでしたっけ?→だめならspe_LD()に組み込む!

これでやったところ(ps3a, 100回平均, 6 SPEs)
make run1 make run2 make run3 make run4 make run5
toolkit1.0 (eclock) 0.0750 0.2615 1.0118 0.0106 0.0196
spe1_kume_20080204_01.c (eclock) 0.0665 0.2215 0.8496 0.0109 0.0206
性能比 (後/前,%) 88.7 (勝) 84.7 (勝) 84.0 (勝) 103 (負) 105 (負)

一部遅いが速くなった(3勝2敗で一応勝ち越し)!?というか一部遅いってことは誤差の範囲だろうか….

問題サイズが小さいやつは苦手?今度はベクトル演算を試してみる.('09/2/5)

'09/2/26

skew2-v2.1-spe1.c(15)をもとに高速化を図った(ソースコード(SPE): spe1_kume_20080226_01.c(11)).

(ps3a, 10回平均, 6 SPEs)
- run1 run2 run3 run4 run5
answer 4800 9581 19168 224 2944
strnum(a) 5120 10240 20480 128 384
strnum(b) 5120 10240 20480 256 3328
[SPE_] 4800 9581 19168 224 2944
[PPE_] 4800 9581 19168 224 2944
eclock 0.043875646 0.137969924 0.510681295 0.009680199 0.01697948
性能比 (対toolkit,%) 58.6 52.2 50.4 91.7 82.0
skew2-v2.2-spe1.c(9)と同程度であった.('09/2/26)

その他

計算時間の平均、中央値、最小値、最大値を求めるスクリプト

  • 上記のrunallで計算した結果を複数受け取る
  • eclockの列の合計、平均、中央値、最小値、最大値をeclock.resultに出力する

eclock.sh

#!/bin/sh

if [ $# -lt 1 ]
then
    echo "Usage: $0 <runall.result files...>"
else
    paste $* > eclock.result.raw
    echo "sum	avg	mid	min	max" > eclock.result
    gawk -f eclock.awk eclock.result.raw >> eclock.result
    rm eclock.result.raw
    cat eclock.result
fi

eclock.awk

#!/usr/local/bin/gawk -f
NR>1{
    SET=NF/4;
    MID=int(SET/2)+1;
    for(i=1;i<=SET;i++) r[i]=$(i*4);
    sort(r,SET);
    s=sum(r,SET);
    printf("%.4f\t%.4f\t%.4f\t%.4f\t%.4f\n",
            s,s/SET,r[MID],r[1],r[SET]);
}
function sum(r,n,       i,s){
    for(i=1;i<=n;i++) s+=r[i];
    return s;
}
function sort(r,n,      i,j,b){
    for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) if(r[i]>r[j]){
        b=r[i]; r[i]=r[j]; r[j]=b;
    }
}

使用例(make runall を10回実行し、計算時間の集計をする)

$ for i in `seq 0 9`; do ./runall.sh; mv runall.result runall.result.$i; done
num(a)  num(b)  answer  eclock
5120    5120    4800    0.07747912
10240   10240   9581    0.26888299
20480   20480   19168   1.01256394
128     256     224     0.00983310
384     3328    2944    0.01803994
num(a)  num(b)  answer  eclock
5120    5120    4800    0.07524991
10240   10240   9581    0.26436496
20480   20480   19168   1.01219702
128     256     224     0.00901103
384     3328    2944    0.01974201
...
$ ./eclock.sh runall.result.*
sum     avg     mid     min     max
2.5687  0.0778  0.0769  0.0728  0.1100
8.7211  0.2643  0.2637  0.2588  0.2722
33.4351 1.0132  1.0125  1.0036  1.0349
0.3812  0.0116  0.0108  0.0087  0.0333
0.6114  0.0185  0.0177  0.0147  0.0420

実行結果を見やすくするシェルスクリプト

make runall を実行し、結果を表形式に整理するシェルスクリプト

表形式にまとめた結果は runall.result に保存される。

runall.sh

#!/bin/sh
# 文字列長、解、および計算時間のラベル
echo "num(a)" > runall.log.anum
echo "num(b)" > runall.log.bnum
echo "answer" > runall.log.ans
echo "eclock" > runall.log.eclk
# 実行
make runall > runall.log
# 文字列長、解、および計算時間をそれぞれgrepし、数値部分を抜き出す
grep strnum\(a\) runall.log | tr -d "[:alpha:][:blank:]=:()" >> runall.log.anum
grep strnum\(b\) runall.log | tr -d "[:alpha:][:blank:]=:()" >> runall.log.bnum
grep answer      runall.log | tr -d "[:alpha:][:blank:]=:()" >> runall.log.ans
grep eclock      runall.log | tr -d "[:alpha:][:blank:]=:()" >> runall.log.eclk
paste runall.log.anum runall.log.bnum runall.log.ans runall.log.eclk > runall.result
# ログファイルの削除
rm -f runall.log*
# 結果の表示
cat runall.result

実行例

$ ./runall.sh
num(a)  num(b)  answer  eclock
5120    5120    4800    0.07354116
10240   10240   9581    0.26230693
20480   20480   19168   1.01341701
128     256     224     0.00926614
384     3328    2944    0.01757097

実行結果を見やすくするシェルスクリプト2

pythonでぶんまわしてfswikiテーブル形式を吐くスクリプト.ps3aで動くことを確認.

runall1.py(15)

サンプルデータ

bluebase共有スペースにサンプルデータおよび答えを置いた。# 圧縮して100M近くあったのでwikiに添付するのは止めて置いた

  • /home/doc/documents/CellChallenge2009/samples においてある。
  • 文字列の長さごとにディレクトリ分けしてある
  • 文字列長は10KBから100KBまで10KBごとに10種類
  • 各ディレクトリに50組100個の文字列が入っている
  • ファイル名は *.data で、乱数種の番号
  • (1.data, 2.data) の編集距離の答えは 1-2.ans に書かれている。同じディレクトリにある。
  • samples
    • 10k
      • 1.data ... 乱数種1で生成した10KB(10240文字)の文字列
      • 2.data
      • 3.data
      • ...
      • 100.data
      • 1-2.ans ... 1.dataと2.dataの編集距離
      • 3-4.ans
      • ...
      • 99-100.ans
    • 20k
      • 1.data ... 乱数種1で生成した20KBの文字列
      • ...
    • ...
    • 100k
      • ...

queue_enq()関数にバグ?

ppe.c:32-38のqueue_enq()関数は、

  • qu->head==QUEUE_SIZE-1
  • qu->tail==0

の時にちゃんと動作しないのでは…?

修正後のqueue_enq()関数

void queue_enq(UINT32 in, queue* qu){
  qu->entry[qu->head] = in;
  if(qu->head != QUEUE_SIZE-1) qu->head++;
  else                         qu->head = 0;
  if(qu->head == qu->tail-1)   qu->state = QUEUE_FULL;
  else if(qu->head == QUEUE_SIZE-1 && qu->tail == 0) qu->state = QUEUE_FULL;
  else                         qu->state = QUEUE_IDLE;
};

参加チーム

規定課題部門

M1一同

  • チーム名: Team KSM
  • 代表者: 久米
  • 監督者: 本多先生
  • 進捗
    • 参加申し込みメール送信済み(12/10、久米)
    • Cell Open Cafeアカウント取得済み(12/11、久米)
      • ユーザID: teamksm

規定課題部門・自由課題部門

  • チーム名:CPUのちGPUところによりCell
  • 代表者:大島
  • 監督者:本多先生

予選

予選結果 http://www.hpcc.jp/sacsis/2009/cell/kiteiyosen2009.htm

上位がオニ速い。不可解。

予選で使用したデータはOpenCafeの

  • /export/home/contest_toolkit/yosendata.tgz
  • /export/home/contest_toolkit/Makefile.yosen

にある。

予選内容

問題1 問題2 問題3 問題4 問題5
データ1 65536 524288 130816 1048320 1048448
データ2 65536 8192 130816 16384 16384
0 516096 122245 1031936 1040256
1位実行時間 0.000 0.061 0.204 0.000 0.192
5位実行時間 0.034 0.481 1.231 0.314 1.578

データの特徴

問題1
解ゼロ。全く同じ文字列の比較。
問題2
文字列長が大きく異なる。内容はおそらくランダム生成。
問題3
文字列長が同じ。内容はおそらくランダム生成。
問題4
(データ1文字数) - (データ2文字数) = (解) なので (データ1) ⊃ (データ2)
問題5
  • データ1…8,160個の「A」 + ランダムな文字列
  • データ2…16,384個の「A」

最終結果

参考

コメント

  • ツールキットのdmaget/putは非同期転送 排他的な転送はGETLLAR/PUTLCを用いる。(4.2.3 MFCアトミック更新 http://tinyurl.com/5l826l) - 松本 (2008年12月15日 19時59分56秒)
  • ↑のGETLLAR/PUTLCは128バイト固定長の転送なので要注意。ロック変数などを使ってうまくやるとよい。 - 松本 (2008年12月22日 07時21分09秒)
  • toolkit1.0でブロック並列化を既にやられてしまった。どうやってさらに早くするか…。 - 松本 (2009年01月06日 02時15分34秒)
  • DMA転送の削減効果が低いのは容量の都合な気がするけど,サイズの変更で時間が延びるのが怪しい.とメモっておく. - 大島 (2009年02月10日 03時40分14秒)
  • 研究室のCellReferenceSetに{ppu,spu}-gccが見当たらない。cc, gcc, makeすら見当たらない。 - 松本 (2009年02月12日 20時25分11秒)
  • vector UINT32 という記述は×.vector unsigned int - 松本 (2009年02月17日 16時20分19秒)
  • vector UINT32 という記述は×。 vector unsigned int と書かないとエラーになる。 - 松本 (2009年02月17日 16時21分16秒)
  • cell01のライブラリがv2。libspe2はv3からなのでコンパイルできない。 - 松本 (2009年03月06日 13時20分58秒)
  • 128文字単位で同じだったら計算を省略できないかと思ったけど,よく考えたらあんまりできない感じ. - 大島 (2009年03月09日 16時36分19秒)
お名前: コメント: