基于RFID技术的供应链新型管理系统研究

张 丽

(安徽工业经济职业技术学院 招生就业处，合肥 230051)

供应链协商智能管理是指决策任务与物理资源映射关系的过程,它是解决并行作业问题的关键.已有研究工作或权衡任务干扰约束和资源利用率,如Whare-Map[1]、Tetrisched[2];或权衡公平性和数据局部性,如Quincy[3]、YARN[4];或权衡公平性和隔离性,如Mesos[5]、Omega[6];或满足优先级等单一约束条件,如Borg[7].上述研究均假设决策目标固定不变,但相关研究表明,相同的作业集合采用固定的管理决策算法,或导致极低的资源利用率,如平均资源利用率小于20%;或引起作业性能下降5倍[8],如任务未绑定特殊硬件进行加速,违反优先级约束.因此,如何提高供应链协商智能管理的灵活性,使其具备按需配置能力,正逐渐引起工业界和学术界的广泛关注,面临巨大挑战.

本文首先对相关工作进行总结,归纳出两种典型的度量指标;接着分析基于队列的供应链协商智能管理模型,举例说明队列模型灵活性不足,难以支持多种管理场景,无法按需配置生效,其本质原因是该模型表达能力不足,且仅能满足局部最优解;然后融合RFID技术图对供应链协商智能管理建模,将满足两种典型度量的供应链管理方法映射为图的构造问题;最后,采用增量方法降低图的求解复杂度.通过实测和仿真两个方面,验证了本方法的有效性.

1 图的放置约束和求解问题

根据前文分析,放置约束、管理延迟是供应链管理两种主要度量指标.本节首先介绍如何从资源视角刻画上述管理目标,并将其转换为图的容量和费用赋值问题.接着针对图的求解问题,提出了一种融合混合式最小费用流算法.

1.1 图的放置约束

放置约束可描述为如下三元组:

placementconstraint(task,resource,utility)>

(1)

其中:task表示任务,resources表示任务约束的资源,表示task放置到resources上所获得的效益.采用效益函数描述放置约束,即

max∑utility

(2)

放置约束可映射到图的边有无构造问题:

在task和resources之间建立一条边task→resources,并赋予一个与效益值相反的费用,即

cost(task→resource)=-utility

(3)

最大效益函数对应最小费用:

图1 图的放置约束构造混合算法

(4)

由公式(2)、(4)可知,通过RFID技术网络表述的放置约束等价于放置约束的定义.如图1所示为防止约束构造示例.任务T1图像处理程序,两台机器M1、M2,M1带有GPU,M2无GPU.T1对M1有放置约束,获得的收益为1,对M2无放置约束,即收益为0.通过RFID技术求解,可以获得最小费用,即最大收益,T1会在M1执行.

1.2 图的求解问题

最小费最大流问题的形式化描述如下：

目标函数

min∑(w,v)∈Ec(w,n)f(w,n)

(5)

约束条件

0≤f(w,v)≤u(w,v)∀(w,v)∈E

(6)

∑(w,v)∈Ef(w,v)-∑(v,w)∈Ef(v,w)=b(v)∀w∈V

(7)

其中,w、v表示图中节点,c(w,v)表示边(w,v)的费用,f(w,v)表示边(w,v)的流量,u(w,v)表示边(w,v)的容量,b(v)>0的顶点为源节点,b(v)﹤0的点为汇聚节点.满足∑vb(v)=0的流，称为可行流.每个节点v的势π(v)是一个实数值,给定节点势的集合,边的相对费用(Reduced cost)定义为cπ(v,w)=c(v,w)-π(v)+π(w).对于可行流f,G(f)为图G的残存网络，满足以下条件之一时,可行流f是最优的：

(i)负圈最优化条件(Negative cycle optimality):G(f)中没有费用为负数的增广圈;

(ii)相对费用最优化条件(Reduced cost optimality):G(f)中每一个边的相对费用cπ(v,w)均大于 0;

(iii)互补松弛最优化条件(Complementary slackness optimality):G(f)的边,或满足cπ(v,w)>0且f(v,w)=0,或满足0

RFID技术求解算法已广泛实践，其核心思想是在满足公式(5)、(6)和(7)的前提下,或维护最大流,不断迭代寻找最小费用;或维护最小费用,不断迭代寻找最大流,直到满足最优化条件,可在多项式时间内解决.

本文提出一种混合式图求解混合算法ICS(Incremental Cost Scaling),通过缓存和复用上次求解结果,仅需对图进行局部运算,即可得到图的全局最优解,实验结果验证了ICS的有效性和适用性.对于图G=(V,E,U,C),其最小费用流为f,G网络结构局部发生改变,改变后的图G′={V′,E′,U′,C′}.混合式最小费用流算法,即图G′融合G的最小费用流f进一步优化,求得G′的最小费用流f′.融合事件驱动模型循环检测全局物理资源的状态改变事件Event(任务提交,机器宕机等),当有事件发生,更新图的结构,然后复用上次求解结果,调用Cost scaling算法对更新后的图进行求解.

2 实验及结果分析

本节主要验证混合算法的灵活性,可支持多种管理目标,具有按需配置能力,本混合算法相应的系统实现为Sirius.使用文中评价混合算法与本混合算法对比,验证本混合算法是否具备相同的能力;最后是混合算法管理延迟和资源开销验证,验证本混合算法是否适应至少万级规模供应链管理场景.

2.1 实验环境

实验环境包括实测环境和仿真环境,物理环境验证Sirius的灵活性即Sirius支持的管理目标是否和现有开源系统性能相当；仿真环境验证Sirius开销,即Sirius在大规模环境下资源消耗与管理延迟.仿真环境：选取Google公开的集群数据,包括10 000个物理节点,其中每个节点配置为24 Core、64 G内存、网络10 Gbps,构造RFID技术网络结构,验证Sirius在供应链协商智能管理的性能.

2.2 放置约束验证

选取图像分析类负载,修改Sirius容量配置K等于1(保证每台机器一个任务).任务数目分为T=10(任务独占GPU)和T=20(任务共享50%GPU),验证Random、Swarm/alschedSirius/alsched的平均任务执行时间.实验结果如图2所示,在T=10时,Sirius/alsched和Swarm/alsched平均任务执行时间显著优于随机管理决策,约为随机管理的两倍.在T=20时,Sirius/alsched平均任务执行时间优于Swarm/alsched,分析可能是Sirius/alsched能够更好的权衡任务等待时间.进一步实验,分析两种放置决策在不同任务下的管理延迟,实验结果如图3所示,随着任务数的增加,Sirius/alsched管理延迟小于Swarm/alsched,与分析结果一致.因此,Sirius支持的Alsched管理决策等价或优于原有系统.

图2 不同管理器平均任务执行时

图3 不同管理器平均任务等待时间

2.3 管理延迟验证

实验采用仿真环境,机器规模选用5 000和10 000两组,负载变化范围从10 000～20 000(数据来源于Google公开的集群负载,评估队列算法Random、非增量算法Cost scaling(CS)、增量算法ICS的运行时间.

实验结果如图4和图5所示.两种算法的运行时间随任务数目增加而增加,近似线性相关,其中CS算法延迟远大于混合式算法和队列算法,且随着规模增加,延迟快速增长.队列算法增长速度其次,ICS算法增长速度最慢.当物理服务器规模达到10 000台时,ICS算法性能优于队列算法.此外,ICS算法管理延迟相对于CS算法最多降低10倍.

图4 不同算法运行时间，5 000个仿真结点

图5 不同算法运行时间,10 000个仿真节点

3 结论

供应链协商智能管理是智能管理的研究热点.本文提出一种融合RFID技术网络的供应链协商智能管理建模混合算法,将任务的资源需求和物理资源供给问题转换成RFID技术图的构造和求解问题.首先总结相关工作,归纳出约束性和管理延迟两种典型的管理目标.接着从资源的视角,将典型管理目标进行描述,并映射到图的构造问题,使其具备适应性调整能力.然后实现了一种RFID技术的混合式求解算法,针对图的求解问题进行优化.

[1] BLACK D L.Scheduling support for concurrency and parallelism in the Mach operating system[J].Computer,1990,23(5):35-43.

[2] KARANASOS K,RAO S,CURINO C,et al.Mercury:Hybrid centralized and distributed scheduling in large shared clusters[C].2015 USENIX Annual Technical Conference (USENIX ATC 15).2015:485-497.

[3] VERMA A,PEDROSA L,KORUPOLU M,et al.Large-scale cluster management at Google with Borg[C].Proceedings of the Tenth European Conference on Computer Systems.ACM,2015:18.

[4] MARS J,TANG L.Whare-map:heterogeneity in homogeneous warehouse-scale computers[J].ACM SIGARCH Computer Architecture News.ACM,2013,41(3):619-630.

[5] TUMANOV A,ZHU T,KOZUCH M A,et al.Tetrisched:Space-time scheduling for heterogeneous datacenters[R].Tech.Rep.CMU-PDL-13-112,Carnegie Mellon University,2013.

[6] ISARD M,PRABHAKARAN V,CURREY J,et al.Quincy:fair scheduling for distributed computing clusters[C].Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles.ACM,2009:261-276.

[7] VAVILAPALLI V K,MURTHY A C,DOUGLAS C,et al.Apache hadoop yarn:Yet another resource negotiator[C].Proceedings of the 4thAnnual Symposium on Cloud Computing.ACM,2013:5.

[8] HINDMAN B,KONWINSKI A,ZAHARIA M,et al.Mesos:A platform for fine-grained resource sharing in the data center[J].NSDI.2011,11:22-27.