并行计算中的动态控制：推测性攻击的模型执行

可在www.sciencedirect.com在线获取理论计算机科学电子笔记327（2016）93-107www.elsevier.com/locate/entcs并行计算中基于模型的推测性攻击的动态控制4卡利安·S 1Mohammed M.奥拉马2斯里坎特湾瑜伽3计算科学与工程橡树岭国家实验室美国田纳西州橡树岭摘要在并行运行的模拟中，处理器必须与其他处理器同步，以保持正确的全局计算顺序。 这可以通过分块计算直到保证正确的顺序来完成，或者通过推测性地继续进行最佳猜测（基于本地信息）以及稍后必要时纠正错误。由于投机性尝试的获利长度取决于在运行时，应用软件和硬件的在线控制系统是必要的，以在阻塞和推测策略之间动态地选择和/或切换。在本文中，我们制定了作为动态线性反馈控制（优化）系统模型的大规模并行计算中的可逆推测计算，并评估其在时间和成本节省方面的性能，传统的（前向）计算。我们用汽车旅行的形式来说明一个精确的类比在动态的、延迟的路线信息下。其目的是帮助做出最佳决策，通过预测在由不同参数和概率分布函数表示的不同环境下的时间和成本节省（或损失）量，选择什么计算方法。我们考虑高斯，指数和对数正态分布函数的情况下。 控制系统旨在将其并入到诸如乐观并行离散事件模拟之类的推测性并行应用中，以在运行时决定何时以及在何种程度上可以有益地执行推测性执行关键词：可逆执行，并行计算，推测执行，基于模型的执行1电子邮件：perumallaks@ornl.gov2电子邮件：olamahussemm@ornl.gov3电子邮件：yoginathsb@ornl.gov4本文由UT-Battelle，LLC根据与美国国防部签订的合同DE-AC 05 - 00 OR 22725撰写。的能量因此，美国政府保留和出版商，通过接受出版的文章，承认美国政府保留一个非排他性的，付费的，不可撤销的，世界范围的许可，出版或复制本手稿的出版形式，或允许他人这样做，美国政府的目的http://dx.doi.org/10.1016/j.entcs.2016.09.0251571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。94K.S. Perumalla等人/理论计算机科学电子笔记327（2016）931介绍1.1推测可逆并行计算可逆计算是传统的只向前计算的放松[1]。在可逆计算中，执行被设计为可以向前和向后：在任何处理器上运行的应用程序被设计为根据需要改变执行方向。这种可逆执行框架在许多情况下都是有用的，例如数据库事务和并行离散事件模拟。在这些应用中，处理器间同步形成了主要成本，这是由于每个处理器需要经常从其他处理器获得关于要遵循的下一个局部轨迹的信息。避免阻塞和浪费时间等待来自其他处理器的信息的一种方法是基于本地信息进行最佳估计，然后依靠可逆计算来追溯轨迹的任何不正确部分。这些不等待完美的全局知识的局部执行部分被称为投机性突袭。投机性突袭的正确性分数越高，收益越大;分数越低，收益越低（或者，更糟糕的是，收益越负）。很难提前确定最佳策略;事实上，最好有一个运行时控制器，它可以动态地决定何时以及在多大程度上应该允许投机性的尝试。换句话说，需要一个在线控制系统，以便动态地控制投机性突袭在这里，我们研究了一种基于模型的控制系统设计方法，该方法对特定应用是不可知的我们探索了主要运行时动态的不同随机分布，并在合成实验中分析了它们的性能。总体问题是由两个相互竞争的目标来定义的：完工时间和完工总成本。我们探索的空间与代表性的（归一化）参数值，以获得我们的方法的效率的初步了解我们的工作在这里提出了从以前的分析在文献中的回滚为基础的并行计算。以前的工作集中在分析应用程序和应用程序类作为一个整体，以确定先验的平均，最好和最坏的情况下，阻塞和投机策略[5，6，7，8，9]。相比之下，我们专注于在线控制的设计问题，以动态选择（并可能切换）之间的封锁和投机执行，并在尝试保持投机性的突袭的长度作为一个选项的运行时控制。1.2类比考虑一个设置，其中驾驶员驾驶车辆到某个最终目的地F，路径是递增地获得的。假设驾驶员当前处于某个里程碑点A。进一步假设，在到达A之后，需要一些处理时间R（t）来确定到下一个里程碑点B的路线。因此，车辆静止，而驾驶员等待确定下一个里程碑B。为了节省时间，驾驶员可能会猜测下一条路线并开始驾驶。在确定下一个里程碑B时，车辆可能已经从A前进到另一个里程碑C。它必须从C点回到D点，K.S. Perumalla等人/理论计算机科学电子笔记327（2016）9395adadCDCDadCDACCDadCD路线偏离了到B的预定路线。因此，从C，它开车回到D，然后继续到B。这个过程在到达最终目的地的途中在B处重复如图1所示。Fig. 1.从A到B的推测遍历路径，通过一个聚合遍历实现，该遍历前进到C，后来发现只有在D之前是正确的，因此在到B的路上从C返回到D，并最终到达F~让我们注意到使用椭圆形行进从点A到点B所传送的距离设ab为两点之间的直接旅行的最短（非推测）距离，点A和B。通过提前开车，可以节省一些时间。实际的节省取决于路线A-C和A-B之间有多少路径是公共的，也就是说，A-D相对于A-B有多长。设A-D的驱动时间为t#−»，C-D的驱动时间为t#»。然后，净时间增益为t#−»−t#»，如图2所示。图二、投机性突袭的净成本等于正向路径加反向路径的总时间请注意，增益不像t#»−t#»那么大。 这是因为反转C-D是在知道正确的路径之后进行的。 所以，如果我们没有提前开车， 我们将在时间t#-»到达D，然而，由于向前行驶，我们必须行驶C-D，这需要时间惩罚t#»。因此，在时间上的净收益仅为t#−»−t#»。这也意味着，根据实际偏离量，在预期路径上，实际上节省的时间可以是正的、零的，甚至是负的。当D离C比离A近得多时，节约是正的。类似地，当D离C比离A远时，节约是负的。虽然有可能在时间上获得（积极的）节省由向前行驶引起的额外的非负燃料成本。 设L#为燃料#»pq直接在点P和点Q之间行驶距离pq的成本。那么，96K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93ACCD燃料成本L~由下式给出：ABL~= L #−»+ L #»+ L #»+ L #»= L #»+2 L #»。（一）阿布阿德dc cd db ab cd假设燃料成本与行驶距离成比例，等式1变为#»#»L~=W（ab+2cd）（2）AB其中W是常数。在本文中，我们考虑W= 1，这表示燃料成本被归一化为等于距离的情况。该成本函数将与另一场景进行比较，其中驾驶员等待下一里程碑B被确定。在这种情况下，我们考虑驾驶员在等待节省燃料的同时转向车辆的情况。一旦确定了下一个里程碑，驾驶员就打开车辆，驶向下一个里程碑B。在这种情况下，我们假设有一个额外的燃料成本启动车辆，表示为S。因此，等待场景的总燃料成本L~由下式描述：AB#»L~=Wab+S（3）AB前面的可逆推测驱动模型的类比与大规模并行计算中的可逆计算[1]的类比是精确等待路由A-B的确定的概念对应于处理器在正确计算中需要采取的真实计算路径。推测性突袭A-C对应于处理器在等待来自其他处理器的信息时避免完全阻塞其计算时可以采取的路径（即，用于完成处理器间同步和通信公共路径A-D对应于由并行程序作为其推测性尝试的结果而获得的计算时间的增益。燃料成本对应于计算消耗的总电能，无论是在正向还是反向。在实践中，确定到下一里程碑的路线的等待时间R（t）、在不等待确切路线信息的情况下向前行驶的推测距离（或时间）d#>>以及在确定下一里程碑之后行驶回到预期路线的距离（或时间）d#>>都是随机的，并且因此可以表示为具有某些分布的随机变量。目的是确定是在向前行驶之前等待关于确切路线信息的指令（策略1），还是通过猜测路线而不等待接收关于确切路线的指令来向前行驶（策略2）。2问题表述和假设在本文中，我们设计了一个动态反馈控制器（优化器），以研究所提出的可逆推测计算的性能，并协助做出正确的决定，选择什么样的策略（策略1或2）。最优决策K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93978N;N过程控制器基于在由不同参数和概率分布函数表示的不同环境下的时间和成本节省（或损失）的量在下一节中，我们用一个线性状态空间模型来表示可逆的投机性突袭问题，该模型使用动态反馈控制公式进行优化。延迟指令5N+7D命令位置图3.第三章。用动态反馈控制系统表示的可逆推测执行问题可逆推测计算问题可以由图3所示的动态反馈控制系统来表示。进程模型表示节点处理模型，其可以在状态空间公式中表示为Xk=AXk−1+BUk−1（4）其中Xk是时间k处的状态，Uk是k处的执行持续时间，A和B是恒定的模型参数。B的值表示处理器速度，并且参数可以被归一化以使得A= 1。 当计算方向为正向（车辆向前移动）时，B的值为正，当计算方向为反向（车辆向后移动）时，B的值为控制器的输入是一系列随机时间延迟的参考指令，Rk+TD，在时间k提供正确的计算路线上的信息，TD是随机时间延迟。这些指令应该在时间k到达控制器，但是由于处理器间同步，它被随机延迟。通信时间或通信时间。在每个时刻k，控制器（优化器）基于当前状态Xk（由反馈链路提供）、计算速度B和预期目的地Rk提供用于向前（或向后）计算的持续时间，预期目的地R k作为随机延迟指令Rk+TD提供给控制器。在我们的分析中考虑了两种策略：• 策略1（基线）：对于每个时刻k，控制器在下一个执行阶段开始之前等待关于计算轨迹的确切信息的延迟指令（计算保持暂停，直到控制器接收到关于正确前进路径的指令一旦接收到指令，控制器计算车辆到达目的地所需的时间Uk，并且以恒定速度开始执行，直到其以Uk时间单位到达预期目的地• 策略2（建议）：对于每个时刻k，控制器不等待关于精确轨迹信息的延迟指令，而是猜测路线并继续执行某个（随机）时间量，TF≤TD。在此之后，计算暂停剩余的时间，直到指令98K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93已接收（如果TF TD<）。一旦接收到指令，控制器就找出执行偏离预期状态轨迹的程度，并计算计算返回预期轨迹所需的时间，TR≤TF，然后执行开始以恒定速度移动，直到它到达最接近预期（正确）轨迹的点。在计算最终满足预期轨迹之后，控制器计算到达目的地的剩余时间，并且计算继续进行直到其到达预期目的地。1210864200 20 40 60 80 100 120 140 160 180 200时间（秒）图四、控制器的操作说明显示了两种3计算和通信延迟分布在我们的分析中，我们考虑了三种情况：（1）反向时间是高斯分布的，(2) 指数分布;（3）对数正态分布。不同分布的基本原理最简单的一个是反向时间的高斯模型，它基本上模拟了一个不正确的阶段，在很大程度上独立于正向执行，使所有推测性的突袭长度都具有相同的可能性。对数正态分布适用于这样的环境，在这种环境中，如果处理器是解耦的，这将高度增加不确定性。参考图1，在-策略1（等待，然后计算）策略2（不等待计算）计算进度（%）K.S. Perumalla等人/理论计算机科学电子笔记327（2016）9399AC随着A-C的距离d的增加（d#>>ed#>>）指数增加与这些CD分布，假设以下操作。(1) 指令的到达间隔时间TD是指数分布的，μ。(2) 前向计算时间TF呈高斯分布，平均值F=μ，标准差SD=μ/ 3。(3) 反向计算时间（与实际路线的偏差）TR是随机的，平均值R=d、d/2、d/3、d/4等，其中d是前向计算距离。我们专注于三种常见的情况下，反向计算时间的概率分布：高斯，指数，或对数正态。(4) 推测执行时间不能超过指令等待时间，TF≤TD。(5) 反向计算时间不能超过正向计算时间（距离），TR≤TF.图4显示了两种策略（等待和计算与不等待的计算）之间可能的动态权衡，该图显示了两种策略所采取的轨迹4数值结果与分析在本节中，我们将展示各种场景下的时间节省和能源成本的数值结果。在模拟中使用以下参数值：X0= 0;A= 1; B= 2;指令的到达间隔时间TD呈指数分布，平均值μ= 5;计算提前时间TF呈高斯分布，平均值F=μ，SD=μ/ 3;每个时间步的目的地点均匀分布在[10， 20]中;到达最终目的地的时间步总数K为100;在每个时间步启动计算的额外能量成本S为6个单位;蒙特卡罗模拟运行的总数为1000。出于空间考虑，我们仅提供了高斯病例的详细性能图表（图5、图6、图7），但在表1中以表格形式提供了其他病例的结果总结。4.1情况1：反向旅行时间为高斯分布图5（a）展示了当反向计算长度是具有平均值R=d的高斯分布时作为时间的函数的计算，其中d是正向计算长度。在这个场景中，我们观察到策略2在策略1之后大约245秒计算到最终状态。这是预期的，因为反向轨迹很长（与正向路径具有相同的均值）。图5（b）展示了同一情景下总能源成本随时间的变化。我们还观察到，策略2比策略21. 因此，对于此场景中使用的参数值，将选择策略1100K.S. Perumalla等人/理论计算机科学电子笔记327（2016）9310090807060504030201000 500 1000 1500时间（秒）(a) 行驶路线显示节省时间为-245秒3000250020001500100050000 500 1000 1500时间（秒）(b) 燃料成本显示，节省的成本为-511单位图五、 反向行驶距离服从均值高斯分布情况下的数值结果R=d，SD=d/ 3比率1ST后245秒断肢tegy 2完成comStra策略1（等待，然后计算）策略2（不等待计算）计算进度（%）策略2比策略1策略1战略2 fi245策略1（等待，然后计算）策略2（不等待计算）总能耗K.S. Perumalla等人/理论计算机科学电子笔记327（2016）9310110090807060504030201000 200 400 600 800 1000 1200 1400时间（秒）(a) 行驶路线显示节省时间为-66.5秒250020001500100050000 200 400 600 800 1000 1200 1400时间（秒）(b) 燃料成本显示节省成本为-145.5单位图第六章反向行驶距离服从均值高斯分布情况下的数值结果R=d/ 2，SD=d/ 6策略1（等待，然后计算）策略2（不等待计算）策略2完成计算策略1后66.5秒计算进度（%）策略1（等待，然后计算）策略2（不等待计算）策略2消耗145.5单位比策略1策略2完成计算66.5策略1总能耗102K.S. Perumalla等人/理论计算机科学电子笔记327（2016）9310090807060504030201000 200 400 600 800 1000 1200 1400时间（秒）(a) 行驶路线显示，节省时间为100秒250020001500100050000 200 400 600 800 1000 1200 1400时间（秒）(b) 燃料成本显示，节约成本194台图第七章反向行驶距离服从均值高斯分布情况下的数值结果R=d/ 4，SD=d/ 12策略1（等待，然后计算）策略2（不等待计算）策略2完成计算策略1前100秒策略1（等待，然后计算）策略2（不等待计算）策略2比策略1少消耗194个单位的能量策略2完成计算策略1前100秒总能耗计算进度（%）K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93103现在，我们考虑反向长度是高斯分布的情况，平均值R=d/ 2，而所有其他参数保持不变。图6展示了该场景的数值结果。我们观察到，在这个场景中，策略2在66左右到达了最终目的地。在策略1之后5秒，策略2消耗了大约145。比策略1多5个单位的能量。我们希望看到这两种策略几乎同时到达目的地，但它们并不一致。这是因为由于前面部分中的假设4和假设5，前进和反向执行时间不是纯高斯分布的。因此，对于此场景中使用的参数值，策略1将被选为最佳。现在，我们考虑反向长度是高斯分布的情况，平均值R=d/ 4，而所有其他参数保持不变。图7展示了该场景的数值结果在这种情况下，我们观察到，策略2比策略1早100秒到达最终状态，策略2比策略1消耗的能量少194个单位。因此，对于本场景中使用的参数值，将选择策略24.2情形2：反向旅行时间服从指数分布表1示出了当反向执行长度以平均值R=d指数分布时的执行时间，其中d是正向执行长度。在这个场景中，我们观察到策略2在策略1之后大约114秒到达最终状态。这是预期的，因为反向长度很大（与正向执行具有相同的平均值）。我们还观察到，策略2比策略1多消耗大约259个单位的能量。因此，对于此场景中使用的参数值，将选择策略1。将此场景与具有相同均值的高斯分布场景（如图5所示）进行比较，我们观察到指数分布的反向时间性能更好。现在，我们考虑反向执行长度是指数分布的情况，平均值R=d/ 2，而所有其他参数保持不变。 我们观察到，在这种情况下，策略2具有与策略2类似的性能。1.一、预计两种情况大约同时到达最终状态，因为反向行驶路线的平均值是正向执行长度的平均值的一半。此外，这是一个巧合，这两种情况消耗相同的能源成本。例如，如果在策略1中的每个时间步处用于启动计算的附加能量燃料成本S小于（或大于）6个单位，则策略1将消耗比策略2更少（或更多）的燃料成本，同时对于两种场景保持相同的完成时间现在，我们考虑反向执行长度呈指数分布的情况，平均值R=d/ 4，而所有其他参数保持不变。我们观察到，在这个场景中，策略2比策略1早108秒到达最终状态，并且策略2消耗的能量比策略1少240个单位。1.一、因此，对于本场景中使用的参数值，将选择策略2。104K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93·R+4.3情形3：反向旅行时间服从对数正态分布表1示出了反向执行长度是对数正态分布的时间，其中平均值R=d和SD=d/ 3，其中d是正向执行长度。注意，这里的平均值R表示相应的高斯随机变量Y的平均值，该高斯随机变量Y使用关系eY生成对数正态随机变量。在这个场景中，我们观察到策略2在策略1之后大约289秒到达最终状态。这是预期的，因为反向执行长度随着正向执行长度d呈指数增加。我们还注意到，策略2比策略1多消耗约585个单位的能量。因此，对于此场景中使用的参数值，策略1将被选为最佳。将这种情况与具有相同平均值的高斯分布和指数分布的情况进行比较，我们观察到对数正态分布的反向时间表现最差。现在，我们考虑反向执行长度是对数正态分布的情况，平均值R=d/ 6，而所有其他参数保持不变。我们观察到在这个场景中，策略2在策略1之后大约54秒到达最终目的地，并且策略2比策略1多消耗大约143个单位的能量。现在，我们考虑反向执行长度是对数正态分布的情况，平均值R=d/ 12，而所有其他参数保持不变。我们观察到，在这种情况下，策略2比策略1早45秒到达最终状态，并且策略2消耗的能量比策略1少53个单位。1.一、因此，对于本场景中使用的参数值，将选择策略2现在，我们考虑反向执行长度是对数正态分布的情况，平均值R=d/ 8，而所有其他参数保持不变。在这个场景中，我们观察到策略2与策略1具有类似的时间节省。这两种情况几乎同时到达最终状态。然而，策略2比策略1多消耗约38.37单位的能量。分析推导的节省时间的情况下，这两个方案到达在同一时间进行了说明下一个设Y是均值为R、方差为σ2的高斯随机变量，即Y（R，σ2），则G∈Y是一个对数正态随机变量，平均值为eσ22[2]的文件。在一般来说，为了使策略2比策略1节省时间，反向执行长度的期望值应该小于前向执行长度的期望值的一半，如前面第1节所述。这可以表述为FE（G）<2（五）其中E（）是期望算子，F是远期的期望值。R+σ2执行长度。 由于G的期望值为e2，因此等式5变为σ2Fe2 <2(6)R+K.S. Perumalla等人/理论计算机科学电子笔记327（2016）93105M3米+设R=F，我们的目标是计算M的值，使得策略2比策略1节省时间（更早到达目的地此外，在我们的模拟中，我们使用σ=F。将均值和方差代入等式6，我们得到F1。F-2F

下载后可阅读完整内容，剩余1页未读，立即下载