一种应用于PISA架构芯片的基本块排布方法

一种应用于pisa架构芯片的基本块排布方法
技术领域
1.本发明涉及芯片编译领域，具体涉及一种应用于pisa架构芯片的基本块排布方法。


背景技术：

2.芯片是电子信息技术的硬件基础，在如今的国际产业竞争大环境下，掌握芯片设计核心技术具有重要意义。
3.本发明着眼于网络通信领域的交换芯片。传统的交换芯片功能固定，当网络协议发生改变时，芯片也需要重新设计，这大大降低了研发效率。为解决这一问题，可编程的交换芯片应运而生。pisa(protocol independent switch architecture)是目前主流的可编程交换芯片架构之一，通常，对pisa架构芯片进行编程的流程是，首先由用户使用特定的编程语言描述报文处理行为得到源程序，然后由编译器编译该源程序，进而生成芯片可以执行的机器码。其中，报文是指网络通信中传输的数据包，数据包中封装有用户传输的数据。编译源程序时，编译器会首先将源程序进行基本块划分，然后将各基本块排布到芯片的各级流水线中。其中，流水线由芯片内的一系列处理单元串联组成，报文将在流水线中依次通过每个处理单元，最终完成处理，各级流水线就是流水线中的各处理单元；基本块是指源程序的一个程序片段，基本块划分就是将一个源程序划分为多个基本块。排布基本块时，要使所有基本块所占用的流水线级数尽可能少，这是因为，减少占用的流水线级数，可以提升芯片的资源利用率，更好地发挥芯片的能力，让芯片完成更多业务。因此，如何排布基本块，使其占用的流水线级数尽可能少，是pisa架构芯片编程中的关键问题。
4.限制流水线级数减少的关键之处在于基本块排布会受到多方面的约束限制。排布基本块时，每个基本块都会占用一定的资源，而每级流水线所拥有的资源是有限的，流水线各级之间也有一定的资源约束条件，因此，排布基本块会受到资源约束。此外，排布基本块还需要满足来自源程序的约束。根据源程序，可以确定任意一个基本块的两方面内容，包括该基本块所读写的变量，以及该基本块运行完成后可以直接跳转至哪些邻接基本块。源程序中，每个基本块都会读或写一些变量，当两个基本块读或写同一变量时，两个基本块就可能有运行次序的要求，这就是数据依赖。一个基本块执行完成后，对于不同的情况，可能会跳转至不同的基本块运行。换言之，有的基本块是否执行，取决于它上游的某些基本块，这就是控制依赖。具体而言，数据依赖包括写后读依赖、读后写依赖、写后写依赖：假定基本块a在基本块b前执行，若a写了某变量且b读了该变量，则b写后读依赖于a，若a读了某变量且b写了该变量，则b读后写依赖于a，若a、b均写了某变量，则b写后写依赖于a。数据依赖对基本块排布的约束是：当b写后读依赖于a或b写后写依赖于a时，a所位于的流水线级数需小于b的级数；当b读后写依赖于a时，a所位于的流水线级数需小于或等于b的级数。控制依赖的具体定义为：如果基本块a有多个邻接基本块，即从基本块a出发有多条路径，而只存在部分路径能够通过下游的基本块b，那么b控制依赖于a。控制依赖对基本块排布的约束是：当b控制依赖于a时，a所位于的流水线级数需小于或等于b的级数。将数据依赖、控制依赖统称为依
赖关系，它们对基本块排布的约束统称为依赖约束。若基本块b不写后读依赖于a、不读后写依赖于a、不写后写依赖于a、不控制依赖于a，则b不依赖于a，否则b依赖于a。
5.综上，对于pisa架构芯片，在已经完成了对源程序的基本块划分，且已知各个基本块所占用的资源数量、各个基本块所读写的变量和各个基本块的邻接基本块的基础上，如何在满足控制依赖、数据依赖、资源约束的条件下，优化基本块排布方法，使其占用的流水线级数尽可能少，对提升芯片资源利用率具有重要价值。
6.直接根据基本块的执行流程图进行排布是一种排布方法，这一排布方法原理简单，实施方便，但是该方法的排布结果有较大的优化空间。本发明公开了一种应用于pisa架构芯片的基本块排布方法，可以进一步减少基本块所占用的流水线级数，提升芯片的资源利用率。


技术实现要素：

7.本发明公开了一种应用于pisa架构芯片的基本块排布方法，可以在满足控制依赖、数据依赖、资源约束的条件下，利用相对较少的流水线级数完成基本块排布，从而提升芯片的资源利用率，更好地发挥芯片的能力。
8.所述应用于pisa架构芯片的基本块排布方法，包括如下步骤：
9.步骤1、读写变量描述：
10.记基本块总数为num
p
，记变量总数为numv，根据各个基本块所读写的变量，计算num
p
行numv列的write矩阵和read矩阵，其中write矩阵用来描述各基本块与各变量之间是否存在写操作的关系，read矩阵用来描述各基本块与各变量之间是否存在读操作的关系，计算方法为对矩阵中每个元素按照如下方法分别赋值：
11.对于元素write
ij
，若基本块i对变量j进行写操作，则令write
ij
为1，否则令write
ij
为0，
12.对于元素read
ij
，若基本块i对变量j进行读操作，则令read
ij
为1，否则令read
ij
为0；
13.步骤2、邻接信息描述：
14.根据各个基本块的邻接基本块，计算num
p
行num
p
列的connect矩阵，其中connect矩阵用来描述各基本块的邻接基本块信息，计算方法为对矩阵中每个元素按照如下方法赋值：
15.对于元素connect
ij
，若基本块j是基本块i的邻接基本块，则令connect
ij
为1，否则令connect
ij
为0；
16.步骤3、基本块顺序求解：
17.根据connect矩阵，调用顺序求解子程序，求解num
p
行num
p
列的order矩阵，其中order矩阵的含义是：
18.当order
ij
为1时表示基本块i在基本块j前执行，当order
ij
为0时表示基本块i不在基本块j前执行；
19.步骤4、基本块度的求解：
20.根据connect矩阵，计算num
p
维degree向量，其中degree向量用来描述各基本块的邻接基本块总数，计算方法为对向量中每个元素按照如下方法赋值：
21.对于元素degreei，令degreei等于基本块i的邻接基本块总数；
22.步骤5、控制依赖求解：
23.建立一个num
p
行num
p
列的control矩阵，令其初值为零矩阵，遍历每一个满足degreei大于1的i，令基本块i为当前父基本块，根据connect矩阵、order矩阵、degree向量、当前父基本块，调用控制依赖求解子程序，更新control矩阵，这样完成i的遍历后，就完成了control矩阵的求解，其中control矩阵的含义是：
24.当control
ij
为1时表示基本块j控制依赖于基本块i，当control
ij
为0时表示基本块j不控制依赖于基本块i；
25.步骤6、数据依赖求解：
26.根据order矩阵、write矩阵和read矩阵，调用数据依赖求解子程序，计算num
p
行num
p
列的datawr矩阵、datarw矩阵和dataww矩阵，其中datawr矩阵、datarw矩阵和dataww矩阵的含义分别是：
27.当datawr
ij
＝1时表示基本块j写后读依赖于基本块i，当datawr
ij
＝0时表示基本块j不写后读依赖于基本块i，
28.当datarw
ij
＝1时表示基本块j读后写依赖于基本块i，当datarw
ij
＝0时表示基本块j不读后写依赖于基本块i，
29.当dataww
ij
＝1时表示基本块j写后写依赖于基本块i，当dataww
ij
＝0时表示基本块j不写后写依赖于基本块i；
30.步骤7、基本块排布：
31.根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵，令arrangement矩阵取初值为num
p
行1列的零矩阵，调用基本块排布子程序，计算arrangement矩阵，其中arrangement矩阵的含义是：
32.当arrangement
ij
＝1时表示基本块i排布到第j级流水线，当arrangement
ij
＝0时表示基本块i不排布到第j级流水线；
33.arrangement矩阵完成计算后，就意味着完成了所有基本块的排布，arrangement矩阵的列数就是所有基本块所占用的流水线级数，记为num
l
，对于任意一个基本块i，它所在的流水线级数为满足arrangement
ij
＝1的j。
34.所述顺序求解子程序，是一个根据connect矩阵求解order矩阵的方法，包括如下步骤：
35.步骤3.1、为order矩阵赋初值：令order矩阵等于connect矩阵；
36.步骤3.2、记录当前order矩阵数值：定义num
p
行num
p
列的oldorder矩阵，其中oldorder矩阵用来记录order矩阵更新前的数值，令oldorder矩阵等于order矩阵；
37.步骤3.3、更新order矩阵：遍历order矩阵的行号i，在order矩阵第i列中找到所有取值为1的元素，记这些元素的行号组成的集合为front，其中front的含义是目前确定的在基本块i前执行的基本块集合，在order矩阵第i行中找到所有取值为1的元素，记这些元素的列号组成的集合为rear，其中rear的含义是目前确定的在基本块i后执行的基本块集合，这样完成行号i的遍历后，遍历j∈front,k∈rear所有(j,k)组合，令order
jk
＝1，这样完成(j,k)的遍历后，就完成了order矩阵的更新；
38.步骤3.4、判断order矩阵是否计算完成：判断order矩阵与oldorder矩阵是否相
等，若不相等，则返回步骤3.2；若相等，则order矩阵计算完成。
39.所述控制依赖求解子程序，是一个根据connect矩阵、order矩阵、degree向量对当前父基本块更新control矩阵的方法，包括如下步骤：
40.步骤5.1、数据初始化：
41.定义num
p
维power向量，该向量最终会用来判断哪些基本块控制依赖于当前父基本块，令power向量的初值为零向量；
42.记当前父基本块为基本块c；
43.定义一个基本块集——待分权集，待分权集的含义是，其中的基本块对应的power值不为0但尚未将其power值平均分配给其邻接基本块，令待分权集的初值取为基本块c的邻接基本块集合；
44.定义变量d，该变量用来记录选择哪一个基本块来分配其power值；
45.遍历待分权集的基本块i，令这样完成基本块i的遍历后，就完成了数据初始化；
46.步骤5.2、选择待分配的基本块：
47.遍历待分权集的基本块i，计算直至为零时停止遍历，然后令d取i；
48.步骤5.3、分配power值：
49.遍历满足connect
di
＝1的所有i，令若基本块i不在待分权集中，则将基本块i加入待分权集，这样完成i的遍历后，将基本块d从待分权集中移除；
50.步骤5.4、判断power向量是否完成计算：
51.若待分权集不为空集且power向量中最大的元素不为1，则返回步骤5.2，否则说明power向量已完成计算；
52.步骤5.5、更新control矩阵：
53.遍历满足poweri》0且poweri《1的所有i，令control
ci
为1，这样完成i的遍历后，就完成了control矩阵的更新。
54.所述数据依赖求解子程序，是一个根据order矩阵、write矩阵和read矩阵计算datawr矩阵、datarw矩阵、dataww矩阵的方法，该方法对矩阵中每个元素按照如下方法赋值：
55.对于datawr
ij
，若order
ij
＝1且则令datawr
ij
为1，否则令datawr
ij
为0，
56.对于datarw
ij
，若order
ij
＝1且则令datarw
ij
为1，否则令datarw
ij
为0，
57.对于dataww
ij
，若order
ij
＝1且则令dataww
ij
为1，否则令dataww
ij
为0。
58.所述基本块排布子程序，是一个根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵计算arrangement矩阵的方法，包括如下步骤：
59.步骤7.1、基本块排布初始化：
60.定义变量n，n的含义是当前正在将基本块向第n级流水线排布，令n取初值1；
61.定义一个基本块集——待分配池，待分配池的含义是当前所有尚未完成排布的基本块的集合，令待分配池的初值为所有基本块的集合；
62.定义一个基本块集——依赖满足池，依赖满足池的含义是待分配池中排布到第n级流水线时满足依赖约束的基本块集，令依赖满足池的初值为空集；
63.定义一个基本块集——约束满足池，约束满足池的含义是依赖满足池中排布到第n级流水线时满足资源约束的基本块集，令约束满足池的初值为空集；
64.定义num
p
行num
p
列的dependence矩阵，其中dependence矩阵的含义是：当dependence
ij
为0时表示当前将基本块j排布到第n级流水线是满足与基本块i的依赖约束的，当dependence
ij
不为0时表示当前将基本块j排布到第n级流水线是不满足与基本块i的依赖约束的；令dependence矩阵的初值为零矩阵；
65.计算num
p
维rely向量，其中rely向量的含义是：relyi为在基本块i执行后才能执行的基本块总数；计算方法为对向量中每个元素按照如下方法赋值：
66.步骤7.2、更新dependence矩阵：
67.令dependence＝control+datawr+datarw+dataww；
68.步骤7.3、更新依赖满足池：
69.令依赖满足池为空集，遍历所有满足的i，若基本块i是待分配池的元素，则将基本块i加入依赖满足池，这样完成i的遍历后就完成了依赖满足池的更新；
70.步骤7.4、更新约束满足池：
71.令约束满足池为空集，遍历依赖满足池的基本块，判断将该基本块排布到第n级流水线是否满足资源约束，若是，则将该基本块加入约束满足池，这样完成依赖满足池的基本块遍历后就完成了约束满足池的更新；
72.步骤7.5、排布基本块：
73.若约束满足池为空集，则在arrangement矩阵的最右侧新增一列零元素，遍历满足arrangement
in
＝1的所有i，令datawr矩阵、dataww矩阵的第i行元素全部为0，这样完成i的遍历后，令n取n+1；
74.若约束满足池不为空集，则找到约束满足池中基本块对应的rely值最大的所有基本块，若只有一个则直接记为基本块i，若有多个则任选其一记为基本块i，令arrangement
in
＝1，令control矩阵、datarw矩阵的第i行元素全部为0，将基本块i从待分配池中移除；
75.步骤7.6、判断是否完成arrangement矩阵的计算：
76.若待分配池不为空集，则返回步骤7.2，否则意味着完成了arrangement矩阵的计算。
77.在完成所有基本块的排布后，可以通过计算结果优度对计算结果进行大致评价，所述结果优度为一个取值范围为(0,1]的评价指标，数值越大表示基本块排布结果越好，计算方法为：
78.步骤a、计算road矩阵
79.计算num
p
行num
p
列的road矩阵，road矩阵用来确定满足数据依赖、控制依赖而不考虑资源约束的情况下所有基本块占用流水线级数的理论最小值，计算方法为对矩阵中每个元素按照如下方法赋值：
80.对于road
ij
，若步骤6计算出的datawr
ij
为1或步骤6计算出的dataww
ij
为1，则令road
ij
取-1，
81.否则，若i＝j或步骤5最终计算出的control
ij
为1或步骤6计算出的datarw
ij
为1，则令road
ij
取0，
82.否则，令road
ij
取∞；
83.步骤b、计算distance矩阵：
84.根据road矩阵，利用图论中的floyd算法，求解num
p
行num
p
列的distance矩阵，distance矩阵的含义是，对于一个以road矩阵为加权邻接矩阵的图，图中任意节点i至任意节点j的最短距离为distance
ij
；
85.步骤c、计算结果优度：
86.所述理论最小值为记为value
min
，所述结果优度为
87.floyd算法为图论的最短路径算法之一，可以根据图的加权邻接矩阵求解该图中任意节点至任意节点的最短路径及最短距离，floyd算法为已有公开内容，不是本发明的创造内容，在此不再赘述。
附图说明
88.图1为所述应用于pisa架构芯片的基本块排布方法的主程序流程图。
89.图2为所述基本块排布子程序中基本块排布方法示意图。
90.图3为算例中源程序基本块的执行流程图。
91.图4为按照本发明对算例进行基本块排布的结果。
92.图5为直接按照执行流程图对算例进行基本块排布的结果。
具体实施方式
93.接下来结合附图对本发明进行进一步的阐述。
94.本发明公开了一种应用于pisa架构芯片的基本块排布方法，可以在满足控制依赖、数据依赖、资源约束的条件下，利用相对较少的流水线级数完成基本块排布，从而提升芯片的资源利用率，更好地发挥芯片的能力。
95.所述应用于pisa架构芯片的基本块排布方法，包括如下步骤：
96.步骤1、读写变量描述：
97.记基本块总数为num
p
，记变量总数为numv，根据各个基本块所读写的变量，计算num
p
行numv列的write矩阵和read矩阵，其中write矩阵用来描述各基本块与各变量之间是否存在写操作的关系，read矩阵用来描述各基本块与各变量之间是否存在读操作的关系，计算方法为对矩阵中每个元素按照如下方法分别赋值：
98.对于元素write
ij
，若基本块i对变量j进行写操作，则令write
ij
为1，否则令write
ij
为0，
99.对于元素read
ij
，若基本块i对变量j进行读操作，则令read
ij
为1，否则令read
ij
为0；
100.步骤2、邻接信息描述：
101.根据各个基本块的邻接基本块，计算num
p
行num
p
列的connect矩阵，其中connect矩阵用来描述各基本块的邻接基本块信息，计算方法为对矩阵中每个元素按照如下方法赋值：
102.对于元素connect
ij
，若基本块j是基本块i的邻接基本块，则令connect
ij
为1，否则令connect
ij
为0；
103.步骤3、基本块顺序求解：
104.根据connect矩阵，调用顺序求解子程序，求解num
p
行num
p
列的order矩阵，其中order矩阵的含义是：
105.当order
ij
为1时表示基本块i在基本块j前执行，当order
ij
为0时表示基本块i不在基本块j前执行；
106.步骤4、基本块度的求解：
107.根据connect矩阵，计算num
p
维degree向量，其中degree向量用来描述各基本块的邻接基本块总数，计算方法为对向量中每个元素按照如下方法赋值：
108.对于元素degreei，令degreei等于基本块i的邻接基本块总数；
109.步骤5、控制依赖求解：
110.建立一个num
p
行num
p
列的control矩阵，令其初值为零矩阵，遍历每一个满足degreei大于1的i，令基本块i为当前父基本块，根据connect矩阵、order矩阵、degree向量、当前父基本块，调用控制依赖求解子程序，更新control矩阵，这样完成i的遍历后，就完成了control矩阵的求解，其中control矩阵的含义是：
111.当control
ij
为1时表示基本块j控制依赖于基本块i，当control
ij
为0时表示基本块j不控制依赖于基本块i；
112.步骤6、数据依赖求解：
113.根据order矩阵、write矩阵和read矩阵，调用数据依赖求解子程序，计算num
p
行num
p
列的datawr矩阵、datarw矩阵和dataww矩阵，其中datawr矩阵、datarw矩阵和dataww矩阵的含义分别是：
114.当datawr
ij
＝1时表示基本块j写后读依赖于基本块i，当datawr
ij
＝0时表示基本块j不写后读依赖于基本块i，
115.当datarw
ij
＝1时表示基本块j读后写依赖于基本块i，当datarw
ij
＝0时表示基本块j不读后写依赖于基本块i，
116.当dataww
ij
＝1时表示基本块j写后写依赖于基本块i，当dataww
ij
＝0时表示基本
块j不写后写依赖于基本块i；
117.步骤7、基本块排布：
118.根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵，令arrangement矩阵取初值为num
p
行1列的零矩阵，调用基本块排布子程序，计算arrangement矩阵，其中arrangement矩阵的含义是：
119.当arrangement
ij
＝1时表示基本块i排布到第j级流水线，当arrangement
ij
＝0时表示基本块i不排布到第j级流水线；
120.arrangement矩阵完成计算后，就意味着完成了所有基本块的排布，arrangement矩阵的列数就是所有基本块所占用的流水线级数，记为num
l
，对于任意一个基本块i，它所在的流水线级数为满足arrangement
ij
＝1的j。
121.如图1所示为所述应用于pisa架构芯片的基本块排布方法的主程序流程图。
122.所述顺序求解子程序，是一个根据connect矩阵求解order矩阵的方法，包括如下步骤：
123.步骤3.1、为order矩阵赋初值：令order矩阵等于connect矩阵；
124.步骤3.2、记录当前order矩阵数值：定义num
p
行num
p
列的oldorder矩阵，其中oldorder矩阵用来记录order矩阵更新前的数值，令oldorder矩阵等于order矩阵；
125.步骤3.3、更新order矩阵：遍历order矩阵的行号i，在order矩阵第i列中找到所有取值为1的元素，记这些元素的行号组成的集合为front，其中front的含义是目前确定的在基本块i前执行的基本块集合，在order矩阵第i行中找到所有取值为1的元素，记这些元素的列号组成的集合为rear，其中rear的含义是目前确定的在基本块i后执行的基本块集合，这样完成行号i的遍历后，遍历j∈front,k∈rear所有(j,k)组合，令order
jk
＝1，这样完成(j,k)的遍历后，就完成了order矩阵的更新；
126.步骤3.4、判断order矩阵是否计算完成：判断order矩阵与oldorder矩阵是否相等，若不相等，则返回步骤3.2；若相等，则order矩阵计算完成。
127.所述控制依赖求解子程序，是一个根据connect矩阵、order矩阵、degree向量对当前父基本块更新control矩阵的方法，包括如下步骤：
128.步骤5.1、数据初始化：
129.定义num
p
维power向量，该向量最终会用来判断哪些基本块控制依赖于当前父基本块，令power向量的初值为零向量；
130.记当前父基本块为基本块c；
131.定义一个基本块集——待分权集，待分权集的含义是，其中的基本块对应的power值不为0但尚未将其power值平均分配给其邻接基本块，令待分权集的初值取为基本块c的邻接基本块集合；
132.定义变量d，该变量用来记录选择哪一个基本块来分配其power值；
133.遍历待分权集的基本块i，令这样完成基本块i的遍历后，就完成了数据初始化；
134.步骤5.2、选择待分配的基本块：
135.遍历待分权集的基本块i，计算直至为零时停止遍历，然后令d取i；
136.步骤5.3、分配power值：
137.遍历满足connect
di
＝1的所有i，令若基本块i不在待分权集中，则将基本块i加入待分权集，这样完成i的遍历后，将基本块d从待分权集中移除；
138.步骤5.4、判断power向量是否完成计算：
139.若待分权集不为空集且power向量中最大的元素不为1，则返回步骤5.2，否则说明power向量已完成计算；
140.步骤5.5、更新control矩阵：
141.遍历满足poweri》0且poweri《1的所有i，令control
ci
为1，这样完成i的遍历后，就完成了control矩阵的更新。
142.所述数据依赖求解子程序，是一个根据order矩阵、write矩阵和read矩阵计算datawr矩阵、datarw矩阵、dataww矩阵的方法，该方法对矩阵中每个元素按照如下方法赋值：
143.对于datawr
ij
，若order
ij
＝1且则令datawr
ij
为1，否则令datawr
ij
为0，
144.对于datarw
ij
，若order
ij
＝1且则令datarw
ij
为1，否则令datarw
ij
为0，
145.对于dataww
ij
，若order
ij
＝1且则令dataww
ij
为1，否则令dataww
ij
为0。
146.所述基本块排布子程序，是一个根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵计算arrangement矩阵的方法，包括如下步骤：
147.步骤7.1、基本块排布初始化：
148.定义变量n，n的含义是当前正在将基本块向第n级流水线排布，令n取初值1；
149.定义一个基本块集——待分配池，待分配池的含义是当前所有尚未完成排布的基本块的集合，令待分配池的初值为所有基本块的集合；
150.定义一个基本块集——依赖满足池，依赖满足池的含义是待分配池中排布到第n级流水线时满足依赖约束的基本块集，令依赖满足池的初值为空集；
151.定义一个基本块集——约束满足池，约束满足池的含义是依赖满足池中排布到第n级流水线时满足资源约束的基本块集，令约束满足池的初值为空集；
152.定义num
p
行num
p
列的dependence矩阵，其中dependence矩阵的含义是：当dependence
ij
为0时表示当前将基本块j排布到第n级流水线是满足与基本块i的依赖约束的，当dependence
ij
不为0时表示当前将基本块j排布到第n级流水线是不满足与基本块i的
依赖约束的；令dependence矩阵的初值为零矩阵；
153.计算num
p
维rely向量，其中rely向量的含义是：relyi为在基本块i执行后才能执行的基本块总数；计算方法为对向量中每个元素按照如下方法赋值：
154.步骤7.2、更新dependence矩阵：
155.令dependence＝control+datawr+datarw+dataww；
156.步骤7.3、更新依赖满足池：
157.令依赖满足池为空集，遍历所有满足的i，若基本块i是待分配池的元素，则将基本块i加入依赖满足池，这样完成i的遍历后就完成了依赖满足池的更新；
158.步骤7.4、更新约束满足池：
159.令约束满足池为空集，遍历依赖满足池的基本块，判断将该基本块排布到第n级流水线是否满足资源约束，若是，则将该基本块加入约束满足池，这样完成依赖满足池的基本块遍历后就完成了约束满足池的更新；
160.步骤7.5、排布基本块：
161.若约束满足池为空集，则在arrangement矩阵的最右侧新增一列零元素，遍历满足arrangement
in
＝1的所有i，令datawr矩阵、dataww矩阵的第i行元素全部为0，这样完成i的遍历后，令n取n+1；
162.若约束满足池不为空集，则找到约束满足池中基本块对应的rely值最大的所有基本块，若只有一个则直接记为基本块i，若有多个则任选其一记为基本块i，令arrangement
in
＝1，令control矩阵、datarw矩阵的第i行元素全部为0，将基本块i从待分配池中移除；
163.步骤7.6、判断是否完成arrangement矩阵的计算：
164.若待分配池不为空集，则返回步骤7.2，否则意味着完成了arrangement矩阵的计算。
165.如图2所示为所述基本块排布子程序中基本块排布方法示意图。
166.在完成所有基本块的排布后，可以通过计算结果优度对计算结果进行大致评价，所述结果优度为一个取值范围为(0,1]的评价指标，数值越大表示基本块排布结果越好，计算方法为：
167.步骤a、计算road矩阵
168.计算num
p
行num
p
列的road矩阵，road矩阵用来确定满足数据依赖、控制依赖而不考虑资源约束的情况下所有基本块占用流水线级数的理论最小值，计算方法为对矩阵中每个元素按照如下方法赋值：
169.对于road
ij
，若步骤6计算出的datawr
ij
为1或步骤6计算出的dataww
ij
为1，则令road
ij
取-1，
170.否则，若i＝j或步骤5最终计算出的control
ij
为1或步骤6计算出的datarw
ij
为1，则令road
ij
取0，
171.否则，令road
ij
取∞；
172.步骤b、计算distance矩阵：
173.根据road矩阵，利用图论中的floyd算法，求解num
p
行num
p
列的distance矩阵，distance矩阵的含义是，对于一个以road矩阵为加权邻接矩阵的图，图中任意节点i至任意节点j的最短距离为distance
ij
；
174.步骤c、计算结果优度：
175.所述理论最小值为记为value
min
，所述结果优度为
176.floyd算法为图论的最短路径算法之一，可以根据图的加权邻接矩阵求解该图中任意节点至任意节点的最短路径及最短距离，floyd算法为已有公开内容，不是本发明的创造内容，在此不再赘述。
177.接下来通过一个简单的算例对本发明的方法进行展示。
178.已知某芯片每级流水线可提供tcam资源的最大数量为1，目前已将源程序划分为1至4共四个基本块，其中，基本块2、基本块4各占用1个tcam资源，基本块1、基本块3不占用tcam资源。源程序读写的变量为1至3共三个变量，基本块1会对变量1进行写操作，基本块2会对变量2进行写操作、对变量1进行读操作，基本块3会对变量3进行写操作、对变量1进行读操作，基本块4不读写任何变量。此外，如图3所示为源程序基本块的执行流程图，由此可见，基本块1的邻接基本块为基本块2、基本块3，基本块2的邻接基本块为基本块4，基本块3的邻接基本块为基本块4，基本块4没有邻接基本块。
179.以上内容为使用本发明提供了充足的已知条件，接下来展示计算中的关键过程。
180.执行步骤1得：
181.执行步骤2得：
182.执行步骤3得：
183.执行步骤4得：degree＝[2 1 1 0]。
[0184]
执行步骤5得：
[0185]
执行步骤6得：执行步骤6得：
[0186]
执行步骤7.1得：待分配池有基本块1、2、3、4，n＝1，rely＝[3 1 1 0]，
[0187]
执行步骤7.2得：执行步骤7.3得：依赖满足池有基本块1、4。
[0188]
执行步骤7.4得：约束满足池有基本块1、4。
[0189]
执行步骤7.5得：约束满足池中基本块对应的rely值最大的基本块为基本块1，待分配池有基本块2、3、4。
[0190]
执行步骤7.6，返回步骤7.2，执行步骤7.2得：执行步骤7.3得：依赖满足池有基本块4。
[0191]
执行步骤7.4得：约束满足池有基本块4。
[0192]
执行步骤7.5得：约束满足池中基本块对应的rely值最大的基本块为基本块4，待分配池有基本块2、3。
[0193]
执行步骤7.6，返回步骤7.2，执行步骤7.2得：执行步骤7.3得：依赖满足池为空集。
[0194]
执行步骤7.4得：约束满足池为空集。
[0195]
执行步骤7.5得：执行步骤7.6，返回步骤7.2，执行步骤7.2得：
[0196]
执行步骤7.3得：依赖满足池有基本块2、3。
[0197]
执行步骤7.4得：约束满足池有基本块2、3。
[0198]
执行步骤7.5得：约束满足池中基本块对应的rely值最大的基本块为基本块2、3，任选其一即可，不妨取基本块2，待分配池有基本块3。
[0199]
执行步骤7.6，返回步骤7.2，执行步骤7.2、7.3，得：依赖满足池有基本块3。
[0200]
执行步骤7.4得：约束满足池有基本块3。
[0201]
执行步骤7.5得：约束满足池中基本块对应的rely值最大的基本块为基本块3，依赖满足池为空集。
[0202]
执行步骤7.6得：arrangement矩阵的计算已经完成，num
l
＝2，即所有基本块所占用的流水线级数为2，其中，基本块1、4占用流水线第1级，基本块2、3占用流水线第2级，即得到如图4所示的排布结果。
[0203]
如果直接按照执行流程图进行基本块排布，将得到如图5所示的结果，即基本块1占用流水线第1级，基本块2、3占用流水线第2级，基本块4占用流水线第3级，也是满足各约束条件的。但是，如果使用本发明进行基本块排布，则可以减少1级流水线占用。
[0204]
此外，可以通过计算结果优度对计算结果进行大致评价，执行步骤a得
执行步骤b得执行步骤c得结果优度为由结果优度的定义可知，本次计算结果对于算例而言达到了理论最优水平，占用更少流水线级数是不可能的。
[0205]
上述算例只是为了便于解释发明内容所举的一个非常简单的例子，实际上，本发明可以应用到非常复杂的场景中。经过实际测试，本发明在普通微型计算机上，处理数百个基本块、变量的复杂问题时，仅需数秒即可完成求解，且能够保持较好的结果优度。

技术特征：
1.一种应用于pisa架构芯片的基本块排布方法，其特征在于：包括如下步骤：步骤1、读写变量描述：记基本块总数为num
p
，记变量总数为num
v
，根据各个基本块所读写的变量，计算num
p
行num
v
列的write矩阵和read矩阵，其中write矩阵用来描述各基本块与各变量之间是否存在写操作的关系，read矩阵用来描述各基本块与各变量之间是否存在读操作的关系，计算方法为对矩阵中每个元素按照如下方法分别赋值：对于元素write
ij
，若基本块i对变量j进行写操作，则令write
ij
为1，否则令write
ij
为0，对于元素read
ij
，若基本块i对变量j进行读操作，则令read
ij
为1，否则令read
ij
为0；步骤2、邻接信息描述：根据各个基本块的邻接基本块，计算num
p
行num
p
列的connect矩阵，其中connect矩阵用来描述各基本块的邻接基本块信息，计算方法为对矩阵中每个元素按照如下方法赋值：对于元素connect
ij
，若基本块j是基本块i的邻接基本块，则令connect
ij
为1，否则令connect
ij
为0；步骤3、基本块顺序求解：根据connect矩阵，调用顺序求解子程序，求解num
p
行num
p
列的order矩阵，其中order矩阵的含义是：当order
ij
为1时表示基本块i在基本块j前执行，当order
ij
为0时表示基本块i不在基本块j前执行；步骤4、基本块度的求解：根据connect矩阵，计算num
p
维degree向量，其中degree向量用来描述各基本块的邻接基本块总数，计算方法为对向量中每个元素按照如下方法赋值：对于元素degree
i
，令degree
i
等于基本块i的邻接基本块总数；步骤5、控制依赖求解：建立一个num
p
行num
p
列的control矩阵，令其初值为零矩阵，遍历每一个满足degree
i
大于1的i，令基本块i为当前父基本块，根据connect矩阵、order矩阵、degree向量、当前父基本块，调用控制依赖求解子程序，更新control矩阵，这样完成i的遍历后，就完成了control矩阵的求解，其中control矩阵的含义是：当control
ij
为1时表示基本块j控制依赖于基本块i，当control
ij
为0时表示基本块j不控制依赖于基本块i；步骤6、数据依赖求解：根据order矩阵、write矩阵和read矩阵，调用数据依赖求解子程序，计算num
p
行num
p
列的datawr矩阵、datarw矩阵和dataww矩阵，其中datawr矩阵、datarw矩阵和dataww矩阵的含义分别是：当datawr
ij
＝1时表示基本块j写后读依赖于基本块i，当datawr
ij
＝0时表示基本块j不写后读依赖于基本块i，当datarw
ij
＝1时表示基本块j读后写依赖于基本块i，当datarw
ij
＝0时表示基本块j不读后写依赖于基本块i，当dataww
ij
＝1时表示基本块j写后写依赖于基本块i，当dataww
ij
＝0时表示基本块j不写后写依赖于基本块i；
步骤7、基本块排布：根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵，令arrangement矩阵取初值为num
p
行1列的零矩阵，调用基本块排布子程序，计算arrangement矩阵，其中arrangement矩阵的含义是：当arrangement
ij
＝1时表示基本块i排布到第j级流水线，当arrangement
ij
＝0时表示基本块i不排布到第j级流水线；arrangement矩阵完成计算后，就意味着完成了所有基本块的排布，arrangement矩阵的列数就是所有基本块所占用的流水线级数，记为num
l
，对于任意一个基本块i，它所在的流水线级数为满足arrangement
ij
＝1的j。2.根据权利要求1所述的一种应用于pisa架构芯片的基本块排布方法，其特征在于：所述顺序求解子程序，是一个根据connect矩阵求解order矩阵的方法，包括如下步骤：步骤3.1、为order矩阵赋初值：令order矩阵等于connect矩阵；步骤3.2、记录当前order矩阵数值：定义num
p
行num
p
列的oldorder矩阵，其中oldorder矩阵用来记录order矩阵更新前的数值，令oldorder矩阵等于order矩阵；步骤3.3、更新order矩阵：遍历order矩阵的行号i，在order矩阵第i列中找到所有取值为1的元素，记这些元素的行号组成的集合为front，其中front的含义是目前确定的在基本块i前执行的基本块集合，在order矩阵第i行中找到所有取值为1的元素，记这些元素的列号组成的集合为rear，其中rear的含义是目前确定的在基本块i后执行的基本块集合，这样完成行号i的遍历后，遍历j∈front,k∈rear所有(j,k)组合，令order
jk
＝1，这样完成(j,k)的遍历后，就完成了order矩阵的更新；步骤3.4、判断order矩阵是否计算完成：判断order矩阵与oldorder矩阵是否相等，若不相等，则返回步骤3.2；若相等，则order矩阵计算完成。3.根据权利要求1所述的一种应用于pisa架构芯片的基本块排布方法，其特征在于：所述控制依赖求解子程序，是一个根据connect矩阵、order矩阵、degree向量对当前父基本块更新control矩阵的方法，包括如下步骤：步骤5.1、数据初始化：定义num
p
维power向量，该向量最终会用来判断哪些基本块控制依赖于当前父基本块，令power向量的初值为零向量；记当前父基本块为基本块c；定义一个基本块集——待分权集，待分权集的含义是，其中的基本块对应的power值不为0但尚未将其power值平均分配给其邻接基本块，令待分权集的初值取为基本块c的邻接基本块集合；定义变量d，该变量用来记录选择哪一个基本块来分配其power值；遍历待分权集的基本块i，令这样完成基本块i的遍历后，就完成了数据初始化；步骤5.2、选择待分配的基本块：遍历待分权集的基本块i，计算直至为零时停止遍历，然
后令d取i；步骤5.3、分配power值：遍历满足connect
di
＝1的所有i，令若基本块i不在待分权集中，则将基本块i加入待分权集，这样完成i的遍历后，将基本块d从待分权集中移除；步骤5.4、判断power向量是否完成计算：若待分权集不为空集且power向量中最大的元素不为1，则返回步骤5.2，否则说明power向量已完成计算；步骤5.5、更新control矩阵：遍历满足power
i
>0且power
i
<1的所有i，令control
ci
为1，这样完成i的遍历后，就完成了control矩阵的更新。4.根据权利要求1所述的一种应用于pisa架构芯片的基本块排布方法，其特征在于：所述数据依赖求解子程序，是一个根据order矩阵、write矩阵和read矩阵计算datawr矩阵、datarw矩阵、dataww矩阵的方法，该方法对矩阵中每个元素按照如下方法赋值：对于datawr
ij
，若order
ij
＝1且则令datawr
ij
为1，否则令datawr
ij
为0，对于datarw
ij
，若order
ij
＝1且则令datarw
ij
为1，否则令datarw
ij
为0，对于dataww
ij
，若order
ij
＝1且则令dataww
ij
为1，否则令dataww
ij
为0。5.根据权利要求1所述的一种应用于pisa架构芯片的基本块排布方法，其特征在于：所述基本块排布子程序，是一个根据order矩阵、control矩阵、datawr矩阵、datarw矩阵、dataww矩阵计算arrangement矩阵的方法，包括如下步骤：步骤7.1、基本块排布初始化：定义变量n，n的含义是当前正在将基本块向第n级流水线排布，令n取初值1；定义一个基本块集——待分配池，待分配池的含义是当前所有尚未完成排布的基本块的集合，令待分配池的初值为所有基本块的集合；定义一个基本块集——依赖满足池，依赖满足池的含义是待分配池中排布到第n级流水线时满足依赖约束的基本块集，令依赖满足池的初值为空集；定义一个基本块集——约束满足池，约束满足池的含义是依赖满足池中排布到第n级流水线时满足资源约束的基本块集，令约束满足池的初值为空集；定义num
p
行num
p
列的dependence矩阵，其中dependence矩阵的含义是：当dependence
ij
为0时表示当前将基本块j排布到第n级流水线是满足与基本块i的依赖约束的，当dependence
ij
不为0时表示当前将基本块j排布到第n级流水线是不满足与基本块i的依赖约束的；令dependence矩阵的初值为零矩阵；
计算num
p
维rely向量，其中rely向量的含义是：rely
i
为在基本块i执行后才能执行的基本块总数；计算方法为对向量中每个元素按照如下方法赋值：步骤7.2、更新dependence矩阵：令dependence＝control+datawr+datarw+dataww；步骤7.3、更新依赖满足池：令依赖满足池为空集，遍历所有满足的i，若基本块i是待分配池的元素，则将基本块i加入依赖满足池，这样完成i的遍历后就完成了依赖满足池的更新；步骤7.4、更新约束满足池：令约束满足池为空集，遍历依赖满足池的基本块，判断将该基本块排布到第n级流水线是否满足资源约束，若是，则将该基本块加入约束满足池，这样完成依赖满足池的基本块遍历后就完成了约束满足池的更新；步骤7.5、排布基本块：若约束满足池为空集，则在arrangement矩阵的最右侧新增一列零元素，遍历满足arrangement
in
＝1的所有i，令datawr矩阵、dataww矩阵的第i行元素全部为0，这样完成i的遍历后，令n取n+1；若约束满足池不为空集，则找到约束满足池中基本块对应的rely值最大的所有基本块，若只有一个则直接记为基本块i，若有多个则任选其一记为基本块i，令arrangement
in
＝1，令control矩阵、datarw矩阵的第i行元素全部为0，将基本块i从待分配池中移除；步骤7.6、判断是否完成arrangement矩阵的计算：若待分配池不为空集，则返回步骤7.2，否则意味着完成了arrangement矩阵的计算。6.根据权利要求1所述的一种应用于pisa架构芯片的基本块排布方法，其特征在于：在完成所有基本块的排布后，可以通过计算结果优度对计算结果进行大致评价，所述结果优度为一个取值范围为(0,1]的评价指标，数值越大表示基本块排布结果越好，计算方法为：步骤a、计算road矩阵计算num
p
行num
p
列的road矩阵，road矩阵用来确定满足数据依赖、控制依赖而不考虑资源约束的情况下所有基本块占用流水线级数的理论最小值，计算方法为对矩阵中每个元素按照如下方法赋值：对于road
ij
，若步骤6计算出的datawr
ij
为1或步骤6计算出的dataww
ij
为1，则令road
ij
取-1，否则，若i＝j或步骤5最终计算出的control
ij
为1或步骤6计算出的datarw
ij
为1，则令road
ij
取0，否则，令road
ij
取∞；步骤b、计算distance矩阵：根据road矩阵，利用图论中的floyd算法，求解num
p
行num
p
列的distance矩阵，distance矩阵的含义是，对于一个以road矩阵为加权邻接矩阵的图，图中任意节点i至任意节点j的最短距离为distance
ij
；
步骤c、计算结果优度：所述理论最小值为记为value
min
，所述结果优度为

技术总结
本发明涉及芯片编译领域，公开了一种应用于PISA架构芯片的基本块排布方法，包括如下步骤：步骤1、读写变量描述；步骤2、邻接信息描述；步骤3、基本块顺序求解；步骤4、基本块度的求解；步骤5、控制依赖求解；步骤6、数据依赖求解；步骤7、基本块排布。本发明还公开了一种结果评价方法，在完成所有基本块的排布后，可以通过计算结果优度对计算结果进行大致评价。本发明可以在满足控制依赖、数据依赖、资源约束的条件下，利用相对较少的流水线级数完成基本块排布，从而提升芯片的资源利用率，更好地发挥芯片的能力。片的能力。片的能力。


技术研发人员：王军年 曹宇靖 许汇鑫 郑天惠
受保护的技术使用者：吉林大学
技术研发日：2023.03.31
技术公布日：2023/8/4