引用本文

王彩璐, 陶跃钢, 杨鹏, 刘作军, 周颖. 云控制系统并行任务分配优化算法与并联控制. 自动化学报, 2017, 43(11): 1973-1983. doi: 10.16383/j.aas.2017.c160504

WANG Cai-Lu, TAO Yue-Gang, YANG Peng, LIU Zuo-Jun, ZHOU Ying. Parallel Task Assignment Optimization Algorithm and Parallel Control for Cloud Control Systems. ACTA AUTOMATICA SINICA, 2017, 43(11): 1973-1983. doi: 10.16383/j.aas.2017.c160504

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160504

关键词

云控制系统，并行处理，任务分配，最优控制，并联控制，Petri网 

摘要

利用Petri网模拟云控制系统的并行处理过程，引入并行处理系统的时钟周期、吞吐率和任务完成时间性能指标，运用极大-加代数方法分析和优化云控制系统并行处理性能.采用子过程细分的优化方式，通过求解一类最优控制问题，设计并行任务分配优化方案，以保证任务完成时间最短，并给出计算最短任务完成时间的有效算法.同时，采用重复设置多套瓶颈段并联的方式提高并行处理能力，并运用Petri网实现瓶颈子过程的并联控制，且给出并联控制在协同云控制系统中的一个应用.

文章导读

云控制系统[1-2]在结构上表现为云计算与信息物理系统的深度融合, 在性能上体现了网络化控制系统[3]和云计算技术[4]的优点.如图 1所示, 云控制系统主要涉及物联网[5]、多智能体系统[6]和复杂系统[7]的控制.云计算为云控制系统中大数据存储与处理、控制器设计和控制系统性能优化提供了有力的技术支持.

图 1  云控制系统

云控制系统研究目前正处在起始阶段, 面临着许多挑战[8].建立云计算、物理对象、计算软件与通信网络的综合模型是云控制系统设计的首要问题.总体任务的分割以及分布式计算单元任务的分配都是云控制系统设计的关键环节.合理提炼云控制系统的性能指标, 并对其进行分析和优化, 对设计云控制系统具有实际意义.

Petri网[9-11]因可表征同步、并发等现象在计算机软硬件[12]、分布式数据库[13]、生产管理[14]、通信网络[15]、生物[16]等系统的建模和分析中有着广泛的应用.极大-加代数[17-19]是一个具有重要理论意义和应用价值的代数系统.基于极大-加代数的线性系统理论已有许多研究.例如, 极大-加线性系统的周期性[20-23]、稳定性[24-25]、能达性[26-28]和可预测性[29-30]等. Baccelli等[18]运用极大-加代数方法给出了Petri网的动态方程.

本文运用Petri网模拟云控制系统的并行处理过程, 并采用极大-加代数方法分析系统性能.并行计算[31]是云计算系统的核心技术, 基本思想是用多个处理器协同求解同一问题, 就是将要求解的问题分解成若干子过程, 让多个子部件并行地处理问题.本文引入并行处理系统的时钟周期、吞吐率和任务完成时间性能指标.并行处理能力强的系统应具备时钟周期小、吞吐率高、任务完成时间短等特点.时钟周期受限于瓶颈子过程的运行时间.从理论角度来看, 子过程划分越细, 系统的时钟周期就越小, 吞吐率就越高, 任务完成时间就越短.然而, 考虑到指令在锁存器中的存取时间, 子过程的细分因锁存器增多而增加指令在子部件之间的传输延迟, 从而一定程度上会抵消因子过程细分而带来的吞吐率提高的效果.采用何种原则对子过程进行分割?如何合理分配各子过程的运行时间, 使任务完成时间最短?在发生指令相关的情况下, 如何用Petri网模拟并行处理过程, 以分析系统性能?是本文将要研究的问题.采用重复设置多套瓶颈段并联的方式同样可达到减小时钟周期的目的, 同时避免因锁存器的增多造成总传输延迟增长的弊端.如何对瓶颈子过程进行并联控制? {如何设置并联通道的数目, 以使任务完成时间最短?}也是本文将要研究的问题.

本文结构如下:第1节介绍有关极大-加代数以及Petri网的概念和结论. {第2节建立云控制器并行处理指令的Petri网模型.第3节提出子过程细分的优化方法, 并给出使得任务完成时间最短的任务分配优化算法.第4节提出重复设置多套瓶颈段并联的优化方法, 并运用Petri网实现瓶颈子过程的并联控制.}第5节概括本文的结论, 并提出进一步研究的问题.

图 2  指令级并行处理

图 3  并行处理系统的Petri网模型

对于云控制系统的并行任务分配优化算法及并联控制, 本文建立了并行处理系统的Petri网模型, 分析了并行处理过程中发生的指令相关现象.为了衡量系统的并行处理能力, 本文引入了时钟周期、吞吐率和任务完成时间性能指标, 并通过两种方式提高系统性能.一种是对子过程进行合理分割, 通过求解一类最优控制问题, 设计并行任务分配优化方案, 以保证任务完成时间最短, 并给出计算最短任务完成时间的有效算法.另一种是重复设置多套瓶颈段并联, 利用Petri实现了瓶颈子过程的并联控制, 并给出并联控制在协同云控制系统控制任务并行处理中的一个应用.并行处理系统的子过程数目越多, 同时进入系统的指令数目就越多, 发生指令相关的机会也就越多.如果处理不当, 将会导致并行处理能力显著下降.在发生指令相关的情况下, 如何合理分配处理任务以保持系统较强的并行处理性能, 是我们将要进一步研究的问题.此外, 相对于瓶颈子过程再细分的优化方法, 并联控制方法较为复杂.合理设置并联通道的数目, 制定最优的并联控制策略, 在低设备成本的前提下, 使任务完成时间达到最短, 也是我们将要进一步研究的问题.

作者简介

王彩璐

河北工业大学控制科学与工程学院博士研究生.主要研究方向为离散事件系统控制与优化.E-mail:cailu_wang@163.com

杨鹏

河北工业大学博士.河北工业大学控制科学与工程学院教授.主要研究方向为系统建模与控制, 康复机器人和智能假肢.E-mail:yangp@hebut.edu.cn

刘作军

南开大学博士.河北工业大学控制科学与工程学院教授.主要研究方向为复杂系统控制与优化.E-mail:liuzuojun@hebut.edu.cn

周颖

北京科技大学博士.河北工业大学控制科学与工程学院副教授.主要研究方向为智能控制与模式识别.E-mail:zhouying2007@163.com

陶跃钢

中国科学院博士.河北工业大学控制科学与工程学院教授.主要研究方向为离散事件系统建模, 控制与优化.本文通信作者.E-mail:yuegangtao@hebut.edu.cn