说点什么

最近在忙着写实验用的程序，调bug调呀调不出来，正好下周组会轮我讲论文，不妨就看篇论文放松一下。
另外说一下，其实GAMES101的课程已经基本看完了，只是没有时间记笔记而已。

原文链接

DroidCloud:Scalable High Density Android™ Cloud Rendering

论文要解决的问题

1. 虽然传统的Android模拟器或Anbox可以将Android系统运行在云上，但会造成严重的性能损失，如下图所示，当多个Android的实例同时运行时，这种现象会尤为明显。
2. 商用Android云渲染服务需要在一个服务器上提供高密度的服务，并且需要高可扩展性使其可以同时服务数百万的用户。

挑战：

1. 系统对Android应用程序透明。
2. 由于共享资源的相互干扰，因此需要对不同的Android OS进行隔离。
3. 在实验中发现，有时当GPU的利用率达到100%时，CPU的利用率才达到30%，因此当一台服务器上有许多渲染任务时，服务器的GPU将会成为整个系统的瓶颈，DroidCloud通过使用远端的GPU来解决这个问题。

DroidCloud

为解决上述的三个挑战,本文实现的DroidCloud实现了三个技术：

1. Android Virtual Device HAL shim （vHAL）layer:用于适应服务器结构并注入远端输入同时保证Android应用程序的透明度。
2. 低开销的隔离策略：以减少不同OS的资源竞争，并平衡开销。
3. 灵活的渲染调度：通过转发渲染命令，以同时使用远端GPU和本地GPU进行渲染。
   此外，本文还做出了如下贡献：
4. 通过定制的Android OS优化单实例和跨实例资源开销
5. 在Intel的Xeon平台上提供可以并行运行上百Android实例的云渲染系统

系统设计

DroidCloud由三个关键部分组成：DC-management、DC-Instance、DC-client。
DC-management：负责调度和管理DC-client和数百万在不同物理节点上的DC-Instance的生命周期。
DC-Client：远端设备，用于流媒体的解码，和捕捉用户的输入。
DC-Instance：是一个隔离的逻辑计算单元，每一个DC-Instance上有一个Android OS的实例。DC-Instance由三个子模块组成，分别是DC-runtime用于支持OS的运行时，DC-Rendering用于图形渲染和编码，DC-Network用于与对应的DC-client进行网络传输。

Virtual Android Device HAL

问题：由于Andorid平台和服务器间的I/O设备的兼容性问题，导致Android应用程序难以不做任何修改的情况下运行在服务器上。

HAL layer用于处理这个问题：

• Remote vHAL：用于将DC-client上的I/O设备数据重定向到DC-Runtime上。DC-Client和DC-Runtime根据数据的不同可以选择TCP、UDP或SCTP等不同的协议进行连接。
• Emulated HAL：用于模拟缺少的功能，比如通过以太网实现的WIFI
• Dummy HAL：用于模拟不太重要的硬件功能，比如振动器、蓝牙等。

Runtime Isolation

DroidCloud通过Linux container（namespace和cgroup机制）的解决方案将一个服务器上的Android系统进行隔离，以保证较少的资源共享和调度开销。除此之外，为andorid的特定功能提供了额外的扩展，如binder（一种Android特定的IPC（进程间通信）机制，由binder server、binder client和binder driver组成）。这是由于必须阻止从一个Android实例到其他实例的IPC。通过创建binder设备节点并将其分配到不同的DC-Instance，其提供不同实例间的隔离。

Flexible Rendering

因此DroidCloud实现了本地渲染和云端的远程渲染。本地渲染是指通过本地的计算节点进行渲染，远程渲染是指利用其它计算节点进行渲染。

本地渲染：通过默认的渲染管线进行渲染。
远程渲染：基于OpenGL的API转发策略。DC-rendering重定向所有的渲染调用到DC-Rendering前端模块。前端模块将参数和数据缓存进行打包，并将其通过TCP/IP或RDMA通道发送至被分配的GPU所在的服务器上。远程渲染后端包含4个模块：

• Command Server：作为TCP/IP服务器接收前端发来数据包，并进行解包。
• GPU Manager： 管理与该服务器关联的GPU，以进行任务调度。
• Rendering Module：负责GPU渲染的软件驱动。
• Encoder：负责编码的软件驱动。

经过编码的视频流将会被送回前端进行流分组，最终发送至客户端。

由上述实验可得，远端渲染可以避免单片SoC的功率限制（40W）。

优化

减少资源使用可以提高云渲染策略的密度。DroidCloud通过多种方法减少资源使用，包括简化单个实例的DC-Runtime和跨实例的资源共享。

单实例的减少资源使用

Android OS在丰富的I/O设备和硬件特性上配备了多种服务和应用。但是云渲染不需要其中的一些应用和服务，因此可以为使用目标进行定制。

Android守护程序Ueventd依赖来自kernel的确切消息来创建设备节点。这种实现在客户端可以运行的很好，但在由数百个DC-Runtime实例的DroidCloud，会产生“消息风暴”，这会随着实例数量的增加而降低DroidCloud的启动速度，因此为Ueventd创建一个固定的设备列表，而不是通过与kernel通信。

通过在DroidCloud中为不重要的特性实现确定的静态工作区。比如，DroidCloud通过AC power（交流电源）模拟电池，并通过避免监控更新以节省CPU的周期。此外，删除蓝牙和多用户等超过20个进程，以节省管理开销和DC-runtime中超过100MB的内存占用。

备注：与Linux相同，Android中的应用程序通过设备驱动访问硬件设备。设备节点文件是设备驱动的逻辑文件，应用程序使用设备节点文件来访问驱动程序。

在Linux中，运行所需的设备节点文件被被预先定义在“/dev”目录下。应用程序无需经过其它步骤，通过预先定义的设备节点文件即可访问设备驱动程序。
但根据Android的init进程的启动过程，我们知道，Android根文件系统的映像中不存在“/dev”目录，该目录是init进程启动后动态创建的。
因此，建立Anroid中设备节点文件的重任，也落在了init进程身上。为此，init进程创建子进程ueventd，并将创建设备节点文件的工作托付给ueventd。

ueventd通过两种方式创建设备节点文件。
第一种方式对应“冷插拔”（Cold Plug），即以预先定义的设备信息为基础，当ueventd启动后，统一创建设备节点文件。这一类设备节点文件也被称为静态节点文件。
第二种方式对应“热插拔”（Hot Plug），即在系统运行中，当有设备插入USB端口时，ueventd就会接收到这一事件，为插入的设备动态创建设备节点文件。这一类设备节点文件也被称为动态节点文件。

跨实例的减少资源使用

通过共享内存和共享编译代码以减少内存和编译成本。

主动文件页去重

每个Android映像由系统分区映像（system.img）、供应商分区映像（vendor.img）和根文件系统（rootfs）。其中系统分区映像和供应商分区映像对于每一个DC-Instance是完全相同的。因此，如果实例之间只共享一个副本，那么存储和页面缓存的成本将得到节省。

layered on write(LOW)技术被用于这种文件页去重，如下图所示，为减少文件映射内存（以及页缓存）的开销，DroidCloud.image是只读的，不同的DC-Instance使用相同的映像，以减少内存缓存的开销。

Android中的分层数据（layered data）用于包含Android系统和应用程序产生的读写数据。为更加灵活地管理这些数据，这些数据分区被移出DroidCloud映像，并保存在本地或中央文件系统中。为了进一步地减少内存缓存开销，分层数据被实现为一个Overlay file system（和docker类似）。其中基本的公共分层数据被保存为只读层，由不同的Android实例共享。可写层在基本层的顶部。分层数据的一个重要用途是共享应用程序的安装。

AOT二进制共享

AOT（Ahead Of Time）运行前编译：
在程序运行前编译，可以避免在运行时编译性能消耗和内存消耗。

通过跨实例应用程序安装，减轻存储和内存占用的开销。在同一组核心上运行多个实例时，应用程序本地库只有一个副本，因此这种共享可以减少指令的cache miss。

实验部分

本文在实验中主要关注一下三个方面：

1. 不同规模场景下CPU、GPU、内存和磁盘的资源开销
2. benchmark的性能
3. 所提到的优化技术在大规模场景中的好处

实验平台如下：

其中Android x86 native是一款标准的Android操作系统，具有完整的功能配置。Emulator和AnBox是为在Linux环境中运行应用而定制的运行库。

实验所用Benchmark如下：

单个Android实例baseline

本实验对运行单个Android实例的项目进行横向比较，作为实例平均资源利用率的baseline。

下图展示了CPU、GPU、内存和磁盘在Gallery Scrolling在60FPS下和idle home panel在无屏幕刷新情况下的利用率。可以发现，DroidCloud作为定值的运行库相比于全功能配置具有较低的资源利用率。

小场景下的DroidCloud

本实验是对运行多个Android实例的项目进行横向比较，目的是在保证QoS的情况下评估每个实例资源开销的可扩展性。

下图展示了本机操作系统运行1、2、4、8和16个实例时典型用例的帧率和延迟。注意Ax86V没有锁帧到60帧，因此在实例数量较少时，显示的性能较好。可以发现，由于DroidCloud采用了深度资源共享的策略，在基本容器实现的基础上提高了可扩展性。

下图展示了在subway suf这个benchmark上，不同实例数量情况下的平均资源利用率。可以看出，由于好的资源共享设计，当实例数量为2资源利用率由明显下降，相对于其他的解决方案实现了更好的性能和QoS。

大场景下的DroidCloud

本实验是对DroidCloud在大规模场景下的垂直比较。DroidCloud、具有远程渲染的DroidCloud（DC-stub）和没有进行资源共享优化的DroidCloud（DC w/o Optimization）进行比较。

下图分别展示了在不同实例数量下的帧率、延迟和不同资源的归一化利用率。对比表明，DroidCloud在高密度场景下有非常好的可扩展性。

说点什么

最近比较忙，所以最近就没看GAMES101的系列课程了，应科研需要，近期读了一下SLI的技术文档，想将一些有用的内容进行分享一下

原文链接

SLI Best Practices

SLI技术总结

SLI技术是什么：Scalable Link Interface，是一种通过多个NVIDIA的GPU划分负载，以提高渲染性能的多GPU配置。

SLI提供的五种多GPU渲染的模式：

1. Alternate Frame Rendering(AFR):多个GPU交替渲染帧，比如在两个GPU的场景下，GPU1渲染帧1，GPU2渲染帧2，然后GPU1再渲染帧3，以此类推。该方式只需要很少的GPU间通信,但由于GPU间性能差距、以及无法减少帧延迟（操作到显示的时间）、CPU的性能上限，因此该模式不容易进行扩展。此外，还有两种可解决的影响AFR扩展的问题：CPU-GPU间同步和帧间依赖产生的GPU同步。
2. Split Frame Rendering(SFR):将一帧的画面划分为多个区域，每一个GPU负责一个区域，划分的区域会因为负载进行动态改变以保证负载均衡。该模式可能会产生重复的计算和GPU间的通信开销。
3. AFR of SFR:该模式将GPU分组，组内的GPU采用SFR的模式，组与组之间采用AFR的模式，比如4个GPU，分成两个AFR组，每个组内的两个GPU以SFR的模式运行。
4. Boost Performance Hybrid SLI Rendering:该模式类似于AFR模式，然而该模式是针对性能差距较大的GPU的场景的，比如两个GPU的场景下，GPU1的性能时GPU2的两倍，则GPU1渲染帧1和帧2，GPU2渲染帧3，然后GPU1渲染帧4和帧5，以此类推。
5. SLIAA:该模式在保证原有的帧率的情况下，通过多个GPU在不同的位置进行采样，并最终进行合并，以提升抗锯齿的性能。

关于SLI的GPU内存的说明

CPU中任何数据的更新都会被广播到所有GPU，每一个GPU都存放了一份数据的备份。（个人见解：存储的数据存在大量的冗余，不能充分利用每个GPU的显存）

AFR的帧间依赖

渲染到纹理

对于SwapChain而言，可以通过设置discard flag（不同DX版本的flag不同），告诉驱动back buffer中的数据不必保留（不必传输到其他的AFR组或GPU中）

对于Render Target而言，没有这个flag，这是由于不知道应用在未来的帧中是否需要被写入Render Target的数据，因此，需要将该数据同步至所有的AFR组或GPU中。这导致GPU间大量的数据在传输，以及同步开销。比如：GPU2将暂停等待GPU1更新共享的Render Target。（该问题可以通过修改SLI的配置文件以阻止帧间的render target传输，或者通过在每一帧开会前调用Clear()函数清除Render Target使得驱动认为改数据不必保留并放弃该Render target的拷贝以解决）

D3D10及以后的Stream Out buffer

和Render target类似，buffer也有类似的问题，但由于没有API机制以清除Buffer，因此只能通过将SLI配置文件添加到驱动程序中。

D3D11中的Unordered Access Views

D3D11中引入的Unordered Access Views概念，可以将其绑定到管线进行随机读写访问。由于任何可能的修改都有可能导致帧间的依赖，因此在缺少配置文件的情况下，应用程序会通过引入适当的帧间同步操作来处理。ID3D11DeviceContext::ClearUnorderedAccessViewUint和ID3D11DeviceContext::ClearUnorderedAccessViewFloat这两个调用可以在每一帧前清除UAV buffer，因此可以去除这种帧间依赖以避免AFR组间的同步开销

Blinn-Phong Reflectance Model

高光+漫反射+环境光照

着色不考虑阴影（不考虑其他物体的存在）

定义及假设：

表面的亮度与表面和光线夹角间的关系

由于能量守恒定律，因此光线随传播距离衰减

因此如上述所示，漫反射的公式为

其中k_d表示光线的反射率

镜面反射，由于光照对应的反射角的亮度最亮，因此通过半程向量h来判断观测点和反射角由多接近，因此镜面反射的公式为

上面的指数控制高光的范围（指数范围大概在100~200的范围）

课程地址

GAMES101

光栅化

Pixel：picture element
由三个红蓝绿三个颜色组成

屏幕空间

像素的坐标如上图由（x,y）组成；
像素的坐标取值在（0,0）到（width-1,height-1）之间；
像素的中心在（x+0.5,y+0.5）;
屏幕覆盖范围（0,0）到（width,height）

视口变换

Canonical Cube to Screen(投影得到的标准立方体到屏幕空间的变换)

将xy平面[-1,1]²转换到[0,width]×[0,height]
转换矩阵如下：

Drawing to Raster Device

为什么使用三角形：

• 三角形是基础多边形；
• 其他多边形可以拆成三角形；
• 三角形一定是平面；
• 可以很容易定义内部和外部；
• 可以根据三个顶点的关系，在三角形内部进行插值，以得到渐变的值。

判断像素与三角形的位置关系：

• 采样：利用像素中心对屏幕空间进行采样，判断像素中心是否在三角形内
  
• inside(tri,x,y)函数：
  三次叉乘，叉乘可以判断一个向量在另一个向量的左侧或右侧，（这里必须保证三角形的绕序）
• 加速光栅化：
  使用轴向包围盒（AABB）：
  包围盒外的不需要进行判断，包围盒内的执行之前的循环。
  
  Increment Triangle Traversal：
  判断每一行的最左和最右，只判断里面的点。

Antialiasing（反走样）

Antialiasing

Sampling Artifacts：采样出现的视觉错误，比如锯齿、摩尔纹等。

Antialiasing Idea：在采样前，先对图像进行模糊

频域分析

傅里叶级数展开：任何一个周期函数可以写成一系列正弦和余弦函数的组合表示
傅里叶变换：

高频率函数需要更高频率的采样：

Aliases：同样的采样方法采样两种频率截然不同的函数，其采样结果却相同，这种现象被称之为走样。

滤波

原图：

高通滤波：高频信号代表边界

低通滤波：模糊处理

同时去掉高频和低频信息

滤波=平均=卷积

卷积：

时域上两个信号的卷积，是两个信号在频域上的乘积；时域上两个信号的乘积，是两个信号在频域上的卷积。

采样

采样 = 复制频谱

走样 = 频谱的混叠

去除走样的方法：

1. 增加采样率
2. 反走样：先做模糊（低通滤波），再做采样
   

对每一个像素覆盖的区域的颜色求一个平均值（低通滤波）

Multi-Sample Antialiasing（MSAA）

假设一个像素被划分为若干个子像素，并对子像素的值进行平均。

缺点：计算量增加。

其他反走样技术

FXAA（Fast Approximate AA）：一种后处理方法，找到图像的锯齿位置，并去掉
TAA（Temporal AA）：复用上一帧的结果

Super resolution/super sampling

将低分辨率的图拉大成高分辨率的图，且需要避免锯齿

DLSS（Deep Learning Super Sampling）：利用深度学习猜缺失的细节

课程地址

GAMES101

二维变换

Scale

此外，如果要沿y轴翻转，则s_x=-1,s_y=1即可，沿x轴翻转同理

Shear（切变）

如果要计算变换矩阵，只需找到变换前后点的对应关系，再将其转换成矩阵表示即可。

Rotate（以原点为中心，逆时针）

Linear Transformation

Translation

然而上式无法转换为二维的变换矩阵
只能写成如下的形式

因此需要引入齐次坐标，以便于将所有变换写成统一的形式

Homogeneous Coordinator

由于向量不需要平移变换，因此向量的第三个数为0，且分别对待点和向量可以保证如下性质。

齐次坐标具有下面性质

因此，点加点表示两个点的中点
齐次坐标表示仿射变换（先线性变换，在平移）：

各种变换的齐次坐标变换表示：

Inverse Transform：
即乘以这个变换的逆矩阵，其意义是该变换的逆变换

需要注意

变换的顺序十分重要，否则可能无法得到想要的结果。
此外，矩阵的应用顺序是从右到左，即最右边的矩阵是第一个变换

变换的合成：

可以先将所有的变换相乘为一个矩阵，再对所有点进行变换。

变换的分解：
加入以点c为中心进行旋转，则如下

三维变换

三维的齐次坐标与二维的类似

其他变换的齐次坐标表示均与二维情况类似，但需要额外考虑z轴。

三维Rotate

其中需要注意的是旋转操作，以x、y、z轴旋转的矩阵分别如下：

其中绕y轴的旋转有所不同，可以考虑右手螺旋定则以解释。

给定旋转轴n和旋转角$\alpha$，默认以原点为起点，所得出的旋转矩阵如下：

四元数也可以用于表示旋转（视频中没有提到具体内容）

View/Camera Transformation

model transformation: 模型自己的变换
View transformation: 相机位置的变换
projection transformation: 投影平面上

相机的三个属性：

View transformation: 将相机移到原点，向上方向为y轴正方向，看向z轴负方向，所有物体按照相机的变换方式进行变换

变换的方式如下

Projection Transformation

Orthographic Projection

只需要去掉z的值，并将结果放倒[-1,1]²的矩形上，就是正交投影

归一化的长方体可以理解为显示区域

Perspective Projection

回顾齐次坐标的性质:

透视变换:

先将远平面挤成近平面，然后再做正交投影

如何挤压:

挤压时齐次坐标的变换方式：

假设变换后的近平面和远平面的z值不变，则有

原文链接

Rendering Elimination: Early Discard of Redundant Tiles in the Graphics Pipeline

论文要解决的问题

由于帧与帧间的连续性，连续两帧的同一区域有可能相同，因此会产生大量的冗余计算，本文将尝试减少这种冗余计算，以提高TBR GPU的渲染效率。
如下图是一组安卓游戏的两个连续帧之间平均相同的tile所占的百分比，以此可以看出，在传统的pipeline中连续帧之间存在大量的冗余计算。

传统Tile-Based架构

Command Processor：用于解析Drawcall和确定向pipeline提交的顶点数据的格式；
Vertex Fetcher：创建顶点的输入流（包括顶点的坐标和颜色等信息）；
Vertex Processor：用于执行Vertex Shader；
Primitive Assembly：将顶点分组成三角形或其他原语，并执行裁剪（clipping）和剔除（culling）技术；
Polygon List Builder：将图元信息存储至Parameter Buffer中，这些信息以一种利用局部性并提高Raster性能的格式存储。该单元也决定每一个图元驻留在哪些tile中；
Tile Scheduler：负责获取给定tile的图元数据，并将其发送至Raster Pipeline；
Rasterizer：将三角形的顶点信息进行插值运算成片元（光栅化）；
Early Depth Test：用于丢弃被先前片元遮挡的片元以使其不会被片元着色；
Fragment Processor：执行fragment shader；
Blending Unit：用于混合先前计算的颜色（用于半透明物体），并将最终结果放到Color Buffer中；
当一个tile的所有图元被计算完毕后，Color Buffer的数据将被刷到内存的Frame Buffer中，并执行下一个tile的Raster Pipeline；

本文所提的优化方式 Rendering Elimination

整体框架

首先可以确定的是，如果一个tile与上一帧的tile的输入包含相同的场景常量和所有覆盖该tile的图元的信息，则这一个tile的最终颜色将与上一个tile的最终颜色相同，因此可以绕过这个tile的整个Raster Pipeline。

但由于这一数据所占的空间很大，因此读取起来比较低效，因此通过对一个tile进行签名的方式进行对签名进行存储至Signature Buffer中。

如上图，Signature Unit计算一个tile的签名，并将其存放在Signature Buffer中。与此同时，Polygon List Builder将图元数据存放在Parameter Buffer。当tile被调度到Raster Pipeline时，将检查该tile的签名是否与上一帧的签名进行对比，如果相同，则跳过Raster Pipeline，并不更新Frame Buffer。

实现需求

由于每一个图元都有可能覆盖任何一个tile。这导致只有所有几何数据都被处理完才能知道这个tile的完整输入，以计算签名。这需要在计算签名时重新将这个tile的数据从Parameter Buffer中读出并进行计算，这是十分低效的。因此，本文提出一种，增量的签名计算方式。无论图元以什么顺序，发送至Signature Unit，该单元将之前的签名与当前场景常量或原语的顶点数据通过如下算法进行计算，并将其重新写到Signature Buffer中。只要最终的tile相同，则该签名值便相同。由于签名的计算和Geometry Pipeline阶段相互重叠，因此可以节省大量的时间。

此外，本文做了大量实验，没有发现一例hashing冲突的结果。

Tabled-based CRC32 Computation

由于计算CRC32需要花费较长的时间，因此为加速这一过程，可以所有可能输入对应的预计算结果存入Look-up Table中，然而如果消息B的长度为n，则需要2ⁿ。因此将输入的消息B划分为B₁…B_kk个一字节的块，每个块对应一个LUT，在减少存储的同时，提高了计算效率。

其中第一个块的LUT为B₁后面跟k-1个字节的0的输入对应的CRC32，第二个块的LUT为B₂后面跟k-2个字节的0的输入对应的CRC32，以此类推。消息B对应的CRC32为这几个LUT中的结果的异或。

Tile输入字节流的结构

如上图所示，若需要两个Drawcalls:Drawcall F(fill,C)和Drawcall S(stripes,A,B)时，其结构如图下方tile的输入字节流结构。

Signature Unit(SU) Architecture

当SU接收到一个新的数据块时，需要计算它的CRC并通过增量的方式更新所有该数据块覆盖的tile的CRC。

对于顶点信息：

1. SU使用Compute CRC Unit计算该图元所有的顶点信息的签名，结果被存在Primitive CRC Register中。
2. 由于顶点信息的属性数量是可变的，以此将该数据块的长度存在Shift Amount P Register中。
3. 利用Polygon List Builder将所有该图元覆盖的tile的id存在OT Queue中。
4. 在计算完该图元的签名后，Signature Unit遍历所有OT Queue的Tile id，并从Signature Buffer中读取对应id的CRC签名，将其发送至Accumulate CRC unit中，此外图元消息的长度也被发往该单元，以此计算算法1中的CRC_Temporary。

对于常量信息：
与顶点处理信息方式类似，但签名需存在Constant CRC Register中，长度需存在Shift Amount C Register中。

由于相同Drawcall的多个图元可能会覆盖相同的tile，但对应的场景常量每个tile中只能被考虑以此。
因此本文使用位图的方式以解决该问题。该位图的长度与tile的数量相等。当位图中的一个位置被设置，则说明对应tile的场景常量签名已经被计算过。当GPU处理下一个Drawcall时，位图需要被清空。
在遍历OT Queue时，首先检查该tile的对应位是否被设置，若被设置，只需要通过Primitive CRC进行更新CRC；否则，设置该位，并更新两次CRC，第一次利用Constanta CRC进行更新，第二次利用Primitive CRC进行更新。

Compute CRC 和 Accumulate CRC Unit的结构

Compute CRC Unit

用于实现算法1循环中的前两步。

由于每个数据块的长度不固定，因此将其拆分为64bit的固定长度，并利用算法2计算CRC。

其中CRC_out存入Primitive CRC或Constant CRC中，ShiftAmount存入Shift Amount P或Shift Amount C中。

Accumulate CRC Unit

用于实现算法1循环中的第3步

由于数据块的长度不固定，左移的量也不固定，因此需要采用增量的方法计算CRC，如算法3所示。

Sign subunit

Sign subunit对64bit的字块使用如Tabled-based CRC32 Computation小节所述的方法，每一个字节对应一个LUT，因此只需要8个LUT即可，其输出结果为8个LUT结果的异或。

Shift subunit

与Sign Subunit结构类似，由于CRC32为32位，而且左移只需要在后面补0即可，因此实际计算的CRC_Accum只与这32位有关。

评估方法

GPU模拟框架：Teapot

能耗计算模型：McPAT

Baseline GPU：ARM Mali-450 GPU

实验结果

benchmark分为三类：css到top为静态相机的benchmark，mst为高动态相机的benchmark，abi到tib为部分为静态相机部分为高动态相机。
注意本文所提方法只能去除颜色和输入都相同的部分，即图15a中黑色的部分。

RE与Fragment Memoization和Transaction Elimination的对比

上图为三种结构的对比，可以看出RE可以根据drawcall的输入绕过整个Raster Pipeline，FM可以根据shader的输入绕过Fragment Shader，TE可以根据Color Buffer是否相同绕过写Frame Buffer的过程。

其中，值得注意的是 Fragment Memoization需要将shader输入的签名和最终输出的颜色缓存下来，然而由于最终输出的颜色所需额内存过大。因此直接存储一帧的输出颜色是不现实的，因此该方法使用了一种同时渲染两个连续帧的架构PFR，该架构可以保证同时渲染两个连续帧的相同块，以便于对比。然而，这只能去除同时渲染的帧的冗余，不能去除不同时渲染的连续帧的冗余。

RE与PFR-aided Fragment Memoization的对比试验如下：

需要注意的是hop的benchmark，它渲染屏幕的大部分只有少数重复的fragment，而且这些fragment大部分都是完全黑的（可能考虑tile颜色相同时，有可能输入可能不同，RE只要输入有一点不同就要重新渲染，而FM只要颜色相同就不需要重新渲染。）

RE与Transaction Elimination的对比试验如下：

RE可以完全跳过raster pipeline 这可以节省大量的执行时间，而TE只能跳过写入Frame Buffer的执行时间，因此只要存在重复输入的tile，RE基本上优于TE。

总结

优点：RE相比于baseline gpu能平均提升1.74倍的运算性能，并可以在GPU和主存上的能耗分别减少38%和48%。
缺点：

1. 无法检测输入不同但颜色相同的tile
2. 计算Hash可能会产生碰撞对，但该几率极小，而且由于帧与帧间的连续性，hash相同两个tile也及其相似，此外由于帧率较高，人眼实际上是无法分别错误的。

以下是个人见解：该方法很好地用硬件去除了帧间计算的冗余，可以考虑利用该方法或者TE、FM结合H.264编码以提高编码效率。

原文链接

Equalizer: A Scalable Parallel Rendering Framework

论文要解决的问题

本文提出了一种可以应用于多种并行场景下的并行渲染框架，该框架的主要贡献如下：

1. 提出一种可以灵活配置图形系统资源的概念：compound trees
2. 通过compound trees可以简单指定并行任务的分解和图形合成方法
3. 根据compound tree可以自动分解和分布式执行渲染任务
4. 支持并行渲染合成时的深度检测和α-混合
5. 完全去中心化的架构，并提供网络swap barrier（用于同步）和分布式object方法
6. 支持低延迟的分布式帧同步和图像合成
7. 最小化的侵入式编程模型

基础概念

equalizer的网络传输只需要交换基础的渲染参数，不传输大量的图形质量和数据。应用程序可以通过equalizer基于分布式对象或消息传递实现高效的动态数据库更新。
此外，Equalizer的另一个优点是灵活且可扩展的配置，因此可以轻松地指定任务分解和图像合成方式。
Equalizer的网络层支持消息传递和分布式对象的创建。通过创建分布式对象的子类，可以创建静态或版本化的对象。对象可以使用集群中的唯一识别符进行处理，这允许对象的远程映射。版本化对象通常用于特定帧的数据，其中为每一个新帧创建一个新的版本。版本信息会通过Equalizer正确地传输到应用程序的渲染代码。这种机制使得分布式变得简单。

系统架构

并行渲染的配置由应用程序或用户提供的配置文件进行初始化，服务器页启动和控制应用程序提供的渲染客户端。
虽然高级别的Euqualizer使用客户端-服务器方法（C-S）但其构建在对等网络层(p2p)上。目前Equalizer提供了TCP/IP套接字和无线带宽技术（InfiniBand）的实现。

应用程序

Equalizer中的应用程序单独驱动渲染，也就是说，它只执行主渲染循环，但并不实际执行任何渲染。
渲染客户端通常与应用程序具有相同的可执行文件，然而在更复杂的实现中，渲染客户端可能是一个瘦渲染器，只包含应用程序指定的渲染代码。
服务器将渲染客户端部署到所有配置指定的节点中。

Equalizer简化的执行流图如下：

渲染客户端

渲染客户端不必执行主循环，由Equalizer完全控制。
渲染客户端由如下几个线程组成：节点主线程、网络接收线程和每一个GPU一个的渲染任务线程。
客户端实现节点主循环用于接收网络事件并进行处理，网络数据包括渲染任务参数，基于此，客户端库设置渲染环境并调用应用程序提供的任务方法。渲染环境包括使用正确的渲染线程，提供任务方法包括视口、平头椎体、视角矩阵和sort-last的数据范围。
所有任务都有默认实现，只有应用程序特定的方法需要实现，包括frameDraw()方法。比如sort-first和sort-last方法。

Equalizer服务器

Equalizer服务器使用应用程序的特定配置为接收到的应用程序的请求提供服务。它服务这些请求通过使用特定的配置、启动节点上的渲染客户端、决定一帧的渲染任务和同步完成帧。
服务器为应用程序维持配置，这有利于跨应用的负载均衡、资源预留和系统资源管理。
配置由两部分组成：

• 第一部分是分层的资源描述
• 第二部分是compound tree，用于说明资源如何被渲染。

分层的资源描述如下表所示：

其中每一个node代表一个CPU核，pip为node上运行的线程（一个线程对应一个GPU）。此外，window代表屏上或离屏的渲染。channel代表视口的一部分（tile-based）。

资源配置的例子如下所示：

Compound Trees

Compound tree结构描述了渲染和合成任务。
由于渲染是异步的，因此Equalizer引入了一个配置延迟，它定义了最慢的渲染线程可以落后多少帧，以便于充分利用资源。
一个compound提供output frames表示向其他节点输出帧，input frames表示从其他节点接收的帧，input frames和output frames用name链接。

一个简单的Compound配置如下所示，其中viewport的四个参数分别为x,y,宽和高。
range代表渲染的数据集的比例。

合成的配置如下所示：

Compound Tree配置案例

sort-first

sort-last

Stereo sort-first

其中Eye表示VR中的左眼或右眼

实际案例

Equalizer实现

需要提供Channel::frameDraw()的实现，用于将渲染例程通过Equalizer并行渲染。cull()和draw()函数由frameDraw进行调用。
此外，渲染参数如摄像机数据被实现为分布式对象，该应用程序的子类基于eqNet::Object基类，并为基类提供数据的指针和大小以便于网络部署。在初始化期间，对象在渲染会话中注册。在每一帧的开始，将提交该对象的一个新版本，并由Equalizer将新版本传递给渲染回调，Equalzier将其对象实例同步到给定版本。
渲染结构由Equalizer基于compound tree进行收集。
高级应用程序可以为渲染的任何阶段提供实现，比如可以覆盖Channel::frameAssemble(),以实现帧图像的自定义合成。
虽然compound tree中的值是固定的但可以根据应用程序的需求（比如负载均衡）进行更新。

Equalizer的UML图如下所示：

总结

Equalizer提供了一种非常便于配置的并行渲染框架，这十分利于在此之上设计负载均衡算法。此外，该框架可以实现渲染的任何阶段，以设计自己的渲染逻辑，使得该框架没有那么死板。程序员似乎不需要考虑Equalizer内部的通信过程，只需要通过eqNet便可以轻松实现自动的分布式对象。

原文链接

Video Encoding Acceleration in Cloud Gaming

论文要解决的问题

本文尝试在云游戏系统中，通过获取游戏引擎中的物体信息（包括位置、运动等信息），绕过服务器在最终为游戏的视频流编码的运动估计过程，以提高编码效率。

一些基本概念

云游戏也被称为游戏即服务（GaaS），大致可被分为三类：

1. Remote Rendering GaaS(RR-GaaS)：游戏逻辑、游戏渲染、视频编码等操作均在服务器侧执行，客户端侧只对视频进行解码和显示。
2. loacl Rendering GaaS：客户端负责游戏渲染，而服务器侧只运行游戏逻辑。
3. Cognitive Resource Allocation GaaS：部分计算操作既可以在服务器侧运行，也可以在客户端运行，这其取决于网络、客户端和服务器的条件。

运动估计：运动估计的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。（摘抄自百度百科）

传统的云游戏架构

如图所示，游戏在客户端和服务器端执行，客户端负责收集用户交互、解码视频；服务器端负责运行游戏逻辑、渲染游戏画面和将对游戏视频流进行编码。
该模式的缺点在于由于大量运算在服务器端运行，这会产生较大的功耗，可扩展性较低（无法同时服务较多的玩家）

本文所提的云游戏架构

主要

该架构在传统的云游戏架构中实现一个interface，用于收集游戏引擎中的信息并将其转换为视频编码器可以使用的信息。通过这些信息跳过或简化编码操作，比如运动估计过程，使得视频编码速度更快。
此外，需要在游戏引擎、interface和视频编码侧做如下操作或改动：

1) 游戏引擎：
主要收集object的位置和朝向，作为object info传输至interface。此外，游戏引擎需要生成一些其他数据，作为game info和game engine info传输至interface。

• game info：object的数量、每个物体的大小（这里应该是估计值）和游戏帧的大小；
• game engine info：游戏引擎的坐标系统

伪代码如下：

2) interface：
interface将接收自游戏引擎的信息转换为视频编码器可以识别的信息。此外，interface还需要接收一些视频编码器的信息，包括视频帧大小、视频帧坐标系统和FPS。
interface利用上述消息，在初始化阶段进行配置，使其能够将游戏信息转换为视频编码器的信息。
在配置阶段结束后，游戏引擎将object的信息发送至interface，interface对其进行转换。

interface的伪代码如下：

如上述代码所示，interface需要将游戏引擎产生的信息转化至笛卡尔坐标系，此外，需要计算一个用于转换object位置和大小的扩展因子。（这是由于游戏帧和视频帧的大小可能不一样）最后，生成object在连续两帧间的运动向量。

3）视频编码器侧：
运动估计从一个起始点开始，在参考框架中得一个区域进行搜索，以便于找到与当前分区最相似的区域。在H.264/AVC标准中，起始点由PMV计算得到，PMV由当前分区的上、左、右分区的运动向量计算生成。

所提方法

背景宏块（background MB）：没有位于任何object边界内的宏块
前景宏块（foreground MB）：位于任何object边界内的宏块

如果object的运动向量接近PMV，则可以推断object的运动向量和最终的motion vector（MV）相同的概率是很高的，因此可以跳过或简化运动估计过程。否则，需要执行完整的运动估计过程。
此外，也可以用此方法检测背景宏块。可以认为，所有背景宏块的运动向量是相似的，因此可以通过计算一个背景宏块的运动向量即可。

所提算法框图如下所示，其中Obj_MV表示object的运动向量（来自游戏引擎），BK_MV表示背景宏块的运动向量，Thr表示阈值。

需要注意的是，需要检测当前帧的背景宏块在上一帧是否也是背景宏块或者在某一个object的后面，如果是后一种，需要执行普通的运动估计过程。
此外，对于每一帧的第一个宏块，需要执行普通的运动估计过程，以获得BK_MV。

实验及分析

直接上结论：

1. 本文所提方法在保证接近于传统H.264的编码的视频质量的同时，总编码时间降低了最多24%；
2. 由于减少了运动估计过程，因此根据文中所提公式，本文所提方法是传统编码器所需能耗的44%；
3. 本文所提方法不止适用于云游戏系统，而且适用于大多数可以提供object运动信息的应用场景。

个人认为本文设计的方法比较巧妙地解决了在云游戏系统场景下视频编码器中对object运动的冗余计算。但是该方法只适用于游戏渲染负载完全在服务器侧的场景，并不适合于offloading的场景。

近期更新

原文链接

Equalizer 2.0–Convergence of a Parallel Rendering Framework

Equalizer简介

开发Equalizer应用的核心任务是将渲染的逻辑与应用程序逻辑分离。但需要调用rendering call时，请求Equalizer渲染一帧。由Equalizer分解和同步渲染任务，并在给定的渲染上下文下并行执行，该上下文是从特定系统配置中抽象出特定应用程序的渲染算法的核心实体。该渲染上下文指定了并行渲染的最小抽象，并给出以下参数：

Buffer：该参数受当前eye pass、eye separation和立体影像设置的影响。
Viewport:二维像素viewport限制渲染区域，该像素viewport受目的viewport和由sort-first分解的viewports的影响。
Frustum：由glFrustum定义，被用于
设置OpenGL的投影矩阵，该frustum受目的视角、sort-first、像素和子像素分解，头部跟踪矩阵和当前eye pass的影响。
Head Transformation：对于平面视角，这是一个单位阵；对于沉浸式渲染，被用于设置多视角矩阵中的视角部分。
Range：是一个区间在[0..1]的一维范围。该参数可选，被用于在sort-last渲染模式中渲染适当的数据子集。
View：包括摄像机、模型和其他应用状态等指定视角的数据。

这些配置决定应用程序如何并行执行，包括是哪个部分：描述物理渲染资源（节点、管道、窗口和通道）的部分、描述可视化设置的部分和描述这些资源如何被用于渲染的部分（该部分描述了渲染任务的分解、结果的合并）。

该执行模型是完全异步的，只有在严格需要的地方才会引入同步点。此外，在默认情况下，采用流水线的方式进行渲染，即一些资源在渲染下一帧，而其他的仍在完成当前帧，当渲染完成后便立即呈现其结果。许多操作都可以以流水线的方式运行，包括：应用程序事件处理、任务计算、负载均衡、渲染、图像回读、压缩、网络传输和合并。

新的分解模式

时间复用

也被称为AFR或DPlex，但不能减少用户输入到屏幕输出间的延迟，更适用于无交互的渲染。此外，要在多线程、多GPU配置下工作，应用程序需要支持异步运行渲染线程。

tile and chunk

tile和chunk分别是sort-first和sort-last的变体，渲染任务放在服务器中心队列中通过轮询，被所有源通过进行排队和处理。

基于像素的分解

通过在图像空间中交叉行或列分解目标通道，每一个通道不能通过视椎体剔除减少几何负载，这是由于每个通道都使用了相同的视椎体。然而，片元的负载由于像素的交叉分布线性地减少，并保证负载均衡。该方法对Equalizer的应用程序透明，并默认使用模板缓冲区将对应像素传输到目标通道。该方法类似于sort-first，但并没有分解viewport。

基于子像素的分解

类似于像素分解，但是将单个像素分解为若干个子像素，每个通道负责一个子像素的渲染，最终通过求平均等方法合并像素。该功能对应用程序不是透明的。

Equalizer

sort-first和sort-last的负载均衡

Equalizer通过利用过去的渲染时间和帧与帧之间的连续性调整不同通道渲染视口的范围以保证负载均衡。Equalizer实现了两种不同的算法，load_equalizer和tree_equalizer。

load_equalizer

load_equalizer利用1D或2D的网格来存储一帧的计算负载，并映射到每一个通道的负载上，\frac{time}{area}表示该负载。通道被组织为一个二叉树。然后利用equalizer通过对网格上的开销的积分利用算法平衡每一层的两个分支的计算开销。

tree_equalizer

tree_equalizer也是使用二叉树来递归地进行负载均衡，通过对每个树上的所有节点进行累加，并使用其为每棵子树调度一个平衡的负载时间。这个算法没有假设2D或1D的负载分布，只是尝试纠正不平衡的渲染时间。

splite mode

splite mode配置tile的布局：通过二叉树分割代替坐标轴的分割，以生成紧凑的2D tile。

Cross-Segment 负载均衡(CSLB)

Cross-Segment优化n个渲染资源到m个输出通道的资源调度。
view equalizer与平衡各个输出通道的load equalizer一起工作。它监视跨输出共享源的使用情况，并激活他们一平衡所有输出的渲染时间。CSLB的独特之处在于它支持平面和非平面可视化系统的负载均衡，以及将渲染资源灵活地分配到各个输出通道。

动态帧分辨率(DFR)

DFR Equalizer能够通过动态调整渲染分辨率以保持稳定的帧率，当性能允许的情况下，可能会采用更好的采样方法（比如supersample）来提升画质。

Frame Rate Equalizer

framerate Equalizer通过延迟swap buffer的交换时间以使得输出的帧率变得平滑，被用于平滑不规则的应用程序渲染算法。

优化

Region of interest

感兴趣的区域是屏幕中显示的内容，通过使用ROI来优化load_equalizer,使得load equalizer使用ROI将负载网络细化到包含数据的区域（这里的意思可能是只对自己负责的渲染区域的数据进行处理），以减少回读和网络传输。

异步合并

作者并没有针对这一点说明很多，只说明了异步合成是对带有合成操作的渲染的流水线化。这里的合成操作包括图像回读、网络传输和将图像从并行运行的线程装配到渲染线程。

下载和压缩插件

合成步骤的压缩对性能来说是至关重要的一步，不仅可以应用到网络传输步骤，还可以应用于GPU到CPU间的传输。Equalizer支持多种压缩算法，这些算法均被实现为运行时加载的插件，并允许扩展。

线程同步模型

实现三种线程模式：完全同步，绘制同步同步和异步

完全同步：所有线程总是执行同一帧，这使得渲染线程能够从所有的操作中读取共享数据，但会获得更低的性能。
绘制同步：所有线程的绘制操作同步，这使得渲染线程在执行绘制操作时可以读取共享数据，但合并时不行。该模式允许多GPU的机器上的渲染合并和数据同步能够相互覆盖。
异步：所有线程异步执行，渲染线程可以在任何时间渲染不同的帧。该模式最快，但需要应用程序在每个渲染线程中拥有每个可变对象的实例。

后续是应用，待对Equalizer进行全面了解后再更新，暂略

总结

本文最值得关注的点在于提出了不同的几种并行渲染模式，其中基于像素划分和子像素划分的模式能够达到较好的负载均衡，但考虑可能在顶点着色器上会存在冗余计算。