相似驱动的细粒度并行任务重构算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (9): 44-50.

相似驱动的细粒度并行任务重构算法

郝水侠,曾国荪,马小信,许金超

同济大学计算机科学与技术系上海201804;同济大学计算机科学与技术系上海201804;同济大学计算机科学与技术系上海201804;同济大学计算机科学与技术系上海201804

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家863高技术研究发展计划(2009AA012201),国家自然基金项目(61103068),NSFC-微软亚洲研究院联合资助

Similarity-driven Fine-grained Parallel Task Reconfigurable Algorithm

HAO Shui-xia,ZENG Guo-sun,MA Xiao-xin and XU Jin-chao

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 异构计算是高性能计算技术的发展趋势,计算任务与体系结构匹配成为异构计算亟待解决的问题。重构技术为实现两者匹配带来了契机,要么任务重构适应体系结构,要么体系结构重构适应任务。提出基于相似驱动的并行任务重构算法以实现异构计算匹配。通过给出任务和系统匹配度量机制定义了图重构操作和图重构基本问题。根据问题给出细粒度重构算法,该算法主要有3个过程:任务图节点对融合、节点和边重构及重构精化过程。用格林威治大学典型实例图作为并行任务及典型体系结构测试了该算法。实验表明它在给定的误差范围内能保证计算任务和体系结构匹配。

关键词: 并行任务,体系结构,异构计算,图相似,重构中图法分类号TP338文献标识码A

Abstract: Heterogeneous computing is a novel trend of high-performance technology．Mismatch between parallel tasks and architecture leads to realize high performance hardly．Reconfiguration technique brings an opportunity for it．In order to realize their matching,this paper provided similarity-driven reconfigurable algorithm．Firstly the paper gave definitions of graph-similarity and graph-reconfiguration．Secondly through building a measurement between task graph and fixed architecture,the paper provided a graph-reconfiguration problem and a similarity-driven reconfigurable algorithm．The algorithm includes three processes:nodes-fused,node_edge_reconfiguration and node_edge_refined．Finally the paper gave a test on Greenwich benchmark with the typical architecture．The results show that the algorithm can realize the optimal match between the parallel tasks and the architectures on heterogeneous computing.

Key words: Parallel task graph,Architecture,Heterogeneous computing,Similarity-driven,Reconfiguration

郝水侠,曾国荪,马小信,许金超. 相似驱动的细粒度并行任务重构算法[J]. 计算机科学, 2013, 40(9): 44-50. https://doi.org/

HAO Shui-xia,ZENG Guo-sun,MA Xiao-xin and XU Jin-chao. Similarity-driven Fine-grained Parallel Task Reconfigurable Algorithm[J]. Computer Science, 2013, 40(9): 44-50. https://doi.org/

参考文献

[1] Kernighan B W,Lin S.An efficient heuristic for partitioning graphs[J]．Bell System Technology Journal,1970,49:291-308
[2] Hendrickson B,Leland R．A multilevel algorithm for partitioning graphs[C]∥Proceedings of the ACM/IEEE Supercompu-ting Conference．1995:626-657
[3] Walshaw C,Cross M．Multilevel mesh partitioning for heterogeneous communication networks[J]．Future Generation Compu-ter System,2001,17(5):601-623
[4] Schloegel K,Karypis G．Wavefront diffusion and LMSR:algo-rithms for dynamic repartitioning of adaptive meshes．Multilevel k-way partitioning scheme for irregular graphs[J]．IEEE Tran-sactions on Parallel and Distributed Systems,2001,12(5):451-466
[5] Need C,Wehn N．Designing efficient irregular networks for hete-rogeneous system-on-chip[J]．Journal of System Architecture,2008,54(2):384-396
[6] Bambha N K,Bhattacharyya S S．Joint application mapping/interconnect synthesis techniques for embedded chip-scale mutliprocessors[J]．IEEE transaction on parallel and distributed systems,2005,6(8):99-112
[7] Kramer R,Gupta R,Soffa M L．The combining DAG:a technique for parallel data flow analysis[J]．IEEE Transactions on Parallel and Distributed Systems,1994,5(8):805-813
[8] 沈轶伟,曾国荪.异构计算中一种图的非均衡划分算法[J].计算机科学,2006,3(6):260
[9] Selvakkumaran N,George K．Multiobjective hypergraph parti-tioning algorithms for cut and maximum subdomain-degree mi-nimization[J]．IEEE Transactions on Computer Aided Design of Intergrated Circuits and System,2006,5(3):504-512
[10] Karypis G,Kumar V．Multilevel k-way partitioning scheme for irregular graphs[J]．Journal of Parallel Distribution Computer,1998,8(1):96
[11] Verbauwhede I,Schaumont P．The happy marriage of architecture and application in next-generation reconfigurable systems[C]∥Proceedings of the 1^st conference on computing frontiers．Ischia,Italy,2004:363-376
[12] Moulitsas I,Karypis G．Architecture aware partitioning algo-rithms[C]∥Proceedings of the 8th international conference on Algorithms and Architectures for Parallel Processing．Agia Napa,Cyprus.,2008:42-53

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed