基于马氏距离的任务图分割方法  

Task Graph Partitioning Method Based on Manhattan Distance

作　　者：马啸[1] 李岳[2] MA Xiao;LI Yue(Department of Military Oceanography, Dalian Naval Academy, Dalian Liaoning 116018, China;Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology,Changsha Hunan 410073, China)

机构地区：[1]海军大连舰艇学院军事海洋系,辽宁大连116018 [2]国防科学技术大学装备综合保障技术重点实验室,湖南长沙410073

出　　处：《图学学报》2017年第3期458-462,共5页Journal of Graphics

摘　　要：对实时性要求较高的嵌入式电子系统,常利用多核处理器来提高其计算速度,故对复杂程度较大的嵌入式电子系统,需分解其功能任务,使其能够映射到不同大小的处理器上,从而可靠地完成复杂系统功能。结合图论相关理论基础,以马氏距离为度量标准,提出了一种任务图分割方法。以4?4二值乘法器为例,对其进行任务图分割,并与重分割方法进行比较。结果分析表明分割后任务子图的节点数目减少,且任务子图间的通信时间较短,验证了分割方法的有效性,有利于实现复杂嵌入式电子系统的应用。Multi-core processor is often used to improve the calculation speed of the embedded system with high real-time requirement,therefore,it needs to disintegrate the functional task of the embedded electronic system with high complexity,mapping it into different sizes of processors to reliably perform the function of complex systems.Combining with the relevant graph theoretical basis,a task graph partitioning method is proposed with the Manhattan distance as the partitioning criteria.Take the binary multiplier as an example,dividing its task graph,and comparing the method with the re-partitioning method.Results analysis show that the number of nodes in task subgraphs is reduced by the partition,and the communication time between the task subgraphs is short relatively,this verifies the effectiveness of the partitioning method,which is conducive to the implementation of complex embedded electronic systems.

关 键 词：嵌入式电子系统 马氏距离 任务图 分割 

分 类 号：TP330[自动化与计算机技术—计算机系统结构]