没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
I
摘 要
多处理器系统功能的实现与系统互连网络的性能密切相关。互连网络的可靠性
是衡量网络性能的重要指标。k 元 n 方体与(n,k)-排列图作为常用的多处理器系统底
层拓扑结构,其子网络可靠性研究对系统的实际应用至关重要。然而评估子网络可
靠性的现有方法难以有效平衡精度与效率。本文针对这一问题,以这两类互连网络
为研究对象,探索可以有效平衡精度与效率的子网络可靠性的评估方法。
在给定精度和置信度下给出了基于蒙特卡洛模拟的子网络可靠性的近似评估方
法所需的最小模拟次数的计算方法,为提高评估效率提供了理论基础。接着,给出
了用于训练神经网络的无故障的 k 元(n-1)方体子网络存在概率的数据集的生成方法,
并基于生成的训练数据集构造了用于评估 k 元(n-1)方体子网络可靠性的 BP 神经网络
模型。实验结果表明,基于 BP 神经网络的 k 元(n-1)方体子网络可靠性的近似评估方
法在兼顾精度和效率方面具有一定优势。最后,设计并实现了基于 MATLAB 的 k 元
(n-1)方体子网可靠性评估系统,为工程师综合评估 k 元(n-1)方体子网络可靠性提供
了分析工具。
为了精确高效地度量概率故障条件下(n,k)-排列图中(n-m,k-m)-排列图子网络的
可靠性,利用容斥原理给出了无故障的(n-m,k-m)-排列图子网络存在概率的上下界,
并给出了评估该子网络可靠性的基于蒙特卡洛模拟的评估方法。考虑到在特定情形
下,利用上下界无法得到较为精确的评估结果,基于蒙特卡洛模拟的评估方法效率
不高,因而还提出了基于 BP 神经网络的(n-m,k-m)-排列图子网络可靠性的近似评估
方法。实验结果表明,基于 BP 神经网络的评估方法可以在保证精度的同时提升效率。
最后,设计并实现了基于 MATLAB 的(n,k)-排列图网络的子网络可靠性评估系统,该
系统可以对(n-m,k-m)-排列图子网络的可靠性进行综合评估。
本文的研究成果可为基于 k 元 n 方体和(n,k)-排列图构建的多处理器系统的任务
调度算法的设计提供理论参考。
关键词:互连网络;k 元 n 方体;(n,k)-排列图;子网络存在概率
II
ABSTRACT
The performance of the system interconnection network affects the function
implementation of the multiprocessor system. The reliability of the interconnection
network is one of the important metrics to measure network performance. The k-ary
n-cube and (n,k)-arrangement graph are commonly used as the underlying topologies of
multiprocessor systems, and the research of their subnetwork reliability have important
implications for the application of multiprocessor systems. However, the existing methods
of subnetwork reliability evaluation are difficult to balance accuracy and efficiency in a
valid way. Aiming at this problem, this paper takes these two types of interconnection
networks as the research object, and explores methods of subnetwork reliability evaluation
that can effectively balance accuracy and efficiency.
The calculation method of the minimum number of simulations required for the
approximation evaluation method of subnetwork reliability based on Monte Carlo
simulation under given accuracy and confidence was given, which provided a theoretical
basis for improving the evaluation efficiency. Then, a generative approach of the data set
for the existence probability of the fault-free k-ary (n-1)-cube subnetwork for training the
neural network was given, and based on the generated training data set, a BP neural
network model for evaluating the reliability of the k-ary (n-1)-cube subnetwork was
constructed. The experimental results show that the approximate method to evaluate the
reliability of the k-ary (n-1)-cube subnetwork based on the BP neural network has certain
advantages in striking a balance between accuracy and efficiency. Finally, a reliability
evaluation system of k-ary (n-1)-cube subnetwork based on MATLAB was designed and
implemented, which provided an analysis tool for engineers to comprehensively evaluate
the reliability of k-ary (n-1)-cube subnetwork.
In order to accurately and efficiently evaluate the reliability of
(n-m,k-m)-arrangement graph subnetwork in (n,k)-arrangement graph under probabilistic
fault conditions, the upper bound and lower bound of the existence probability of
fault-free (n-m,k-m)-arrangement graph subnetwork were given by using the
inclusion-exclusion principle, and the Monte Carlo method was also used to evaluate the
III
subnetwork reliability. Note that under certain circumstances, the upper bound and lower
bound could not be used to obtain accurate evaluation results, and the evaluation method
based on Monte Carlo simulation was not efficient, an approximate evaluation method for
the reliability of (n-m,k-m)-arrangement graph subnetwork based on BP neural network
was proposed. The experimental results show that the approximate method to evaluate the
reliability of the (n-m,k-m)-arrangement graph subnetwork based on the BP neural
network can improve the efficiency while ensuring the accuracy. Finally, a subnetwork
reliability evaluation system for (n,k)-arrangement graph based on MATLAB was
designed and implemented, which coulde comprehensively evaluate the reliability of the
(n-m,k-m)-arrangement graph subnetwork.
The research results of this paper can provide a theoretical reference for the design of
task scheduling algorithms for multiprocessor systems based on k-ary n-cubes or
(n,k)-arrangement graphs.
Key words: Interconnection network; k-ary n-cube; (n,k)-arrangement graph; Subnetwork
existence probability
目 录
1 绪论 ......................................................................................................... 1
1.1 研究背景、目的和意义................................................................... 1
1.2 无故障子网络存在概率估计研究进展 .......................................... 2
1.3 基本概念与性质 ............................................................................... 3
1.3.1 图论术语和记号 ......................................................................... 3
1.3.2 k 元 n 方体网络 ........................................................................... 3
1.3.3 (n,k)-排列图网络 ......................................................................... 4
1.4 论文框架 ........................................................................................... 4
2 k 元 n 方体的无故障子网络存在概率评估 .......................................... 7
2.1 准备工作 ........................................................................................... 7
2.2 基于蒙特卡洛的近似评估方法 ...................................................... 9
2.2.1 蒙特卡洛模拟最小模拟次数理论计算 .................................... 9
2.2.2 实验分析 ................................................................................... 11
2.3 基于神经网络的近似评估方法 .................................................... 13
2.3.1 方法介绍 ................................................................................... 13
2.3.2 数据集生成方法 ....................................................................... 14
2.3.3 BP 神经网络模型 ...................................................................... 17
2.4 基于 MATLAB 的 k 元(n-1)方体子网可靠性评估系统 .......... 22
2.4.1 系统开发目的 ........................................................................... 22
2.4.2 系统功能展示 ........................................................................... 23
2.5 小结 ................................................................................................. 27
3 (n,k)-排列图的无故障子网络存在概率评估 ...................................... 29
3.1 准备工作 ......................................................................................... 29
3.2 理论计算 ......................................................................................... 30
3.3 基于蒙特卡洛的近似评估方法 .................................................... 46
3.3.1 基于蒙特卡洛模拟的子网络存在概率的近似评估方法 ...... 46
3.3.2 实验分析 ................................................................................... 49
3.4 基于神经网络的近似评估方法 .................................................... 50
3.4.1 方法介绍 ................................................................................... 50
3.4.2 数据集生成方法 ....................................................................... 51
3.4.3 BP 神经网络模型 ...................................................................... 53
3.5 基于 MATLAB 的(n,k)-排列图网络的子网络可靠性评估系统
.............................................................................................................. 57
3.5.1 系统开发目的 ........................................................................... 57
3.5.2 系统功能展示 ........................................................................... 57
3.6 小结 ................................................................................................. 60
4 总结与展望........................................................................................... 63
参考文献 ................................................................................................... 65
剩余72页未读,继续阅读
资源评论
2201_75761617
- 粉丝: 21
- 资源: 7339
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功