没有合适的资源?快使用搜索试试~ 我知道了~
沙特国王大学学报大整数乘的顺序和并行滑动窗口算法哈齐姆·M作者声明:a,b.Fathyc,a哈萨克斯坦哈伊尔大学计算机科学与工程学院信息和计算机科学系b埃及开罗艾因夏姆斯大学理学院数学系c埃及开罗爱资哈尔大学理学院数学系。阿提奇莱因福奥文章历史记录:收到2022年2023年2月8日修订2023年2月10日接受在线预订2023年关键词:乘法大整数窗口策略并行算法加速A B S T R A C T在科学和工程应用中,乘法和除法等基本运算的开销严重影响着应用程序的运行时间,特别是在数据量很大的情况下。在这项研究中,我们提出了一个公式,以尽量减少成本的乘法运算的整数时,每个整数的大小和整数相乘的数量是大的。基于一种窗口策略,从理论上推导出了使大整数序列相乘代价最小的最佳窗口大小。据我们所知,没有以前的研究提出了这个公式。然后我们设计了三个有效的算法,一个顺序和两个并行。使用三个参数进行实验研究:(1)整数的大小,(2)序列的大小,(3)线程的数量。结果表明:(1)所设计的串行算法比已有算法的速度提高了64%以上;(2)所设计的并行算法比已有算法的速度平均提高了50%以上;(3)所设计的并行算法具有超线性的加速性能。版权所有2023作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍乘法运算是计算机运算的核心功能之一。该操作很重要,原因如下:首先,许多原始算术运算基于乘法运算,例如逆乘、除法和平方(Brent和Zimmermann,2010)。其次,大量的科学和工程领域使用乘法运算作为诸如密码学的计算中的主要运算(Rivest等人,1978;Fathy等人, 2018年)。在乘法运算中遇到的主要挑战是,与诸如加法和减法的其他原始运算的成本相比,执行该运算的成本很大,特别是当数据大小很大更详细地说,如果我们有两个大的数字,每个数字的大小都是这两个数的乘法是O'和*通讯作者。电子邮件地址:khaledfathy@azhar.edu.eg(K.A.Fathy)。沙特国王大学负责同行审查分别,当使用本地方法时(Furer,2009)。因此,当'很大时,两个成本之间的差异是显著的。对于一些科学和工程应用,他们的解决方案需要对大数据序列应用乘法运算在这种情况下,解决这些问题所需的计算时间例如,如果我们有一个由五个整数组成的序列,每个整数的大小都是'-位数。在最坏的情况下,将五个整数相乘的数字乘法成本如下:(1)将五个整数相乘的数字乘法成本前两个整数是“2”。(2)将(1)的结果乘以第三个整数的2′- 位 数 的 数 乘 代 价为2 ′ 2。(3)将(2)的结果(3 '位数)与第四个整数相乘的数字乘法成本为 3 ' 2。( 4)将(3)的结果4 ′- 位 数 乘 以 第 三 整 数 的 位 数 乘 法 成 本 为 4 ′2。 因此,将五个大小为'的整数相乘的总的数字乘法器i的成本是10 '2。因此,以往的研究提出了不同的算法其目的是降低两个大整数或一系列大整数相乘的成本。这些算法基于不同 的 策 略 , 如 原 生 (Brent 和 Zimmermann , 2010 ) , 分 而 治 之( Bilardi 和 Stefani , 2019; Rao , 2015; Zanoni , 2010;Rezai 和Keshavarzi,2017),窗口(Bahig和Fathy,2021;Bahig等人,2020;Brumnik等人, 2014)和快速傅立叶变换(De等人,2013; Fischer和Stockmeyer,1974; Furer,2009;https://doi.org/10.1016/j.jksuci.2023.02.0111319-1578/©2023作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页:www.sciencedirect.comH.M. Bahig和K.A. Fathy沙特国王大学学报132DeDe我...DeHarveya等人,2016; Luders,2015; Rao,2015; Schonhage等人,1971; Toom,1963; Wu,1995; Zanoni,2010; Stefani,2019; Rezai和Keshavarzi,2017)。另外,这些算法中的一些是在并行系统上设计的(Fathy等人,2018; Bahig和Fathy,2021; Gaudry等人,2007;Bunimov 和 Schimmler , 2003;Sinha 和 Srimani , 1988;Tembhurne,2018; Tembhurne和Sathe,2014; Yuen和Feng,1994;Stefani,2020; Akl,1997; Bahig等人, 2021),如多核系统和图形处理单元(GPU),以加快计算时间。在这项研究中,我们有兴趣尝试解决一个大整数序列相乘的问题;因为我们的目标是克服两个挑战:整数的大小和序列的大小。在我们的尝试中,我们专注于窗口策略,因为基于窗口的算法是目前已知的最快的大整数序列相乘算法。采用这种策略的主要挑战是,据我们所知,没有理论推导出最佳窗口大小,以尽量减少乘法所需的时间一个大整数序列此外,已知的用于将大整数序列相乘的最快并行算法在成本(时间复杂度与处理器数量的乘积)方面不是最优的(Bahig等人, 2021年)。因此,在本研究的工作中,我们专注于实现以下目标:1. 推导了一个计算窗口大小的公式,使大整数序列相乘的运行时间2. 在确定最佳窗口大小的基础上,设计了一种快速顺序算法3. 开发两个并行算法来加速所提出的顺序算法。所提出的并行算法比已知的并行算法更快,更可扩展。本文的其余部分组织如下:在第2节中,我们提供了一个简短的概述,相关的工作乘以一个序列的大整数。在第3节中,我们给出了最小化运行时间的最佳窗口大小公式在第四节中,我们提出了三个算法的基础上确定的窗口大小在第三节。所提出的算法之一采用顺序的方法和其他两个算法使用并行的方法。在第5节中,我们提出的实验结果进行测量所提出的算法的性能,并将它们与最知名的顺序和并行算法产生的结果进行比较。最后,第6节总结了本文,并强调了一些需要进一步考虑的开放性问题。2. 相关工作在本节中,我们简要回顾了已经提出的用于乘以大整数序列的不同算法,以及从顺序和并行角度开发的算法。从顺序计算的观点出发,提出了两种主要的策略来求n个大整数的乘法,A 1/4a0; a1;.n-1个。第一种策略是基于执行n-1的本地方法迭代 在每个迭代i;16in,输出M乘以ai,其中M初始化为0。<这种方法的主要缺点是,在每次迭代中,当M与i相乘时,数字乘法的数量增加。这会导致将一个大整数序列相乘所需的运行时间增加。第二种顺序计算策略基于窗口方法(Bahig等人,2020年)。该算法由n=w次迭代组成,其中w是窗口的大小在每次迭代i;26i6n=w,该算法将第i个窗口的整数相乘,并将结果与输出M相乘,其中M的初始值是第一个窗口中的整数相乘的结果。实验表明,窗口方法比本地方法快得多。与窗口方法相关的主要挑战是,没有理论公式推导出最小化乘法时间的窗口大小的最佳值。一个很好的例子说明了这两种方法之间的差异和窗口大小对整数序列相乘所需的运行时间的影响,可以在Bahig等人的文章中找到。(2020年)。从并行计算的观点来看,对于n个大整数的乘法,提出了两种主要的策略。第一种策略是基于二叉树方法。该方法的第一阶段涉及将整数序列划分为p个子序列,其中p是处理器的数量。然后,每个处理器计算n=p个整数的乘法。第二阶段涉及对从阶段1获得的p个整数应用二叉树技术。该算法是最优的,但其主要缺点是其运行时间随着整数和序列的大小。另一种有效的并行方法在上述方法的第一阶段中采用简化策略,该简化策略被称为EPP (高效并行乘积)(Bahig等人, 2021年)。该算法从n个元素开始,通过使用logn= log logn- 1次迭代将它们减少到logn个整数在第i次迭代中,由该算法生成的整数是n=login。最后,算法将logn个整数依次相乘该算法不是最优的,但当整数的大小较大时,它比上述最优Park-Park-Algorithm要快3. 窗口大小在本节中,我们推导出w的最佳值,它在乘以一个大整数序列时给出了为了计算简单,我们只考虑两个大小为l的整数相乘时的数字相乘次数。请注意,当我们将两个大小为l位的整数数字加法运算出现在进位运算和两位或两位以上数字的加法运算此外,如果我们将两个长度为l和m的数相乘,则乘法需要lm次数字乘法,结果的长度为将被限制在lm和lM 1 .一、推导w的最佳值的思想包括三个阶段。阶段1基于计算大小为w的单个窗口的数字乘法的总数的上限和下限。阶段2是基于计算乘以n个整数所需的数字乘法的总数的上限和下限。阶段3涉及从阶段1和2导出窗口的大小,从而最小化乘以n个大整数的时间3.1. 阶段1在这个阶段,我们需要计算乘以一个单一窗口的成本为了计算单个窗口的数字乘法的成本, . 首先,通过窗口中的第一个元素初始化结果,即,mw¼aj. 乘法第二个元素aj=1,由结果成本l2和长度在该步骤之后的结果的I/O被限制在2L和2L-1之间。将第三个元素aj 2乘以结果的成本是有限的在2L2和2L2-L之间,并且在该步骤之后的结果的长度被限制在3L和3L-2之间。将第四个元素乘以结果的成本限制在3l2和3l2-2l之间,H.M. Bahig和K.A. Fathy沙特国王大学学报133- ð- -2-2--2ðÞ2ð--þ --ðÞð- Þð- ÞWWð ÞDW姆乌布2周22周222W2 2 22该步骤后的结果长度限制在4l和4l- 3之间;Tn;lnl2w-1n-wnn-1l2ð5Þ将第w个元素与结果相乘的成本限制在wl-1/2和wl-1/2/2/2之间,并且在该步骤之后的结果的长度限制在wl和wl之间W1.一、的单个窗口的数字乘法的总成本,mub2 2注意,Tmubn;ln不依赖于w的值。对于下限,Tmlb<$n;l<$:nnnT mn; lt mw; lz 2 z-z 3 z-2 z···-1z2000年W个大小为L的元素,每个都被限制在上,磅重量lb你...t w l和下界t wl。nl2w-1w-1穆乌布;wlb;1/2-2wz123···tmubw;l的值可以计算如下:n nþðw-1ÞÞ-zð 1þ 2þ 3þ···þðw- 2ÞÞt w ll22l23l2w1l2nl2w-1w-1zn-1n-2穆乌布;··- -1/2-2周2-21/4升1/2/3升···nl2w-12Zerow-1Zerow-2Zeronl2Wtw;ll2w-1wð1Þn的价值tmlbw;l可以计算如下:nl2w-12Zerow-1Zerow-2Zeronl2Wtmw;ll22l2-l 3l2- 2l···w- 1l2-w- 2ln-w2周2次lb1/4 l123···w-1-1123···w-2nl2w-12Zerow-1Zerow-2Zeronl2Wl2-1-2 -3 -4 - 5 - 6 - 7- 8- 10 - 1lw-2w- 1n-w2Wtmlbw;l¼2-2ð2Þnl2w-122019年12月23日星期二2W基于等式1和等式2,tm w;l的值满足以下不等式ðn-wÞðnwl-2nwlþ2wlþnw-2wþnl-nþ2Þ2Wl2-1- 2 -3 -4 - 5 - 6 - 7 -8 - 10 -12lw-2w- 16tmw;l6l2w1w2ð3ÞTmlbn;l¼nl2w-122019年12月23日星期二2周2周此外,单个窗口的乘法的长度满足以下不等式:n-w2Wwl-100w-16lw6wl4nn-1l222019年12月23日星期二2W3.2. 阶段2n-w2W为了计算乘以n个整数的数字乘法的总成本,我们计算每个窗口的成本加上nn-1l222011-2012-2013年24nl- 2n2ln2-n- 2 2将其结果乘以总结果的成本。第一次的代价窗口的长度仅为t_m_w;l_m,并且在该步骤之后的最终结果的长度被限制在w1和w1-m_w-l_m之间。n2l-n22n-2nl2Wnn-1l2为简单起见,设z/wl-ww-1= 1。第二次胜利的代价是-Tmlbn;ldow是tmw;l加上其结果乘以最终结果的成本结果.乘以第二个窗口其中,l是以下的函数:通过将最终结果限制在z2和w2之间,并且将该步骤之后的最终结果的长度限制在2z- 1和2w1之间。w总是负数(见附录A)。从等式5和6,我们有以下不等式:第三个窗口的成本是tm w;l加上将其结果乘以最终结果的成本。将第三窗口的结果乘以最终结果的成本被限制在2z2-z和2w2l2,并且在该步骤之后的最终结果的长度被限制在3z- 2和3wl之间,等等。n n1l22周/周16Tmn;l63.3. 阶段3n n1l22ð7 Þ第n个窗口的成本是tmm mw;ln加上将其结果乘以最终结果的成本。将第n个窗口的结果乘以最终结果的成本限制在这一阶段的目标是找到w的值,使/n的值越小越好。我们通过对/w相对于w求微分,然后将微分设为等于零来找到w的值,如下所示:n2nn22Zerw-1Zerz---和决赛d2 2该步骤之后的结果被限制在nz-1/n-1和nwl/nl之间。/wnl-2l-n2n l-n2n- 2nlw w wDW1/2-2周2次数字乘法的总成本Tmn;l限制在上限Tmubn;l和下限Tmlbn;l之间,其可以计算如下:将d/w设置为0对于上界,T姆乌布;)nl-2l-n 2¼n2l-n22n-2nlw2nTmn;l tmw;l 2002年, 2013年3月1周2小时2小时n2l-n22n-2nlW-þþ-þþþþWWW¼¼¼¼þ2¼¼þH.M. Bahig和K.A. Fathy沙特国王大学学报13422 2222Wl2-wW乌布wUB你...w2¼n l2w-1w2n2nl-2l-nl-2��nl2w-1w2l2n-1nnl2w-1sWn2l-n22n- 2nl¼2þ2¼2þ21/4nl-2l-2nH.M. Bahig和K.A. Fathy沙特国王大学学报135ln-2-n-22p二二二p2p2p4pp2dw2w3wpUBwppp2p22我2i 1pp2p22p2p2p2p2¼--联系我们2p2pp-wnl2nw¼snln-2-nn-2w<$qnl-n4.2. 首次提出的并行算法并行化所提出的序列算法的第一种所提出的方法从计算窗口的最佳大小w开始,nL-1因此,w的最佳值 是使用等式8 .第八条。然后算法将输入数组分为分区并将这些分区分布在pdwe部分wpnð8Þ处理器.在那之后,该算法执行两个主要步骤。在第一步骤中,每个处理器计算dne个分区的乘法结果,除了检查一阶导数,我们还将确保w的值将通过如下检查二阶导数检验来最小化函数:d2/nwnn2ln2n2 nldw2w3d2/W/W因为d2/dww的值总是正值,所以w使该值最小化DW//4. 所提出的方法在这一节中,我们详细介绍了三种方法,以提高性能的n个整数的乘法,每个l位在第一小节中,我们描述了顺序算法,该算法基于等式中的窗口w8 .第八条。在第二和第三小节中,我们描述了两个并行算法,并行化所提出的顺序算法。4.1. 提出的顺序算法在这一小节中,我们描述了一个序列算法,用于乘以一个数组A的n个数字,每个数字的大小为l第一wp顺序地,通过采用算法WM所使用的相同策略。第一步产生p个结果,这些结果被存储在辅助阵列m1/4m0;m1;. ;m p-1。在第二步中,算法使用辅助阵列m上的二叉树范例,使用p个处理器来计算乘法的最终值。算法2以伪代码的形式示出了解决方案的步骤,并被命名为并行窗口乘法1(PWM1)。PWM1算法的运行时间为O,其中t1和t2分别是在步骤1和2的情况下,在最坏情况下,两个整数相乘的运行时间。的总数位乘法为算法PWM1可以是计算如下。在步骤1中,每个处理器计算n的乘法 分区。每个分区的长度最多为w。wωp首先,每个处理器pi使用t个wl个数字乘法来计算第一部分的乘法,然后将结果存储在长度为wl个数字的mi中第二,pi使用t个整数乘法计算第二分区的乘法,然后使用多个整数乘法计算第二分区的乘法。将mi的值乘以使用w2l2位乘法的结果,并且mi的长度变为2wl。第三,pi使用t个整数乘法计算第三个分区的然后将mi的值乘以使用2W2L2位乘法的结果,并且mi的长度变为3W1。一般来说,pi该算法的步骤涉及计算w的最佳值,当量8 .第八条。然后将输入数组划分为dne个分区,执行nwωp连续迭代,所以总位数-W其中每个分区的长度为w,除了最后一个分区的长度可以小于w对于每个分区,算法计算其乘法并将其乘以总结果,即初始化为1。算法1将解决方案的步骤显示为伪该步骤的乘法可以计算如下:t1n t m w;l 2002年, 2013年3月 þ···þ ð- 1名妇女nl2w-1 ww2l2n nwp22wpwp它被称为窗口乘法(WM)。WM算法的运行时间为Ontm,其中tm是时间1/4nl2w-1l2n nnl2w-1n-wp最坏情况下两个整数相乘的复杂度总所提出的算法的数字乘法是On2l2,见等式五、算法1. 窗口乘法1/2便士2019- 01 -22 00:00:00m i的长度至多为nl 数字。在步骤2中,有两个循环外部循环是顺序的,需要Ologp次迭代。内部循环是并行的,使用最多的处理器,每个处理器在每次迭代中只执行一个操作。在外部循环的第一次迭代中,内部循环使用p个处理器。每个处理器pi使用n2l2^20n2l2将每个长度为nl的元素m2i和m2i1 数字乘法,并将结果存储在m i,其长度为2 nl。在外部循环的第二次迭代中,内部循环使用p个处理器。每个处理器p i 乘以元素m和m,每个长度为2 nl,使用4 n2l21/422n2l2位-乘法并将结果存储在长度为4nl的mi中。通常,在外部循环的第k次迭代中,内部循环使用p处理器。每个处理器p 将元素m2i相乘2ki和m,每个长度为knl,使用2个k-1个kn2l2个数字乘法2i 1p p2并将结果存储在长度为2knl的m中。总数Ip可以如下计算步骤2中的数字乘法:t1/221-1n2l2 22 2 - 1n2l2 22 3 - 1n2l2···22logp-1n2l21/20/22/24/2···H.M. Bahig和K.A. Fathy沙特国王大学学报136pp这个级数是一个有限的几何级数,它的和是4logp-1。四比一因此,步骤2中的数字乘法的总数为t1/t2/tPWM 1中的数字乘法总数乘法的值。算法3以伪代码的形式给出了求解步骤,并命名为并行窗口乘法2(PWM2)。23是t 阿勒特p2n2l2n2l2n2l2公司简介nl2On2l2。PWM2算法的运行时间为Ont1logpt2,其中1 233p22p2-2p¼t1和t2是两个整数相乘的运行时间,步骤1和2,在最坏的情况下。的总数算法2. PWM 2的并行窗口乘法1(PWM 1)数字乘法与PWM 1的数字乘法相同2Nn因为第一步需要时间,第二步需要时间,二分之一与PWM 1的第二步骤的相同算法3.并行窗口乘法2(PWM2)5. 性能比较在本节中,我们进行了一个实验,研究所提出的算法,顺序和并行,在不同的数据集上的性能。在第一小节中,我们给出了实验中使用的硬件和软件规格以及用于生成数据集的不同参数在第二个子-第节,我们比较了所提出的顺序算法与最优序贯算法(OM)的性能进行了比较。在第三节中,我们从运行时间上比较了这两种并行算法与最好的并行算法(EPP),并在第四节中,4.3. 第二种并行算法第二种并行算法由两个主要步骤组成第一步是将输入数组划分为p个分区,并将这些分区分布在p个处理器上。每个处理器pi将算法WM应用于大小为dne的子阵列,并产生乘法的结果mi。w的值由下式给出:第四小节我们根据加速比和可扩展性来比较相同。5.1. 实验规范和数据集我们使用C++语言、GNU多精度软件包(GMP)和würnð9Þ开放多处理(OpenMP)。GMP是一个用于处理大型数据集的软件包,而OpenMP是一组库路由和编译器指令,可用于C++程序,在第二步中,该算法使用辅助阵列m上的二叉树范例,使用p个处理器来计算最终多线程共享内存平台。我们使用GCC编译器在Ubuntu 16.04操作系统下运行所有程序。pppH.M. Bahig和K.A. Fathy沙特国王大学学报137¼¼¼¼¼所有程序都运行在名为e2- standard-32的Google云系统上,该系统由32个vCPU和128 GB内存组成实验中使用的数据集是根据每个大整数l的大小和数组中大整数的数量n生成的。 的值大小的的大整数是64; 128; 256; 512和1024位,而数组中大整数的个数的值为2k;4k; 8 k; 16 k和32 k,其中k1024.数据是使用子程序随机生成的在GMP。所有的算法,顺序的和并行的,都运行在相同的数据生成。对于n和l的每个固定值,我们生成一个包含50个随机实例的数据集对于并行程序,我们在实验中考虑不同的线程值,其中p1/42 ; 4; 8; 16和32。5.2. 顺序运行时间比较表1提供了最优顺序算法OM和所提出的窗口乘法算法WM的运行时间的比较细节。每一行表示两种算法的运行时间,其中l为固定值,n为不同值。从表1中的数据,我们观察到以下情况:1. WM算法在所有情况下都比OM算法快。2. 对于一个固定的数组大小,WM算法所获得的改善百分比随着整数l的大小的增加而增加。 例如,当n= 8 k时,和164、 128、256、 512和1024,使用WM算法的改善百分比是84:3%; 85:5%,89:1%; 92:4%和95:1%。图1a示出了对于具有固定阵列大小的所有研究情况,WM算法实现的改进的百分比。注意,x因此,x3. 对于固定大小的元素l,WM算法获得的改进的百分比随着输入数组n的大小的增加而增加。例如,当l 1/4512和n2k;4k;8k; 16k和32k,改善百分比WM算法的平均识别率分别为84:5%、 87:8%、 90:3%、 92:4%和95:3%。图1b显示了WM算法在所有研究的固定大小的大整数情况下所实现的改进百分比。4. 通过WM算法实现的改进的百分比对于所有研究的情况是显著的;因为通过基于w的导出值的所提出的顺序算法实现的最小改进大于或等于64%。5.3. 并行运行时间比较在这一小节中,我们比较了使用不同数据集和线程数的三种并行算法EPP、PWM1和PWM2的运行时间。实验分别基于三个参数对三种算法的并行运行时间进行了测量。其中两个参数与表1OM和WM算法的时间比较Fig. 1. WM算法的改进百分比。连续时间比较实验,即,数组大小和大整数大小,而另一个是线程数。在测量并行算法的运行时间时使用为测量顺序算法的运行时间而生成的相同数据。n2K4K8K16K32KLOMWMOMWMOMWMOMWMOMWM640.030.010.110.030.450.112.360.3710.011.151280.100.030.380.091.550.296.90123.483.22560.360.081.450.265.910.8324.062.6192.858.375121.400.225.690.6922.572.1994.927.23383.2418.1310244.070.5716.391.8766.744.79270.8613.21093.9540.86H.M. Bahig和K.A. Fathy沙特国王大学学报138图二. 当n<$4 2k时,并行算法之间的时间比较。图三. n<$4k时并行算法的时间比较。见图4。 当n<$8k时并行算法的时间比较。图五. n16k时并行算法的时间比较。见图6。 n<$32k时并行算法的时间比较。H.M. Bahig和K.A. Fathy沙特国王大学学报139¼¼¼ð Þ使用不同的参数运行三个并行算法的结果在五个图中呈现,图1. 2比6每个图表示对于固定的n值和不同的p和l值,三种算法的并行运行时间。从图中所示的数据,我们观察到以下情况:1. 每个并行算法的运行时间都比顺序算法快算法,WM,除了在一情况当n=2k,l= 64,p=32时。这意味着当数组和数据的大小很小时,线程数很大时,并行算法是无效的。2. 当p为2; 4; 8和16时,几乎所有情况下,每个并行算法的运行时间都随着线程数的增加而减少。3. 在p32的情况下,每个并行算法的运行时间大于p32和l512时相同算法的运行时间。<<这意味着高效的使用大量线程,p32时数组的大小数据量非常大。4. 当p1/4 2以及n和l的值较大时,EPP算法比PWM 1和PWM 2更快。在p/4的情况下,EPP算法-Rithm比PWM1和PWM2快一点,但改进不显著。5. 当p>4时,两种算法PWM1和PWM2都比EPP算法快,且改进显著。6. 这两种算法的行为,PWM1和PWM2,几乎在所有情况下都接近相等。5.4. 加速和可扩展性在本小节中,我们测量了三种并行算法EPP、PWM1和PWM2所实现的加速比。的加速每个并行算法的运行时间等于WM算法的运行时间与使用p个线程的并行算法的运行时间之比,WM算法代表了用于乘以n个大整数的最佳顺序算法。图7-11显示加速三种并行算法中的一种从图中所示的数据,我们注意到以下几点。1. 一般来说,PWM1和PWM2算法与EPP算法相比显示出显著的提高,特别是当p>4时。见图7。 当n≥2k时,并行算法的加速比。见图8。 当n≥4k时,并行算法的加速比。见图9。 当n≥8k时,并行算法的加速比。H.M. Bahig和K.A. Fathy沙特国王大学学报140¼¼¼¼¼¼¼¼见图10。 当n≤16k时,并行算法的加速比。见图11。 当n≥32k时,并行算法的加速比。2. 在p2的情况下,EPP算法的加速比优于PWM1和PWM2算法。3. 在p =4的情况下,当n和l较大时,EPP算法的加速比略优于PWM1和PWM2算法。另外,当n和l不太大时,EPP算法的加速比小于PWM1和PWM2算法的加速比。4. 当p为32时,不同的n和l值,EPP算法的加速比都有所下降。另一方面,PWM1和PWM2算法的加速比在n和l较大时增加,诸如当n P 8k和l为0时。lP 512。5. PWM1算法的加速比略好于当p616时,PWM 2算法的加速比优于PWM 1算法;当p32时,PWM2算法的加速比优于PWM 1算法。6. 当n很大且26p6 16时,PWM1和PWM2算法的加速比行为是超线性的。否则,加速是次线性的。6.结论和未决问题大整数序列的乘法问题是计算机算术中的重要问题之一,因为乘法运算的代价很高,特别是当数据量很大时。为了解决这个问题,我们开发了一个快速顺序算法,关于窗口战略我们工作的新颖之处在于衍生-此外,我们并行化的顺序提出的算法,通过使用两个并行的方法上的共享内存模型。提出的并行算法和已知的最快的并行算法,是使用不同数量的线程,p2, 4, 8, 16,和32的实验比较表明,这两个建议的并行算法是更快的,有一个高的加速比相比,以前的作品。本文的研究为减少大数相乘所需的时间做出了新的贡献然而,有许多开放的研究问题,出现在有关这些贡献。例如,如果我们考虑数字加法运算,那么w的值在理论上是多少其次,如果我们考虑其他乘法方法,如Karatsuba和Toom-Cook方法,w的值第三,如果输入数组包含不同大小的数字,w的值是多少第四,使用GPU对所提出的算法有什么影响?我们希望在未来的研究中解决这些问题。竞争利益作者声明,他们没有已知的竞争性财务利益或个人关系,可能会影响本文报告的工作。附录A定理1.n2-2n>n2-n- 18nP 42 2一个理论公式的大小的窗口,迷你-最小化所研究问题的数字乘法运算的成本使用不同的序列大小n^2k;4k; 8k; 16k和32k以及整数大小164; 128; 256; 512和1024进行的所提出的和最知名的顺序算法的实验比较表明,所提出的顺序算法能够实现大于64%的显著改进。证据我们将使用数学归纳法证明该定理如下:基本情况n4:左边是8,右边是5。因此,当n为4时,定理成立归纳假设:假设定理成立的所有值n到一些k;kP4。H.M. Bahig和K.A. Fathy沙特国王大学学报14122ffiffiffi-我...nnl22nl-2l- 2n nn2l--n2--n2nl-n2lnnn2ln-n2nln-1-nþ2n-n2-2nl2-n22n-2-1n-n2-2n>-n22n-ð-2->2-2þ-2 -22n2k2k2kK -2 k>2-2 - 110归纳步骤:设n<$k=1。那我们就想证明kBahig,H.,Alghadhban,A.,Mahdi,M.,Taibi,K.,Bahig,H.,2020.大整数乘法算法的加速。工程技术应用科学Res. 10(6),6533-6541.Bahig,H.,Bahig,H.,Fathy,K.,2021年多核系统上大数据量产品快速可扩展算法并发计算:实践经验33(2),e5259。https://doi.org/10.1002/cpe.5259网站。比拉尔迪,G.,史蒂芬妮,L.D.,2019.的I/O复杂性的toom-cook整数22乘法。在:第三十届年度ACM-SIAM离散算法研讨会论文集,加利福尼亚州圣地亚哥,pp。2034-2052年。通过将2k- 1添加到Inq的两侧10我们得到k22k 1- 2k- 2>k3k- 2所以k 12-2k1>k23k-2布伦特河,Zimmermann,P.,2010.现代计算机算术。北京大学出版社.布鲁姆尼克河,Kovtun,V.,Okhrimenko,A.,Kavun,S.,2014.密码学应用中整数乘法的性能改进技 术 。马瑟问题Eng. .Bunimov,V.,Schimmler,M.,2003年。一种高效的并行乘法算法大整数讲课注释计算Sci. 279 0 ,923-928。现在,我们将比较k2<$3k-2与Inq的右侧。11De,A.,Kurur,P.,Saha,C.,Sapthasrishi,R.,2013年。 快速整数乘法,k23k2、2-2>2 222-2-1 ¼ 22- 1模运算 SIAM J. Com put . 42(2),685-699。Fathy,K.,Bahig,H.,Ragab,A.,2018. 一种快速并行模幂算法。Arabian J. Sci.Eng.43,903-911中描述的。Fischer,M.,斯托克迈耶湖,一九七四年快速在线整数乘法。J.计算机因此,该定理对n<$k<$1成立利用图解归纳法的原理,证明了该定理对8nP4成立.H定理2. /pn总是负数。证据从等式8,我们推导出w的最佳值是w/pn。通过将w的值代入/w,我们得到系统科学9(3),317-331.Furer,M.,2009年更快的整数乘法。 SIAM J. Comput. 39(3). 979- 15Gaudry , P. , Kruppa , A. , Zimmermann , P. , 2007. 基 于 gmp 的 schonhage-strassen大整数乘法算法实现2007年国际符号和代数计算研讨会论文集167-174。Harveya,D.,Hoevenb,J.,Lecerf,G.,2016.更快的整数乘法。J. Complexity 36,1吕德斯角,2015.大数乘法的dkss算法实现。在:2015年ACM符号和代数计算国际研讨会上的会议记录,英国巴斯,pp。第267-274页。pp.20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000饶是如此,美国,2015. 有趣结果产生Karatsuba乘法-蒙托族公式在:第六国际会议记录2 2n2l n 2n2nl2p33计算机和通信技术会议,印度阿拉哈巴德,pp。317-322.Rezai,A.,Keshavarzi,P.,2017.压缩sd:一种新的编码算法及其在乘法中的应用。国际计算机马瑟94(3),554-569.里维斯特河,Shamir,A.,阿德曼湖1978.一种获得数字签名和公钥密码系统的方法。Commun. ACM 21(2),120-126。p联系我们pp2331pp22 22- 2-2019-02-22zahlen。计算7,281-292。Sinha,B.,Srimani,P.,一九八八年一种新的并行乘法算法及其VLSI实现实施. 在ACM第十六届年度会议上,p2p3n2 3pn计算机科学,pp. 366-372.Stefani,L.,2019年。整数混合算法的I/O复杂度由定理1可知,n2- 2n>n2-n-18nP 4.乘法https://arxiv.org/abs/1912.08045网站。第3页2 2n232p2Stefani,L.,2020. 通信最优并行标准与Karatsuba整数分布式内存模型中的乘法。 https://arxiv.org/abs/2009。14590Tembhurne,J.,2018年gpu上大整数的并行乘法Commun.Comput. 信息格式。 Sci. 827,276-285。)n22p32nln2n32p1坦布赫恩,J.,萨特,美国,2014年。性能评价的长整数在共享存储器架构上使用openmp和mpi进行乘法。在印度诺伊达举行的第七届当代计算国际会议上,因此,/pn总是负数。H引用Akl,S.,1997.并行计算:模型与方法。普伦蒂斯厅,上鞍河,新泽西州。Bahig,H.,Fathy,K.,2021.一种高开销前缀运算的高效并行策略。超级计算机。77,5267-5288。pp. 283-288.Toom,A.,1963.实现整数乘法的功能元素方案的复杂性。苏联数学Doklady 3,714-716.吴,Y.,1995.整数常数乘法的强度约简。ACMSIGPLAN Notices 30(2),42-48.Yuen,C.,冯,M.,1994.并行乘法:并行编程中的一个案例研究。ACM SIGPLANNotices 29(3),12-17.Zanoni,A.,2010.非常不平衡长整数乘法的迭代toom-cook方法。在:2010年符号和代数计算国际研讨会的会议记录,德国慕尼黑,pp。319-323联系我们Schonhage,A., Strassen,V., Zanichelli,F., 1971. Schnelle乘法器联系我们)22-1:þ:n
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功