基于Petri网的多DSP系统模型及其应用研究
|
摘要
多处理器并行处理系统在许多领域都有广泛的应用,是目前获得高性能处理系统的方法之一。然而由于存在系统体系结构,通信带宽和软件并行性等诸多因素的影响,往往会很大程度上制约多处理器系统性能的发挥;而且多处理器系统结构复杂,还会降低系统的可靠性。因此有效的评估多处理器并行处理系统的性能和可靠性是系统设计阶段必不可少的任务之一。本文针对这一要求,建立了一个以Petri网为基础的多DSP并行处理系统模型,并应用该模型对多DSP系统进行性能评估和指导系统的容错设计。
文章首先详细论述了基本Petri网和随机Petri网的相关理论,以及广义随机Petri网的分析方法。然后介绍了以ADSP14060为核心的多DSP并行处理系统的结构特征,特别分析了在实际应用中常用的“主从”并行结构和“流水线”结构的特点;在系统结构分析的基础上,分别建立了基于广义随机Petri网的多DSP并行处理系统模型,并应用该系统模型对“主从”结构和“流水线”结构的性能进行了全面的评估,找到影响系统性能的各种因素和提高系统性能的办法。最后分析了多DSP并行处理系统的可靠性,并提出一种系统的容错方案,该容错方案能够有效提高系统的可靠性。
实验结果表明,应用基于Petri网的系统模型所得到的系统性能参数,能够有效的表征系统实际的性能,满足对系统性能评估的要求。
Nowadays, Multi-processor parallel system has been widely used in many areas, and is one of the methods to get the high performance system. But as under the influence of many factors, such as system structure, communication bandwidth, parallel degree of software, etc, the multi-processor parallel system can not work out its capacity fully; and as the multi-processor parallel system always has a very complex structure, this may reduce the reliability of the whole system. So it is necessary to do the performance evaluation and reliability evaluation of the whole system during the design period. Aiming at this request, the dissertation focuses on the research of building a multi-DSP parallel processing system model based on the Petri net, and using such model to evaluate the performance of the multi-DSP system, as well as guide a design of the system fault tolerance.
Firstly, the theory of Petri net, stochastic Petri net, and methods of analyzing the general stochastic Petri net (GSPN) is dissertated in the thesis. Secondly, the structure of the multi-DSP system, basing on ADSP14060 SHARC DSP, is discussed, especially the structure of“master-slave”and“pipeline”, which are the most common using structures. Under the basis of structure analyzing, the multi-DSP parallel system model based on the general stochastic Petri net(GSPN) are built, and using the system models, the performances of“master-slave”and“pipeline”parallel structures are evaluated. The results of performance evaluation show the main factors that influence the performance of the multi-DSP parallel system, and the methods that can improve the performance of the system. Finally, the reliability of the multi-DSP parallel system is analyzed, and a fault tolerance design is showed.
The results show that the Petri-net based system model can efficiently evaluate the performance of the real system, and the model can fulfill the requirement of multi-DSP system’s performance evaluation.
文章首先详细论述了基本Petri网和随机Petri网的相关理论,以及广义随机Petri网的分析方法。然后介绍了以ADSP14060为核心的多DSP并行处理系统的结构特征,特别分析了在实际应用中常用的“主从”并行结构和“流水线”结构的特点;在系统结构分析的基础上,分别建立了基于广义随机Petri网的多DSP并行处理系统模型,并应用该系统模型对“主从”结构和“流水线”结构的性能进行了全面的评估,找到影响系统性能的各种因素和提高系统性能的办法。最后分析了多DSP并行处理系统的可靠性,并提出一种系统的容错方案,该容错方案能够有效提高系统的可靠性。
实验结果表明,应用基于Petri网的系统模型所得到的系统性能参数,能够有效的表征系统实际的性能,满足对系统性能评估的要求。
Nowadays, Multi-processor parallel system has been widely used in many areas, and is one of the methods to get the high performance system. But as under the influence of many factors, such as system structure, communication bandwidth, parallel degree of software, etc, the multi-processor parallel system can not work out its capacity fully; and as the multi-processor parallel system always has a very complex structure, this may reduce the reliability of the whole system. So it is necessary to do the performance evaluation and reliability evaluation of the whole system during the design period. Aiming at this request, the dissertation focuses on the research of building a multi-DSP parallel processing system model based on the Petri net, and using such model to evaluate the performance of the multi-DSP system, as well as guide a design of the system fault tolerance.
Firstly, the theory of Petri net, stochastic Petri net, and methods of analyzing the general stochastic Petri net (GSPN) is dissertated in the thesis. Secondly, the structure of the multi-DSP system, basing on ADSP14060 SHARC DSP, is discussed, especially the structure of“master-slave”and“pipeline”, which are the most common using structures. Under the basis of structure analyzing, the multi-DSP parallel system model based on the general stochastic Petri net(GSPN) are built, and using the system models, the performances of“master-slave”and“pipeline”parallel structures are evaluated. The results of performance evaluation show the main factors that influence the performance of the multi-DSP parallel system, and the methods that can improve the performance of the system. Finally, the reliability of the multi-DSP parallel system is analyzed, and a fault tolerance design is showed.
The results show that the Petri-net based system model can efficiently evaluate the performance of the real system, and the model can fulfill the requirement of multi-DSP system’s performance evaluation.
引文
[1] Gander T J. Infantry anti-tank guided weapons. International defence review, 1996, 29(1): 51~56
[2] 付伟. 红外制导武器的现状及发展趋势. 红外技术, 1999, 21(3) : 8~13
[3] 闫肃, 王明海, 刘新学. 巡航导弹制导方式分析. 飞航导弹, 2000, 7 : 55~57
[4] 崔焕庆. 基于 Petri 网的 MPI 并行程序建模与正确性验证: [硕士学位论文]. 山东: 山东科技大学, 2004: 2~6
[5] Arjan J C, van Gemund. Symbolic Performance Modeling of Parallel Systems. IEEE Transactions On Parallel And Distributed Systems, 2004, 14: 154~165
[6] Tsinarakis, Tsourveloudis, Valavanis. Modeling, Analysis, Synthesis, and Performance Evaluation of Multioperational Production Systems With Hybrid Timed Petri Nets. IEEE Transactions On Automation Science and Engineering, 2006, 3(1): 29~46
[7] Estrin G, Fenchel R S, Razouk R R. SARA(System Architects Apprentice): modeling, analysis, and simulation support for design of concurrent systems. IEEE Transactions On Software Engineering, 1986, 12: 293~311
[8] 朱晓东, 王世明. 多时钟域处理器架构的性能和功耗分析. 计算机工程, 2005, 31(24): 75~77
[9] 王宇, 薛文革, 李增智. UML 建模方法在 TMN 开发中的应用研究. 计算机工程与应用, 2001, 4: 40~42
[10] Huaping Dai, Youxian Sun. An Algebraic Model for Performance Evaluation of Timed Event Multigraphs. IEEE Transactions On Automatic Control, 2003, 48(7): 1227~1230
[11] Ali Abedi, Amir K Khandani. An Analytical Method for Approximate Performance Evaluation of Binary Linear Block Codes. IEEE Transactions On Communications, 2004, 52(2): 228~235
[12] David M Nicol, William H Sanders, Kishor S Trivedi. Model-Based Evaluation: From Dependability to Security. IEEE Transactions On Dependable And SecureComputing, 2004, 1(1): 48~65
[13] 丁正己, 谢磊. Petri 网在多处理器系统性能分析中的应用. 信息大学学报, 2000, 1(4): 58~60
[14] 林闯, 李雅娟, 王忠民. 性能评价形式化方法的现状和发展. 电子学报, 2002, 30(12): 1917~1922
[15] 候蓉晖, 史浩山. 一种基于随机 Petri 网的资源共享系统性能分析方法. 计算机应用, 2005, 25(4): 881~882
[16] 刘鸿, 林闯, 吴建平. 一种紧同步随机 Petri 网模型的性能分析方法. 软件学报, 2003, 14(6): 1029~1036
[17] 林闯. 一种资源共享系统的模型和近似性能分析. 计算机学报, 1997, 20(10): 865~871
[18] Noé Lopez-Benitez. Petri-Net Based Performance-Evaluation of Distributed Homogeneous Task Systems. IEEE Transactions On Reliability, 2000, 49(2): 188~198
[19] Marsan M A, Conte G, Balbo G. A class of generalized Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions On Computer System, 1984, 2(2): 93~122
[20] 林闯. 随机 Petri 网和系统性能评价. 第二版. 北京: 清华大学出版社出版, 2005: 1～11, 19~35, 233~255
[21] 许京奕, 宋佳兴. 基于 GSPN 的工作流模型性能评价方法与应用. 计算机工程与应用, 2005, 19: 189~198
[22] 张建东, 高晓光. GSPN 的分析方法及其应用. 火力与指挥控制, 2005, 30(5): 27~31
[23] 曾小伟, 陈吉红, 向华. 计算 Petri 网 S 不变量和 T 不变量算法. 华中科技大学学报, 2001, 29(11): 1~3
[24] 曾小伟, 向华, 陈吉红. Petri 网可视化工具的设计与实现. 华中科技大学学报(自然科学版), 2002, 30(6): 43~45
[25] 黄勇, 张友良, 汪惠芬. 基于广义随机 Petri 网的可视化建模与仿真工具. 计算机集成制造系统, 2004, 10(8): 892~897
[26] 杨光宇, 郑应平. 面向对象 Petri 网建模与仿真的可视化环境. 系统仿真学报, 1997, 9(3): 7~11
[27] Baca A. Examples of Monte Carlo Methods in reliability estimation based on reduction of prior information. IEEE Transactions On Reliability, 1993, 42(4): 645~649
[28] 肖刚, 李天柁. 系统可靠性分析中的蒙特卡罗方法. 第一版. 北京: 科学出版社, 2003: 10~49
[29] 苏涛, 吴顺君. 高性能 DSP 与高速实时信号处理. 第一版. 西安: 西安电子科技大学出版社, 2002: 46~99
[30] 吴敏渊, 金伟正, 胡志雄. ADSP 系列数字信号处理器原理. 第一版. 北京: 电子工业出版社, 2002: 286~303
[31] 李锦波, 石岩, 曹治国. 面向实时图像处理的嵌入式操作系统研究. 红外与激光工程, 2004, 33(6): 651~654
[32] 赵广州, 张天序, 王岳环. 基于 AD14060 的 FPGA+多 DSP 可重构信息处理机设计, 2005, 21(1): 86~89
[33] 王祖斌, 彭应宇等. 一种新型多 DSP 并行计算结构及其应用. 系统工程与电子技术, 2001, 23(3): 19~22
[34] Barry Wilkinson, Micheal Allen. 并行程序设计. 第一版. 北京: 机械工业出版社, 2005: 4~10
[35] K C Chang, Zhi Tian, Shozo Mori. Performance Evaluation for MAP State Estimate Fusion. IEEE Transactions On Aerospace and Electronic Systems, 2004, 40(2): 706~714
[36] Jinsheng Huang, Ming J Zuo. Dominant Multi-State Systems. IEEE Transactions On Reliability, 2004, 53: 362~368
[37] 曹治国, 左峥嵘. 红外海面小目标检测的并行实现技术. 华中科技大学学报, 2001, 29(2): 52~54
[38] 徐维新, 秦英孝. 可靠性工程. 第一版. 北京: 电子工业出版社, 1988: 5~8
[39] 蔡俊. 可靠性工程学. 第一版. 哈尔滨: 黑龙江科学技术出版社, 1990: 4~7
[40] 黄祥瑞. 可靠性工程. 第一版. 北京: 清华大学出版社, 1990: 3~9
[41] Dave E, Eckhardt. An Experimental Evaluation of Software Redundancy as a Strategy for Improving Reliability. IEEE Transactions On Software Engineering,1991, 17(7): 692~702
[42] Héctor Cancela, Mohamed El Khadiri. The Recursive Variance-Reduction Simulation Algorithm for Network Reliability Evaluation. IEEE Transactions On Reliability, 2003, 52: 207~212
[43] Naruemon Wattanapongsakorn, Steven P Levitan. Reliability Optimization Models for Embedded Systems With Multiple Applications. IEEE Transactions On Reliability, 2004, 53(3): 406~416
[44] 张庆成, 金海, 张浩. MPI 程序容错系统的分析和设计. 计算机工程与科学, 2005, 27(6): 89~92
[45] 屈婉霞, 蒋句平, 杨晓东. 并行计算机系统容错设计. 计算机工程与科学, 2005, 27(9): 69~84
[46] 张国平, 夏学知, 涂葵. 一种改进 PVM 检错机制实时性能的方法. 计算机与数字工程, 2006(2): 1~11
[47] Victor P Nelson. Fault-Tolerant Computing: Fundamental Concepts. IEEE Computer, 1990, 7: 19~25
[48] Rachid Guerraoui, Andre Schipper. Software-Based Replication for Fault Tolerance. IEEE Computer, 1997, 4: 68~74
[49] Herbert Hecht. Fault-Tolerant Software. IEEE Transactions On Reliability, 1979, 28(3): 227~232
[50] Rosario Romera, José E. Valdés, and Rómulo I. Zequeira. Active-Redundancy Allocation in Systems. IEEE Transactions On Reliability, 2004, 53(3): 313~318
[51] Suprasad V Amari, Hoang Pham, Glenn Dill. Optimal Design of k-out-of-n: G Subsystems Subjected to Imperfect Fault-Coverage. IEEE Transactions On Reliability, 2004, 53(4): 567~575
[52] Daniel Berleant, Jianzhong Zhang. Bounding the Times to Failure of 2-Component Systems. IEEE Transactions On Reliability, 2004, 53(4): 542~550
[2] 付伟. 红外制导武器的现状及发展趋势. 红外技术, 1999, 21(3) : 8~13
[3] 闫肃, 王明海, 刘新学. 巡航导弹制导方式分析. 飞航导弹, 2000, 7 : 55~57
[4] 崔焕庆. 基于 Petri 网的 MPI 并行程序建模与正确性验证: [硕士学位论文]. 山东: 山东科技大学, 2004: 2~6
[5] Arjan J C, van Gemund. Symbolic Performance Modeling of Parallel Systems. IEEE Transactions On Parallel And Distributed Systems, 2004, 14: 154~165
[6] Tsinarakis, Tsourveloudis, Valavanis. Modeling, Analysis, Synthesis, and Performance Evaluation of Multioperational Production Systems With Hybrid Timed Petri Nets. IEEE Transactions On Automation Science and Engineering, 2006, 3(1): 29~46
[7] Estrin G, Fenchel R S, Razouk R R. SARA(System Architects Apprentice): modeling, analysis, and simulation support for design of concurrent systems. IEEE Transactions On Software Engineering, 1986, 12: 293~311
[8] 朱晓东, 王世明. 多时钟域处理器架构的性能和功耗分析. 计算机工程, 2005, 31(24): 75~77
[9] 王宇, 薛文革, 李增智. UML 建模方法在 TMN 开发中的应用研究. 计算机工程与应用, 2001, 4: 40~42
[10] Huaping Dai, Youxian Sun. An Algebraic Model for Performance Evaluation of Timed Event Multigraphs. IEEE Transactions On Automatic Control, 2003, 48(7): 1227~1230
[11] Ali Abedi, Amir K Khandani. An Analytical Method for Approximate Performance Evaluation of Binary Linear Block Codes. IEEE Transactions On Communications, 2004, 52(2): 228~235
[12] David M Nicol, William H Sanders, Kishor S Trivedi. Model-Based Evaluation: From Dependability to Security. IEEE Transactions On Dependable And SecureComputing, 2004, 1(1): 48~65
[13] 丁正己, 谢磊. Petri 网在多处理器系统性能分析中的应用. 信息大学学报, 2000, 1(4): 58~60
[14] 林闯, 李雅娟, 王忠民. 性能评价形式化方法的现状和发展. 电子学报, 2002, 30(12): 1917~1922
[15] 候蓉晖, 史浩山. 一种基于随机 Petri 网的资源共享系统性能分析方法. 计算机应用, 2005, 25(4): 881~882
[16] 刘鸿, 林闯, 吴建平. 一种紧同步随机 Petri 网模型的性能分析方法. 软件学报, 2003, 14(6): 1029~1036
[17] 林闯. 一种资源共享系统的模型和近似性能分析. 计算机学报, 1997, 20(10): 865~871
[18] Noé Lopez-Benitez. Petri-Net Based Performance-Evaluation of Distributed Homogeneous Task Systems. IEEE Transactions On Reliability, 2000, 49(2): 188~198
[19] Marsan M A, Conte G, Balbo G. A class of generalized Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions On Computer System, 1984, 2(2): 93~122
[20] 林闯. 随机 Petri 网和系统性能评价. 第二版. 北京: 清华大学出版社出版, 2005: 1～11, 19~35, 233~255
[21] 许京奕, 宋佳兴. 基于 GSPN 的工作流模型性能评价方法与应用. 计算机工程与应用, 2005, 19: 189~198
[22] 张建东, 高晓光. GSPN 的分析方法及其应用. 火力与指挥控制, 2005, 30(5): 27~31
[23] 曾小伟, 陈吉红, 向华. 计算 Petri 网 S 不变量和 T 不变量算法. 华中科技大学学报, 2001, 29(11): 1~3
[24] 曾小伟, 向华, 陈吉红. Petri 网可视化工具的设计与实现. 华中科技大学学报(自然科学版), 2002, 30(6): 43~45
[25] 黄勇, 张友良, 汪惠芬. 基于广义随机 Petri 网的可视化建模与仿真工具. 计算机集成制造系统, 2004, 10(8): 892~897
[26] 杨光宇, 郑应平. 面向对象 Petri 网建模与仿真的可视化环境. 系统仿真学报, 1997, 9(3): 7~11
[27] Baca A. Examples of Monte Carlo Methods in reliability estimation based on reduction of prior information. IEEE Transactions On Reliability, 1993, 42(4): 645~649
[28] 肖刚, 李天柁. 系统可靠性分析中的蒙特卡罗方法. 第一版. 北京: 科学出版社, 2003: 10~49
[29] 苏涛, 吴顺君. 高性能 DSP 与高速实时信号处理. 第一版. 西安: 西安电子科技大学出版社, 2002: 46~99
[30] 吴敏渊, 金伟正, 胡志雄. ADSP 系列数字信号处理器原理. 第一版. 北京: 电子工业出版社, 2002: 286~303
[31] 李锦波, 石岩, 曹治国. 面向实时图像处理的嵌入式操作系统研究. 红外与激光工程, 2004, 33(6): 651~654
[32] 赵广州, 张天序, 王岳环. 基于 AD14060 的 FPGA+多 DSP 可重构信息处理机设计, 2005, 21(1): 86~89
[33] 王祖斌, 彭应宇等. 一种新型多 DSP 并行计算结构及其应用. 系统工程与电子技术, 2001, 23(3): 19~22
[34] Barry Wilkinson, Micheal Allen. 并行程序设计. 第一版. 北京: 机械工业出版社, 2005: 4~10
[35] K C Chang, Zhi Tian, Shozo Mori. Performance Evaluation for MAP State Estimate Fusion. IEEE Transactions On Aerospace and Electronic Systems, 2004, 40(2): 706~714
[36] Jinsheng Huang, Ming J Zuo. Dominant Multi-State Systems. IEEE Transactions On Reliability, 2004, 53: 362~368
[37] 曹治国, 左峥嵘. 红外海面小目标检测的并行实现技术. 华中科技大学学报, 2001, 29(2): 52~54
[38] 徐维新, 秦英孝. 可靠性工程. 第一版. 北京: 电子工业出版社, 1988: 5~8
[39] 蔡俊. 可靠性工程学. 第一版. 哈尔滨: 黑龙江科学技术出版社, 1990: 4~7
[40] 黄祥瑞. 可靠性工程. 第一版. 北京: 清华大学出版社, 1990: 3~9
[41] Dave E, Eckhardt. An Experimental Evaluation of Software Redundancy as a Strategy for Improving Reliability. IEEE Transactions On Software Engineering,1991, 17(7): 692~702
[42] Héctor Cancela, Mohamed El Khadiri. The Recursive Variance-Reduction Simulation Algorithm for Network Reliability Evaluation. IEEE Transactions On Reliability, 2003, 52: 207~212
[43] Naruemon Wattanapongsakorn, Steven P Levitan. Reliability Optimization Models for Embedded Systems With Multiple Applications. IEEE Transactions On Reliability, 2004, 53(3): 406~416
[44] 张庆成, 金海, 张浩. MPI 程序容错系统的分析和设计. 计算机工程与科学, 2005, 27(6): 89~92
[45] 屈婉霞, 蒋句平, 杨晓东. 并行计算机系统容错设计. 计算机工程与科学, 2005, 27(9): 69~84
[46] 张国平, 夏学知, 涂葵. 一种改进 PVM 检错机制实时性能的方法. 计算机与数字工程, 2006(2): 1~11
[47] Victor P Nelson. Fault-Tolerant Computing: Fundamental Concepts. IEEE Computer, 1990, 7: 19~25
[48] Rachid Guerraoui, Andre Schipper. Software-Based Replication for Fault Tolerance. IEEE Computer, 1997, 4: 68~74
[49] Herbert Hecht. Fault-Tolerant Software. IEEE Transactions On Reliability, 1979, 28(3): 227~232
[50] Rosario Romera, José E. Valdés, and Rómulo I. Zequeira. Active-Redundancy Allocation in Systems. IEEE Transactions On Reliability, 2004, 53(3): 313~318
[51] Suprasad V Amari, Hoang Pham, Glenn Dill. Optimal Design of k-out-of-n: G Subsystems Subjected to Imperfect Fault-Coverage. IEEE Transactions On Reliability, 2004, 53(4): 567~575
[52] Daniel Berleant, Jianzhong Zhang. Bounding the Times to Failure of 2-Component Systems. IEEE Transactions On Reliability, 2004, 53(4): 542~550