单功能非线性流水线的Petri网调度方法  

Single function nonlinear pipeline scheduling method based on Petri nets

作　　者：束德勤[1] 范昊[1] 张亮[1] 

机构地区：[1]山东农业大学信息科学与工程学院,山东泰安271018

出　　处：《计算机工程与设计》2016年第9期2390-2393,共4页Computer Engineering and Design

基　　金：山东省高等学校科技计划基金项目(J11LG26);山东农业大学青年科技创新基金项目(23659)

摘　　要：在非线性流水线的调度中须找出一种合适的时间间隔,避免流水线各功能段的使用冲突并使流水线有较高的吞吐率和效率,为此提出一种基于Petri网的单功能非线性流水线的建模及调度方法。对流水线的工作过程建立直观清楚的Petri网模型,直接利用网结构求出禁止启动距离和初始可调度向量;根据网模型的一步并发和冲突检测缩小Petri网可达图的状态空间,得到流水线的可调度图;由可调度图的闭合回路,得到最优调度方案。结合一个流水线调度实例,验证了该方法的正确性。Finding out the time interval to enter a new task to the pipeline in nonlinear pipeline scheduling can avoid functional section using conflict and make the pipeline has high throughput and efficiency.A single function nonlinear pipeline modeling and scheduling method based on Petri nets was then proposed.Intuitive and clear Petri net model for the working process of pipeline was established,the forbidding initiation interval and the initial schedulable vector were found out using net structure.The state space of Petri net reachability graph was reduced,and the schedulable graph of the pipeline was got.The optimal scheduling plan was obtained using the closed loop of schedulable graph.With an example of pipeline scheduling,the correctness of this method is verified.

关 键 词：非线性流水线 流水线调度 PETRI网 冲突检测 可达图 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]