0
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 <!DOCTYPE html>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 <!--
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 Google HTML5 slide template
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 Authors: Luke Mahé (code)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 Marcin Wichary (code and design)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 Dominic Mazzoni (browser compatibility)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 Charles Chen (ChromeVox support)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 URL: http://code.google.com/p/html5slides/
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 -->
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 <html>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 <head>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 <title>2013-05-21</title>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 <meta charset='utf-8'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 <script
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 src='http://html5slides.googlecode.com/svn/trunk/slides.js'></script>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 </head>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 <style>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 /* Your individual styles here, or just use inline styles if that’s
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 what you want. */
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 .slides article { background-image: none !important; background-color: white; }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 </style>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 <body style='display: none'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 <section class='slides layout-regular template-default'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 <!-- Your slides (<article>s) go here. Delete or comment out the
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 slides below.-->
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 <article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 <h1>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 Ceriumによる
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 <br>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 正規表現マッチャの実装
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 </h1>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 Masataka Kohagura
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 <br>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 14th May , 2013
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 <article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 研究目的
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 本研究室では、Cell用に作られたCeriumにて並列プログラミングを行なっている。様々な例題を実装することにより、どのような問題でも並列処理ができることを証明する。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 現在は文字列サーチを実装している段階で、ボイヤームーア法を実装している。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 セミグループという、分割したファイルに対して並列処理をさせるような手法によって、既存の文字列サーチと処理速度を比較し、どれだけ速くなるのかを測定する。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 <article class='smaller'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 ボイヤームーア法とは(1)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 <div align="center">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 <IMG SRC="BM1.jpg" ALT="BM1">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 </div>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 検索したい文字列(pattern data)の長さをmとする。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 pattarn dataとtext dataを、pattern dataの末尾から比較を行なっていく。<br>比較したtext dataの文字列がpattern dataの要素に含まれていない場合は、pattern dataをm個ずらし、再比較を行う。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 <article class='smaller'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 ボイヤームーア法とは(2)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 <div align="center">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 <IMG SRC="BM2.jpg" ALT="BM1">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 </div>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 比較したtext dataの文字がpattern dataの要素に含まれている場合は、pattern dataの末尾からその要素がどれだけ離れているかで決定される。この図であれば、末尾から2個離れているので、pattern dataを2個ずらし、最比較。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 <article class='smaller'>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 BM法をCで実装
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 <section>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 <pre>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103 int BM_method(char *text,char *pattern,unsigned long long *match_string){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 int skip[256];
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 int i,j,text_len,pattern_len;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 int k = 0;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 text_len = strlen(text);
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 pattern_len = strlen(pattern);
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 for (i = 0; i < 256; ++i){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 skip[i] = pattern_len;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 for (i = 0; i < pattern_len-1 ; ++i){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 skip[(int)pattern[i]] = pattern_len - i - 1;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 i = pattern_len - 1;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 while ( i < text_len){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 j = pattern_len - 1;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 while (text[i] == pattern[j]){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 if (j == 0){
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 match_string[k] = text[i];
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 k++;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125 --i,--j;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 i = i + max((int)skip[(int)text[i]],pattern_len - j);
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 return -1;
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 }
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 </pre>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 <article class>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 分割時の処理について
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138 <p>現在実装している処理</p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139 <div align="center">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 <IMG SRC="search_idata.jpg" ALT="sid">
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141 </div>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143 i_dataを1文字だけ多く取ってきて、abが分割されたときでも結果が返ってきてくれるように設定している。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 <article class>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 <h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 現在の問題点
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 </h3>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 分割回りで結果が返ってこない。(上手く処理されていない)
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 <p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 taskが2個以上になるとき、cpuの個数を2個以上に設定しないと結果が返ってこない。
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 </p>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 </article>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 </body>
|
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 </html>
|