《基于汉擎底座的Pattern Matching算法》赛题讨论&答疑

欢迎大家参加EDA²侠客岛难题挑战·2025的《基于汉擎底座的Pattern Matching算法》赛题。
大家有任何题目问题、技术问题，都可以在此交流讨论，各领域专家会及时答疑。

如果无法播放，请点击此处在新窗口打开

您还可添加“基于汉擎底座的Pattern Matching算法群”赛题专属微信群，一起沟通交流。

侠客岛的出题专家老师们好，想请你们帮忙解决环境问题，我测试赛题基于汉擎底座的Pattern Matching算法的判题环境时
发现赛题中提供的docker镜像出现一些C++编程环境问题，具体情况如下，特向老师们咨询解决
build.sh运行时缺少cmake工具，自己安装了一个cmake，然后还是报错找不到链接器ld，
其中报错collect2: fatal error: cannot find 'ld'
然后ls -l /usr/bin/ld，几层跳转之后发现系统中安装的/usr/bin/ld指向的是空的文件

chaossi 发表于 2024-12-30 16:46
侠客岛的出题专家老师们好，想请你们帮忙解决环境问题，我测试赛题基于汉擎底座的Pattern Matching算法的判 ...

docker只提供了运行二进制的环境，里面没有cmake环境，需要本地编译成可执行文件后，再在环境里面运行，避免出现本地代码好好的，上了环境跑不起来。 注意要用静态编译，避免找不到.so文件。

解决版图模式匹配问题的赛题，已经在多个EDA比赛中出现过。在以往的赛题中，模式和版图图形通常是基于曼哈顿结构的，很少涉及非曼哈顿结构。然而，在这一次侠客岛的比赛中，首次引入了非曼哈顿结构的任意角度模式。
在数字集成电路设计领域，布局和布线后的版图一般以曼哈顿结构为主，或者在少数情况下出现45度或135度角的图形。而此次赛题中引入的非曼哈顿任意角度结构，是否具有实际应用价值

非曼哈顿图形

德玛西亚 发表于 2024-12-30 18:47
docker只提供了运行二进制的环境，里面没有cmake环境，需要本地编译成可执行文件后，再在环境里面运行， ...

因为想在自己本地编译，但是发现本地环境无法链接so的动态库，静态编译因为赛题给的3rd_lib源码b不完整，无法编译，而库中提到的git仓库是一个私有的库，请问能否公开或者申请加入呢

无法git clone

chaossi 发表于 2025-1-6 15:09
无法git clone

可以直接下载压缩包，或者fork到你个人仓库，然后clone

独照松月 发表于 2025-1-7 15:10
可以直接下载压缩包，或者fork到你个人仓库，然后clone

请问关于medb 还有 hanqing 这两个仓库如何下载呢  因为它两是私有仓库，和赛题提供的公有仓库是权限不同的。我本地只有x86机器，没有arm的 无法编译

chaossi 发表于 2025-1-9 17:23
请问关于medb 还有 hanqing 这两个仓库如何下载呢  因为它两是私有仓库，和赛题提供的公有仓库是权限不同 ...

https://gitee.com/eda2_xiakedao/hisilicon-2025-hanqing
这里的readme.md 提供了操作步骤，你可以参考下。

请问我在本地能跑过给的测例，但是打榜显示低于100分~是打榜的测例和我们拿到的不一样么，还是说环境之类的问题~这种情况下，我们有什么信息来辅助调试么，不能纯靠瞎猜吧~

打酱油的 发表于 2025-2-25 16:17
请问我在本地能跑过给的测例，但是打榜显示低于100分~是打榜的测例和我们拿到的不一样么，还是说环境之类的 ...

你好，打榜的测例和你们拿到的测例是不一样的。如果怀疑环境问题，请看题目的《作品提交》章节，确保提交的作品符合要求

王冠 发表于 2025-2-25 18:50
你好，打榜的测例和你们拿到的测例是不一样的。如果怀疑环境问题，请看题目的《作品提交》章节，确保提交 ...

那还是没啥有效信息啊~过了就是过了，不过就继续瞎猜

打酱油的 发表于 2025-2-26 08:28
那还是没啥有效信息啊~过了就是过了，不过就继续瞎猜

你要根据官方给的测试case多次调试，多方面找优化方向，如果分数有提升，说明你的优化方向是对的。

烟花 发表于 2025-2-27 18:56
你要根据官方给的测试case多次调试，多方面找优化方向，如果分数有提升，说明你的优化方向是对的。 ...

我现在是官方给的测例都能过，但是打榜测例有个过不了~只要这个不过，再优化分数也没变化呀~准备放弃了

赛题方专家好，请问：
1. pattern图形一定被pattern框包含吗，有没有与pattern框相交的情况
2. jog和move可能同时发生在一条边上吗
3. 一个图形上最多有几条边发生move
4. 存不存在向两个不同方向move的情况，比如一个10*10的矩形，向左右两侧move 5，变成20*10

王粤龙 发表于 2025-3-4 10:02
赛题方专家好，请问：
1. pattern图形一定被pattern框包含吗，有没有与pattern框相交的情况
2. jog和move可 ...

1. 没有
2. 可能
3. 理论上，没有上限
4. 存在
可以重点关注我们提供的公开测试用例

专家们好，请问
1、是否会出现带斜边的空心多边形？

chaossi 发表于 2025-3-14 12:54
专家们好，请问
1、是否会出现带斜边的空心多边形？

赛题描述没有这个约束，参考公开case示例，建议综合考虑

专家们好，请问
edge_movement 参数指的是单条边的约束还是多条边移动距离总和的约束？
比如说，这里是 2<5 && 3<5 (每条边都满足 < 5)   还是 （2+3）<= 5  (多条边移动距离总和小于5)

chaossi 发表于 2025-3-14 18:47
专家们好，请问
edge_movement 参数指的是单条边的约束还是多条边移动距离总和的约束？
比如说，这里是 2 ...

第一种 2<=5&&3<=5 还是第二种（2+3）<=5

专家们好，请问模糊匹配-jog，题目描述 jog_length 不会大于图形的边长，是说jog_length小于全部图形边长，还是小于出现jog的这个图形的边长

chaossi 发表于 2025-3-14 19:03
第一种 2

是第一种情况

dyj 发表于 2025-3-16 11:45
专家们好，请问模糊匹配-jog，题目描述 jog_length 不会大于图形的边长，是说jog_length小于全部图形边长， ...

都不是，是小于出现jog所在边的边长度，保障jog会挖出一个凹形，否则和edge_movement一样了，另外jog不会挖穿图形，详情可以参考我们提供的公开case

专家们好，请问会出现空心多边形从外部进内部有2条重叠边的情况吗

专家们好，在官方给的case3里面，在pattern的marker框内部所有边都可移动时，对应可匹配的marker框是不唯一的，请问赛题会出现在layout上同一个位置匹配成功时，marker框位置不唯一的情况吗？或者有什么图形上的特征可以计算唯一的marker框？
图中，我画了Layout上蓝色的实线marker框，我认为它可以在虚线marker框范围内左右平移

dyj 发表于 2025-3-18 15:06
专家们好，请问会出现空心多边形从外部进内部有2条重叠边的情况吗

赛题描述没有这个约束，参考公开case示例，建议综合考虑

chaossi 发表于 2025-3-18 16:30
专家们好，在官方给的case3里面，在pattern的marker框内部所有边都可移动时，对应可匹配的marker框是不唯一 ...

marker框结果要是唯一的，marker框和图形的相对位置是不变的。即使在edge_movement和jog场景下，也是如此。你举的例子中，实线蓝区marker框是对的，不能左右平移

专家们好
1、marker框和图形的相对位置是不变的，我想请问这个相对位置是如何确定的呢？在我的理解中上，因为前面有回答活动边的数量理论上无上限，所以marker内的图形我理解成可以在edge_movement的范围内移动，但是您这里的回答相对位置我不太理解如何确定的，比方说，图形固定某一个点或者一条边不可移动？但是这也和前面回答的另一个同学的问题“存不存在向两个不同方向move的情况，比如一个10*10的矩形，向左右两侧move 5，变成20*10” 矛盾了。
2、第二点是我找到一个不在答案中的marker框，没有发现为什么它不在答案中。如下，它是case03的第二个Pattern EdgeMove4，Layout上的坐标是（11036, -3630）。图中，红色的斜线框是Layout的多边形，绿色的框是我自己理解赛题后绘制的活动范围，edge_movement=5，黑色框是marker，蓝色框是pattern的形状。

chaossi 发表于 2025-3-19 14:02
专家们好
1、marker框和图形的相对位置是不变的，我想请问这个相对位置是如何确定的呢？在我的理解中上，因 ...

如果我绘制的图形的活动范围是正确的话，marker框就是可移动的（在没有将周围无关图形圈进来的前提下），

@chaossi 感谢提问：
1、不冲突，可以认为和marker接近的边不移动，详见下图1，蓝色的边不移动。

2、你提供的这个图，有个jog，见下图2的红色圆形框位置，不满足edge_movement定义，所以匹配不上。

王冠 发表于 2025-3-19 15:05
@chaossi 感谢提问：
1、不冲突，可以认为和marker接近的边不移动，详见下图1，蓝色的边不移动。

好的，谢谢专家的回复
1、这个信息很关键
2、我确实未考虑到parameter文件中jog=0的约束

专家好，我找了一个更复杂的case
我认为接近marker框的定义 分上下左右四个方向，每个方向都有一个最接近的距离，大于这个距离的边则可以移动。
图中，上下左右四个方向的最接近的边的最小距离都相等，我绘制蓝色的边是不可移动，右下角绿色的边是可以移动。请问我的理解是否正确呢

chaossi 发表于 2025-3-19 16:06
专家好，我找了一个更复杂的case
我认为接近marker框的定义 分上下左右四个方向，每个方向都有一个最接近的 ...

我上面的理解是针对多个多边形的，寻找最接近marker框的边。
或者还有第二种理解，是针对单个多边形，每个多边形上 每个方向上最接近marker的边不可活动，也就是上面的图中，绿色的边也不可以活动。
不知道哪种理解正确？

chaossi 发表于 2025-3-19 16:10
我上面的理解是针对多个多边形的，寻找最接近marker框的边。
或者还有第二种理解，是针对单个多边形，每 ...

第一种正确，绿色的边可以移动，但不会超过蓝色的边

chaossi 发表于 2025-3-19 16:10
我上面的理解是针对多个多边形的，寻找最接近marker框的边。
或者还有第二种理解，是针对单个多边形，每 ...

上一个回复不严谨，绿色变可以动，有些蓝色边可能往里缩。能确定的是移动前和移动后的所有图形的最小外接矩形（BoundingBox）是不变的。

专家好，请问
pattern上，BoundingBox会与marker重叠吗，目前看是给的这些public case是可以避开了内部的多边形与marker重叠

chaossi 发表于 2025-3-23 16:28
专家好，请问
pattern上，BoundingBox会与marker重叠吗，目前看是给的这些public case是可以避开了内部的多 ...

不会重叠

专家好，这个case07有多层，多了 网格+每一层的expect的marker，这个会影响匹配吗

chaossi 发表于 2025-3-25 09:32
专家好，这个case07有多层，多了 网格+每一层的expect的marker，这个会影响匹配吗 ...

这应该是case05，不影响匹配

专家老师好
1、请问运行时是直接运行src同级目录下的bin执行，还是sh src下的build.sh后src/build/的bin？这主要是为了确定我可执行文件的输出位置
2、我将代码写到src下自己新建的include的文件夹下，然后cmake文件有相应的修改链接到include下的代码文件，这样是否会违反赛题要求？

补充一问:
3、omp多线程库是否能使用

chaossi 发表于 2025-4-2 10:25
补充一问:
3、omp多线程库是否能使用

1. 通过 sh build.sh 生成的可执行文件在 src/build 目录下。src 同级目录下的 bin 是参赛者提交作品的可执行文件，一般来说，就是拷贝了 src/build 目录下的 bin
2. 不违反，只要不修改 main.cpp 中的文件，然后实现 pattern_matching.cc 文件中的指定接口，保证程序入口代码为 main.cpp 即可，自己新增代码文件、第三方库、或修改构建脚本都是允许的
3. 可以

请问那打分程序 运行的是./build.sh之后src/build/下的bin，还是src同级目录的bin呢？

我自己在官方给的docker环节测试时所有case都能success，但是提交后全是0分，想问一下，能否查询一下我的程序在官方的环境下是否发生了什么环境上的错误。我自己配官方给的docker，编译时碰到的主要问题是缺少cmakelists.txt中缺少引用zlib库

chaossi 发表于 2025-4-2 20:47
请问那打分程序 运行的是./build.sh之后src/build/下的bin，还是src同级目录的bin呢？  ...

src同级目录的bin

王冠 发表于 2025-4-3 09:47
src同级目录的bin

那请问能否调整一下，如果选手提交的src同级目录的bin因为环境问题无法运行，就运行编译src下的build.sh后的/build/bin呢。因为我还是怀疑我能跑通所有的公开case，不至于提交后都是0分，毕竟我本地qemu模拟的arm架构docker的环境可能还是和官方的服务器的肯定有差异

chaossi 发表于 2025-4-3 09:11
我自己在官方给的docker环节测试时所有case都能success，但是提交后全是0分，想问一下，能否查询一下我的程 ...

不是环境错误

王冠 发表于 2025-4-2 13:49
1. 通过 sh build.sh 生成的可执行文件在 src/build 目录下。src 同级目录下的 bin 是参赛者提交作品的可 ...

我调整了下OMP的设置，本地测试结果是时间减少挺多的，内存消耗持平~但是跑分却是大幅降低，啥原因呢

打酱油的 发表于 2025-4-14 09:17
我调整了下OMP的设置，本地测试结果是时间减少挺多的，内存消耗持平~但是跑分却是大幅降低，啥原因呢 ...

公开case和打榜case有差异，可能某些优化的仅适用于公开case。后台打分的机器是独占资源的。

王冠 发表于 2025-4-14 15:23
公开case和打榜case有差异，可能某些优化的仅适用于公开case。后台打分的机器是独占资源的。 ...

嗯，这么说又到了撞大运的阶段