Skip to content

laigroup/EDA_Sampling

Repository files navigation

EDA_Sampling

时间安排:

11月24日:技术报告提交,截止时间17:00 11月25日-11月28日:初赛评审 11月29日:作品上传服务器,关闭参赛队服务器访问通道,截止时间17:00 11月30日-12月7日:复赛技术评审 12月8日-12月10日:技术验收成绩公示 12月中下旬:竞赛决赛(待通知)

一、赛题要求

1、运算操作完成情况

单目运算符:

LOG NEG (!×) //逻辑非

BIT NEG (~x) //按位非

MINUS (-) //负号

双目运算符:

ADD (a + b)

SUB (a - b)

MUL (a * b)

DIV (a / b)

LOG_AND (a && b) //逻辑与

LOG_OR (a || b)//逻辑或

EQ (a == b)

NEQ (a != b)

LT (a < b)

LTE (a <= b)

GT (a > b)

GTE (a >= b)

BIT_AND (a & b) //按位与

BIT_OR (a | b)//按位或

BIT_XOR (a^b)//按位异或

RSHIFT (a >> b)

LSHIFT (a << b)

IMPLY (a -> b) // 等同于: (!a) || b

注: 除乘法和除法操作外,其他操作基本已经实现。

2、常量以及位宽

变量和常量位宽限制在64位以下,且都为 unsigned

由于同一个约束表达式内可能有不同位宽的变量和常量,所以表达式需要做隐式类型转换,具体规则可参照IEEE Std 1800™-2017, IEEE Standard for SystemVerilog— Unified Hardware Design, Specification, and Verification Language, 11.6 Expression bit lengths.

3、随机采样

每个测试题要求生成1000组随机解,这些解需要满足均匀概率分布。随机解按照json格式输出到文件。

思路: 假设经过统计有n条可满足路径经过BDD结点u,其中走u左分支的路径数为x,则走u右分支的路径数为n-x。 故在采样时,在u处走左分支的概率为x/n,走右分支的概率为(n-x)/n。

4、 可执行文件要求

提交的执行脚本或文件需要支持参数 -seed ,比如 -seed 123456

不加-seed直接执行时,默认seed为0

这个seed作为随机种子,用于生成伪随机序列。在求解过程中需要用随机数时,要从该随机序列提取随机数。评审时,我们可以指定不同的seed,用于检查结果的随机性。

二、最终测试(以满分为标准)

1、simple

  • simple_n5_m8_b8-16_t0.0311
  • simple_n10_m10_b4-32_t0.051
  • simple_n10_m10_b4-32_t0.053
  • simple_n10_m10_b4-32_t0.0516
  • simple_n10_m10_b4-32_t0.0518
  • simple_n10_m15_b32-64_t0.8
  • simple_n20_m20_b4-64_t1.6
  • simple_n20_m20_b16-32_t13.7
  • simple_n50_m50_b4-8_t4.3
  • simple_n150_m100_b4-16_t0.3 合取时间过长

2、medium

  • medium_n20_m20_b4-64_t32.8
  • medium_n20_m20_b4-64_t39.2
  • medium_n20_m20_b4-64_t43.1
  • medium_n20_m20_b16-32_t39.7
  • medium_n25_m25_b4-32_t51.3
  • medium_n25_m25_b4-32_t66.2 结点数多(297438个),统计时间长
  • medium_n30_m30_b4-32_t21.3
  • medium_n30_m30_b4-32_t65.9
  • medium_n35_m35_b4-16_t34.6
  • medium_n50_m50_b4-8_t31.1

3、complex

  • complex_n25_m25_b4-32_t109.8
  • complex_n25_m25_b4-32_t168.7
  • complex_n25_m25_b4-32_t183.9
  • complex_n30_m30_b4-32_t132.4
  • complex_n30_m30_b4-32_t149.9 结点数多(138044个),统计时间长
  • complex_n35_m35_b4-16_t93.2
  • complex_n35_m35_b4-16_t113.9
  • complex_n40_m40_b4-8_t85.7
  • complex_n40_m40_b4-8_t102.9
  • complex_n50_m50_b4-16_t99.0

三、工作日志

2023/10/12

DO: 解决了常量问题

TODO: 完成逻辑左移和右移操作

2023/10/14

DO: 基本实现了除乘除外的其他运算

TODO: 找到尽可能高效的方法实现乘法和除法运算

2023/10/16

DO: 实现了变量乘常数的操作,以及完成了通过遍历BDD验证正确性的测试代码。

TODO: 完成乘数为变量的乘法操作和除法操作。

2023/10/19

DO: 完成了乘法和除法操作

TODO: 检验程序正确性,调整代码

2023/10/20

DO: 完善了代码的格式,提高了代码的复用性,尝试将约束合取在一起

TODO: 合取之后进行输出,可满足路径过多,爆内存

2023/10/21

DO: 尝试测试给定文件,但是由于变量的重复定义导致错误,代码需要重构

TODO: 重构代码,解决问题,再次验证给定测试文件

2023/10/24

DO: 修改代码,运行测试用例成功,但是尚未验证结果的正确性;登录服务器修改密码。

TODO: 完成输出格式的转换(二进制位向量转十六进制),验证赛题给出的部分解是否全部包含在输出文件中。

2023/10/26

DO: 测试给定文件result.json,simple下的第一个测试文件(n5_m8_b8-16_t0.0311)全部可以满足,第二个测试文件(n10_m10_b4-32_t0.051)求解第八个约束,再进行合取时时间过长。

TODO: 继续验证其他测试数据,修改优化代码。

2023/10/28

DO: 修改测试函数,提高复用性个和可读性;完善逻辑右移和逻辑左移的代码,使其右操作数可以为变量;数据规模增大,程序运行时间过长,可能需要优化算法。

TODO: 尝试解决随机采样问题

2023/11/1

DO: 使用CUDD提供的变量排序优化,约束合取能够在合理时间内完成;测试代码,发现问题,取反操作在某些情况下需要先进行位扩展再进行取反。

TODO: 解决BUG,根据KCBox考虑如何进行采样。

2023/11/2

DO: 位扩展问题解决了一部分。解决思路,即统一同一约束中的各个变量位宽为最大变量位宽。这种解决方法有较大问题,因为某些自决定位宽的运算符(逻辑运算符)会隔离位宽的统一。

TODO: 目前想到的方法,在计算约束前先遍历一遍约束树,统计各个运算符所在的子表达式中的最大位宽。

2023/11/3

DO: 位扩展基本解决,测试文件全部通过,但是不能保证完全没有BUG;编写采样代码demo。

TODO: 检查代码是否存在其他BUG,完成采样代码,优化变量排序。

2023/11/4

DO: 基本实现了采样代码,并且将采样结果输出到了json文件

TODO: 根据直播答疑结果可能要修改采样过程;选择较优的变量排序方法进行优化;优化代码,降低耦合,提高可读性。

2023/11/5

DO: 彻底解决了位宽对齐问题

TODO: 优化代码;按照赛题要求提供执行接口和操作命令(随机数种子接口、输入输出文件路径等)。

2023/11/6

DO: 解决了采样代码的算法BUG,提供了可执行文件的参数接口。

TODO: 验证reslut文件的正确性

2023/11/10

DO: 代码基本完成,模型数过多,c++内置数据类型存不下,改用string存储;BDD采样时,结点唯一存在的表示是其索引和左右指针,故进行模型计算时不要重复,也不要漏掉。

TODO: 编写设计报告;将程序部署到服务器

2023/11/10

DO: 修改采样代码,目前全部测试样例都可以得到满分

TODO: 编写设计文档;优化代码;部署到服务器

2023/11/20

DO: 初步完成设计文档;程序已经部署到服务器;更新了采样部分的代码(展开归约后隐藏的路径);编写了运行程序和测试程序的脚本文件

TODO: 进一步完成设计文档;优化程序

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published