基于贪心的可重构阵列优化算法性能研究

黄式东　刘勇　姚建峰　薛瑞

摘要：可重构阵列通过重构的方式实现其高容错能力，不同的重构方案对其性能有着重要的影响。该文基于贪心算法的应用，针对可重构电路的重构优化问题，实现了基于贪心思想的重构优化算法，并与同步优化算法在性能上进行了对比。实验表明，基于贪心的重构优化算法在性能上具有一定的优势。

关键词：可重构阵列；贪心；优化算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）13-0091-02

1概述

传统的计算方式有两种，一种是采用对通用微处理器进行软件编程的方式；一种是采用ASIC的方式。软件编程的方式通用性好，但运算速度不高；ASIC方式处理速度快，但只能针对特定的应用，通用性不好。可重构计算（reconfigurable eom-puting）是以上两种求算方式的一种折中。这种求算方式是通过对结构可变的硬件进行软件配置，以适应不同的应用需求，故其既具有了软件的灵活性，又具备了ASIC硬件的高速性。可重构计算的思想最早由加利福尼亚大学洛杉矶分校的Estrin教授在其论文中提出。当时的计算机还是电子管计算机，电子存储器也刚刚出现，计算机处理速度很慢，存储容量也很小，因此许多算法是当时通用计算机所不能解决的。为了解决这些受限计算问题，其第一次提出了可重构计算的思想，即设计一种可变的计算机体系结构，通过特定的指令集配置，该计算机结构可变为针对特定算法的专用计算机结构。

刚开始可重构设备是作为板路逻辑使用的，随着发展，现在的可重构硬件以不同的粒度出现在系统中，尤其是在片上系统中的使用越来越多了。主要是因为可重构硬件的能够提供弹性的功能，能够减少设计开销和投向市场的时间，并且在容错方面有着更好的特性。主要的应用在Software-defined ra-dio，医学图形图像处理，网络处理器，加解密M，科研数据获取和处理，航天飞行器，机器人，汽车电子，图像视屏处理设备等。除了这些特定领域的一些应用，现在可重构计算技术在通用计算领域的应用也变得越来越广泛。因为计算技术在人们生活中各个方面的渗透正在逐步的深入并在深刻地改变着人们的生活方式，同时也产了大量数据，为了支持计算技术进一步的方便人们的生活和处理这些海量信息，云计算技术在此背景下产生了。云计算技术中很多都使用了虚拟技术，如Ama—zon的EC2、微软的Azure等。但虚拟技术同时带来了性能的损失，云计算需要寻找新的出路一高效能，但是高效能的必然之路是体系结构的创新。邬江兴院士在此背景下提出了基于认知的计算机体系结构PRCA，该体系结构使用的关键技术就是可重构计算技术。按照不同的划分标准，可重构系统可以划分为不同的类型。按照重构的方式划分可以分为静态重构和动态重构；按照与主处理器的耦合关系划分可以分为紧耦合重构和松耦合重构；按照重构的粒度划分可以分为细粒度重构和粗粒度重构。当然针对每种划分方式也可以划分的更细，如按照重构粒度又可以划分为电路级可重构、芯片级可重构、处理核级别的可重构和节点级别的可重构。电路级别的可重构是从基本门级别人手的重构，计算系统将功能部件的逻辑用FP-GA实现，当应用算法改变时，通过改变FPGA的配置来改变其功能，这种重构也称为门级别可重构。部件级可重构是从功能部件如手，通过对功能部件的重新组合来適应不同的计算需求。核级别可重构在标准处理器单元的基础上增加一些计算设备，为通用计算提供特殊的计算支持，以实现大计算量指令和子程序的执行；或者是在多核互连的基础上，使处理器位数可变、处理器的个数可变或处理器间互连结构可变以达到重构的目的。节点级别的可重构是在多节点互连的基础上，使节点的个数和互联结构可变以达到重构的目的。

对于电路级可重构，不同的重构方案对计算性能有着重要的影响。原始物理阵列是一个4x5的阵列，如图1所示，图中的方格表示重构单元，实心圆点表示开关，重构单元之间通过线路和开关实现互通互联。为了方便描述问题，此处省略了重构单元之间的部分连线。现对开关出现的位置信息进行编号，即行号，如图1中1，2，3；重构单元之间只经过一个开关的连接称为短连接，经过两个开关的连接称为长连接，如图1中x1，x2，x3。如果两个重构单元之间通过短连接进行互联，那么它们之间的通信时间要比通过长连接实现互联的重构单元之间的通信时间要短，假设一个长连接比短连接多1个通信延迟，如果按照图1中的重构方案，因为3个长连接x1，x2，x3分别出现在不同的行中，这样会造成增加3个通信延迟；如果按照图2中的重构方案，因为3个长连接x1，x2，x3都出现在同一行，最终造成只增加1个通信延迟。当阵列规模很大时，可见不同的重构方案会造成很大的性能差异。现有多个长连接可以出现在多个位置（这里用行号表示）上，那么最终这些长连接如何分布，才能使电路性能达到最优。关于贪心算法及其应用，杨书影在文献中进行了阐述；Chor Ping Low在文献中介绍了贪心思想在可重构电路优化方面的应用。张元瑞，武继刚等人针对可重构电路的优化问题，提出了同步优化算法；本文在同步算法问题表述形式的基础上，采用贪心的优化思想，实现可重构电路的优化算法，然后在性能上与同步优化算法进行了比较，发现基于贪心的优化算法在速性能上具有一定的优势。

2基于贪心重构优化算法

算法描述如下：

Algorithm Greed_OPT；/*贪心优化算法。/

输入：每个长连接及其分布情况；

输出：优化后长连接的分布情况；

Begin

（1）根据输入，统计每个位置（行号）总共出现的次数；

（2）选取出现次数最多的行号；

（3）找出哪些长连接的位置包含该行号；如果包含，则把该长连接的最终位置记为该行号，然后在输入中删除该长连接及其分布信息，更新输入后，转到步骤（1），直到输入中所有的长连接都被删除，算法终止。

End

为了具体说明算法执行过程，现举例如下。现有长连接{[X1]（2，3，4），[X2]（7，8），[X3]（4，5，6），[X4]（5，6，7），[X5]（4，5，6），[X6]（6，7，8）]，它们的具体分布情况如图3所示。统计每个行号出现的次数，得到{1行→0次；2行→1次；3行→1次；4行→3次；5行→3次；6行→4次；7行→3次；8行→2次1。发现第6行出现的次数最多，然后把包含6的长连接在输入中删除，它们是[X3]（4，5，6），[X4]（5，6，7），[X5]（4，5，6），[X6]（6，7，8），刪除后新的输入情况是{[X1]（2，3，4），[X2]（7，8）}；在新的输入基础上统计每个行号出现的次数，得到{1行+0次，2行→1次；3行→1次；4行→1次；5行→0次；6行→0次；7行→1次；8行→1次1；从中选取出现次数最大的为第2行（出现次数相同时，选择行号最小的），删除包含第2行的长连接[X1]（2，3，4），然后更新当前的输入，得到{[X2]（7，8）}；重复执行上述过程，直到所有的长连接都被删除，算法结束。采用贪心优化算法，长连接的最终分布情况如图4所示，表示为[X3，X4，x5，x6]（6），[X1]（2），[X2]（7）。

采用同步优化算法na得到的最终分布情况是[X1，X3，X5]（4），[X2，X4，X6]（7）。长连接只需要分布在两个不同的行中，是本实例的一个最优解。

3实验结果说明

测试机器处理器配置为4核Intel（R）Core（TM）i3-3240，内存8GB，Windos7操作系统，在此平台下进行的测试。总的可重构单元数为1千万，分别比较了贪心优化算法和同步优化算法在长连接个数为10万、20万、30万、40万、50万时的性能，结果如图5所示。结果表明贪心算法在速度上有明显的优势。从图5可以看出，随着长连接数目的增加，优化算法所花费的时间基本上成线性增长，说明实验结果能够真实地反映实际情况。

4结束语

本文针对可重构电路的优化问题，详细介绍了基于贪心的可重构优化算法，并与同步优化算法做了性能比较，实验结果说明基于贪心的优化算法在性能上有明显的优势，但是基于贪心的优化算法得到长连接的最终分布情况不一定是最优的。基于同步优化算法得到长连接的最终分布情况是最优的，但是在速度上没有贪心优化算法快。同时本文给出的优化实例，只涉及了长连接的纵向移动，没考虑长连接的横向移动情况；拟计划做进一步研究，同时还可以利用其他的优化算法来解决重构电路的重构优化问题。