Mercurial > hg > Members > masakoha > masa
view 2013/Dec-2013/17th.html @ 9:e4748bca1eb3
mkdir 2013
| author | Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 14 Jan 2014 04:18:59 +0900 |
| parents | Dec-2013/17th.html@dafc2806d661 |
| children |
line wrap: on
line source
<!DOCTYPE html> <!-- Google HTML5 slide template Authors: Luke Mahé (code) Marcin Wichary (code and design) Dominic Mazzoni (browser compatibility) Charles Chen (ChromeVox support) URL: http://code.google.com/p/html5slides/ --> <html> <head> <title>slide</title> <meta charset='utf-8'> <script src='http://html5slides.googlecode.com/svn/trunk/slides.js'></script> </head> <style> /* Your individual styles here, or just use inline styles if that’s what you want. */ .slides article { background-image: none !important; background-color: white; } </style> <body style='display: none'> <section class='slides layout-regular template-default'> <!-- Your slides (<article>s) go here. Delete or comment out the slides below.--> <article> <h1> Cerium Task Manager <br> による正規表現の実装 </h1> <p> Masataka Kohagura <br> 10th December , 2013 </p> </article> <article> <h3> 研究目的 </h3> <p> 当研究室では、CellやマルチコアCPUで並列プログラミングを可能にするCerium Task Managerを開発している。 </p> <p> マルチコア CPU を最大限に活かすためには、プログラムの並列度を向上させなければならないが、実装が難しい。 当研究室では Cerium Libraryを提供することによって並列プログラミングを容易にしているが、ファイル読み込み等のI/O部分に関してはまだAPIが実装されていない。 </p> <p> 本研究ではその例題として正規表現を実装し、I/Oの順次読み込みとTaskの並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げる。 </p> </article> <article> <h3> 今週のしたこと </h3> <ul> <li> read関数によるfileの順次読み込み<br> (読み込み部分をread()からpread()へ変更) </li> <li> Read Taskのブロック化<br> (1つずつ起動していたものを、ブロック単位で起動するようにした) </li> <li> MapReduce関数の整理 </li> <ul> </article> <!-- <article class='smaller'> <h3>I/O並列化のシーケンス図(mmap)</h3> <div align="center"> <IMG SRC="mmap.png"> </div> <li> codeがシンプル(readを書いて読み込まなくていいため) </li> <li> memoryより大きなファイルは開けない </li> <li> readの先読みがOS依存 </li> </article> --> <article> <h3> readからpreadへ</h3> <p>変更前</p> <section><pre> int *fd = (int *)s->get_input(rbuf,0); ///ファイルディスクリプタの受取 long readsize = (long)s->get_param(0); long task_number = (long)s->get_param(1); char text[(long)readsize]; <font color="red">read(*fd,text,(long)readsize);</font> s->printf("[start task No. %d]\n",task_number); s->printf("%s\n",text); </pre></section> <p>変更後</p> <section><pre> <font color="red">pread(*fd, text, (long)read_size , division_size*task_number);</font> </pre></section> </article> <article class='smaller'> <h3> pread </h3> <section><pre> read(int fd, void *buf, size_t count); </pre></section> <section><pre> pread(int fd, void *buf, size_t count, <font color="red">off_t offset</font>); </pre></section> <ul> <li> fd:ファイルディスクリプタ </li> <li> buf:readするDataの格納領域 </li> <li> count:どれだけの量(byte)を読み込むか </li> <li> offset:ファイルの先頭からどれだけの量(byte)を飛ばして読み込むのか </li> </ul> <p> read関数だと、Taskの起動する順番やタイミングによって同じ場所を読み込んだりしてしまう。read関数は読み込んだ後にファイルディスクリプタをずらしてしまうので、そのような現象が起こると考えられる。 </p> <p> pread関数だと、ファイルディスクリプタを動かさずにoffsetを取ることで読み込む場所が替えることができる。これだと、上記の現象が起こらずにすむ。 </p> </article> <article> <h3> readでの読み込みの失敗例 </h3> <section><pre> % ./fileread -file d.txt filesize : 16398 one_task_size: 16384 task_num : 2 [start task No. 0] firstaaaaaaaaaaaaaaaaaaaaaa...16380 doin [start task No. 1] firstaaaaaaaaa </pre></section> <section><pre> [start task No. 0] gxbaaabaaabab [start task No. 1] gxbaaabaaabab </pre></section> </article> <article class='smaller'> <h3>Read Taskのblock化</h3> <p>変更前</p> <section><pre> run_start(TaskManager *manager,char *filename) { HTask *read; int *fd = (int*)manager->allocate(sizeof(int)); if ((*fd=open(filename,O_RDONLY,0666))==0) { fprintf(stderr,"can't open %s\n",filename); } ... for(int task_number = 0; task_number < task_num; task_number++){ read = manager->create_task(READ_TASK); read->set_cpu(spe_cpu); [task settings(省略)] } } </pre></section> </article> <article class='smaller'> <p>変更後</p> <section><pre> run_start(TaskManager *manager,char *filename) { int *fd = (int*)manager->allocate(sizeof(int)); if ((*fd=open(filename,O_RDONLY,0666))==0) { fprintf(stderr,"can't open %s\n",filename); } if (fstat(*fd,sb)) { fprintf(stderr,"can't fstat %s\n",filename); } ... FilereadPtr fr = (FilereadPtr)manager->allocate(sizeof(Fileread)); HTaskPtr run = manager->create_task(RUN_BLOCKS, (memaddr)&fr->self, sizeof(memaddr),0,0); run->spawn(); } </pre></section> </article> <article class='smaller'> <p>RUN_BLOCKS</p> <section><pre> SchedDefineTask1(RUN_BLOCKS,run16); run16(SchedTask *manager, void *in, void *out) { FilereadPtr fr = (FilereadPtr)in; HTaskPtr wait; for (int i = 0; (fr->left_size > 0) && (i < fr->task_blocks); i++) { HTaskPtr read = manager->create_task(Read_task); read->set_cpu(fr->cpu); if (i == fr->task_blocks / 2) wait = read; [task settings(省略)] } return 0; } </pre></section> <ul> <li> Taskを1個1個起動ではなくブロック単位で起動している理由は、メモリの再利用のためである。 1個1個起動すると、その分のメモリが必要となり、Task数が多くなると肥大化する。 ブロック単位で起動することでメモリを節約するとともに、メモリの書き換えが少なくて済むので高速化につながる。 </li> </ul> </article> <article class='smaller'> <h3>Taskのブロック化の図(1)</h3> <p>word countでの実装</p> <p> <div align="center"> <img src="images/old_run_task_blocks.jpg" width="40%" height="40%"> </div> </p> <ul> <li> run16がブロック単位でTaskを起動する。word countでは48 Task/1block。 </li> <li> ブロック内の処理が全て終わらないと、新しいブロックを生成することができない。<br> すべてのTaskが終わるまで待つので、オーバヘッドが起こる。 </li> </ul> </article> <article class='smaller'> <h3>Taskのブロック化の図(2)</h3> <p>filereadでの実装</p> <div align="center"> <img src="images/new_run_task_blocks.jpg" width="40%" height="40%"> </div> <ul> <li> run16でブロック単位を起動することは変わりはないが、1ブロックのTask数の半分がspawnすると新しいブロックを起動するようになっている。 </li> </ul> </article> <article class='smaller'> <h3>Map Reduce</h3> <p> <div align="center"> <img src="images/mapreduce.jpg" width="100%" height="100%"> </div> </p> <ul> <li> スライド作成間に合わない・・・ </li> </ul> </article> </body> </html>