欢迎访问《图学学报》 分享到：
图学学报

图学学报

• 图学教育 • 上一篇    

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

  

  1. 1. 海军大连舰艇学院军事海洋系，辽宁 大连 116018；
    2. 国防科学技术大学装备综合保障技术重点实验室，湖南 长沙 410073
  • 出版日期:2017-06-30 发布日期:2017-07-06

Task Graph Partitioning Method Based on Manhattan Distance

  1. 1. Department of Military Oceanography, Dalian Naval Academy, Dalian Liaoning 116018, China;
    2. Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology,
    Changsha Hunan 410073, China
  • Online:2017-06-30 Published:2017-07-06

PDF (PC)

193

摘要： 对实时性要求较高的嵌入式电子系统，常利用多核处理器来提高其计算速度，故
对复杂程度较大的嵌入式电子系统，需分解其功能任务，使其能够映射到不同大小的处理器上，
从而可靠地完成复杂系统功能。结合图论相关理论基础，以马氏距离为度量标准，提出了一种
任务图分割方法。以44二值乘法器为例，对其进行任务图分割，并与重分割方法进行比较。
结果分析表明分割后任务子图的节点数目减少，且任务子图间的通信时间较短，验证了分割方
法的有效性，有利于实现复杂嵌入式电子系统的应用。

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

Abstract: 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.

Key words: embedded electronic systems, Manhattan distance, task graph, partitioning