基于休假串联排队的三值光学计算机请求数分析

张 杰，庞 昆，张 冕，赵 佳，王先超*

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

2003年金翊等为充分发挥光计算的并行性提出TOC原理与结构[1]，基于该理论目前已构建出四代TOC硬件系统[2-5]，2018年搭建的SD18已达1 152位。然而关于TOC性能评价的研究却很少。文献[6-7]基于M/M/1排队系统对TOC性能评价进行建模，发现计算量和网络传输速度是影响系统响应时间的瓶颈。但该模型考虑的是TOC不需保养和检修的理想状态，不能真实反映TOC的计算生态。

另一方面，排队系统作为分析和评价系统性能的有效工具[8-12]，被应用于计算机系统和通讯网络的性能分析与评价[13-14]。同经典排队系统相比，休假排队系统是指利用闲期对服务设施进行检修或者服务员在闲期中去休假的排队系统，更能真实地反映服务会中断的事实，同时还为系统的过程控制和优化设计提供了灵活性。系统中无请求时才能开始休假称为空竭服务休假[15]。根据休假结束规则，当休假结束时系统仍然空闲，就接着开始一个新的独立同分布的休假，直到某个休假结束系统中有顾客，服务员就结束休假开始服务为多重休假[16-18]。多年来，专家们提出了矩阵分析法[19-20]等以解决休假排队问题。

本文拟利用M/M/1排队和M/M/n排队同时考虑TOC休假，提出其服务模型，选取系统平均请求数重要指标，对其性能进行分析和评价。

1 三值光学计算机服务模型

为分析TOC服务性能，首先建立其服务模型。该模型由4个阶段构成：

Stage 1：Client将用户提交的运算请求发送至RM(receiving module)，RM将未接收的运算请求存入第一层队列即请求队列；从非空请求队列中取出一个请求，将其发送至PPM(preprocessing module)。

Stage 2：PPM将RM发送过来的请求插入第二层队列即待预处理请求队列；从非空待预处理请求队列中取出一个请求，把用户输入的十进制数据转换成MSD数据，再根据运算生成光学处理器的控制信号，将其发送至SAM(scheduling and allocating module)。

Stage 3：SAM将接收到任务按FCFS策略插入第三层队列即待调度任务队列；按既定的调度策略调度任务并按处理器分配策略分配数据位；将运算结果发送至运算结果发送模块TM(Transmitting Server)。

Stage 4：TM(transmitting module)将运算结果加入第四层队列，并取出一个将其发送至相应的Client。

假设各阶段中的队列都是阻止请求延迟，排队规则都是先到先服务(first come first served,FCFS)。

2 TOC的请求调度与处理器分配算法

TOC因其具有独特的特点，本文提出了一种处理器均分策略（processor divided equally strategy,PDES)下请求调度和处理器分配算法。请求调度不但包括将调度队列Q队首的请求发送至TOC，并将其删除，还包括获取请求中的二元三值逻辑运算个数、各逻辑运算的运算量和总运算量，队长LQ减1。同时，假设TOC光学处理器的数据在PDES策略下，首先根据TOC光学处理器的特点，将整个光学处理器数据位分成n等分，构成n个可独立使用的小光学处理器。SAM接收运算请求后，首先判断TOC是否在休假。若是，则将其按FCFS排队；否则判断是否有空闲的小光学处理器。若有，则立即对其调度，并为其分配一个小光学处理器；否则，直到有小光学处理器空闲时才进行调度。而后为已调度请求分配一个小光学处理器资源，并以按比例分配策略将一个小光学处理器的数据位分配各运算，以保证各运算能够同时完成。处理器均分策略下请求调度和处理器分配算法如下：

Step 1：系统启动后参数初始化。正在处理的请求数NProc=0，调度队列Q的长度LQ=0，并将各小光学处理器的状态State均置为0，i=0(i用于指示当前待分配的小光学处理器)。

Step 2：当第一个请求到达时，将其放入Q，LQ增 1，转 Step 4。

Step 3：SAM判断NProc是否为n。若是，将请求插入Q，LQ增 1，转 Step 10；否则，转 Step 4。

Step 4：从Q中调度一个请求，NProc增 1，LQ减1，转 Step 5。

Step 5：i=imodn，查看第i个小光学处理器的状态，即判断State[i]是否为0。若为0，将State[i]置 1，转 Step 7；否则，转 Step 6。

Step 6：i增 1，转 Step 5。

Step 7：j=1。

Step 8：判断j是否大于请求中二元三值逻辑运算个数NLog。若是，转Step 12；否则，转Step 9。

Step 10：SAM接收到“运算完成”信号时，NProc减1，并回收小光学处理器资源即将相应的小光学处理器状态State置0，转Step 11。

Step 11：判断LQ是否为0。若是，向TOC发送“休假”信号，转Step 13；否则转Step 4。

Step 12：将分配结果Nj(j=1,2,...,NLog)和所分配处理器的重构码发送至TOC，转Step 10。

Step 13：SAM接收到TOC发送的“休假结束”信号时，转Step11。

Step 14：算法结束。位总数为N。

3 性能分析模型

本文选取平均请求数作为性能评价指标。记平均请求数为R

其中Ri(i=1,2,3,4)表示各阶段的平均请求数。

“渺小感”不是妄自菲薄，自轻自贱，而是一种人生历练之后大智慧。人生在世，低调谦逊是我们应该保持的姿态。因为渺小感，所以冷静睿智。保持渺小感，人生虽然没有江山万里的壮阔雄浑，却能拥有小桥流水的自然雅致。

3.1 Stage 1的性能分析

选用经典M/M/1排队系统对Stage 1建模。假设请求到达时间间隔和接收时间独立同分布服从参数分别为1/λ和1∕μ1的指数分布。

由文献[21]知，ρ1=λ∕μ1＜1时 RM 将达到稳定状态。记第m个状态的概率为，由K氏代数方程，可得

可得

于是，该阶段平均请求数R1

其中：λ为单位时间内请求平均到达率，μ1为单位时间内RM的平均接收率。再假设请求中待传输的平均数据量为D，网络的平均传输速度为ξ，则μ1=ξ∕D。

3.2 Stage 2的性能分析

根据Burke定理[22]，系统达到平衡状态时Stage 1的输出是均值为λ的Poisson过程。即也可用M/M/1排队系统对Stage 2建模。假设PPM进行数据预处理的速率为τ，则其服务速率μ2=τ∕D。时，可得其平均请求数

3.3 Stage 3的性能分析

SAM按FCFS对请求调度后将其发送至TOC，同时为已调度的请求分配光学处理器，并将分配结果及所分配处理器的重构码发送至TOC。TOC光学处理器的重构部件以全并行方式完成重构后，编码器对控制内码表示的数据进行编码，即将电信号转换成光信号，而后运算器便对其进行光计算，最后解码器将运算结果转换以通信内码表示的数据。因为光学处理器具有巨位性，可以并行处理多个运算请求。本文拟考虑采用具有多重休假和空竭服务的M/M/n排队系统对Stage 3进行性能分析。假设请求到达Stage 3的时间间隔、TOC休假时间、TOC忙期相互独立。显然，单位时间内请求到达Stage 3的平均到达率也是λ。

由处理器均分使用策略，光学处理器被均分为n个具有相同硬件配置的小光学处理器。两次相继休假期之间的时间为TOC忙期，由前述算法可知，每个小光学处理器完成运算后，如果SAM中没有待处理的请求，而尚有其他小光学处理器在处理请求，TOC不能进入休假状态，相应的小光学处理器只能转为空闲状态。仅当所有小光学处理器都空闲，且SAM中的队列Q变为空，TOC才同步开始一个随机长度为v的休假；假期到达的请求将被依次插入至Q的队尾；TOC休假结束时都向SAM发送“休假结束”信号，如收到“休假”信号，则开始下一次独立同分布休假，否则将结束休假，进入忙期；此时若SAM的队列Q有LQ(＜n)个请求，调度Q中的所有请求，LQ个小光学处理器开始工作，其余n-LQ个小光学处理器处于空闲状态；若LQ≥n，调度Q中的n个请求，剩下n-LQ个请求继续等待。可以看出，这里的休假指TOC的光学处理器和解码器休假，称其为TOC休假。

由文献[23]可知，Stage 3的计算量远大于数据量D。为简化性能分析，假设Stage 3的计算量为数据量D的20倍即20D。同时，假设TOC的休假时间v服从参数为1∕δ的指数分布，TOC所有光学处理器的处理速度为σ，则其服务速率μ3=σ∕20D，每个小光学处理器的服务速率μ3E=σ∕20nD。

下面用拟生灭过程模型[19-20]求系统稳态下R3。令Q(t)表示t时刻SAM中请求数，并定义如下V(t)函数。

{(Q(t),V(t))}构成状态空间为 Ω={(0,1)}⋃{(k,j)|k≥1,k∈N,j=0,1}的二维Markov过程。

当有请求到达SAM，TOC完成一个请求的运算或光学处理器和解码器休假结束时，状态发生改变。按层次将该过程的状态排序，可得其状态转移机制。将状态按字典序排列，G可写成如下分块三角阵。

由文献[19]可得

其中，

3.4 Stage 4的性能分析

同样可用M/M/1排队系统对该阶段建模分析。假设TM需要处理的数据量为D/2，TM的处理速率与PPM进行数据预处理的速率相同，即也为τ，则TM的数据服务速率μ41=2τ∕D，数据发送服务速率μ42=2ξ∕D。当ρ41=0.5λD∕τ＜1 ，且ρ42=0.5λD∕ξ＜1时，可得 Stage 4 的平均请求数

4 性能仿真

本节将通过一些仿真实验和数值例子来探讨TOC的性能分析，其中的参数都是演示性的，并且可以被修改以适应不同环境下TOC。

4.1 请求到达率对系统性能的影响

为计算请求数，首先给出各参数取值。请求到达率λ∈{5i|1≤i≤12,i∈N}，表示每小时到达请求数，网络平均传输速度ξ=20MB/s，每个请求平均数据量D=1 GB，PPM和TM的处理速度τ=2.5 GB/s，数据位总数N=1 000，OP处理速度为σ=2 GB/s，TOC休假时间v服从参数δ=10，小光学处理器数n=4。令ρ=max{ρ1,ρ2,ρ3,ρ41,ρ42}，当ρ＜1时，系统将到达平稳状态。可得平稳时R仿真结果如图1所示。可以看出，平均请求数随到达率λ的不断增加而增加。

4.2 小光学处理器数量n对系统性能的影响

在上节基础上，本节讨论小光学处理器数量n，n∈{2,3,4,5}，对R和U的影响。其他条件不变时的实验结果如图2所示。系统平均请求数R随着n的增加有所增加，即n的增加导致系统性能降低。

图1 平均请求数随λ变化

图2 n对平均请求数的影响

5 小结

为分析和评价TOC性能，本文首先引入串联排队和同步多重休假排队，建立TOC四阶段服务模型，系统中没有请求即空竭服务时TOC光学处理器才开始休假。以系统平均请求数作为系统性能指标，构建其数学模型，并进行数值仿真。结果表明平均请求数随请求到达率的增加而增加。同时，还分析了处理器均分策略下被分成的小光学处理器数目对系统性能的影响，结果显示其增加将导致系统性能降低。下一步将基于异步休假策略研究三值光学计算机性能。