C
アルゴリズム
数学
論理演算
論理回路

クワイン・マクラスキー法とペトリック法による論理圧縮アルゴリズムをCで実装


初版ソースコード

https://github.com/jun6231jp/logic_comp/blob/master/logic_comp.c


ビルド

gcc logic_comp.c -o logic_comp.out -lm -std=c99 -O3



事前準備


ディレクトリ作成

実行ディレクトリ内に次のディレクトリを作成する。

・table

・table_lack

※改善版ソースでは不要


真理値表の作成

テキストファイルに次のように記述する。(パターン+半角スペース+真理値)

例は10bit入力の真理値表。ここではファイル名をtable_10Dとする(なんでも良い)。

表に無いパターン(下記例では0000000000など)はドントケアとして扱われる。


真理値表例

0000001100  1

1000011100 1
0100011100 1
1100111100 0
0010111100 0
1010111100 0
0110111100 0
1110111100 1
0101111100 1
1101111100 1
0100000001 1
0000000011 1
1100000011 1
1101101010 1
0011101010 0
1011101010 0
0111101010 0


初版ソースコード実行


実行結果


結果例

# ./logic_comp.out table_10D

10:3:8
logic comp 2 ... end 87 lines
logic comp 4 ... end 366 lines
..resized table_2 : 0 lines
logic comp 8 ... end 883 lines
..resized table_4 : 0 lines
logic comp 16 ... end 1345 lines
..resized table_8 : 0 lines
logic comp 32 ... end 1331 lines
..resized table_16 : 0 lines
logic comp 64 ... end 835 lines
..resized table_32 : 0 lines
logic comp 128 ... end 302 lines
..resized table_64 : 0 lines
logic comp 256 ... end 52 lines
..resized table_128 : 5 lines
..making table_128 compact ...end
logic comp 512 ... end 3 lines
..resized table_256 : 15 lines
..making table_256 compact ...end
[`4] + [`6] + [9]
[`0][`2] + [`1][`2] + [`3][8] + [`5][7] + [`7][`8] + [`2][3] + [3][5]
[0][1][`5] + [0][1][`7] + [0][1][8] + [0][1][3] + [0][1][2]
10:4:4
exec time 54670 [ms]


結果の見方

 ['A]=NOT(A)

 [A][B]=AND(A,B)
 [A]+[B]=OR(A,B)
 [A](改行)[B]=OR(A,B)


注意点

同じ実行ディレクトリ内で複数実行すると、中間ファイルの競合が発生する。

また、12281文字の配列を用意しているが、これは入力bit幅最大16bitに対応させている。mallocで動的メモリ割り当てを行うことで(メモリ容量範囲内では)無制限に入力bit幅を拡張することができるようになる。

今後改善予定。


実行時間オーダ

runtime.png

図は入力bit幅(dimension)を横軸、実行時間(ms対数)を縦軸にプロットしたものである。

入力となる真理値表をランダムに作成して実行することで真理値表のパターンばらつきによる実行時間誤差の傾向も見ることができている(dimension=11,12は時間がかかるためプロット数を省略している)。入力bit幅が1bit増すごとに実行時間が約10倍となることが分かる。dimension=12で数時間の実行時間であることからdimension=13で数日かかることが予想される。実用面を考えると高速化が必要でありアルゴリズムを見直す必要がある。

(dimensionが小さい領域では特性がフラットになっているが、これは処理時間よりファイル入出力時間が支配的になるからだろう。)


真理値表最小化アルゴリズム

論理最小化および高速化のため、プログラムの入力である真理値表を最小化するアルゴリズムを追加する。

下記の真理値表のAと書かれた縦一列を削除することを考える。

このとき、2行目と5行目のように一致するパターンが存在するとする。

例ではそれらの真理値は2行目は0、5行は1となっており、異なった値である。

つまり、Aの列を削除すると論理に矛盾が生じる(同じ001100のパターンに対し、真理値が0,1の両方存在することになる)。よってA列を削除することはできない。

逆に、A列を削除しても一致するパターンが無い場合、もしくは一致するパターンがあるが真理値も同じである場合、A列は削除可能である。

実行時間オーダのグラフから、1列削除できれば実行時間はおよそ1/10倍に短縮できる。

このような判定をすべての列に対して実施し、真理値表のビット幅を低減させる。


真理値表1列削除の概念

A...     0

A001100 0
A... 0
A... 1
A001100 1
A... 1


改良版ソースコード

https://github.com/jun6231jp/logic_comp/blob/master/logic_comp_rev2.c


ビルド

gcc logic_comp_rev2.c -o logic_comp.out -std=c99 -O3



初版からの変更点

・真理値表最小化アルゴリズムを追加(下記ソースコード中のtable_remake関数)

・パターンマッチングの部分のアルゴリズムを改造

・クイックソート使用

・compact関数の重複パターンの削除漏れ修正。(名前もduplicate_detectに変更)

・resize関数修正

・sortuuniq関数修正

・完全オンメモリ動作化

中間ファイルを作成しないため、tableディレクトリ作成不要。

メモリリークも解消。


改良版ソースコード実行


実行結果


結果例

# ./logic_comp_rev2.out table_10D

#table_mask [1111000001]
logic comp 2 ... end 15 lines
logic comp 4 ... end 16 lines
Resize ..end table_2 : 0 lines
logic comp 8 ... end 7 lines
Resize ..end table_4 : 1 lines
logic comp 16 ... end 1 lines
Resize ..end table_8 : 3 lines
..making table_8 compact ...end
..making table_16 compact ...end
[9]
[`0][`2] + [`1][`2] + [`2][3]
[0][1][2]
exec time 0.005026 [s]

真理値表が簡易化可能な場合、実行結果も変化する。

余分なOR演算項が省かれ、必要十分な論理式となる。


実行時間比較

logic_comp.png

dimension=10で100倍ほど高速化。dimensionが大きくなるほど差が開いている。

改良版ソースコード実行時間はばらつきが大きいが、これは真理値表最小化アルゴリズムによる高速化幅が真理値表ごとに異なるからである。


OpenMPで並列処理

並列処理することで更に高速化させる。


section並列化

高速化のため、論理ペアのテーブルから上位論理ペア抽出処理と下位論理ペア重複削除処理をsection単位で並列化した。

https://github.com/jun6231jp/logic_comp/blob/master/logic_comp_openmp_section.c


ビルド

gcc -fopenmp logic_comp_openmp_section.c -o logic_comp_openmp_section.out -std=c99 -O3


CPU_openmp.png

2スレッド並列なので2コアの稼働率が100%になっている。


for並列化

上位論理ペア抽出処理と下位論理ペア重複削除処理それぞれのforループを並列化した。

https://github.com/jun6231jp/logic_comp/blob/master/logic_comp_openmp_for.c


ビルド

gcc -fopenmp logic_comp_openmp_for.c -o logic_comp_openmp_for.out -std=c99 -O3


core_openmp_for.png

全コアで並列処理を行っていることが分かる。


実行時間比較

bit幅6~15までのtableを作成し、実行時間を比較した。

bit幅
logic_comp_rev2実行時間(秒)
logic_comp_openmp_section実行時間(秒)
logic_comp_openmp_for実行時間(秒)

6
0.000234
0.000133
0.000109

7
0.000313
0.000214
0.000606

8
0.000334
0.000220
0.000626

9
0.000423
0.000423
0.000917

10
0.000625
0.000629
0.001228

11
0.00315
0.00310
0.00403

12
0.215
0.179
0.112

13
7.30
4.48
2.80

14
54.1
33.3
17.3

bit幅が11以下のように小さい場合はシングルスレッドの方が高速な場合が見られる。全体の処理時間が短い場合OpenMPがコアにジョブを割り当てる時間が無視できなくなるからであると考えられる。

bit幅が12以上になるとsection並列化はシングルスレッドに比べておよそ2倍の高速化になっている。2並列化の効果が得られていることが分かる。

for並列化はシングルスレッドに比べて3倍程度の高速化となっている。12コアでの並列ではあるが、シングルスレッドはforループ内でパターンマッチするとbreak処理をするため、forループを12並列処理しても12倍の高速化にはならない。


付録

入力のテーブルをカルノー図のようにマトリックスで表示する。

https://github.com/jun6231jp/logic_comp/blob/master/table_show.c


ビルド

gcc table_show.c -o table_show.out -lm -std=c99 -O3



実行例

./table_show.out table_4D_random

4,4
0 0 1 1
0 1 1 0

00 0 0 1 0
01 0 1 1 1
11 * 1 0 1
10 0 1 1 1

./table_show.out table_8D_random
16,16
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

0000 * 0 * 0 * * * * 1 * * * 0 * * 0
0001 * 1 0 0 1 * * 1 0 * * 1 1 * * *
0011 0 1 * 1 * * 0 * 0 0 0 * 0 * * 1
0010 1 0 1 * 0 1 * 1 1 1 * 0 0 * * 0
0110 1 * 1 0 * 1 1 1 0 * 1 0 0 * 1 1
0111 * * 0 * * 0 0 * * 0 0 * 0 0 0 1
0101 * 0 * * 0 1 * * 1 1 0 0 * * 0 0
0100 * 1 1 * 0 * * * * 0 0 * 0 * 0 *
1100 * * 1 * 0 0 0 0 * * 0 * * 0 * *
1101 0 * 1 * 0 1 0 * 0 * 0 0 1 * * *
1111 0 * 1 0 1 1 * 1 * * * 1 1 * 0 0
1110 * * 0 0 * 0 0 1 * 0 1 1 1 1 * *
1010 1 * * 1 * * 0 * 0 * * 1 * * * 1
1011 * 1 * * * * * 1 1 * 0 * 1 0 1 0
1001 0 1 0 0 1 1 1 1 * 0 * 0 1 * 1 *
1000 * 0 1 0 * * * * 1 1 1 1 0 * * 1