[0033] 本发明的一种面向数据并行计算容错的快速并行复算方法包括：
[0034] (1)错误快速恢复方法
[0035] 在数字地形分析领域，数字高程模型拥有海量的数据。处理这样的高程模型数据将会耗费很长的计算时间和需要高效的I/O处理。当一个进程失效时，该计算任务需要重新启动以及所有的计算任务不得不回滚到未出错前的位置重新计算。为了提高处理的效率，一般将海量数字地形高程模型数据划分成许多小的数据块，采用多线程或多进程方法同时处理这些数据块以提高计算的效率。在出现某个数据块对应的计算任务出错时，本发明将该数据块重新划分成更小的数据块，并使用空闲进程进行快速并行计算，从而提高了纠错的效率。该方法称为快速并行复算方法。
[0036] 快速并行复算采用二次冗余策略，即将一个数据块分发到两个进程进行计算，其中一个称为计算进程，另外一个称为备份计算进程。当两个进程计算完毕并将结果发给主进程，主进程将会比较结果是否一致。若不一致，主进程会再次划分该数据块成更小的数据块，并分发法给空闲的进程进行快速计算，该过程称为复算进程。
[0037] 为了简化问题的讨论，下面是一些基本定义。设一个进程集合P＝{P1,P2,…,Pn},其中Pi为第i个进程，数据块集合B＝{B1,B2,…,Bn},其中Bi为待处理的第i个数据块，数据结果集R＝{R1,R2,…,Rn},其中Ri对应第i个数据块的计算结果。
[0038] 本发明快速并行复算方法包括六个步骤，给出如下：
[0039] 步骤1：数据分发。主进程按照事先划分的数据块进行数据分发。为了支持冗余计算，每一个数据块需要分发给两个计算进程。例如，将数据块B分发给进程P和P’。
[0040] 步骤2：冗余计算。在双冗余计算策略下，两个计算进程P和P’分别计算同一个数据块B，R和R’分别为它们的计算结果。
[0041] 步骤3：检错。主进程收到两个进程的计算结果R和R’，然后进行结果比较。如果结果一致，表明计算准确，则主进程保存结果。否则结果不一致，表明计算结果有错，则需要重新划分该数据块和重新计算。
[0042] 步骤4：数据块再次细分。一旦发现该数据块存在计算错误，则主进程将该数据块再次划分为4或者16个子块并再次分发给空闲的计算进程。
[0043] 步骤5：复算。复算进程接收数据子块，并进行计算和返回结果给主进程。
[0044] 步骤6：结果融合。主进程将收到的子块结果进行融合得到该数据块的结果，并保存。
[0045] (2)结果错误检测方法
[0046] 为了提高检错的效率，采用多线程技术并发地检查每个数据的计算结果是否正确。在共享内存模式下，主节点启动多个线程，每个线程负责接收计算进程及其副本进程对某个数据块的计算结果，并进行结果比较。结果检测步骤如下：
[0047] 步骤1：主进程为每个数据块创建一个线程。该线程负责将该数据块分发给一个计算进程和一个副本进程，然后等待接收结果。
[0048] 步骤2：一旦进程计算完毕，并请求发回结果，线程分别接收来自计算进程和其副本进程的结果。
[0049] 步骤3：接收完毕后，线程开始比较结果有无错误。两个结果对应的每个单元的值的差σ给出如下：
[0050] σ＝Rij-R’ij，i＝1,..,m；j＝1,..,n,
[0051] 如果σ＜ξ,则差值在容许的范围内，否则认为误差大于许可值，累积误差数k加1，即k＝k+1。这里ξ误差上界。
[0052] 步骤4：计算误差率，计算方法如下：
[0053]
[0054] 这里，k为误差累计数。
[0055] 步骤5：当误差率r达到阈值ε时，即r>ε,则说明出现计算错误。这里ε由具体算法确定。
[0056] (3)检错与纠错交错进行的复算方法
[0057] 一旦计算进程与其副本进程的计算结果不一致，则复算过程被启动来快速纠错。线程按照划分原则将出错的数据块再次划分为4个子块，然后分发给四个复算进程进行计算。复算进程计算完成后将结果发给线程进行结果融合。
[0058] 由于检测完整个数据块以后再进行复算，线程检测时间和复算时间开销比较大。如果将数据块按照划分原则进行逻辑划分，比如划分成4个逻辑子块。当计算进程和其副本进程计算完成第一个逻辑子块时，将该子块的结果发送给线程进行比较，然后继续执行第2个逻辑子块，使得对第1个逻辑子块的计算结果正确性检测和第2个逻辑子块的计算同时进行，从而提高了系统的效率。
[0059] 如图1所示，数据块B0被逻辑地划分为4个逻辑子块B00、B01、B02和B03，并被分发生给进程P执行。同时，其副本数据块B0'被分发给副本进程P'执行。当B0的第一个逻辑子块B00和B0'的逻辑子块B00'执行完毕，它们的结果立即发给主节点上对应的线程。线程收到逻辑子块的结果后，立即执行比较过程，检查逻辑子块R00和R00'的而结果是否一致。同时，B0上的逻辑子块B01和B0'的逻辑子块B01'继续执行。
[0060] 一旦逻辑子块B00发生错误，则该子块被发给一个新进程进行快速复算。与此同时，逻辑子块B01及其副本B01'的也在进程P和P'上进行计算完毕，其结果R01和R01'被上传和检查，而逻辑子块B02和B02'开始在进程P和P'上执行。
[0061] 这种方法是一种细粒度的复算过程，使得检错和复算纠错同时进行，从而缩短了复算过程的时间。
[0062] 从上面的分析可以看出，快速复算过程比基本的复算过程要节约较多时间。设C为原始数据块的计算时间，D为检错的时间，则基本复算过程的时间开销为C+D+C/4,即为1.25C+D如图2所示。当采用快速复算过程时，由于检错和复算几乎同时进行，逻辑子块B00,B01,B02的计算与结果检测是同时进行的，所以快速复算的时间开销仅等于C，如图3所示。而当逻辑子块B02出错时，需要额外的C/4纠错时间，快速复算时间开销为C+0.25D，如图4所示。
而当逻辑子块B03出错时，需要额外的D/4检错时间和C/4纠错时间，快速复算时间开销为
1.25C+0.25D，如图5所示。
[0063] 实施例：
[0064] 本发明的实施例提供一种基于冗余计算机制的并行计算快速复算方法，如图6所示，包括以下步骤：
[0065] 步骤101：读入数据与数据分发。首先主节点的进程读入数据，按照数据划分策略，启动相应的线程。然后，每个线程依据二次冗余计算策略，将每个数据块分发给两个从节点进程，对数字地形分析中的坡度算法进行二次冗余计算。最后，每个线程等待计算结果。
[0066] 步骤102：冗余计算。每个从节点的进程接收到数据块后发起计算，每个数据块逻辑上划分成4个逻辑子块。当计算完成一个逻辑子块后，进程将逻辑子块的结果发给主节点上对应的线程，然后继续下一个逻辑子块的计算。
[0067] 步骤103：错误检测。每个线程接收到两个进程的逻辑子块的计算结果后，立即进行该子块的一致性检查比较。若两个子块的计算结果一致，则保存结果，否则进入104步启动复算过程。若该子块是最后一个子块，则进入106步进行数据融合，否则等待处理下一个子块。
[0068] 步骤104：重分发子块。线程分发出错的逻辑子块给一个从节点的进程，然后等待结果。
[0069] 步骤105：子块复算。从节点的进程接收到子块数据后，发起子块的计算过程。计算完成后，进程将子块结果发给线程。
[0070] 步骤106：主节点进程融合结果，并保存结果到磁盘。
[0071] 以下进一步详细地说明本发明实施例中的各个细节问题。
[0072] 本发明所涉及的数据均是点集均匀的格网数字地形高程模型数据。
[0073] 如图7所示，错误检测的具体过程：
[0074] 步骤201：线程分别接收到来自计算进程和其副本进程的结果，对于坡度算法其是一个矩阵。
[0075] 步骤202：计算不一致累计数。接收完毕后，线程开始比较两个结果有无错误。若两个结果矩阵对应的每个单元的值的差为σ。如果σ＜0.1,则差值在容许的范围内，否则认为误差大于许可值，累积误差累计数k加1，即k＝k+1(k初始为0)。
[0076] 步骤203：计算误差率。计算方法如下：
[0077]
[0078] 步骤204：当误差率r达到阈值0.15时，即r>0.15,则说明出现计算错误。
[0079] 如图8所示，快速并行复算的具体过程：
[0080] 快速并行复算的原理是利用线程检错和进程复算纠错进行，使得检错过程和复算过程同时进行，达到提升整个容错过程的效率，减小容错的开销。每个数据块逻辑上划分成逻辑子块，每个进程计算完每个逻辑子块就发给主节点上的线程进行比较检错。
[0081] 步骤301：冗余计算。从节点的进程计算每个逻辑子块，完成一个子块的计算后发送结果给主节点的线程。若是最后一个逻辑子块，则线程结束该数据块的计算，否则，继续执行下一个逻辑子块。
[0082] 步骤302：错误检测。主节点上的线程接收到两个从节点的计算进程的逻辑子块的计算结果后，立即进行该子块的结果一致性检查。若两个子块的计算结果一致，则线程融合子块结果。否则，计算结果有错，则进入303步启动复算过程。若该子块是该数据块的最后一个子块，则进入306步进行结果保存，否则线程等待接收下一个子块的计算结果。
[0083] 步骤303：重分发逻辑子块。线程检测到某个数据块的逻辑子块的结果有错，则立即分发出错的逻辑子块给一个从节点的计算进程，然后等待结果。
[0084] 步骤304：子块复算。从节点的进程接收到逻辑子块后，发起子块的计算过程。计算完成后，进程将子块的结果发给线程。
[0085] 步骤305：数据融合。线程收到逻辑子块的计算结果后，将结果融合到该数据块的结果中。
[0086] 步骤306：结果保存。将该数据块的结果保存。
