Hybrid rendering withscheduling under uncertainty

 

scheduling underuncertainty, 调度问题中，不确定性是比较显著的影响因素。因此，任务在实际完成前，所需要的时间很难被估算出。

  时间波动

1、QL服务器处理时间受服务器随机加载

2、渲染参数，影响服务器和客户端的处理时间

  3、操作系统

Quality Level:  A QL is a representation of a data set to bedisplayed, which can be independently rendered on either the client, theserver, or both, to produce an image.

混合渲染，在客户端和服务器端分别执行渲染任务，而这些任务如何分配，并且在不确定因素的影响下，能够进行相应的调整，使得渲染效果更优。 

QL 是要显示的数据集的代表，它可以独立在客户端或者服务器端绘制，或者两者都能绘制，生成图像。

预采样策略（Pre-Sample Strategy）

列表

Accumulated time  (AT) = processing time(pt)  +  transfer time(tt)

 

从A列表中的每个QL（pt_NDs  tt_NDs）取出随机样本 pt 、tt  AT=pt+tt ，生成B列表。

 

 

将B列表中第一个QL ，放入到C列表。

 

 

 

 

问题：任何QL都有可能被选作Interactive QL ，如果一个不满足Interactive QL条件的QL被当作Interactive QL，那么将会出现停顿现象，然而，系统允许终止Interactive QL，如果该QL不满足条件，但是，又会引发另外一个问题，如果没有QL满足FPS目标，那么系统将承受持续的中断，并且在交互时，其不能更新。

 

分布对比策略（Distribution-Comparison Strategy）

 

AT_ND  = pt_ND  +  tt_ND

 

B列表的前两个QL1，QL2进行比较，随机从各自的AT_ND中选出一个样本，进行比较，小的那个QL放入 C表。

 

 

分布函数的初始化与更新策略

QL所需timings的正态分布函数，需要获取平均值 和 方差。

①初始化条件：获得最小量QLs的timings，来初始化ND

②系统自动调度一个QL来帮助获得timing，直到达到①的条件

故前N个执行的QL中，取N+1个为正态函数的平均值

求方差

 

更新

根据完成了的QL的实际timing来更新 正态函数ND，而更新的快慢由一个权重系统。

处理时间获取与估计

Processingtime 是render  time ，服务器端还包括 图片编码时间

每个QL由多个work units 组成。

估计

 w是work units的个数，wc是平均每个work unit的完成时间，e是平均编码时间

传输时间获取与估计

t是传输时间，pt是前一个QL的传输时间，w是等待时间，p处理时间

估计

在渲染中止的情况下，来估计处理和传输时间

et是估计的传输时间，ei是估计的图片大小，客户端跟踪tr传输率byte/ms，rt是往返时间。