考虑任务不确定性的片上网络鲁棒性应用映射问题研究

Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks

标准应用映射问题中,每个任务的通信量是确定值,而实际应用中任务通信具有突发性和时变特征,因此将任务通信量建模为不确定值具有现实意义。该文利用区间流法对任务不确定性进行描述,基于保守因子对鲁棒性应用映射问题建模,提出了求解问题的改进禁忌搜索算法(Tabu-RAM),通过5个Benchmark案例对本文模型和算法进行了验证。实验结果表明Tabu-RAM能够求解传统应用映射问题,且优于现有文献中给出的算法。此外,与传统禁忌搜索算法相比,Tabu-RAM算法在求解鲁棒性应用映射问题时具有更好的性能和稳定性。

In the standard application mapping problem,it is assumed that the communicating traffic of a task is a fixed value.In the real applications,the communication traffic is uncertain due to the time-varying and bursty characters.Therefore,it has the practical significance modeling the task with communicating traffic uncertainty.Given the interval flow and a conservation factor,the robust application mapping problem is formulated by a min-max model,and then solved by a revised Tabu-based algorithm (Tabu-RAM) in this paper.The algorithm is verified under five benchmark instances.As the experimental results show,under the standard application scenarios,the Tabu-RAM performs better than other methods proposed in the literature. In addition,under the application scenarios with uncertain tasks,experimental results show that the TabuRAM performs better and more stable than the traditional tabu algorithm.