旋转门算法除了平行四边形算法之外，还能用三角形算法来表示。

图遍历算法

图遍历算法是最基本的图算法之一，由指定节点开始，按照一定规则遍历图结构中所有的连通节点，包括宽度优先搜索(Breadth First Search,BFS)和深度优先搜索(Depth First Search, DFS)等核心算法。

作为最基本的图遍历算法，宽度优先搜索算法代表了图遍历算法的计算特性，具有非常重要的研究意义。一方面，BFS算法是最短路径、邻接查询、可达性查询等算法的实现基础，广泛应用于图分割、信念传播统计以及网络社区结构发现等领域;另一方面，BFS算法作为典型的数据密集型算法，体现了数据密集型应用对高性能计算系统的需求，广泛应用于大规模并行计算系统的数据处理能力评测，已经成为Parboil, Rodinia和Graph500等基准测试程序的核心算法。

在实际应用中，图的规模在不断增大，相应的，对图的存储和处理开销不断增加，有效地实现大规模并行BFS算法具有十分重要的意义。

稀疏线性方程组求解法

稀疏线性方程组的求解是对自然科学和社会科学中许多实际问题进行数值模拟时的关键技术之一。在高层建筑、桥梁、水坝、防洪堤的结构设计中，需对变形与应力情况进行模拟；在油气资源探测与分析、数值天气预报、飞行器的动力学分析中，需利用流体力学方程组进行模拟;在进行恒星大气分析与核爆实验时，常需利用辐射流体力学与粒子统计平衡等规律进行模拟。在对这些问题进行分析模拟时，通常利用偏微分方程建立数学模型。在对偏微分方程的离散求解过程中，稀疏线性方程组求解算法扮演着十分重要的角色。在许多不以偏微分方程建模的问题中，稀疏线性方程组求解同样发挥了重要的作用。在空中交通控制、电力线路中的最优电流问题中，需利用数学规划求解;在对采纳某项政策时在某给定条件下对国内、国际多个区域的相应经济指标进行预测时，需利用CGE模型进行分析；在可靠性分析、排队网络分析与计算机系统性能评估中，常利用具有大量状态的离散Markov链进行模拟。在这些问题的求解中，稀疏线性方程组的求解都占有重要位置，并且往往是整个计算过程中的性能瓶颈，稀疏线性方程组的高效求解是计算数学和工程应用中十分重要的课题之一。

解稀疏线性方程组的方法包括直接法(direct method)与迭代(iterative method)两类。直接法指在不考虑计算舍入误差的情况下，通过包括矩阵分解和三角方程组求解等有限步的操作求得方程组的精确解，因此又称精确法;迭代法指给定一个初始解向量，通过一定的计算构造一个向量列(一般通过逐次迭代得到一系列逼近精确值的近似解)，向量列的极限为方程组理论上的精确解。迭代法对存储空间的需求低，在求解高阶非病态稀疏线性方程组方面具有一定优势。然而，迭代法不适合求解病态问题，性能因问题而异，并且面临精度控制、收敛速度慢或不收敛等问题。与迭代法相比，直接法的通用性好，求解结果精度高，性能稳定。当矩阵分解结果能够被多次后续计算重用以及多右端项时，直接法的优势尤其明显。在有限元分析、模拟电路瞬态仿真等应用领域的商用软件均采用直接法求解器作为标准的稀疏线性方程组求解器。但直接法的缺点在于对存储资源要求较高，无法处理高阶稀疏矩阵。

一般来说，迭代法的求解速度高于直接法。但是，如果使用直接法时矩阵分解过程能够被很多后续计算重复使用，则后续的三角阵求解可以非常快速实现，此时直接法在性能上具有优势。典型例子是模拟电路瞬态仿真，这时需要多次以Newton-Raphson方法求解非线性方程，每一次求解均会在工作点附近展开为线性方程，而且所有线性方程的矩阵分解方式都是固定的，因此求解该类问题最好的方法是直接法。稀疏矩阵的矩阵分解在GPU上的实现是很困难的，主要难点在于现有算法的数据依赖性导致可利用的并行性不足。此外，矩阵元素的排列顺序对计算过程中间结果矩阵的非零元素个数有很大影响，同时矩阵分解后的非零元素的分布与原来矩阵可能很不相同。

迭代法的理论基础相对复杂，并且具有多种不同的具体算法，但其基本形式均为从一个猜测解出发，通过多次迭代逐渐收敛，当误差满足一定条件时迭代中止。共扼梯度法(CG)是迭代法的主流方法之一，特别适合于特征值为良态分布的对称正定方程组；其它迭代法包括Jacobi、逐次超松弛(SOR)、广义极小剩余(GMRES)、预条件共扼梯度(PCG)等。迭代法的核心算法是稀疏矩阵向量乘(SpMV)，因此实现SpMV的高效并行结构也是实现迭代法的基础。

直接法由高斯消元法发展向来，求解过程包括矩阵排序(matrix ordering)符号分解(symbolic factorization)、数值分解(numerical factorization)、三角方程组求解((triangular solves)四个步骤。其中，矩阵排序和符号分解属于预处理部分。矩阵排序通过启发算法置换稀疏矩阵的行列，试图在后续计算中维持矩阵的稀疏性或数值稳定性。符号分解则是预先对矩阵分解后的稀疏结构进行预测，预先分配存储空间并记录数据相关性。直接法的计算瓶颈在于数值分解部分和三角方程组求解部分，高效的直接法求解依赖于二者的高效实现。

对于一个稀疏线性方程组是选择直接法还是迭代法求解，一般有如下原则：对于低阶矩阵或大型带状矩阵所对应的线性方程组，用直接法求解；而对于大型(非带形)矩阵所对应的线性方程组，用迭代方法求解。实际上，选用何种方法还要看具体的应用背景，比如，对于线性规划和一些结构工程应用，只有直接法是切实可行的。对于精度要求很高的问题，还可以采用由直接法得到初始解再用迭代法进行迭代的方法求解，这种方法称为迭代精化法。

DFSA算法可采用各种方法预测待识别的标签数量，然后动态调整最优帧长，与FSA相比，系统效率有明显改善，接近36．8%。但是，当标签数量较多（特别是标签数量大于500）时，采用由预测标签数量设置最优帧长的方案会使系统效率急剧下降。因此，在标签数量较多的情况下，为了使系统效率得到提高，EPCClass1Gen2标准中采用了Q值算法，该算法可以实时自适应地调整帧长 。

Q值算法

在Q值算法中，阅读器首先发送Query命令，该命令中含有一个参数Q（取值范围0～15），接收到命令的标签可在[0，2Q－1]范围内（称为帧长）随机选择时隙，并将选择的值存入标签的时隙计数器中，只有计数器为0的标签才能响应，其余标签保持沉默状态。当标签接收到阅读器发送的QueryRep命令时，将其时隙计数器减1，若减为0，则给阅读器发送一个应答信号。标签被成功识别后，退出这轮盘存。当有两个以上标签的计数器都为0时，它们会同时对阅读器进行应答，造成碰撞。阅读器检测到碰撞后，发出指令将产生碰撞的标签时隙计数器设为最大值（2Q－1），继续留在这一轮盘存周期中，系统继续盘存直到所有标签都被查询过，然后阅读器发送重置命令，使碰撞过的标签生成新的随机数 。

根据上一轮识别的情况，阅读器发送Query－Adjust命令来调整Q的值，当标签接收到Query－Adjust命令时，先更新Q值，然后在[0，2Q－1]范围内选择随机值。EPCClass1Gen2标准中提供了一种参考算法来确定Q值的范围.其中：Qfp为浮点数，其初值一般设为4．0，对Qfp四舍五入取整后得到的值即为Q；C为调整步长，其典型取值范围是0．1

该算法在参数C的辅助下对Q值进行动态调整，但是C太大会造成Q值变化过于频繁，导致帧长调整过于频繁，C太小又不能快速地实现最优帧长的选择。因此，研究者们对Q值的调整进行了各种优化 。

基于最大吞吐量调整Q值的算法

文献提出一种基于最大吞吐量对Q值进行调整的算法，其中定义了以下变量：Nt为已识别的标签个数；N为识别标签所需的总时隙数；NC为冲突时隙的个数；nu为上一轮未识别的标签个数；e为冲突时隙中的平均标签个数；PC为冲突时隙所占的比例 。

这些参数之间的关系为PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由于Aloha类算法的最大吞吐量为0．368（e－1）[5]，该算法以此作为调整Q值的依据。当系统吞吐量达到或接近0．368时，阅读器仅需调用2Q－1次QueryRep命令，而不需要在接下来的盘存周期中调整Q值。当吞吐量小于0．368时，根据未识别的标签个数nu来调整Q值 .

基于分组的位隙Aloha算法

文献提出一种基于分组的位隙Aloha算法，该算法采用位隙Aloha算法中的128位预定序列，代表128个位隙。若某个标签选择了第i个位隙，则将第i位置1，其余各位都置0。当标签数量为15时，位隙Aloha算法可获得最大吞吐率88．38%，但随着标签数量的增加，算法性能急剧下降 。

因此，基于分组的位隙Aloha算法通过对标签进行分组来提高算法的性能。该算法在查询命令中设置了一个位隙计数器的参数Q（Q为整数，且0≤Q≤15），当标签收到阅读器发送的查询命令后，在[0，2Q－1]范围内生成一个随机数，即代表选择了相应的位隙，只有选择了0的标签才会立即响应。同时，该算法根据冲突位隙数动态地对Q值进行调整：当冲突位隙数小于11时，Q减1且最小为0；当冲突位隙数在11～20之间时，Q保持不变；当冲突位隙数大于20时，Q加1且最大不超过15 。

综上所述，基于Aloha的防碰撞算法原理简单、容易实现，对新到达的标签具有较好的适应性，尤其对于标签持续到达的情况有较好的解决方案，但该类算法存在几个明显的缺点：①响应时间不确定，即同一批标签在不同时刻进行识别所需要消耗的时间相差很大；②个别标签可能永远无法被识别；③Aloha算法达到最佳吞吐率的条件是其帧长等于标签数量，当需要识别的标签数量较多或选择的帧长与实际待识别标签数量不符时，系统性能将明显下降。而基于树的算法则很好地解决了这些问题 。