摘要:在计算机的指令调度问题中,按什么样的时间间隔向流水线输入新任务,才能不发生功能段使用冲突,并且使流水线有较高的吞吐率和效率,是非线性流水线调度要解决的问题.非线性流水线的无冲突调度方法,最早是由E.S.Davidson及其学生们于1971年提出的.现有文献,也有用Petri网和有限自动机理论来解决该问题的,但这些方法大都存在复杂性高、效率低、不直观、不易于理解等问题.提出了一种基于Petri网的单功能非线性流水线的建模及调度方法.其主要思想是先对流水线的工作过程建立直观清楚的Petri网模型,直接利用网结构求出禁止启动距离和初始可调度向量,然后根据网模型的一步并发和冲突检测缩小Petri网可达图的状态空间,得到流水线的可调度图,最后由可调度图的闭合回路,直观的得到最优调度方案.该方法对流水线的工作过程给出了直观的图形表示,网的运行自然的反应了流水线的工作过程,求解调度方法简单、高效、易于理解,所见即所得.结合一个流水线调度实例,给出了Petri网建模和求解最佳调度方案的过程,验证了该方法的正确性.