并行计算机故障诊断及WDM网络路由与波长分配问题研究

摘要

高性能并行计算系统是求解大规模计算问题的主要工具之一,在科学与工程的各个领域有着广泛的应用。在大规模并行处理系统中,处理器间通信是制约系统整体性能的瓶颈。随着系统规模的不断增大,带宽需求量也越来越大。光互连网络由于具有极高带宽、极低功耗、极低时延等优点,成为继电互连网络之后最有希望的互连网络。波分复用(WDM)网络是一类重要的光互连网络,其核心思想,是将光纤带宽划分为多个数据通道,可以同时传输多个具有不同波长的信号。在WDM网络中,波长是极为宝贵的资源。所谓路由与波长分配(RWA)问题,就是要用最少的波长,在WDM网络上实现预定通信模式。
　　本研究主要内容包括：⑴确定了三元超立方体中由m个顶点导出的最大子图。⑵运用三元超立方体的最大导出子图,确定了在WDM一维阵列以及WDM网格上实现双向三元超立方体通信模式和单向三元超立方体通信模式所需的最小波长数,并设计了相应的波长分配方案。另外,还提出了在WDM圆环上实现双向3元超立方体通信模式的一种有效波长分配方案。⑶确定了双向3元超立方体通信模式在WDM一维阵列上按维运行时所需波长数,从而大大降低了所占用的波长资源。随着并行计算系统规模的不断增大,系统中的处理器不可避免地会出现故障,因此需要快速、准确地定位故障处理器,保证在故障发生时系统仍能正常运行。系统级诊断是故障定位的一条有效途径,其核心思想,是让处理器相互测试,并根据测试结果定位故障处理器。诊断度是系统级诊断的一个重要概念,用于衡量系统的自诊断能力。系统级诊断的一项重要任务,就是要确定并行计算机底层互连网络的诊断度。g-好邻居条件诊断度是最近提出的新诊断度,它假设每个结点至少有g个好邻居。与通常的诊断度相比,g-好邻居条件诊断度能够显著提高系统的自诊断能力。三元超立方体是一类典型的互连拓扑。本文取得的研究成果,就是确定了三元n维立方体在PMC模型下的g-好邻居条件诊断度。