本程序代码是基于 [1] 中理论实现的一个样例.
(一) 程序的使用
如果直接编译程序,运行的时候请确保目录结构为:
./ # 工作目录
|-- CA-w-h.exe # 主程序
|-- mvsis50720.exe # 主程序会调用它,程序名是 hard code
|-- master.mvsisrc # mvsis 程序会读取 其实是空文件
| # 没有的话会多输出一行字影响主程序读取
|-- pla/ # 存放结果的目录 目录名是 hard code
| |-- case-00/ # 分别存放不同 case 的结果 数字范围是 00 到 99
| |-- case-01/ # vector.txt中有多少个case就建多少个文件夹
| `-- ...... # 可以使用脚本批量生成
`-- vector.txt # 程序的输入 文件名是 hard code
vector.txt 格式
第 1 行: 原始多项式中变量个数 k, 需要的精度 m. 两个整数, 使用空格隔开 第 2 行: 每个变量分别的最高次 d_1, ..., d_k. k 个整数, 用空格隔开 第 3 行: 第一个 case 的 problem vector, d_1 个整数, 用空格隔开 ......
从第三行开始就是每个 case 的 problem vector.
运行程序结束后会在每个 case 的目录下生成结果, 命名为 solution-xxx.pla. 请使用 ABC 进行下一步处理.
(二) ABC 处理
ABC 是 Linux 下面的程序, 请在 http://people.eecs.berkeley.edu/~alanmi/abc/ 下载
将 abc.rc, mcnc.genlib, 以及要处理的结果 solution-xxx.pla 和 ABC 程序放在同一个目录下, 运行 ABC 程序. 在 ABC 里输入以下命令
read_genlib mcnc.genlib read solution-xxx.pla clp; sop; fx; st; dch; b; map write_eqn solution-xxx.eqn
这样就会在目录里生成 solution-xxx.eqn 的结果. 是个文本文档, 记录了得到的逻辑电路.
(三) 如何得到 problem vector
两种方法:
第一种方法
使用 MATLAB 程序(见目录 Univariate-Bernstein-Approximation)直接转化为 Bernstein polynomial, 然后对系数进行近似来得到 problem vector.
例: tanh(x)
假设在 MATLAB 程序里选择需要的多项式最高次是 4 (k = 1, d_1 = 4), 运行得到的 Bernstein 系数为
0.0008, 0.2483, 0.5031, 0.6550, 0.7619
于是对应的 Bernstein polynomial 为:
tanh(x) ~= 0.0008choose(4,0)x^4 + 0.2483choose(4,1)x^3(1-x) + 0.5031choose(4,2)x^2(1-x)^2 + 0.6550choose(4,3)x(1-x)^3 + 0.7619choose(4,4)*(1-x)^4
假设需要的精度系数 m = 8, 于是有
0.0008choose(4,0) ~= 0/256 0.2483choose(4,1) ~= 254/256 0.5031choose(4,2) ~= 773/256 0.6550choose(4,3) ~= 671/256 0.7619*choose(4,4) ~= 195/256
最终得到的 problem vector 就是 V = [0 254 773 671 195]. 如果只有这一个 case, vector.txt 可以写成
1 8 4 0 254 773 671 195
第二种方法
先将函数用其他多项式逼近, 然后再转换为 Bernstein polynomial (其实是转化为一般的 binary combination polynomial, 但 Bernstein polynomial 是等价的, 可以直接使用 [2] 中的公式)
例: tanh(x)
使用麦克劳林展开式 tanh(x) ~= x - x^3/3 + 2x^5/15 - 17x^7/315 + 62*x^9/2835
这里使用一点小变换, 令 t = x^2, f(t) = 1 - t/3 + 2t^2/15 - 17t^3/315 + 62*t^4/2835. 那么
tanh(x) = x * f(t)
只需得到 f(t) 的电路, 其输入为 t 的地方与 x 的 squaring unit 相连, 输出用 multiplier 乘以 x.
对于 f(t), 使用 [2] 中的公式可以得到
b[0] = 1 b[1] = 11/12 b[2] = 77/90 b[3] = 253/315 b[4] = 311/405
那么 f(t) 的 Bernstein polynomial 为
f(t) = b[0]*choose(4,0)*t^4 + b[1]*choose(4,1)t^3(1-t) + b[2]*choose(4,2)t^2(1-t)^2 + b[3]*choose(4,3)t(1-t)^3 + b[4]choose(4,4)(1-t)^4
假设 m = 8
b[0]*choose(4,0) ~= 256/256 b[1]*choose(4,1) ~= 939/256 b[2]*choose(4,2) ~= 1314/256 b[3]*choose(4,3) ~= 822/256 b[4]*choose(4,4) ~= 197/256
所以 problem vector 是 V = [256 939 1314 822 197], vector.txt 可以写成
1 8 4 256 939 1314 822 197
Reference
[1] Peng, X., & Qian, W. (2018). Stochastic Circuit Synthesis by Cube Assignment. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(12), 3109-3122.
[2] Qian, W., & Riedel, M. D. (2008, June). The synthesis of robust polynomial arithmetic with stochastic logic. In Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE (pp. 648-653). IEEE.