一个改进的并列处理算法

一、问题的提出八十年代中期,日本推出的PNAP-1系统(ParallelNetwork Analysis Program-1),是一个实用、有效的计管机并列处理系统.但是,该系统在动态分配各基点计算机的任务时,是由输入端顺序向输出端划分级别(Level),然后按级进行处理.这种算法存在的主要问题:①同一级中同时存在几个可以进行第K次处理电路时,其处理顺序不明确.②存在反馈时,如何处理尚无规律可循.③如何寻求各点的加权路径并未考虑.这里,“第K次处理”是指某电路的全部扇出(FANOUT)电路中,(K-1)次运算已经完成;全部扇入(FANIN)电路中第K次运算已经完成.二、按优先度排序的算法为了解决上述存在问题,笔者提出一个改进的不分级方案,对各个可能处理(?)电路,按优先度(Priority)从高至低进行选择.其优先度确定方法如下: