半導体不良ビット高速グループ化
１．概要
◆２次元平面上の２点ｐ，ｑの距離Ｄがｄ未満である点を１つのグループにまとめる。
※半導体の不良ビットを距離の閾値によってグループ化するときなどに応用可能。
◆距離によるビットのグループ化は、素朴な方法ではビット数Ｎ個に対して
Ｎ×（Ｎ−１)／２ 回
の距離の計算が必要となる。
◆本プログラムでは、ほぼビット数Ｎに比例した時間でグループ化出来る。
２点の座標をそれぞれ(x1,y1),(x2,y2)としたときの距離ｄは
dx ＝ |x1−x2|
dy ＝ |y1−y2|
距離ｄ ＝ ｍａｘ｛dx，dy｝
距離ｄと閾値Ｄが、ｄ ＜ Ｄ のときに２つの点は同じグループに入れる。
※半導体の不良ビットを距離の閾値によってグループ化するときなどに応用可能。
◆距離によるビットのグループ化は、素朴な方法ではビット数Ｎ個に対して
Ｎ×（Ｎ−１)／２ 回
の距離の計算が必要となる。
◆本プログラムでは、ほぼビット数Ｎに比例した時間でグループ化出来る。
２点の座標をそれぞれ(x1,y1),(x2,y2)としたときの距離ｄは
dx ＝ |x1−x2|
dy ＝ |y1−y2|
距離ｄ ＝ ｍａｘ｛dx，dy｝
距離ｄと閾値Ｄが、ｄ ＜ Ｄ のときに２つの点は同じグループに入れる。
２．近隣点のグルーピングのアルゴリズムの概要
辺の長さがｄの正方形のメッシュをつくり、メッシュと点の関係を作る。
・メッシュ内の点同士は距離がｄ未満なので同じグループに属する。
・８方向の隣接メッシュ内の点について距離を調べる。
隣接しないメッシュ間ではどのペアも距離がｄ以上となるので調べる必要はない。
グループを統合するアルゴリズム
・２つの集合の統合にははユニオンファインド木を用いる。
・マージの手間は点の数にほぼ無関係で定数時間である。
詳細はソースファイルgrouping_memo.hを参照してください
・メッシュ内の点同士は距離がｄ未満なので同じグループに属する。
・８方向の隣接メッシュ内の点について距離を調べる。
隣接しないメッシュ間ではどのペアも距離がｄ以上となるので調べる必要はない。
グループを統合するアルゴリズム
・２つの集合の統合にははユニオンファインド木を用いる。
・マージの手間は点の数にほぼ無関係で定数時間である。
詳細はソースファイルgrouping_memo.hを参照してください
３．使用方法
◆ダウンロード（ダウンロードのページからもダウンロードできます）
sample02.zip 920 KB (942,948 バイト) ソース付き
３．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。
sample02フォルダの内容
(a)使用許諾契約書.txt
(b)仕様書.xls
(c)group_bit.exe
(d)group_bit_dll.dll
(e)idata.txt
３．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
３．３ 使用方法
(1)ＤＯＳプロンプト画面を表示します。
(2)インストールディレクトリ/sample02に移動します。
(3)入力データファイルを準備します。
(a)idata.txt
(4)プログラム実行。
groupBit.exe
(5)出力データファイルを確認します。
(a)odata.txt
(b)error.log
sample02.zip 920 KB (942,948 バイト) ソース付き
３．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。
sample02フォルダの内容
(a)使用許諾契約書.txt
(b)仕様書.xls
(c)group_bit.exe
(d)group_bit_dll.dll
(e)idata.txt
３．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
３．３ 使用方法
(1)ＤＯＳプロンプト画面を表示します。
(2)インストールディレクトリ/sample02に移動します。
(3)入力データファイルを準備します。
(a)idata.txt
(4)プログラム実行。
groupBit.exe
(5)出力データファイルを確認します。
(a)odata.txt
(b)error.log
４．性能
◆テスト結果(処理回数＝ビット数分の処理を繰り返した回数)
※テストデータでは、閾値20で全てのビットが1つにグループ化する。
◆検証
(1)ほぼビット数に比例した処理時間となる。（ビット数Ｎの２乗ではない）
(2)閾値が大きくなるとさらに高速になる。
◆テスト環境
ＯＳ：Microsoft Windows XP Proffesional
ＣＰＵ：Pentium４ ３ＧＨｚ（ＨＴ）
メモリ：２ＧＢ
| Xサイズ | Yサイズ | 閾値 | ビット数 | 処理回数 | 合計時間 | 時間/回 | グループ数 |
| 4096 | 4096 | 2 | 10000 | 100 | 1.8 | 0.018 | 4588 |
| 4096 | 4096 | 2 | 100000 | 10 | 1.9 | 0.19 | 44341 |
| 4096 | 4096 | 2 | 1000000 | 1 | 0.9 | 0.9 | 441159 |
| 4096 | 4096 | 5 | 10000 | 100 | 1 | 0.01 | 42 |
| 4096 | 4096 | 5 | 100000 | 10 | 0.6 | 0.06 | 142 |
| 4096 | 4096 | 5 | 1000000 | 1 | 0.8 | 0.8 | 142 |
| 4096 | 4096 | 20 | 10000 | 100 | 0.2 | 0.002 | 1 |
| 4096 | 4096 | 20 | 100000 | 10 | 0.2 | 0.02 | 1 |
| 4096 | 4096 | 20 | 1000000 | 1 | 0.2 | 0.2 | 1 |
◆検証
(1)ほぼビット数に比例した処理時間となる。（ビット数Ｎの２乗ではない）
(2)閾値が大きくなるとさらに高速になる。
◆テスト環境
ＯＳ：Microsoft Windows XP Proffesional
ＣＰＵ：Pentium４ ３ＧＨｚ（ＨＴ）
メモリ：２ＧＢ
５．開発環境
Visual Studio 2005 C++