基于NEH算法的三值光学计算机任务调度优化研究

庞 昆，张 杰，刘德方，张雨臣，王先超*

（阜阳师范大学 a.数学与统计学院；b.计算机与信息工程学院，安徽 阜阳 236037）

20世纪以来，电子技术经历了从电子管、晶体管到超大规模集成电路的发展，电子计算机也从早期体积庞大的初代计算机发展到现在的微型计算机。随着大数据时代的到来，电子计算机由于制作工艺而产生的能耗和带宽等问题制约其进一步发展，而光计算机用光代替电子来实现计算，可以突破电子计算机的瓶颈。近些年光学计算机的研究取得了一系列可喜的进展，如光学稳定多谐振荡器的发展[1]、完全可重构的光子集成信号处理系统的发明与研究[2]等等。三值光学计算机(ternary optical computer,TOC)由有光态时的两个互相垂直的偏振光和无光态表示三值信息，因其处理器具有按位可重构性、按位可分配性和并行性等优点，引起诸多研究者关注[3-4]。图1为参展国际工业博览会的三值光学计算机——SD16。

图1 三值光学计算机实物图

然而，TOC的任务调度仍存在一些问题，有待于优化。以加法计算为例，在三值光学计算机服务模型中，采用先到先服务(first come first served,FCFS)的策略进行任务调度[5-6]，导致系统平均响应时间得不到优化，其中响应时间是指任务的等待时间与处理时间之和。本文以MSD（modified signed digit）加法运算器为例[7]，以平均响应时间为性能指标，采用流水线技术，基于NEH(Nawaz-Enscore-Ham)算法进行任务调度优化，从而使其效率得到提高，整体性能得以进一步优化。

1 流水线任务调度算法

1.1 流水线调度问题

流水线调度（flow-shop scheduling，FSS)问题[8]是一类值得研究的工程问题，其主要任务就是在有限的资源约束情况下，确定每个任务的加工顺序、加工时间，以达到最优化的生产目标，即平均响应时间达到最小。机器一次只能处理一个子任务，子任务一旦开始必须继续进行直到完成。假设机器j上的作业i所需的处理时间记为tij。只有在机器j上的处理完成后，才能由机器j+1处理作业。流程调度问题是确定作业的处理顺序，使得平均响应时间达到最小[9]。同顺序流水作业是著名的调度问题之一，其中两台机器的同顺序流水问题可使用Johnosn算法[10]求得最优解，但仍是 NP（non-deterministic polynomial）完全问题[11]。

1.2 任务调度算法

NP完全问题的解空间涉及组合爆炸，所以有效解决NP完全问题的方法是不存在的。针对此类问题现代科学主要采用启发式算法。启发性算法主要包括禁忌搜索算法[12]、遗传算法[13]、模拟退火算法[14]、人工神经网络[15]等等。由Nawaz等三人提出的NEH算法被认为是最优的[16-19]。该算法的核心思想主要是按任务的平均响应时间将以给定的任务时间矩阵中的任务进行降序排列。再取上述序列中的前两个任务并找到其中最小的平均响应时间对应的序列结果。对于第个任务，在个可能的位置中，将其插入到使得部分序列的平均响应时间最小的位置。最终得到整个任务集的最小平均响应时间对应的任务序列。

NEH算法目前主要应用在车间调度[20]以及流水线调度[21-22]中，本文拟使用NEH算法对三值光学计算机任务调度进行优化。

2 基于流水作业的TOC计算模型

2.1 流水作业计算模型

MSD加法分3步——同时进行T和W变换、同时进行T'和W'变换及T变换，在4种逻辑运算器上完成[7]，所以三值光学计算机的MSD加法可采用流水线技术。为此，首先将三值光学计算机处理器进行合理分配并重构成图2所示的五个独立的逻辑运算部件——T和W变换器、T'和W'变换器和T变换器。

图2 改进后的MSD加法器部件示意图

当某个任务到达时，根据处理器位数和数据的位数将其中的数据分为许多组。T和W变换器对第一组数据进行T和W变换得到；T′和W′变换器对进行T′和W′变换得到的同时，T和W变换器对第二组数据进行T变换和W变换得到；T变换器对进行T变换得到运算结果R1的同时，T′和W′变换器对进行T′和W′变换得到，T和W变换器对第三组数据D03进行T变换和W变换得到。以此类推，直到该任务的所有数据计算完毕，再处理下一个任务，如图3所示。

图3 MSD加法器流水作业时空图

2.2 流水线模型与非流水线模型对比

以加法为例进行流水线(flow shop，FS)模型与非流水线(non-flow shop，NFS)模型对比。当使用NFS模型进行运算时，数据进入MSD加法器，分3步依次进行T和W变换、T′和W′变换以及T变换，每进行一步变换都要进行1次运算器的重构(Reconfiguration)。虽然每次重构都是并行的且时间也比较短，但当数据量很大时，重构次数就很大，因此重构将严重影响系统性能，不容忽视。下面举例说明FS模型的优势。假设完成1次重构时间tre=100ns，光学处理器位数为80 000，处理速度v即进行逻辑变换的速度v=50 GB/s，任务的计算量为100 GB。将任务分组，非流水时每组数据d1为2.4 KB，流水时每组数据d2为0.8 KB。两种情况下分别被分为g1=4.37×107组、g2=1.31×108组。

因为在流水作业时，处理器被均分为3份，所以非流水作业时进行逻辑变换的速度应该为流水作业时的3倍，但是非流水作业对每1组数据进行计算处理过程中必须经历3次重构，才可以完成任务的处理。由此可得NFS和FS时完成任务的时间tnfs和tfs分别为

根据公式（1）和（2）分别计算任务量为 100 GB的任务，得到完成时间分别为：NFS时13.777 s，FS时6.000 s。由实验结果，不难得出如下结论：TOC在处理同一任务时，采用NFS模型的完成时间远大于采用FS模型的完成时间。因此，为提高系统效率，拟对TOC系统中采用FS模型。

显然，某时刻系统中会存在多个待处理的任务，且不同处理顺序将会影响系统的性能。为此，本文选用平均响应时间作为系统性能指标，并基于NEH算法探寻给定任务集的最优调度序列。

3 基于NEH算法的TOC任务调度优化

3.1 基于NEH算法的任务调度算法

为说明基于NEH算法的TOC任务调度算法，先给出相关符号说明，见表1。

表1 相关符号及其含义

具体算法如下。

算法输入：任务的处理时间矩阵。

算法输出：最优任务调度序列。

Step 1 根据输入的时间矩阵，得到任务Δ(i)对应机器Mi的工序加工时间pi即pj,Δ(i)，对其进行求和计算得到Ti。再将n个任务按照Ti的降序排列，得到初始排列Δ′；

Step 2 令k=1，此时初始排列Δ′的前k-1个任务构成部分排列Δp，将Δ′的第k个任务插入到Δp的k个可能的空挡，产生k个临时排列，取最小平均响应时间的临时排列为此k个任务构成的部分排列Δp；

Step 3 令k=k+1，重复步骤2；

Step 4 直到所有任务都完成序列，即使得得到最优的任务加工序列 Δp，使得，此时得到的部分排列 Δp即为算法的可行解Δopt。

Step 5 输出最优序列Δopt，算法结束。

3.2 基于NEH算法的任务调度举例

假设3个任务在3台机器的处理时间矩阵如表2。使用上述算法进行任务调度的过程如下。

Step 1 根据输入的任务时间矩阵，得到任务Δ(i)对应机器Mj的工序加工时间。

Step 2k=1,Δ′=∅ .将任务插入到 Δ′中得到新的序列Δp={2}。

Step 3k=2,Δp={2},将任务 1 插入到 Δp中得到两个新的序列即：{1,2},Ts=21、{2,1}，Ts=22选定时间较短的序列作为新序列即新序列为{1,2}。

Step 4k=3,Δp={1,2},将任务 2 插入到 Δp中得到三个新的序列即：{1,2,3}{3,1,2}{1,3,2}，其中{1,2,3}序列的Gantt图如图4。其余Gantt图略。

表2 NEH举例的加工时间矩阵/min

图4 序列Gantt图

根据算法计算出三种序列所对应的完工时间Ts，如表 3。

表3 三种序列对应完工时间Ts/min

Step 5 得到最优化的序列序列{3,1,2}。算法结束。

4 基于NEH算法的TOC任务调度仿真

首先使用Matlab对给定任务集使用枚举算法进行仿真，列出所有可能序列及其所对应的平均响应时间、最优解和程序运行时间。再使用Matlab对该任务集进行NEH算法求解，得到平均响应时间、最优解和程序运行的时间。

三值光学计算机的参数假设依旧保持上文2.2中的数据不变，现假设任务集中存在10个任务，各个部件对每个任务的处理时间加工矩阵如表4。

分别取前6个任务、前8个任务和全部10个任务进行枚举算法与NEH算法进行求解。在上述仿真实验中，使用Matlab2016a软件实现，运行在一台intel i7-7700(3.6 GHz)处理器上，内存大小为8 GB。具体结果见表5。

表4 3×10加工时间矩阵/min

表5 枚举算法与NEH算法对比

由表5可知，在任务数为6与8时，NEH算法与枚举算法求得的最优解是一致的，即枚举算法与NEH算法均可寻得最优解。但当任务数增加到10时，任务序列数高达10！，此时NEH算法得出结果与枚举法最优解存在细微差别，即NEH算法求得了一个次优解。从程序运行时间来看，虽然n=6时枚举法所用时间优于NEH算法但是也仅仅快了0.168 s，因为NEH算法本身存在一定的运算量，导致任务集较小时，耗时略大，所以几乎可以忽略不计。当n分别为8与10时，NEH算法的程序运行时间分别约是枚举算法的5.55%和0.13%。并且整个趋势会随着任务数的增大不断加大如图5。因此，NEH算法在寻求最佳调度序列时具有明显的优越性。结合表4和5可以看出，对单任务多数据的流水线，采用短作业优先调度策略可以使给定任务集的平均响应时间最小。

图5 枚举法与NEH算法运行时间对比

5 小结

本文对TOC先到先服务模型进行优化，即改进为流水任务模型的处理策略，并在此基础上对任务处理顺序运用NEH算法进一步的优化，得到最佳序列，使用最佳序列进入流水任务模型以达到最小化平均响应时间的目的。本模型提出单任务多数据流水线与短作业优先调度策略相结合的优化策略。仿真实验结果表明本文算法可以使给定任务集的平均响应时间最小。文章还将仿真结果与枚举算法结果相对比，证明该实验结果具有一定的可靠性。