基于量子蚁群算法的片上网络映射研究.pdfVIP

第３４卷第１ 期 计 算 机 应 用 研 究 Ｖｏｌ．３４Ｎｏ．１ ２０１７年１ 月 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｊａｎ．２０１７ 基于量子蚁群算法的片上网络映射研究 范绍聪，刘怡俊 （广东工业大学计算机学院，广州５１０００６） 摘 要：随着片上网络的兴起和发展，针对带宽和时延约束下实现低功耗成为其设计的焦点之一。为此，提出 一种基于量子蚁群映射算法的方法来解决片上网络设计中使ＩＰ核映射的通信功耗最小化问题。该算法改变蚁 群算法中信息素的释放方式，采用量子优化算法中的量子概率幅代替，信息素的更新则通过使用量子相位旋转 的方式，实现蚂蚁信息素的自适应更新，用于有效地降低蚁群算法容易早熟收敛的情况。通过实验对比研究，该 算法在快速有哪些信誉好的足球投注网站和全局寻优能力上，均优于蚁群算法。 关键词：片上网络；低功耗；量子蚁群算法；量子旋转门；自适应相位 中图分类号：ＴＰ３９３．０３ 文献标志码：Ａ 文章编号：１００１ ３６９５（２０１７）０１ ０１５６ ０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ２０１７．０１．０３３ ＲｅｓｅａｒｃｈｏｎＮｏＣｍａｐｐｉｎｇｂａｓｅｄｏｎｑｕａｎｔｕｍａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ ＦａｎＳｈａｏｃｏｎｇ，ＬｉｕＹｉｊｕｎ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，ＧｕａｎｇｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ５１０００６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｉｎｇｏｆｎｅｔｗｏｒｋｓｏｎｃｈｉｐ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｂａｎｄｗｉｄｔｈａｎｄｄｅｌａｙｃｏｎｓｔｒａｉｎｔｓｔｏａｃｈｉｅｖｅｌｏｗｐｏｗｅｒ ｃｏｎｓｕｍｐｔｉｏｎｈａｄｂｅｃｏｍｅｏｎｅｏｆｔｈｅｈｏｔｓｐｏｔｓｏｆｔｈｅｄｅｓｉｇｎ．Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｅｄａｑｕａｎｔｕｍａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ （ＱＡＣＡ） ｓｔｒａｔｅｇｙｔｏｍａｐａｐｐｌｉｃａｔｉｏｎｓｏｎｎｅｔｗｏｒｋｓｏｎｃｈｉｐ．ＴｈｉｓＱＡＣＡｕｓｅｄｑｕａｎｔｕｍｂｉｔｉｎｑｕａｎｔｕｍｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｔｏｒｅｐｌａｃｅ ｔｈｅａｎｔｃｏｌｏｎｙｐｈｅｒｏｍｏｎｅ．Ｂａｓｅｄｏｎｔｈｅａｄａｐｔｉｖｅｐｈａｓｅｒｏｔａｔｉｏｎｓｔｒａｔｅｇｙ，ｉｔｍａｄｅｔｈｅｐｈｅｒｏｍｏｎｅｕｐｄａｔｅｄｙｎａｍｉｃａｌｌｙｔｏｒｅｄｕｃｅ ｔｈｅｐｒｅｍａｔｕｒｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｅｆｆｅｃｔｉｖｅｌｙ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｂｅｔ ｔｅｒｔｈａｎｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｂｏｔｈａｔｔｈｅａｂｉｌｉｔｙｏｆｓｅａｒｃｈｃａｐａｂｉｌｉｔｙａｎｄｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎ． Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｓｏｎｃｈｉｐ（ＮｏＣ）；ｌｏｗｐｏｗｅｒ；ｑｕａｎｔｕｍａｎｔａｌｇｏｒｉｔｈｍ；ｑｕａｎｔｕｍｒｏｔａｔｉｏｎｇａｔｅ；ａｄａｐｔｉｖｅｐｈａｓｅ 呈现阶乘性的递增，因此ＩＰ核映射是一个ＮＰ难问题。对有ｎ 引言 个ＩＰ核的系统，有着ｎ！种不同的映射方式，可知图１ 一共有９ 随着硬件工艺技术的发展，片上系统的集成度越来越高， 的阶乘种映射结果。因此设计使用映射算法在有限的迭代次 片上系统（ＳｏＣ）因总线带宽的限制和系统ＩＰ核数的增多，使 数下得到映射的近似最优解，是解决 ＩＰ 核映射的主要方法。 得其需要更好的通信方式来代替。而片上网络（ＮｏＣ）的出现 目前已经有不少国内外