Mercurial > hg > Members > masakoha > masa
annotate Dec-2013/17th.html @ 8:0ce451f35622
add 27th slide
| author | Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 27 Dec 2013 19:04:32 +0900 |
| parents | dafc2806d661 |
| children |
| rev | line source |
|---|---|
| 0 | 1 <!DOCTYPE html> |
| 2 | |
| 3 <!-- | |
| 4 Google HTML5 slide template | |
| 5 | |
| 6 Authors: Luke Mahé (code) | |
| 7 Marcin Wichary (code and design) | |
| 8 | |
| 9 Dominic Mazzoni (browser compatibility) | |
| 10 Charles Chen (ChromeVox support) | |
| 11 | |
| 12 URL: http://code.google.com/p/html5slides/ | |
| 13 --> | |
| 14 | |
| 15 <html> | |
| 16 <head> | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
17 <title>slide</title> |
| 0 | 18 |
| 19 <meta charset='utf-8'> | |
| 20 <script | |
| 21 src='http://html5slides.googlecode.com/svn/trunk/slides.js'></script> | |
| 22 </head> | |
| 23 | |
| 24 <style> | |
| 25 /* Your individual styles here, or just use inline styles if that’s | |
| 26 what you want. */ | |
| 27 .slides article { background-image: none !important; background-color: white; } | |
| 28 | |
| 29 </style> | |
| 30 | |
| 31 <body style='display: none'> | |
| 32 | |
| 33 <section class='slides layout-regular template-default'> | |
| 34 | |
| 35 <!-- Your slides (<article>s) go here. Delete or comment out the | |
| 36 slides below.--> | |
| 37 | |
| 38 <article> | |
| 39 <h1> | |
| 40 Cerium Task Manager | |
| 41 <br> | |
| 42 による正規表現の実装 | |
| 43 </h1> | |
| 44 <p> | |
| 45 Masataka Kohagura | |
| 46 <br> | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
47 10th December , 2013 |
| 0 | 48 </p> |
| 49 </article> | |
| 50 | |
| 51 <article> | |
| 52 <h3> | |
| 53 研究目的 | |
| 54 </h3> | |
| 55 <p> | |
| 7 | 56 当研究室では、CellやマルチコアCPUで並列プログラミングを可能にするCerium Task Managerを開発している。 |
| 57 </p> | |
| 58 <p> | |
| 59 マルチコア CPU を最大限に活かすためには、プログラムの並列度を向上させなければならないが、実装が難しい。 | |
| 60 当研究室では Cerium Libraryを提供することによって並列プログラミングを容易にしているが、ファイル読み込み等のI/O部分に関してはまだAPIが実装されていない。 | |
| 0 | 61 </p> |
| 62 <p> | |
| 6 | 63 本研究ではその例題として正規表現を実装し、I/Oの順次読み込みとTaskの並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げる。 |
| 0 | 64 </p> |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
65 |
| 0 | 66 </article> |
| 67 | |
| 68 <article> | |
| 69 <h3> | |
| 70 今週のしたこと | |
| 71 </h3> | |
| 5 | 72 <ul> |
| 73 | |
| 74 <li> | |
| 75 read関数によるfileの順次読み込み<br> | |
| 76 (読み込み部分をread()からpread()へ変更) | |
| 77 </li> | |
| 78 | |
| 79 <li> | |
| 6 | 80 Read Taskのブロック化<br> |
| 5 | 81 (1つずつ起動していたものを、ブロック単位で起動するようにした) |
| 82 </li> | |
| 83 | |
| 84 <li> | |
| 85 MapReduce関数の整理 | |
| 86 </li> | |
| 87 | |
| 88 <ul> | |
| 0 | 89 </article> |
| 90 | |
| 91 <!-- | |
| 92 <article class='smaller'> | |
| 93 <h3>I/O並列化のシーケンス図(mmap)</h3> | |
| 94 <div align="center"> | |
| 95 <IMG SRC="mmap.png"> | |
| 96 </div> | |
| 97 <li> | |
| 98 codeがシンプル(readを書いて読み込まなくていいため) | |
| 99 </li> | |
| 100 <li> | |
| 101 memoryより大きなファイルは開けない | |
| 102 </li> | |
| 103 <li> | |
| 104 readの先読みがOS依存 | |
| 105 </li> | |
| 106 | |
| 107 </article> | |
| 108 --> | |
| 109 | |
| 110 | |
| 111 <article> | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
112 |
| 5 | 113 <h3> readからpreadへ</h3> |
| 114 <p>変更前</p> | |
| 0 | 115 <section><pre> |
| 5 | 116 int *fd = (int *)s->get_input(rbuf,0); ///ファイルディスクリプタの受取 |
| 117 long readsize = (long)s->get_param(0); | |
| 118 long task_number = (long)s->get_param(1); | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
119 |
| 5 | 120 char text[(long)readsize]; |
| 121 | |
| 122 <font color="red">read(*fd,text,(long)readsize);</font> | |
| 123 | |
| 124 s->printf("[start task No. %d]\n",task_number); | |
| 125 s->printf("%s\n",text); | |
| 0 | 126 </pre></section> |
| 127 | |
| 5 | 128 <p>変更後</p> |
| 0 | 129 <section><pre> |
| 5 | 130 <font color="red">pread(*fd, text, (long)read_size , division_size*task_number);</font> |
| 0 | 131 </pre></section> |
| 132 | |
| 133 </article> | |
| 134 | |
| 5 | 135 <article class='smaller'> |
| 0 | 136 <h3> |
| 5 | 137 pread |
| 0 | 138 </h3> |
| 5 | 139 |
| 0 | 140 <section><pre> |
| 5 | 141 read(int fd, void *buf, size_t count); |
| 142 </pre></section> | |
| 143 | |
| 144 <section><pre> | |
| 145 pread(int fd, void *buf, size_t count, <font color="red">off_t offset</font>); | |
| 0 | 146 </pre></section> |
| 147 | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
148 <ul> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 <li> |
| 5 | 150 fd:ファイルディスクリプタ |
| 151 </li> | |
| 152 <li> | |
| 153 buf:readするDataの格納領域 | |
| 154 </li> | |
| 155 <li> | |
| 156 count:どれだけの量(byte)を読み込むか | |
| 157 </li> | |
| 158 <li> | |
| 159 offset:ファイルの先頭からどれだけの量(byte)を飛ばして読み込むのか | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 </li> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
161 </ul> |
| 5 | 162 |
| 163 <p> | |
| 164 read関数だと、Taskの起動する順番やタイミングによって同じ場所を読み込んだりしてしまう。read関数は読み込んだ後にファイルディスクリプタをずらしてしまうので、そのような現象が起こると考えられる。 | |
| 165 </p> | |
| 166 <p> | |
| 167 pread関数だと、ファイルディスクリプタを動かさずにoffsetを取ることで読み込む場所が替えることができる。これだと、上記の現象が起こらずにすむ。 | |
| 168 </p> | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 </article> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
170 |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
171 |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
172 <article> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
173 <h3> |
| 5 | 174 readでの読み込みの失敗例 |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
175 </h3> |
| 0 | 176 <section><pre> |
| 5 | 177 % ./fileread -file d.txt |
| 178 filesize : 16398 | |
| 179 one_task_size: 16384 | |
| 180 task_num : 2 | |
| 181 [start task No. 0] | |
| 182 firstaaaaaaaaaaaaaaaaaaaaaa...16380 | |
| 183 doin | |
| 184 [start task No. 1] | |
| 185 firstaaaaaaaaa | |
| 186 </pre></section> | |
| 187 | |
| 188 <section><pre> | |
| 189 [start task No. 0] | |
| 190 gxbaaabaaabab | |
| 191 [start task No. 1] | |
| 192 gxbaaabaaabab | |
| 193 </pre></section> | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
194 </article> |
| 0 | 195 |
| 5 | 196 <article class='smaller'> |
| 197 <h3>Read Taskのblock化</h3> | |
| 198 <p>変更前</p> | |
| 199 <section><pre> | |
| 200 run_start(TaskManager *manager,char *filename) | |
| 201 { | |
| 202 HTask *read; | |
| 203 int *fd = (int*)manager->allocate(sizeof(int)); | |
| 204 | |
| 205 if ((*fd=open(filename,O_RDONLY,0666))==0) { | |
| 206 fprintf(stderr,"can't open %s\n",filename); | |
| 207 } | |
| 208 ... | |
| 209 | |
| 210 for(int task_number = 0; task_number < task_num; task_number++){ | |
| 211 read = manager->create_task(READ_TASK); | |
| 212 read->set_cpu(spe_cpu); | |
| 213 | |
| 214 [task settings(省略)] | |
| 215 | |
| 216 } | |
| 217 } | |
| 218 </pre></section> | |
| 219 </article> | |
| 220 | |
| 221 <article class='smaller'> | |
| 222 <p>変更後</p> | |
| 223 <section><pre> | |
| 224 run_start(TaskManager *manager,char *filename) | |
| 225 { | |
| 226 int *fd = (int*)manager->allocate(sizeof(int)); | |
| 227 | |
| 228 if ((*fd=open(filename,O_RDONLY,0666))==0) { | |
| 229 fprintf(stderr,"can't open %s\n",filename); | |
| 230 } | |
| 231 | |
| 232 if (fstat(*fd,sb)) { | |
| 233 fprintf(stderr,"can't fstat %s\n",filename); | |
| 234 } | |
| 235 ... | |
| 236 | |
| 237 FilereadPtr fr = (FilereadPtr)manager->allocate(sizeof(Fileread)); | |
| 238 | |
| 239 HTaskPtr run = manager->create_task(RUN_BLOCKS, (memaddr)&fr->self, sizeof(memaddr),0,0); | |
| 240 run->spawn(); | |
| 241 } | |
| 242 </pre></section> | |
| 243 </article> | |
| 244 | |
| 245 <article class='smaller'> | |
| 246 <p>RUN_BLOCKS</p> | |
| 247 <section><pre> | |
| 248 SchedDefineTask1(RUN_BLOCKS,run16); | |
| 249 | |
| 250 run16(SchedTask *manager, void *in, void *out) { | |
| 251 | |
| 252 FilereadPtr fr = (FilereadPtr)in; | |
| 253 HTaskPtr wait; | |
| 254 | |
| 255 for (int i = 0; (fr->left_size > 0) && (i < fr->task_blocks); i++) { | |
| 256 HTaskPtr read = manager->create_task(Read_task); | |
| 257 read->set_cpu(fr->cpu); | |
| 258 | |
| 259 if (i == fr->task_blocks / 2) wait = read; | |
| 260 | |
| 261 [task settings(省略)] | |
| 262 | |
| 263 } | |
| 264 return 0; | |
| 265 } | |
| 266 </pre></section> | |
| 267 | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
268 <ul> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
269 <li> |
| 5 | 270 Taskを1個1個起動ではなくブロック単位で起動している理由は、メモリの再利用のためである。 |
| 271 1個1個起動すると、その分のメモリが必要となり、Task数が多くなると肥大化する。 | |
| 272 ブロック単位で起動することでメモリを節約するとともに、メモリの書き換えが少なくて済むので高速化につながる。 | |
| 273 </li> | |
| 274 </ul> | |
| 275 </article> | |
| 276 | |
| 277 | |
| 278 <article class='smaller'> | |
| 279 <h3>Taskのブロック化の図(1)</h3> | |
| 280 <p>word countでの実装</p> | |
| 281 <p> | |
| 282 <div align="center"> | |
| 283 <img src="images/old_run_task_blocks.jpg" width="40%" height="40%"> | |
| 284 </div> | |
| 285 </p> | |
| 286 <ul> | |
| 287 <li> | |
| 288 run16がブロック単位でTaskを起動する。word countでは48 Task/1block。 | |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
289 </li> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
290 <li> |
| 5 | 291 ブロック内の処理が全て終わらないと、新しいブロックを生成することができない。<br> |
| 292 すべてのTaskが終わるまで待つので、オーバヘッドが起こる。 | |
| 293 </li> | |
| 294 </ul> | |
| 295 </article> | |
| 296 | |
| 297 <article class='smaller'> | |
| 298 <h3>Taskのブロック化の図(2)</h3> | |
| 299 <p>filereadでの実装</p> | |
| 300 <div align="center"> | |
| 301 <img src="images/new_run_task_blocks.jpg" width="40%" height="40%"> | |
| 302 </div> | |
| 303 <ul> | |
| 304 <li> | |
| 6 | 305 run16でブロック単位を起動することは変わりはないが、1ブロックのTask数の半分がspawnすると新しいブロックを起動するようになっている。 |
|
2
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
306 </li> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
307 </ul> |
|
6f538bc4614b
add 10th December slide
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
308 </article> |
| 0 | 309 |
| 6 | 310 <article class='smaller'> |
| 311 <h3>Map Reduce</h3> | |
| 312 <p> | |
| 313 <div align="center"> | |
| 314 <img src="images/mapreduce.jpg" width="100%" height="100%"> | |
| 315 </div> | |
| 316 </p> | |
| 317 <ul> | |
| 318 <li> | |
| 319 スライド作成間に合わない・・・ | |
| 320 </li> | |
| 321 </ul> | |
| 322 </article> | |
| 0 | 323 </body> |
| 324 </html> |