「マルチスレッド線型探索」の版間の差分

(3人の利用者による、間の4版が非表示)

1行目:

'''マルチスレッド線型探索'''~~とは、通常は1個ずつ候補を見ていく~~[[線型探索]]を、

'''マルチスレッド線型探索'''（読み：まるちすれっどせんけいたんさく）とは、通常は1個ずつ候補を見ていく[[線型探索]]を、一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。

~~一度に複数の候補を見ることで~~[[高速化]]することを狙ったテクニックである。

== 概要 ==

[[線形探索]]は単純に総当たりで[[データ]]を探す手法である。

単純であるが故に[[並列処理]]に都合がよく、処理終了通知などを除き基本的に[[スレッド]]間の[[同期]]の必要がなく、[[ロック]]が発生しないため、[[並列度]]を限りなく高めることができる。

このため[[マルチスレッド]]化や[[GPGPU]]化などにより比類なき高速化を望めるというものである。

なお、この[[アルゴリズム]]に限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コストやデータ転送コストなどの前準備の処理時間が、主目的の処理時間を上回ってしまう場合があるので注意する必要がある。

ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。

==使用例==

9行目:

16行目:

* [[マルチスレッド]]

* [[線型探索]]

* [[OpenMP]]

[[category: アルゴリズム]]

@@ 1行目: / 1行目: @@
-'''マルチスレッド線型探索'''とは、通常は1個ずつ候補を見ていく[[線型探索]]を、
+'''マルチスレッド線型探索'''（読み：まるちすれっどせんけいたんさく）とは、通常は1個ずつ候補を見ていく[[線型探索]]を、一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。
-一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。
+== 概要 ==
+[[線形探索]]は単純に総当たりで[[データ]]を探す手法である。
+単純であるが故に[[並列処理]]に都合がよく、処理終了通知などを除き基本的に[[スレッド]]間の[[同期]]の必要がなく、[[ロック]]が発生しないため、[[並列度]]を限りなく高めることができる。
+このため[[マルチスレッド]]化や[[GPGPU]]化などにより比類なき高速化を望めるというものである。
+なお、この[[アルゴリズム]]に限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コストやデータ転送コストなどの前準備の処理時間が、主目的の処理時間を上回ってしまう場合があるので注意する必要がある。
+ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。
 ==使用例==
@@ 9行目: / 16行目: @@
 * [[マルチスレッド]]
 * [[線型探索]]
+* [[OpenMP]]
+[[category: アルゴリズム]]