固定结构约束下并行计算关键路径不变的可扩展方法

计算机应用 ›› 2014, Vol. 34 ›› Issue (12): 3417-3423.

固定结构约束下并行计算关键路径不变的可扩展方法

熊焕亮¹,²,吴沧海¹,匡桂娟²,³,杨文姬¹

1. 江西农业大学软件学院,南昌 330045
2. 同济大学计算机科学与技术系,上海 200092;
3. 青岛农业大学理学与信息学院,山东青岛 266109

收稿日期:2014-06-30 修回日期:2014-08-04 出版日期:2014-12-01 发布日期:2014-12-31
通讯作者: 吴沧海
作者简介:熊焕亮(1977-),男,江西新建人,博士研究生,CCF会员,主要研究方向:并行分布处理、云计算；吴沧海(1979-),女,浙江上虞人,副教授,硕士,主要研究方向:并行计算、可信软件；匡桂娟(1972-),女,山东青岛人,博士研究生,主要研究方向:并行计算、云计算。
基金资助:
国家863计划项目;国家自然科学基金资助项目;上海市优秀学科带头人计划项目;教育部网络时代的科技论文快速共享专项;江西省教育厅科技计划项目

Critical-path-unchanged extensions for parallel computing under fixed structure constraint

XIONG Huanliang¹,²,WU Canghai¹,KUANG Guijuan²,³,YAGN Wenji¹

1. College of Software, Jiangxi Agricultural University, Nanchang Jiangxi 330045, China;
2. Department of Computer Science and Technology, Tongji University, Shanghai 200092, China;
3. College of Science and Information, Qingdao Agricultural University, Qingdao Shandong 266109, China

Received:2014-06-30 Revised:2014-08-04 Online:2014-12-01 Published:2014-12-31
Contact: WU Canghai

摘要/Abstract

摘要：

在固定结构的需求下,并行计算无法通过规模扩展提升其计算性能。针对此类并行计算可扩展问题,分析影响可扩展性的并行任务因素及体系结构因素,采用带权图对并行任务及体系结构进行建模,并提出一种关键路径不变的可扩展方法,其核心思想是固定图结构,仅合理地调整图节点权值和边权值。通过进一步推导,得出一些关于新扩展方法的性质结论。应用网格计算模拟工具SimGrid开展的实验结果表明,所提出的扩展方法能有效解决此类扩展问题,且保持速度效率不变。

Abstract:

Extending in parallel computing is an effective approach to achieve higher computing performance. However, under the constraint of the fixed structure, it is difficult to improve the performance of parallel computing only by extending its scale simply. Concerning such extension problem of parallel computing, this paper investigated the factors from architecture and parallel tasks which affect its scalability, and modeled the architecture as well as parallel tasks by the weighted graph. Then, an extension method was proposed that the critical path remained unchanged. The novel extension method, in essence, did not change the graph’s structure and only adjusts the graph’s weights. Additionally, some conclusions about the new extension method were drawn by further derivation. Finally, the simulative experiments on the platform SimGrid were conducted to test the effectiveness of the proposed extension method. The results show that the proposed method can solve such extension problem, and at the same time it also realize isospeed-e extension. it can help guide practical extensions of parallel computing.

中图分类号:

TP338

熊焕亮吴沧海匡桂娟杨文姬. 固定结构约束下并行计算关键路径不变的可扩展方法[J]. 计算机应用, 2014, 34(12): 3417-3423.

XIONG Huanliang WU Canghai KUANG Guijuan YAGN Wenji. Critical-path-unchanged extensions for parallel computing under fixed structure constraint[J]. Journal of Computer Applications, 2014, 34(12): 3417-3423.

参考文献

［1］LI X, MAO Z, HU Q, et al. Design & analysis of scalable parallel algorithms［M］. Beijing: National Defense Industry Press, 2000:42-46.(李晓梅,莫则尧,胡庆丰,等. 可扩展并行算法的设计和分析［M］. 北京:国防工业出版社,2000: 42-46.)
［2］GRAMA A, GUPTA A, KUMAR V. Iso-efficiency: measuring the scalability of parallel algorithms and architectures［J］. IEEE Parallel and Distributed Technology, 1993, 1(3): 12-21.
［3］SUN X H, ROVER D T. Scalability of parallel algorithm machine combinations［J］. IEEE Transactions on Parallel Distributed Systems, 1994, 5(6):599-613.
［4］ZHANG X, YAN Y, HE K. Latency metric: an experimental method for measuring and evaluating parallel program and architecture scalability［J］. Journal of Parallel and Distributed Computing, 1994, 22(3): 392-410.
［5］WU X F, LI W. Performance models for scalable cluster computing［J］. Journal of Systems Architecture, 1997, 44(3):189-205.
［6］CHEN J, LI X. Near-optimal scalability: a practical scalability metric ［J］. Chinese Journal of Computers, 2001, 24(2):179-182.(陈军, 李晓梅. 近优可扩展性: 一种实用的可扩展性度量［J］.计算机学报, 2001, 24(2):179-182.)
［7］WANG Y, YANG X. A more effective scalability model for parallel system ［J］. Chinese Journal of Computers, 2001, 24(1): 84-90.(王与力, 杨晓东. 一种更有效的并行系统可扩展性模型［J］.计算机学报, 2001, 24(1): 84-90.)
［8］CHI L, LIU J, HU Q. Evaluation and test for scalability of numerical parallel computation［J］. Journal of Computer Research and Development, 2005, 42(6):1073-1078.(迟利华, 刘杰, 胡庆丰. 数值并行计算可扩展性评价与测试［J］. 计算机研究与发展, 2005, 42(6):1073-1078.)
［9］BOSQUE J L, ROBLES O D, TOHARIA P, et al. Evaluating scalability in heterogeneous systems［J］. The Journal of Supercomputing, 2011, 58(3):367-375.
［10］CHEN Y, SUN X H, WU M. Algorithm-system scalability of heterogeneous computing ［J］. Journal of Parallel and Distributed Computing, 2008, 68(11): 1403-1412.
［11］YANG X. Sixty years of parallel computing［J］. Computer Engineering and Science, 2012, 34(8):1-10.(杨学军. 并行计算六十年［J］. 计算机工程与科学, 2012, 34(8):1-10.)
［12］WANG Z, YANG X. Metrics of measuring parallel computing systems［J］. Computer Engineering and Science,2010,32(10):44-48. (王之元, 杨学军. 并行计算系统度量指标综述［J］.计算机工程与科学, 2010,32(10):44-48.)
［13］YANG X, WANG Z, XUE J. The reliability wall for exascale supercomputing［J］. IEEE Transactions on Computers, 2012, 61(6):767-779.
［14］XIONG H, ZENG G, WU C, et al. Relationships between latency scalability and execution time［J］. Journal of Computer Applications, 2014, 34(3):663-667. (熊焕亮,曾国荪, 吴沧海,等. 延迟可扩展性与并行执行时间的关系［J］. 计算机应用, 2014, 34(3):663-667.)
［15］SUN X, NI L. Scalable problems and memory-bounded speedup［J］. Journal of Parallel and Distributed Computing, 1993, 19(1): 27-37.
［16］YANG X, DU J, WANG Z. An effective speedup metric for measuring productivity in large-scale parallel computer systems［J］. The Journal of Supercomputing, 2011, 56(2): 164-181.
［17］XIONG H, ZENG G, ZENG Y, et al. A novel scalability metric about iso-area of performance for parallel computing［J］. The Journal of Supercomputing, 2014, 68(2):652-671.
［18］CAO J, ZENG G, NIU J, et al. Availability-aware scheduling method for parallel task in cloud environment［J］. Journal of Computer Research and Development, 2013, 50(7):1563-1572. (曹洁,曾国荪,钮俊,等. 云环境下可用性感知的并行任务调度方法［J］.计算机研究与发展, 2013, 50(7):1563-1572.)
［19］LI X, ZHANG X. Energy-aware resource management mechanism for virtualized cloud datacenter［J］. Journal of Computer Applications, 2013, 33(12):3586-3590.(李小六, 张曦煌. 虚拟化云计算数据中心能量感知资源分配机制［J］. 计算机应用, 2013, 33(12):3586-3590.)
［20］DUBOC L, ROSENBLUM D S, WICKS T. A framework for characterization and analysis of software system scalability［C］// Proceedings of the 6th Joint Meeting of the European Software Engineering. New York: ACM, 2007: 375-384.
［21］HAO S, ZENG G, TAN Y. Scalability analysis of heterogeneous computing based on computation task and architecture to match［J］. Acta Electronica Sinica, 2010, 38(11): 2585-2589.(郝水侠, 曾国荪, 谭一鸣. 计算任务与体系结构匹配的异构计算可扩展性分析［J］. 电子学报, 2010, 38(11): 2585-2589.)
［22］WU C, XIONG H, JIANG H, et al. Extension in proportion for parallel computing under the constraint of fixed structure［J］. Journal of Computer Applications,2014,34(11):3234-3240.(吴沧海,熊焕亮,姜火文,等.固定结构约束下并行计算成比例的可扩展方法［J］.计算机应用,2014,34(11):3234-3240.)

[1]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[2]	李宏梅杨天国张磊莫瑞超许小龙徐占洋. 云环境下面向数据密集型应用的容错性资源配置方法[J]. 计算机应用, 0, (): 0-0.
[3]	龚道永, 宋长明, 刘沙, 漆锋滨. 超级计算机网络引导技术研究与分析[J]. 计算机应用, 2019, 39(6): 1577-1582.
[4]	伏舒存, 付章杰, 邢国稳, 刘庆祥, 许小龙. 移动边缘环境下面向工作流管理的计算迁移方法[J]. 计算机应用, 2019, 39(5): 1523-1527.
[5]	付眸杨贺昆吴唐美何润冯朝胜康胜. 基于Spark Streaming的快速视频转码方法[J]. 计算机应用, 0, (): 0-0.
[6]	赵瑞祥, 郑凯, 刘垚, 王肃, 刘艳, 沈焕学, 周谦豪. 基于申威众核处理器的混合并行遗传算法[J]. 计算机应用, 2017, 37(9): 2518-2523.
[7]	付晨, 钟诚, 叶波. MapReduce并行加速数据流多模式相似性搜索[J]. 计算机应用, 2017, 37(1): 37-41.
[8]	薛胜军, 胡敏达, 许小龙. 云环境下公平性优化的资源分配方法[J]. 计算机应用, 2016, 36(10): 2686-2691.
[9]	薛胜军, 邱爽, 许小龙. 云环境下能耗感知的公平性提升资源调度策略[J]. 计算机应用, 2016, 36(10): 2692-2697.
[10]	关国栋, 滕飞, 杨燕. 基于心跳超时机制的Hadoop实时容错技术[J]. 计算机应用, 2015, 35(10): 2784-2788.
[11]	匡桂娟, 曾国荪, 熊焕亮. 关注用户服务评价反馈的云资源再分配方法[J]. 计算机应用, 2015, 35(7): 1837-1842.
[12]	陈诚, 战荫伟, 李鹰. 基于网页链接分类的PageRank并行算法[J]. 计算机应用, 2015, 35(1): 48-52.
[13]	刘智翔宋安平徐磊郑汉垣张武. 多重网格格子Boltzmann方法的并行算法[J]. 计算机应用, 2014, 34(11): 3065-3068.
[14]	张广蓉陈庆奎章刚赵海燕高丽萍霍欢. 基于MapReduce的并行化模糊划分算法[J]. 计算机应用, 2014, 34(11): 3073-3077.
[15]	吴沧海熊焕亮姜火文杨文姬. 固定结构约束下并行计算成比例的可扩展方法[J]. 计算机应用, 2014, 34(11): 3234-3240.