系统级概率故障诊断的最小测试数

系统级故障诊断中的核心问题，是要用最小的开销完成诊断任务．由于测试数是诊断开销的一部分，希望测试数达到最小．在几种概率测试模型下，我们给出了概率诊断中最小测试数的上界和下界，这两个界具有同一数量级．

一种计算一维Walsh变换的MIMD并行算法

本文给出了一种计算一维Walsh变换的MIMD并行算法。它结构简单、易使用且性能好。当变换长度为N(=2~n),可用处理机数为1/n,它具有约1/n倍加速及100％的处理机利用率。

分布式系统级故障诊断概况

一、引言系统级故障诊断的概念自从1976年由Preparata、Metze和Chien提出以来.有关系统级故障诊断的问题得到了越来越多的重视.

一种计算一维离散Fourier变换的MIMD并行算法

1.引言 一维离散Fourier变换(即一维DFT)的快速计算是许多应用领域的迫切要求,若干年来,人们从软、硬方面对此进行了深入研究,提出了不少高效的串、并算法和专用硬件,随着多处理机的广泛应用,研究计算一维DFT的多处理机并行算法(即MIMD并行算法)具有重要意义。

一种计算多项式变换的MIMD并行算法

本文针对在图象处理等领域中广泛应用的多项式变换发计了一种性能较好、结构简单且适合多处理机的并行算法。

关于链路故障的分布式故障诊断

一、引言 在分布式系统中,故障诊断应包括故障结点机的诊断和故障链路的诊断,故障链路的诊断在分布式系统级故障诊断中占有重要地位,它不仅是分布式乐统级故障诊断的目标,而且也是分布式系统级故障诊断的前提,因为一个系统的链路发生故障,则将会对故障结点机的诊断带来困难。在现有的诊断算法中,并不是所有的诊断算法都考虑了链路故障。 在分布式系统中,虽然任两个结点机之间都能进行通讯,也即都能进行互测,因而实际分布式系统的测试图的拓扑结构可以是任意结构的,但我们一般只在实际分布式系统的拓扑结构是分布式的或多总线的情形下才考虑链路故障。因为在单总线系统中,链路故障的出现将是致命的,会使整个系统的故障诊断成为不可能,因此一般不考虑链路故障。

一维Walsh变换的阵列协处理器的设计

本文给出了一种用短序列Walsh变换芯片构成长序列Walsh变换阵列协处理器的方法.按此法,易用2~t片2~t长芯片构成2^(2t)长的Walsh变换的阵列协处理器,并且易用2^(t+1)片2~t长芯片及2^(2t)个蝶形运算器构成2^(2t+1)长的Walsh变换的阵列协处理器.

求多总线系统容错度的多项式时间算法

求多总线系统容错度的多项式时间算法陈四清，周六丁（重庆大学计算机科学系重庆６３００４４）ＰＯＬＹＮＯＭＩＡＬ－ＴＩＭＥＡＬＧＯＲＩＴＨＭＳＦＯＲＤＥＴＥＲＭＩＮＡＴＩＮＧＴＨＥＦＡＵＬＴ－ＴＯＬＥＲＡＮＣＥＤＥＧＲＥＥＯＦＭＵＬＴＩＢＵＳＳＹＳＴＥＭ...

可靠通讯网与可靠多总线结构间的关系

讨论了可靠通讯网与可靠多总线结构间的关系。提出了以图论为工具对可靠通讯网进行逻辑设计,然后用多总线结构对其加以实现的方法。并给出了可靠通讯网的处理机容错度和对应的多总线结构处理机容错度间的关系。

解三对角Toeplitz方程组的MIMD并行算法

本文把秩1修正技术和一阶线性递推并行消去法结合起来,给出了求解三对角Toeplitz方程组的MIMD并行算法。该算法结构简单,存储省,处理机之间通讯比较少,而且对处理机台数没有特殊要求;相对于追赶法的加速比可接近P/2(P为处理机台数)。值得指出的是,本文的算法关键产考虑并组织了一阶常系数线性递推的并行计算。

非对称模型下的顺序诊断算法

讨论了顺序ｔ－可诊断系统的诊断算法问题。在Ｍａｌｅｋ和ＢＧＭ模型下，分别提出了一种顺序诊断算法，这些算法在测试图是二部图的情形下都是多项式时间复杂性的。

图顶点m着色的一种新算法

本文提出了一种求解圆顶点m着色的“智能”回溯算法.实验结果表明,对求解适当规模的顶点着色问题,新算法较常规算法快2～7倍.分析结果表明,对求解难度更大的这类问题,新算法则会更优.

用多项式变换及W变换计算二维卷积

本文先给出了一种用Ｗ变换计算模（ｚ＾Ｎ＋１）多项式积的新算法。然后将它与多项式变换结合用于计算Ｎ×Ｎ（Ｎ＝２＾ｔ）二维复值圆卷积。这种结合法完成上述卷积仅需２Ｎ＾２·（ｌｏｇ２Ｎ＋３／２）次实乘及１０·Ｎ＾２·ｌｏｇ２Ｎ＋Ｎ＾２次实加。该乘法量仅为常规多项式变换法的一半。

一维离散Fourier变换的阵列协处理器设计

提出了一种用短DFT芯片构成长序列DFT的阵列协处理器的有效方法。此法易用2~l片、2~l长DFT芯片及2^(2l)个乘法器构成2^(2l)长的DFT阵列协处理器,也易用2^(l+1)片、2~l长DFT芯片,2^(2l+1)个乘法器及2^(2l)个蝶形运算单元构成2^(2l+1)长的DFT阵列协处理器。文中给出了它们的并行结构及分析结果。它们具有并行计算度高,芯片需求少,简单易实现的特点。

用可变长短序列WHT芯片计算长序列Walsh-Hadmard变换

提出了能够将任一长序列变换有效地分解为一组定长的短序列变换的方法及算法,通过用短序列芯片计算这些短序列变换,从而可高速完成任意长序列的变换。

Walsh-Hadamard变换ASIC的并行结构设计

针对具有广泛应用的Walsh-Hadamard变换,研究了适合其ASIC设计的算法与SFG阵列结构、位串计算、可变长功能等方面的内容,并给出了Walsh-Hadamard变换ASIC的一种合理结构。

实圆卷积新算法及与现有算法的比较

本文给出了一种实序列圆卷积的新算法,它完成N(N=2~M)点实序列圆卷积仅需 N·(log_2N-1)+2次实乘、3N·(log_2N-1)+10次实加及2N个实数单元。通过与现有卷积算法比较,当N较大且N=2~M时,它比其它算法各项指标都优。

一种只需4N^2单元的N阶矩阵快乘法及其实现

本文改进了V.Strassen矩阵快乘算法,在时间复杂性保持相同,但将其空间复杂性从ON^(2.81)降至4N^2。文中还给出了改进算法的实现技术。

适合多处理机MPSCU的并行排序算法

本文给出了一个适合多处理机MPSCU的并行排序算法。它用k个处理机能在O((N/k)log_2N/k+N)时间内完成N点排序。

求所有点对最短路径的两个MIMD并行算法

基于多处理机MPSCU,设计了两个求解所有点对最短路径问题的适用并行算法。这两个并行算法使用k个处理机均能在O(N^3/k)时间内求解N个顶点无向图的所有点对问题。它们都已在MPSCU上实现。