ToB企服应用市场:ToB评测及商务社交产业平台

标题: 2022年全国研究生数学建模竞赛华为杯D题PISA架构芯片资源排布题目求解全过 [打印本页]
作者: 怀念夏天    时间: 2024-7-29 06:23
标题: 2022年全国研究生数学建模竞赛华为杯D题PISA架构芯片资源排布题目求解全过
2022年全国研究生数学建模竞赛华为杯

D题 PISA架构芯片资源排布题目

原题再现：

  一、配景介绍
芯片是电子行业的基础，在当前日益复杂的国际形势下，芯片成了各个大国必争的高科技技术。本课题关注网络通信领域的交换芯片，传统的交换芯片功能固定，当出现新的网络协议时，必须重新筹划芯片，而芯片从筹划到利用，往往必要几年的时间，因此固定功能的交换芯片大大降低了研发效率，为相识决此题目，诞生了可编程的交换芯片。PISA（Protocol Independent Switch Architecture）是当前主流的可编程交换芯片架构之一，其有着和固定功能交换芯片相当的处理速率，同时兼具了可编程性，在将来网络中具有广阔的应用场景[1-2]。
在对PISA架构作进一步阐明之前我们首先澄清几个根本概念：
  1. 报文：报文即网络通信中传输的数据包，在网络通信中，用户传输的数据被封装成一个个的数据包进行传输。
  2. 根本块：根本块是源程序的一个程序片断，对源程序进行根本块分别会将源程序分别为一个个的根本块。至于根本块如何分别本身也是一个值得探讨的题目，但超出了本题目的范围，在此不再多加赘述。
  3. 流水线：流水线为一系列处理单元串联构成，报文在流水线中按次序依次通过每个处理单元，终极完成处理。流水线各级便是指流水线中各处理单元。
  PISA架构如图1所示，其包括报文解析（parser）、多级的报文处理流水线（Pipeline Pocket Process）、以及报文重组（Deparser）三个构成部分。报文解析用于识别报文种类；多级的报文处理流水线用于修改报文数据，在现实的PISA架构芯片中，不同的芯片流水线的级数大概不同；报文重组用于报文重新组装。本课题只关注其中多级的报文处理流水线部分。在PISA架构编程模型中，用户利用P4语言描述报文处理行为得到P4程序，再由编译器编译P4程序，进而天生芯片上可以执行的机器码。编译器在编译P4程序时，会首先将P4程序分别为一系列的根本块，再将各根本块排布到流水线各级当中。由于各根本块均会占用肯定的芯片资源，将根本块排布到流水线各级便是将各根本块的资源排布到流水线各级当中（即必要确定每个根本块排布到流水线哪一级），因此我们将根本块的排布题目称作PISA架构芯片资源排布题目。在现实的PISA架构芯片的筹划中，为了减少连线的复杂度，往往对流水线各级的资源、以及流水线各级之间的资源有着多种多样的约束条件，这一系列复杂的资源约束条件使得资源排布题目尤为困难。然而，芯片的各类资源均有限，越高的资源利用率意味着能够越好的发挥芯片的能力，让芯片支持更多的业务，因此，高资源利用率的资源排布算法对于编译器筹划至关紧张。

   图1 PISA架构图     二、题目描述 由根本块定义可知根本块为源程序的片断，根本块中会执行指令来完成计算，指令执行时会读取指令源操作数（即读源操作数对应的变量）进行计算，再将计算效果赋值给目的操作数（即写目的操作数对应的变量）。对于分别好的根本块，每个根本块中的指令并行执行，执行时按照先读后写的次序（由芯片底层实现所决定），即先同时读出所有的目的操作数，再并行执行所有指令的计算，末了同时将计算效果赋值给目的操作数。由于并行向同一个变量写多次时存在辩论，因此每个根本块只会写同一个变量一次（即根本块中不存在多条指令对相同变量赋值）。   根本块可以被抽象成一个节点，抽象后根本块中执行的具体指令被屏蔽，只生存读写的变量信息。当根本块A执行完可以跳转到根本块B执行时，在A和B之间增加一条有向边，这样P4程序即可表示为一个有向无环图（P4程序不存在循环），称作P4程序流程图，如图2左图所示。PISA架构资源排布便是将P4程序流程图中的各节点（即各根本块）在满足约束条件下排布到流水线各级当中。约束条件来自于两方面，一方面来自于P4程序本身，P4程序每个根本块均会写一部分变量（即对变量赋值）和读一部分变量，变量的读写使得根本块之间存在数据依靠，同时，根本块执行完后大概跳转到多个根本块执行，从而使得根本块之间也存在着控制依靠，数据依靠和控制依靠约束了根本块排布的流水线级数的巨细关系，关于数据依靠和控制依靠的具体阐明参见附录A；另一方面的约束条件来自于芯片的资源约束，芯片中的资源包括TCAM、HASH、ALU、QUALIFY四类（附录B中表明了四类资源的作用以供感爱好的同砚进一步相识，不相识并不影响题目作答）。流水线中针对于这四类资源有着严格的限定（具体的资源限定在赛题中进行阐明），资源排布时不能违反芯片的资源限定。   本题目中，输入数据给出了各根本块在P4程序流程图中的毗邻关系，各根本块占用的四类资源的数量，以及各根本块读写的变量信息，本题目的赛题统共包括两个子题目，必要同砚们在满足上述数据依靠、控制依靠、以及各具体子题目的资源约束条件下进行资源排布，并充分考虑各子题目的优化目标，以求最大化芯片资源利用率。   为了帮助大家进一步理解本题目，在附录C中给出了一个简单的资源排布示例。

   图2 PISA架构资源排布示意图    三、输入数据阐明
  输入数据包罗三个附件，分别给出了各根本块资源利用情况、各根本块读写的变量信息、以及各根本块在流图中的毗邻根本块，各附件格式如下：
  （1）attachment1.csv：各根本块利用的资源信息

  表中第一列为根本块编号，第2列到第5列为各根本块利用的四种资源的数目，资源统共分为四种（TCAM、HASH、ALU、QUALIFY），比如由上表可以知道，0号根本块必要占用2个ALU资源，4号根本块必要占用10个ALU资源和3个Qualify资源。
  （2）attachment2.csv：各根本块读写的变量信息

  表中第一列表示根本块编号，第二列中“W”表示写，“R”表示读，后续列表示本根本块写或者读的变量，当某一行从第三列及后续列没有任何元素时，阐明此编号的根本块没有写（或读）任何变量（此时该根本块单纯作为连接别的根本块的中心根本块，没有执行任何计算）。比方：0号根本块写了变量X0、X1，但没有读任何变量，1号根本块既没有写任何变量，也没有读任何变量。
  （3）attachment3.csv：各根本块在流程图中的毗邻根本块信息

  表中第一列为根本块编号，后续列为与当前根本块在流程图中毗邻的根本块编号，即在流程图（如图2左图所示）中，本根本块到后续列中的根本块之间存在有向边连接。比如，由上表第一行可知，0号根本块到1号根本块和2号根本块之间存在有向边连接（即0号根本块执行结束后可以跳转到1号根本块或2号根本块执行），由第三行可知从2号根本块出发没有边（即根本块2执行后程序结束，不会再跳转到别的根本块执行）。通过此文件可以确定根本块在源程序的执行次序，确定每个根本块执行后跳转的目的根本块，进而构建起根本块的流程图。
  四、题目
  本课题必要建立资源排布题目的数学模型，并在此基础上处理如下两个题目。
  题目1：给定资源约束条件如下：
  （1）流水线每级的TCAM资源最大为1；
  （2）流水线每级的HASH资源最大为2；
  （3）流水线每级的ALU资源最大为56；
  （4）流水线每级的QUALIFY资源最大为64；
  （5）约定流水线第0级与第16级，第1级与第17级，…，第15级与第31级为折叠级数，折叠的两级TCAM资源加起来最大为1，HASH资源加起来最大为3。注：如果必要的流水线级数超过32级，则从第32开始的级数不考虑折叠资源限定；
  （6）有TCAM资源的偶数级数量不超过5；
  （7）每个根本块只能排布到一级。
  在上述资源约束条件下进行资源排布，并以占用的流水线级数只管短为优化目标。请给出资源排布算法，输出根本块排布效果，输出的效果格式如下：

  题目2：考虑如图3所示的流图，根本块2和根本块3不在一条执行流程上（因为根本块1执行完后要么执行根本块2，要么执行根本块3，根本块2和根本块3不大概都执行）。准确来说，在P4程序流程图中，由一个根本块出发可以到达另一个根本块则两根本块在一条执行流程上，反之不在一条执行流程上。对于这种不在一条执行流程上的根本块，可以共享HASH资源和ALU资源，根本块2和3中恣意一个的HASH资源与ALU资源均不超过每级资源限定，根本块2和3即可排布到同一级。据此，对题目1中的约束条件（2）、（3）、（5）作如下更改：
  （2）流水线每级中同一条执行流程上的根本块的HASH资源之和最大为2；
  （3）流水线每级中同一条执行流程上的根本块的ALU资源之和最大为56；
  （5）折叠的两级，对于TCAM资源约束不变，对于HASH资源，每级分别计算同一条执行流程上的根本块占用的HASH资源，再将两级的计算效果相加，效果不超过3。
  别的约束条件同题目1，更改资源约束条件后重新考虑题目1，给出排布算法，输出根本块排布效果。输出格式同题目1。

   图3 流图示例  整体求解过程概述(择要)

  随着全球“芯”缺浪潮的连续发酵，作为“工业粮食”的芯片技术成为我国亟待突围的财产之一。PISA 作为兼具良优点理速度与可编程性的交换芯片架构，有效缓解了传统固定功能的交换芯片研发效率低下的题目。为充分发挥芯片能力，高资源利用率的芯片资源排布算法的选择显得尤其紧张。鉴于此，本文将复杂的根本块资源排布题目拆解为多个子题目，并结合各类约束条件，通过建立目标规划模型与根本块排布模型逐步求解，然后筹划启发式规则对求解效果进行优化，终极将得到的尽大概短的流水线级数作为题目的解。
  针对题目一，本文将其分别为依靠关系分析和根本块资源排布两个子题目。针对子题目一，分析处理附件 attachment3.csv 数据得到控制流图 CFG 与控制流图的前向支配树FDT，CFG 和 FDT 差集即为根本块的控制依靠关系。其次，读取附件 attachment2.csv 中根本块的读写关系，利用广度优先搜索算法 BFS 判断根本块间的连通性来确定命据依靠关系。将控制依靠与数据依靠关系取并集得到完备的依靠关系。针对子题目二，将完成的依靠关系抽象为带权有向无环图，开端确定根本块在流水线中排布的层级关系。然后，以占用只管短的流水线级数为主要目标，结合 attachment1.csv 中的根本块资源需求和给定的资源约束条件建立了目标规划模型。模型的求解筹划了根本块排布模型，依据串行排布的原则，从无前序依靠关系的根本块中依据随机规则选取根本块放入最早可放入的流水线级，直到所有根本块完成排布。题目一得出流水线占用级数为 40 级。
  针对题目二，由于不在一条执行流程上的根本块可以共享 HASH 资源和 ALU 资源，我们在题目一的基础上引入不在一条执行流程上的根本块的概念，缓解了题目一中对HASH 和 ALU 的占用题目。本文将题目二拆解为判断两个根本块是否在同一条执行流程、根本块资源排布两个子题目。针对子题目一，根据程序流程图，利用广度优先搜索算法判断两个根本块是否在一条执行流程上，即从一个根本块出发是否可到达另一个根本块，获得根本块执行流程关系对称矩阵。针对题目二，同样以占用只管短的流水线级数为主要目标，结合不在同一执行流程上的根本块可共享 HASH 和 ALU 资源这一条件与更改后的三个约束，建立与题目一雷同的目标规划模型。求解时对于有新的根本块排布的流水线，合并该级流水线中与其处于不同控制流的根本块对 HASH 和 ALU 的资源需求。题目二得出流水线占用的级数为 34 级。
  求解方案优化考虑到随机规则选取的不稳固性，对根本块选取规则进行优化，本文构建了最早开始时间 EST、最多紧后资源块 MST、最早开始时间且最多紧后资源块EST_MST 等 6 种启发式规则，依据启发式规则选取要加入流水线的根本块。本文综合了10 次随机规则和 6 种启发式规则求解的最优效果作为终极的流水线排布方案。优化后，题目一得出流水线占用级数为 40 级。题目二得出流水线占用的级数为 34 级。末了，本文发现了题目一的性能瓶颈在于 HASH 资源，题目二的性能瓶颈在于TCAM 资源。通过综合考虑控制依靠、数据依靠和各级流水线的资源约束条件，证实了所提方案的有效性与普适性。总结了所提算法与模型的优缺点，并对将来研究工作进行了展望。
模型假设：

  [1] 假设实行场景均位于抱负状态，不受温度和电磁等因素影响。
  [2] 假设实行过程中不存在由芯片故障导致的误差。
  [3] 假设只关注 PISA 架构芯片多级的报文处理流水线部分。
  [4] 假设每级流水线除题目所给的资源约束外，其他条件均相同。
  [5] 假设可排布的流水线级数没有上限。
  [6] 假设随机模型种取随机数的过程是完全随机的。
题目分析：

题目一分析：

  题目一要求考虑各根本块间的数据依靠、控制依靠关系情况下，结合给定的资源约束条件，实现根本块资源排布并优化，使占用的流水线级数只管短，以求最大化芯片资源利用率。题目给出 attachment1.csv、attachment2.csv、attachment3.csv 三个附件分别为各根本块利用的资源信息、各根本块读写的变量信息以及各根本块在流程图种的毗邻根本
块信息。
  通过对题目分析，我们得出本题可拆解为以下三个子题目：
  子题目一：通过筹划算法与模型，对附件二、附件三中的数据进行处理分析，确定各根本块间的控制依靠关系与数据依靠关系，从而开端确定根本块在流水线中排布的层级关系。
  子题目二：结合题目所给资源约束条件与附件一的资源利用数据，建立模型，确定根本块在流水线中的级数排布情况。
  子题目三：对根本块排布进行优化，使得根本块占用的流水线级数尽大概短。
题目二分析：

  题目二在题目一的基础上引入不在一条执行流程上的根本块的概念，对于不在一条执行流程上的根本块，可以共享 HASH 资源和 ALU 资源。由此，题目二对于题目一缓解了 HASH 和 ALU 的占用。题目同样要求给出根本块在流水线中的排布算法与效果，但对约束条件进行了更改。
  结合分析，题目二可拆解为以下两个子题目：
  子题目一：根据程序流程图，建立模型，确定一个根本块出发是否可到达另一个根本块，即两个根本块是否在一条执行流程上。
  子题目二：结合不在同一执行流程上的根本块可共享 HASH 和 ALU 资源这一条件与更改后的约束，建立模型，确定根本块在流水线中的级数排布情况，并使占用的流水线级数只管短。
模型的建立与求解整体论文缩略图




全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码：

部分Python程序如下:

  1. import networkx as nx
  2. import matplotlib.pyplot as plt
  3. import numpy as np
  4. import csv
  5. import scipy as sp
  6. # 入度
  7. inGF = []
  8. # 第一步：dfs
  9. dfn = []
  10. rak = []
  11. fa = []
  12. search_path = []
  13. # 第二步：sdom
  14. val = []
  15. bel = []
  16. sdom = []
  17. # 第三步：idom
  18. idom = []
  19. # 比较获取 CDG
  20. cdg = []
  21. idomGF = nx.DiGraph()
  22. def read_csv3(file_name):
  23. f = open(file_name, encoding='UTF8')
  24. csv_reader = csv.reader(f)
  25. control_edges = []
  26. for line in csv_reader:
  27. adj_num = len(line)
  28. if adj_num > 1:
  29. for i in range(1, adj_num):
  30. control_edges.append((int(line[0]), int(line[i])))
  31. f.close()
  32. # print(control_edges)
  33. return control_edges
  34. def subgraph(pointList, linkList):
  35. G = nx.DiGraph()
  36. GF = nx.DiGraph()
  37. # 转化为图结构
  38. for node in pointList:
  39. G.add_node(node)
  40. GF.add_node(node)
  41. for link in linkList:
  42. G.add_edge(link[0], link[1])
  43. GF.add_edge(link[1], link[0])
  44. return G, GF
  45. def dfs(GF):
  46. # GF 的 root 为人为添加的序号最大的根
  47. root = len(GF.nodes) - 1
  48. T = nx.dfs_tree(GF, root)
  49. for n in GF.nodes():
  50. fa.append(0)
  51. dfn.append(n)
  52. global rak
  53. rak = list(T) # 所有节点
  54. for i in range(0, len(fa)):
  55. dfn[rak[i]] = i
  56. for i in list(T.edges): # 所有边
  57. fa[i[1]] = i[0]
  58. # print(dfn)
  59. # print(rak)
  60. # print(fa)
  61. def find(v):
  62. # 还未被遍历
  63. if v == bel[v]:
  64. return v
  65. tmp = find(bel[v])
  66. if (dfn[sdom[val[bel[v]]]] < dfn[sdom[val[v]]]):
  67. val[v] = val[bel[v]]
  68. bel[v] = tmp
  69. return bel[v]
  70. def tarjanFDT():
  71. # 初始化 val 和 sdom
  72. for i in range(0, len(dfn)):
  73. val.append(i)
  74. sdom.append(i)
  75. bel.append(i)
  76. idom.append(i)
  77. # 从大到小遍历 dfs 树
  78. for i in range(len(dfn) - 1, 0, -1):
  79. # dfs 序最大的点 u
  80. u = rak[i]
  81. # 获取 GF 原图中所有 u 的前驱
  82. neighbors = G.neighbors(u)
  83. for v in neighbors:
  84. find(v)
  85. if (dfn[sdom[val[v]]] < dfn[sdom[u]]):
  86. sdom[u] = sdom[val[v]]
  87. # print(sdom)
  88. sdomGF = nx.DiGraph()
  89. for i in range(0, len(sdom)):
  90. sdomGF.add_node(i)
  91. sdomGF.add_edge(sdom[i], i)
  92. bel[u] = fa[u]
  93. u = fa[u]
  94. neighbors = sdomGF.neighbors(u)
  95. for v in neighbors:
  96. find(v)
  97. if sdom[val[v]] == u:
  98. idom[v] = u
  99. else:
  100. idom[v] = val[v]
  101. for i in range(0, len(dfn)):
  102. u = rak[i]
  103. if idom[u] != sdom[u]:
  104. idom[u] = idom[idom[u]]
  105. global idomGF
  106. for i in range(0, len(idom)):
  107. idomGF.add_node(i)
  108. idomGF.add_edge(idom[i], i)
  109. # nx.draw_networkx(sdomGF, with_labels=True)
  110. # plt.show()
  111. # nx.draw_networkx(idomGF, with_labels=True)
  112. # plt.show()
  113. def getInGF():
  114. # 遍历 GF 所有点
  115. for i in range(0, len(GF.nodes)):
  116. # 初始化：0 标识入度为 0
  117. inGF.append(0)
  118. for edge in GF.edges:
  119. inGF[edge[1]] = 1
  120. def addGFRoot():
  121. # print(len(GF.nodes))
  122. GF.add_node(len(GF.nodes))
  123. for i in range(0, len(inGF)):
  124. if inGF[i] == 0:
  125. GF.add_edge(len(GF.nodes) - 1, i
  127. # nx.draw_networkx(GF, with_labels=True)
  128. # plt.show()
  129. if __name__ == '__main__':
  130. # 读 attachment3.cvs
  131. linkList = read_csv3("./data/attachment3.csv")
  132. pointList = []
  133. for i in range(0, 607):
  134. pointList.append(i)
  135. # 原始有向无环图 G，反向图 GF
  136. G, GF = subgraph(pointList, linkList)
  137. # 获取 GF 入度为 0 的所有点
  138. getInGF()
  139. # 为 GF 添加根节点
  140. addGFRoot()
  141. # 获取 G 的前向支配树，也就是 GF 的支配树，存储在 idomGF 中（即
  142. FDT）
  143. dfs(GF)
  144. tarjanFDT()
  145. # 对比 G 原图和 FDT 图，寻找在 G 但不在 FDT 中的边，得到 CDG
  146. for edgeG in G.edges:
  147. edgeGf = (edgeG[1], edgeG[0])
  148. # 标识是都存在相同，初始化为 0
  149. flag = 0
  150. for edgefdt in idomGF.edges:
  151. if edgeGf == edgefdt:
  152. flag = 1
  153. break
  154. else:
  155. continue
  156. if flag == 0:
  157. cdg.append(edgeG)
  158. f = open("./data/control_dependance_less_equal.txt", "w")
  159. f.writelines(str(cdg))
  160. f.close()
  161. print(len(cdg))
  162. print(cdg)
复制代码
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4