跳转至

L. EDA

分数：200分

Accelerating EDA

注：更新了 Baseline。Input 位于只读文件系统，所以需要以只读方式打开；请修改您的代码，以避免出现 Assertion Error。

背景

EDA，也就是电子设计自动化，是一种用于设计电子系统的方法。EDA工具可以帮助工程师设计和分析电子系统，从而提高设计效率。EDA工具通常包括模拟仿真、数字仿真、布局设计、布线设计等功能，帮助工程师快速设计出高质量的电子系统。正是 EDA，使大规模集成电路的设计成为可能，推动了电子系统的发展。

EDA的主要任务包括：

  • 逻辑设计：使用硬件描述语言（如Verilog或VHDL）描述电路的功能。
  • 仿真与验证：通过仿真工具验证设计的正确性，确保电路在逻辑和时序上符合预期。
  • 综合：将高级的逻辑描述转换为门级网表（gate-level netlist），即由基本逻辑门（如AND、OR、NOT等）组成的电路。
  • 布局布线（Place and Route）：将逻辑门映射到物理芯片上，并确定它们的位置和连接方式。
  • 时序分析：确保电路在物理实现后能够满足时序要求，避免信号延迟等问题。

在EDA的布局布线阶段，布线优化是一个关键问题。布线优化的目标是在满足电路性能要求的前提下，最小化导线的长度和面积，从而减少功耗、提高芯片的性能和可靠性。

随着技术的进展，EDA工具也遇到了很多瓶颈。如布局设计、布线设计等，都是NP完全问题，难以在合理的时间内找到最优解。因此，如何加速EDA工具成为了一个重要的问题。

说明

RSMT

在布线优化中，直角斯坦纳最小树（Rectilinear Steiner Minimal Tree, RSMT）问题是一个经典问题。RSMT的目标是在平面上用直角线（即水平和垂直线）连接一组给定的点（称为引脚或节点），并且可以通过引入额外的点（称为斯坦纳点）来减少总布线长度。RSMT问题的解是一个树结构，称为直角斯坦纳树，它连接了所有的引脚，并且总长度最小。

RSMT问题在VLSI（超大规模集成电路）设计中非常重要，因为它可以用于估计电路的布线长度、布线拥塞和互连延迟。RSMT问题的难点在于它是一个NP完全问题，意味着随着引脚数量的增加，问题的复杂度会急剧上升，难以在多项式时间内找到最优解。

FLUTE 方法

FLUTE（Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm）是一种基于查找表的快速RSMT算法，专门用于VLSI设计中的低度网络（即引脚数量较少的网络）。FLUTE的核心思想是通过预计算的查找表来快速构建RSMT，从而在保证高精度的同时，显著提高计算速度。

FLUTE的主要特点：

查找表（Lookup Table）：FLUTE通过预计算所有可能的低度网络的RSMT解，并将这些解存储在查找表中。对于给定的网络，FLUTE只需查找表中的相应条目，即可快速得到最优解。

低度网络的优化：FLUTE特别适用于低度网络（引脚数量较少的网络），因为低度网络的解空间较小，查找表可以覆盖所有可能的解。对于高度网络（引脚数量较多的网络），FLUTE使用网络分割技术将网络分解为多个低度子网络，然后分别求解。

精度与速度的权衡：FLUTE允许用户通过调整参数来控制精度和计算速度之间的权衡。用户可以选择更高的精度，但计算时间会相应增加；或者选择更快的计算速度，但精度可能会有所降低。

FLUTE的工作流程：

  • 查找表生成：FLUTE首先为低度网络生成查找表。查找表中存储了每个网络的潜在最优布线长度向量（POWV）和对应的潜在最优斯坦纳树（POST）。这些数据是通过边界压缩技术和递归算法生成的。
  • 网络分割：对于高度网络，FLUTE使用网络分割技术将网络分解为多个低度子网络。分割时，FLUTE会评估不同的分割方式，并选择最优的分割方案。
  • 查找表查询：对于每个低度子网络，FLUTE通过查找表快速找到最优的RSMT解。
  • 结果合并：将各个子网络的解合并，得到整个网络的RSMT。

FLUTE的优势：

  • 速度快：FLUTE的计算速度非常快，尤其是对于低度网络，几乎可以与RMST（上文是RSMT，这里是RMST，并不相同）算法相媲美。
  • 精度高：FLUTE在低度网络上能够找到最优解，对于高度网络也能提供非常接近最优的解。
  • 灵活性：FLUTE允许用户通过调整参数来控制精度和计算速度之间的权衡，适用于不同的应用场景。

目标

本项目的目标是加速FLUTE算法。我们提供了 baseline.cpp 可供使用，这是一个单线程程序。

运行方式

确保可执行文件的同目录下有 POMV9.dat 和 PORT9.dat ，这是FLUTE算法的查找表。运行时需要传入两个参数，分别是输入文件和输出文件。例如：

./flute data.in.bin data.out.bin

数据格式

你可以使用 datagen 生成数据，也可以使用我们提供的数据进行测试。输入输出都是二进制格式，数据格式如下：

  • 输入文件： data.in.bin
    • 网络数量（num_nets）：一个整数，表示网络的总数。
    • 引脚起始索引（pin_st）：一个整数数组，长度为num_nets + 1，表示每个网络的引脚在data_x和data_y数组中的起始位置。
    • 引脚坐标（data_x 和 data_y）：两个数组，分别存储所有引脚的x坐标和y坐标。
  • 输出文件： data.out.bin
    • 结果x坐标（result_x）：一个数组，存储所有分支的x坐标。
    • 结果y坐标（result_y）：一个数组，存储所有分支的y坐标。
    • 邻居节点索引（result_n）：一个数组，存储每个分支的邻居节点索引。

附件中提供了一组参考输入输出文件， d1.in.bin 与 d1.out.bin 。你也可以通过 datagen.cpp 直接生成测试文件。

运行环境

本题较为特殊，需要提交一个 env 文件指定运行环境，可选的环境如下：

  • intel ：Intel 8358 CPU，16核心，24GB内存
  • arm ：Kunpeng 920 CPU，16核心，24GB内存
  • cuda ：NVIDIA L40 GPU，48G显存，附 4 核心 CPU，24GB内存
  • npu ：华为 Ascend 910B NPU，64G显存，附 20 核心 CPU，128GB内存。选手可用测试镜像 crmirror.lcpu.dev/hpcgame/asend:ubuntu20.04 。

评测标准

本题总分 200，采用分点评测的方式。

num_nets = 10000 的测试点，只验证正确性，20分。

num_nets = 1000000 的输入180分，设运行时长为T，评分规则如下：

  • T大于 800s：不得分
  • 20 < T <= 800：得分 = 450/(x-15)
  • 14 < T <= 20：得分 = 90 + 15*(20-T)
  • T <= 14：满分

提交内容

提交一个 impl.cpp 文件、以及选择的运行环境、自定义的编译选项（flags）

运行环境可以参考上文，自定义的编译选项可以为空，也可以指定编译选项，例如 -O2 。

最终我们运行的编译命令是：

  • intel ： icpx impl.cpp -o impl $(flags)
  • arm ： bisheng-clang++ impl.cpp -o impl $(flags)
  • cuda ： nvcc impl.cu -o impl -arch=sm_89 $(flags)
  • npu ：联系管理员，手工评测

附件