A graph placement methodology

homework › vlsi
,

A graph placement methodology

intro

problem

chip floorplanning, a challenging problem2 that has long defied automation

outcome

under 6 h VS months by human experts (baseline)

前置知识

image-20231218154221817

  1. 芯片由多个模块组成，比如内存子系统、计算单元和控制逻辑系统。

  2. 这些模块可以通过电路组件的（netlist）来描述，其中包括宏和标准单元。

    Netlist是一个描述电子系统中组件（如电阻、电容、晶体管等）以及它们之间连接关系的列表。

    Netlist包含了电路的逻辑信息,但是不包括布局信息.我们的工作本质上就是把netlist转化为布局信息

    TODO: netlist 在代码中是如何体现的?

  3. 芯片平面布局的目标是在遵循密度和布线拥塞的硬约束的情况下，优化功耗、时序、面积和导线长度等性能指标。

image-20231218154315934

前人局限性

image-20231218154833627

  1. 划分： 对局部的关注牺牲了全局解的质量.因此不适用于大规模

    实质上就是分治算法

    将整个电路网表划分成若干个较小的子块,对每个子块进行独立的优化处理,将优化后的子块重新组合，形成整体的电路优化结果。

  2. 退火:尽管能得到最优解,但是对于大型电路,收敛太慢

  3. 统计方法:Routing congestion（布线拥塞）和timing violations（时序违例）之所以不容易用可微分的方式进行优化.

    布线拥塞指的是芯片特定区域对路由资源（例如金属轨道或通道）的需求很高，导致拥塞和潜在的性能问题。

    因为这两个经常需要用到离散的决策,难以用可微的方式优化(比如线长)

人类是怎么做的

  • 生成

  • 打回上级

Chip floorplanning is a game

Chip floorplanning is analogous to a game with varying pieces (for example, netlist topologies,macro counts, macro sizes and aspect ratios), boards (varying canvas sizesand aspect ratios) and win conditions (relative importance of differentevaluation metrics or different density and routing congestion constraints).

更深层的意义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
In addition to the immediate impact on chip floorplanning, the ability
of our method to generalize and quickly generate high-quality solutions
has major implications, unlocking opportunities for co-optimization
with earlier stages of the chip design process. Large-scale architectural
explorations were previously impossible, because it took months of
human effort to accurately evaluate a given architectural candidate.
However, modifying the architectural design can have an outsized
impact on performance, and would facilitate full automation of the
chip design process. Automating and accelerating the chip design
process can also enable co-design of AI and hardware, yielding
high-performance chips customized to important workloads, such
as autonomous vehicles, medical devices and data centres.
At an abstract level, our method learns to map the nodes of a hypergraph onto a limited set of resources, subject to constraints. Placement optimizations of this form appear in a wide range of science and
engineering applications, including hardware design1, city planning16,
vaccine testing and distribution17, and cerebral cortex layout18. Therefore, we believe that our placement optimization methodology can be
applied to impactful placement problems beyond chip design.
Beyond the experimental results reported here, our method is
already having real-world impact, and our floorplan solutions are in
the product tapeout of a recent-generation Google tensor processing
unit (TPU) accelerator.

第二节:Chip floorplanning as a learning problem

The underlying problem is a high-dimensional contextual banditsproblem

我们在开题报告中的论文里谈到这个优化问题实际上是一个多臂老虎机问题,而进一步地,Chip floorplanning是一个高维上下文多臂老虎机

  1. 上下文赌博机问题： 传统的赌博机问题是一个多臂老虎机问题，其中有多个拉杆（臂），每个拉杆都对应于一个潜在的奖励分布。在上下文赌博机问题中，每次选择拉杆不仅取决于拉杆的历史回报，还取决于当前的环境或上下文。这个上下文可以是一个向量，包含描述当前状态的多个特征。
  2. 高维度： 高维度表示有很多特征或维度。在上下文赌博机问题中，高维度上下文意味着上下文向量中包含了大量的特征，每个特征都可能影响到在某一时刻选择哪个拉杆。

高维上下文赌博机问题涉及在每个时间步骤选择拉杆时，需要考虑一个包含大量特征的上下文向量。

Markov decision process 是什么？它是不是常用来解决上下文（contextual）赌博机（bandits）问题

Markov Decision Process（MDP，马尔可夫决策过程）是一种数学框架，用于建模决策问题，特别是在涉及随机性和不确定性的情境中。MDP是强化学习的一部分，其核心思想是通过在不同状态下采取不同的动作来最大化期望累积奖励。

MDP 的基本要素包括：

  1. 状态（States）： 描述系统可能处于的不同情况或状态。

  2. 动作（Actions）： 描述在给定状态下可以采取的决策或动作。

  3. 转移概率（Transition Probabilities）： 描述在执行某个动作后系统从一个状态转移到另一个状态的概率。

  4. 奖励函数（Reward Function）： 描述在执行某个动作后系统获得的奖励。

MDP 是一种用于制定强化学习问题的框架，其中代理（agent）通过在不同状态下执行不同动作来学习如何最大化累积奖励。这种框架在许多领域都有应用，例如机器人控制、游戏策略、资源管理等。

关于上下文赌博机问题，MDP 可以与上下文结合，形成上下文MDP（Contextual MDP）来处理带有上下文信息的决策问题。在上下文MDP中，每个状态不仅包括环境的内在状态，还包括外部上下文信息。这种方法可以很自然地扩展到上下文赌博机问题，其中上下文信息被视为状态的一部分。

因此，MDP提供了一个通用的数学框架，可以用于建模并解决包括上下文赌博机在内的各种强化学习问题。

OUR MDP

  1. 状态（States）： 包含有关部分布局的信息，包括电路图、节点和边的特征，当前待放置的节点以及电路图的元数据。

  2. 动作（Actions）： 当前宏可以放置在网格单元(grid cells of the chip canvas canvas)上的所有可能位置。

  3. **转移概率（Transition Probabilities）：**在给定状态下执行某个动作后,所有可能的下一状态的概率分布

    ==TODO:==这个转移是确定的吗?

  4. 奖励函数（Reward Function）： 奖励是代理导线长度、拥塞和密度的负权重和。每次迭代只关心最终结果的情况(因此中间状态的奖励函数简单置零)

具体实现

loss function

image-20231218183504210

  • θ: RL agent

  • G: dataset of netlists of size K

  • g: one netlist in G

  • $R_{p.g}$: reward of placement p for netlist g

  • E: expected

  • πθ: policy distribution 具体而言，πθ描述了在每个可能的状态下，代理选择每个可能动作的概率。我们的强化学习过程实际上就是调整策略的过程.

Designing domain-adaptive policies

  1. we first focused on learning rich representations of the state space.

img



本文总阅读量次