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