「マルチスレッド線型探索」を編集中
ナビゲーションに移動
検索に移動
この編集を取り消せます。 下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
| 最新版 | 編集中の文章 | ||
| 1行目: | 1行目: | ||
| − | '''マルチスレッド線型探索''' | + | '''マルチスレッド線型探索'''とは、通常は1個ずつ候補を見ていく[[線型探索]]を、一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。 |
== 概要 == | == 概要 == | ||
| − | + | 線形探索は単純に総当たりで[[データ]]を探す手法である。線形探索は単純であるが故に[[並列処理]]に都合がよく、処理終了通知などを除き基本的に[[スレッド]]間の[[同期]]の必要がなく、[[ロック]]が発生しないため、[[並列度]]を限りなく高めることができる。 | |
| − | + | このため[[マルチスレッド]]化や[[GPGPU]]化などにより高速化を望めるというものである。 | |
| − | このため[[マルチスレッド]]化や[[GPGPU]] | ||
| − | + | なお、このアルゴリズムに限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コスト（スレッド生成に要する時間）やデータ転送コストが主目的の処理時間を上回ってしまう場合があるので注意する必要がある。 | |
ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。 | ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。 | ||
