改进启发式算法求解PISA架构芯片资源排布问题

Improved Heuristic Algorithm to Solve Resource Allocation Problem of PISA Architecture Chip

摘要: 在PISA架构设计时，为减少连线复杂度，往往对流水线各级资源以及各级流水线资源有多种多样约束，研究高资源利用率的资源排布算法对编译器设计尤为重要。论文从资源排布的PISA架构资源约束、流图中基本块约束出发，建立单目标整数规划模型，设计并改进启发式算法并设计近似单调队列求解模型。实验结果表明改进的启发式算法有效降低PISA资源排布方案的复杂度的同时提升了资源利用率。针对两个具体的资源排布问题，给出最小流水层数为59级与35级的资源排布方案，相比基于规则的启发式算法分别降低了21层与15层，验证了算法的有效性与稳定性。

Abstract: In the design of PISA architecture, in order to reduce the complexity of connections, there are often various constraints on the resources at all levels of the pipeline, as well as on the resources at all levels of the pipeline. Therefore, studying resource allocation algorithms with high resource utilization is particularly important for compiler design. Starting from the resource constraints of the PISA architecture for resource allocation and the basic block constraints in the flow graph, the paper establishes a single objective integer programming model, designs and improves heuristic algorithms, and designs an approximate monotonic queue solving model. The experimental results show that the improved heuristic algorithm effectively reduces the complexity of PISA resource layout schemes while improving resource utilization. For two specific resource allocation problems, a resource allocation scheme with a minimum number of flow layers of 59 and 35 is proposed. Compared with rule-based heuristic algorithms, it reduces 21 and 15 layers respectively, verifying the effectiveness and stability of the algorithm.