多选择软硬件划分问题的启发式算法比较-计算机应用与软件.pdf

第３２卷第２期　　　 计算机应用与软件 Ｖｏｌ３２Ｎｏ．２ ２０１５年２月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｆｅｂ．２０１５ 多选择软硬件划分问题的启发式算法比较 朱峰军　武继刚　宋庆增 （天津工业大学计算机科学与软件学院　天津３００３８７） 摘　要　　软硬件协同设计作为嵌入式系统开发的重要技术，随着嵌入式系统的广泛应用变得越来越重要。软硬件划分是软硬件 协同设计的关键环节，是经典的组合优化问题，已被证明是ＮＰ完全问题。对于一个给定的任务而言，由于在硬件实现中存在并行 执行的潜力，具有不同面积的硬件可以提供不同的执行速度。这样，一个任务根据可利用的硬件面积可以有多种硬件实现方式。现 有的软硬件划分方法通常仅仅考虑单一的硬件实现方式，却忽略了多种选择的硬件实现方式。对于多选择的软硬件划分问题，分别 使用模拟退火算法和遗传算法，提出了可行性的解决方案。并与禁忌有哪些信誉好的足球投注网站算法进行比较，寻找多选择软硬件划分问题的相对较好的 启发式算法。实验结果表明，在求得的解的质量方面，禁忌有哪些信誉好的足球投注网站算法相比于其他两种算法而言是最好的；在获得较好解的速度方面， 模拟退火算法和遗传算法要比禁忌有哪些信誉好的足球投注网站算法快得多。 关键词　　多选择软硬件划分　模拟退火　遗传算法　禁忌有哪些信誉好的足球投注网站 中图分类号　ＴＰ３　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１５．０２．０５３ ＨＥＵＲＩＳＴＩＣＡＬＧＯＲＩＴＨＭＳＣＯＭＰＡＲＩＳＯＮＳＦＯＲ ＭＵＬＴＩＰＬＥＣＨＯＩＣＥＨＡＲＤＷＡＲＥ／ＳＯＦＴＷＡＲＥＰＡＲＴＩＴＩＯＮＩＮＧ ＺｈｕＦｅｎｇｊｕｎ　ＷｕＪｉｇａｎｇ　ＳｏｎｇＱｉｎｇｚｅｎｇ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＳｏｆｔｗａｒｅ，ＴｉａｎｊｉｎＰｏｌｙｔｅｃｈｎｉｃＵｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ３００３８７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ａｓｔｈｅｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｑｕｅｏｆｅｍｂｅｄｄｅｄｓｙｓｔｅｍｄｅｖｅｌｏｐｍｅｎｔ，ｈａｒｄｗａｒｅ／ｓｏｆｔｗａｒｅ（ＨＷ／ＳＷ）ｃｏｄｅｓｉｇｎｉｓｂｅｃｏｍｉｎｇ ｉｎｃｒｅａｓｉｎｇｌｙｉｍｐｏｒｔａｎｔａｌｏｎｇｗｉｔｈｔｈｅｗｉｄｅｓｐｒｅａｄａｐｐｌｉｃａｔｉｏｎｓｏｆｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ．Ｈａｒｄｗａｒｅ／ｓｏｆｔｗａｒｅｐａｒｔｉｔｉｏｎｉｎｇｉｓｔｈｅｃｒｕｃｉａｌｓｔｅｐｉｎＨＷ／ ＳＷｃｏｄｅｓｉｇｎ，ａｎｄｉｓａｃｌａｓｓｉｃｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｓａｔｉｏｎｐｒｏｂｌｅｍａｓｗｅｌｌ，ｈａｓｂｅｅｎｐｒｏｖｅｎｔｏｂｅｔｈｅＮＰｃｏｍｐｌｅｔｅ．Ｆｏｒａｇｉｖｅｎｔａｓｋ， ｈａｒｄｗａｒｅｗｉｔｈｄｉｆｆｅｒｅｎｔａｒｅａｓｍａｙｐｒｏｖｉｄｅｄｉｆｆｅｒｅｎｔｅｘｅｃｕｔｉｏｎｓｐｅｅｄｓｄｕｅｔｏｔｈｅｐｏｔｅｎｔｉａｌｏｆｐａｒａｌｌｅｌｅｘｅｃｕｔｉｏｎｉｎｉｔｓｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｔｈｕｓ，ｏｎｅ ｔａｓｋｍａｙｈａｖｅｍｕｌｔｉｐｌｅｃｈｏｉｃｅｉｎｈａｒｄｗａｒｅｉｍｐｌｅｍｅｎｔａｔｉｏｎａｃｃｏｒｄｉｎｇｔｏｔｈｅａｖａｉｌａｂｌｅｈａｒｄｗａｒｅａｒｅａｓ．ＥｘｉｓｔｉｎｇＨＷ／ＳＷ ｐａｒｔｉｔｉｏｎｉｎｇ ａｐｐｒｏａｃｈｅｓｕｓｕａｌｌｙｏｎｌｙｃｏｎｓｉｄｅｒａｓｉｎｇｌｅｈａｒｄｗａｒｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｍａｎｎｅｒ，ｂｕｔｏｖｅｒｌｏｏｋｔｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｍｅａｎｓｗｉｔｈｍｕｌｔｉｐｌｅｃｈｏｉｃｅ．Ｆｏｒ ｔｈｅＨＷ／ＳＷｐａｒｔｉｔｉｏｎｉｎｇｐｒｏｂｌｅｍｗｉｔｈｍｕｌｔｉｐｌｅｃｈｏｉｃｅ，ｉｎｔｈｉｓｐａｐｅｒｗｅｐｒｅｓｅｎｔｔｈｅｓｏｌｕｔｉｏｎｓｗｉｔｈｆｅａｓｉｂｉｌｉｔｙｂｙｕｓｉｎｇｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｒｅｓｐｅｃｔｉｖｅｌｙ．Ｍｏｒｅｏｖｅｒ，ｔｈｅｙａｒｅｃｏｍｐａｒｅｄｗｉｔｈｔａｂｕｓｅａｒｃｈａｌｇｏ