基于加权中值算子算法的鲁棒变换计算及性能提升策略

可在www.sciencedirect.com在线获取理论计算机科学电子笔记349（2020）81-102www.elsevier.com/locate/entcs基于加权中值算子算法赫苏斯·E 拉米雷斯1委内瑞拉加拉加斯西蒙玻利瓦尔大学何塞·帕雷德斯2Universidad de Los AndesMérida，委内瑞拉Yudith Cardinale3委内瑞拉加拉加斯西蒙玻利瓦尔大学摘要基于加权中值算子算法的鲁棒变换计算当它暴露在脉冲噪声中时发出信号。由于该算法需要很长的执行时间，时间，它是不是有用的实时信号处理系统。在这种情况下，这项工作提出了几种策略，以提高其性能，如减少冗余计算，优化的内存访问，和多线程版本的算法。此外，原始的估计方法进行了修改，以减少更多的平均执行时间，保持数值结果的质量水平。实验结果表明，通过减少冗余计算和优化内存访问，在不修改估计方法和不使用多线程处理的情况下，性能提高了30%;通过引入估计方法的修改，性能提高了93%;通过引入多线程处理，性能提高了97%关键词：鲁棒变换，加权中值，优化，高性能，多线程1引言在信号处理的背景下，线性变换包括将离散信号从一个域映射到另一个域，以暴露信号的特征，从而允许以更简单的方式处理和分析它当一个信号被传送时1电子邮件：13-11170@usb.ve2电子邮件：jparedes@ula.edu.ve3电子邮件：ycardinale@usb.vehttps://doi.org/10.1016/j.entcs.2020.02.0141571-0661/© 2020作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。82J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81通过一种媒介，它曾经是一种退化的方式。这种效应被称为噪声。脉冲噪声显示信号强度的急剧增加，尽管这些增加的持续时间与它们之间的时间相比很短。这类噪声通常用尾部比高斯分布的尾部更加权的分布来建模，例如拉普拉斯分布。在通信系统中，通常需要获得通过具有噪声的信道接收的信号的变换[1]。如果该噪声本质上是脉冲的，则有必要使用鲁棒的方法来计算变换，因为脉冲噪声是高度退化的。在此背景下已经提出了几种算法[2，3，4，5，6，7，8]。特别地，在先前的工作[9]中，提出了基于加权中间算子（RTWM）算法的鲁棒变换。虽然这些用于计算鲁棒变换的解决方案是有效的，但是由于它们的算法复杂性，它们需要用于处理的高计算成本。因此，它们在实时信号处理中的应用是不合适的。出于这个原因，它是必要的，以实现有竞争力的数值精度的计算时间，开发成本较低的算法在这个意义上，我们提出了几种策略，以减少执行时间的RTWM算法，其中包括减少冗余计算，使用的分层存储系统，并使用多线程的执行。此外，对算法的原始结构进行了修改，从而在保持数值结果质量的同时提高了执行时间。实验结果表明，通过减少冗余计算和优化存储器访问，在不对估计方法进行修改和不使用多线程处理的情况下，性能提高了30%;当对估计方法进行修改时，性能提高了93%;通过结合多线程处理，性能提高了97%。这项工作的备忘录组织如下。第2节介绍了RTWM算法的基础。 在第3节中，我们提出了与冗余计算、存储器访问和估计方法相关的改进。 第4节专门介绍多线程版本。实验结果见第5节。我们在第6节中结束这项工作。2基于加权中值算子的在[9]中提出的RTWM算法计算离散信号的变换，该离散信号的样本已被脉冲噪声干扰RTWM基于基于由L1范数正则化的最小绝对偏差的回归来估计变换，其导致在其分量中呈现分散的解[10]。离散信号表示为向量z∈Cn。 计算变换 一 个信号的变换矩阵Φ∈Cnxn乘以信号以获得变换后的信号x∈Cn。 此矩阵由列J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8183∈2ǁ −∗ ǁX其表示正交信号（即，其内积等于0），根据期望执行的表征来选择。原始信号可以通过应用另一个基于 在原始变换的逆矩阵上;因此我们有z=x。在以下条件下计算的信号变换中包含的信息：当原始信号Z受到噪声的影响时，前述过程会严重恶化，这可能发生在其传输介质中、采样过程中或其操作的其它阶段。采样信号的特征在于y=z+v。其中z是原始信号，vCn，是的噪音向量后者的组件被假定为独立和相同的分布。当噪声向量v遵循具有零均值的高斯分布时，变换的估计在最大概率原则下是最优的，作为以下优化问题的解（参见等式（1））：x=argminy−x2（一）X然而，当噪声遵循大于高斯分布的重尾分布时，该方法的性能显著降低。拉普拉斯分布是当位置参数调整到中位数时概率最大化的分布[11]。 这种分布通常用于对具有大于高斯分布的重尾分布的现象（例如，脉冲噪声）进行建模。RTWM算法将该问题转化为一个L1范数正则化的最小绝对偏差回归问题，其求解方法是利用坐标归约法和加权中值算子来计算变换的各个系数.RTWM基于以下事实：在最大后验概率（MAP）框架下，最佳变换由找到最小化y Psi x1的x的问题的解决方案给出;如果噪声向量的分量是独立和相同分布的，并且遵循拉普拉斯分布。在某些实际应用中，信号的变换具有低百分比的非零系数。为了有利于这种类型的解决方案，一项被添加到取决于非零系数的大小的最小化问题。这是由正则化参数缩放的解向量的L1因此，鲁棒变换的估计针对解决以下优化问题（参见等式（2））：x= arg min{y−x<$1+λ<$$>x <$1}（2）在RTWM中估计解向量的所选方法是基于协调下降方法，该方法包括将N维问题减少到连续的一维问题。 该方法假设估计向量的所有条目都是已知的，除了其中之一。这使得问题可以简化为一个众所周知的优化问题，其解决方案是84J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81NK阿吉克ΨK⎧⎨(y−Ψ∗x+Ψk∗x)i.ΣKKKi=N+1K2i=1Ki=1X基于加权中值算子（参见等式（3）和（4））。xm+1=argmin{y−xm+kxm−kxk1+λxm 1}（3）KKKxm+1=argmin{|Ψi=1|| (y − Ψ ∗ x+100xm）-x|+λ |X|（四）为了明确方程（4）中待极小化函数的特征，提出了方程（4）中各项的重新定义重新定义了术语“k”和“i作为向量w的compponents，而项（y−nxm+ nknxm）ik我被分组作为z向量的分量。此外，这些向量中附加了惩罚项，因为它与前面的向量具有相同的结构，λ是w的最后一个分量，0是z的最后一个分量。其每个输入的定义在等式（5）和（6）中定义。这允许您将等式（4）重写为等式（7）所示。zi=M mK阿吉克岛对于i=1，...，N（五）w=|阿吉克岛| 对于i=1，...，Niλ i=N+1（六）xm+1= argminN+1个|z i − xk||（七）|(7)Ki=1这是一个分段线性函数，具有凸的特殊性，因此它至少有一个极小点。这类函数的最小值点可以使用加权中值算子找到一组值的加权中值与每个值的相关权重计算如下：对值zi进行排序，然后从最低到最高添加权重，直到累积和超过或等于值W o=1<$N +1 wi。因此，最后一个zi该算子应用于凸分段线性函数的参数当回顾该算子的定义时，可以看到，在这种情况下，它累积斜率，直到总和超过或等于斜率总和的一半。可以证明，当自变量等于zi的加权中值时，函数达到其最小值点（参见等式（8））。xm+1=中位数（（wiQzi）|（8）第二次定期报告上述方法用于迭代估计方法的构造：从零矢量开始，连续估计其每个分量，将所有其他分量设置为在前一次迭代中估计的值。从最后估计的向量开始重复该过程，直到初始优化问题中的误差收敛到适当的值，或者一旦某个误差收敛到适当的值，XKk我阿吉克岛X所考虑的是加权中值。MJ.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8185θx||K∗K∗← ← ← ← ←←←进行了多次迭代。在每次迭代中确定加权中值的方法对算法的性能有重要影响。在这项工作中，我们使用[12]中描述的方法，其算法复杂度为O（N），其中N是向量的大小，并且包括选择枢轴，使其成为接近中位数的元素，从而增加每次迭代丢弃的项目数量。式（2）中参数λ的最佳值为λ=θxK 根据使用的框架。这些涉及的参数是未知的。根据citebib：DXA中进行的实验，建议为每个组件设置θx参数这建议为每个待估计的分量设置不同的正则化在MAP框架下θxk可以用xk来估计。这导致正则化参数的最佳值取决于待估计的分量的值的事实最接近的已知值是在前一次迭代中获得的值，因此用于估计。另一方面，由于分子的值是未知的，因此建议在迭代发生且解向量收敛时重新定义正则化参数。以这种方式，最初该参数被赋予高值以有利于分散，在每次迭代中减小;因此，可以具有对估计向量的构成影响较小的非零分量。正则化参数以指数方式递减，这提供了必要的平滑性，使得向量的所有非空分量可以在执行迭代时出现。因此，我们有方程（9）来对正则化参数进行建模λm+1=τm（九）K|Xm|其中τ m=τ0β m，τ0是常数，β是衰减参数，通常是接近1的值以确保平滑。然而，由于分量可能为空，因此将分母加上一个分母以避免除以零。利用等式（10）中给出的表达式来计算正则化参数λm+1=τ（十）K+ |Xm|现在已经描述了RTWM的所有方面，为了清楚起见，以伪代码呈现算法1算法1与[9]中提出的算法不完全相同，其算法复杂度为O（itmax N3），其中itmax为迭代次数，N为向量的大小。然而，通过简单的修改（即，通过重新安排迭代周期，将计算复杂度O（N）降为O（1），得到了复杂度为O（itmax <$N2）的算法1。Algoritmo 1RTWM。原始O（itmax）1：函数RTWM（y，r，N，β，τ0，tolerance，iterationsNumber）2：x 0;y′0;re 0;im 0;w′0;阈值 τ03：对于m=0，m次Number，m++do4：对于k=0，kN，k++do5：λ阈值c+λx[k] λ86J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）812012年2月2日←←←∗[i][k]← ǁǁ6：z[0] 0;w[0]λ7：对于i=0，j=1，iN，i++do8：如果k=0，则9：z[j]←y[i]−y'[i]+x[k] −y [i][k]10：w[j][i][k]11：j++12：x[k]←getW eightedMedian（z，w，，w′，re，im，j）13：y′←x第14章： 能量15：如果能量耐受，则<16：休息17：阈值阈值β18：返回x该算法接收我们想要从中获得变换y的信号、变换的逆矩阵、要处理的信号的长度N、正则化的指数衰减参数β、正则化参数τ0的初始值、相对于原始信号容限的归一化误差能量中所需的最小值以及在估计中要执行的迭代次数作为参数。在第2行，初始化保持m和m+ 1次迭代的解估计的向量，以及用于正则化参数的计算的初始边界值。从第3行开始的循环按照指示的次数估计解决方案。向量x的每个分量的估计在第4行的周期内完成。在那里，计算待估计的分量的正则化参数。从第7行到第11行，计算向量w和z，将链接到正则化参数的向量作为第一项，其他向量根据上述等式计算。在第12行，使用向量z和w上的加权中值运算符估计当前坐标。在行13和14上，用最后估计的解计算向量YJ，并且在YJ和y之间找到归一化误差能量。如果该能量低于最小容差，则算法停止以返回x的最后估计，否则，边界值以β因子呈指数递减（第15至18行）。3RTWM性能的改进RTWM算法的性能改进过程分为几个阶段。它们中的每一个都侧重于改进[9]中提出的实现，并在第2节中描述，以减少总的执行时间。这是合理的，因为该算法的实际应用旨在实时处理由电信设备接收的信号。这意味着算法必须适合于在具有低计算能力的设备上运行，这些设备可以集成到数据处理系统中。以下各节将逐步介绍改进的版本，直到最终算法的开发。J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8187←←尼加拉瓜k←← ← ← ← ←←←←3.1版本1：简化计算在算法的当前状态下矢量z的计算基于等式（11）。可以看出，被估计的分量的先前值涉及N次乘法，然后涉及N次求和。使用代数，等式（11）可以简化为仅用和来代替这些运算，如等式（12）所示。zyi−yiJ+xki，k尼加拉瓜k（十一）zyi−yiJ+x吉吉（十二）这个新的表达式揭示了向量z的所有分量都被估计的分量的先前值当考虑一个zentry将是componentxk的新值，项yi−yi′是前一个值和新值之间的差异。因此，正确的做法是删除前一个组件的值之和，然后添加执行更新所需的差异，而不是替换xk 这在等式（13）和（14）中陈述。应该注意的是，该优化假设一旦分量xk取了非零值，则通过选择与正则化参数相关的元素，它将不再取该值在加权中位数。这是有效的，因为正则化参数具有主要减小的行为，尽管其值肯定会由于估计过程中xk然而，如果估计中的趋势是减小xk的绝对值，则一旦正则化参数已经通过指数衰减被充分递减并且通过加权中值算子选择另一个元素作为校正器，则算法将在后续迭代中实现它。zyi−yiJ杰希角（十三）xk+= getWeightedMedian（z，w）（14）此优化表示节省N次乘法和N次求和，仅 用一次求和替换它们。这是一个重要的优化，因为操作使用复杂的浮点数和双精度进行计算是昂贵的在处理时间。 算法2显示了相对于第2节中给出的原始版本所做的修改，用红色标记Algoritmo 2RTWM。版本1：简化计算1：函数RTWM（y，r，N，β，τ0，tolerance，iterationsNumber）2：x 0;y′0;re 0;im 0;w′0;阈值 τ03：对于m=0，m次Number，m++do4：对于k=0，kN，k++do5：λ←阈值c+x[k]6：z[0] 0;w[0]λ7：对于i=0，j=1，iN，i++do8：如果k[i][k]=0，则88J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）812002年2月2日←∗∗[i][k]← ǁǁ9：z[j]←y[i]−y'[i]10：w[j][i][k]11：j++12：x[k]←x[k]+getW eightedMedian（z，w，w′，re，im，j）13：y′←x第14章： 能量15：如果能量耐受，则<16：休息17：阈值阈值β18：返回x3.2版本2：内存访问改进在以不断访问存储器来获得计算所需数据为特征的算法中，仔细考虑访问模式是非常重要的这是因为存储器访问时间比在处理器中执行算术运算的时间长得多。为了缓解这个瓶颈，大多数当前的处理器具有分层存储器系统，其特征在于具有各种存储器设备，其中访问时间与其数据存储容量成分级存储器系统的优点之一是，当在主存储器中访问数据时，存储器处理器不仅将该数据复制到具有最低等待时间的设备之一（即，高速缓存），而是一组数据在他旁边，称为页面。此操作的目的是利用下一个指令需要访问此数据的高概率，并使其在低延迟设备（如高速缓存）上可用为了有效地利用分层存储器系统，算法实现处理连续定位的数据是重要的。访问矩阵的模式是一个临界点，它可能会因内存访问而产生瓶颈。 矩阵可以被认为是数组的数组。因此，如果数据 需要在每次迭代中访问不同的阵列，由于没有访问连续的数据，因此分层存储器系统将不会被有效地使用。每种编程语言都有一种方法来对齐矩阵中的数据。在C和C ++语言中，对齐是在行级别完成也就是说，每一行可被认为是连续存储的数据阵列RTWM需要访问矩阵k的列向量以估计解向量的每个分量并确定向量z和w。当通过矩阵的列向量访问矩阵时，分层存储器系统没有被有效地使用，因为访问的数据没有存储在连续的区域中。为了解决这个问题，可以使用转置矩阵，允许通过转置矩阵的行访问的列因此，它允许有效使用存储器系统的访问模式。然而，转置矩阵的使用迫使算法使用的内存量加倍。 由于原始矩阵仍然是必要的，因为它用于计算向量x，其中矩阵通过其行访问关于存储器访问的另一个改进是基于存储器布置相对于虚拟存储器页的大小的对准。由于内存处理程序复制处理器所需数据所在的页面并将其存储在低延迟设备中，因此在该页面上，J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8189←←← ǁǁ← ← ← ←←2012年2月2日←∗我≤尽可能多的数据将很快被访问如果所需的内存由内存处理程序分配在页面大小的倍数的位置，则可以确保这一点通过这种方式调整排列，使其占据尽可能少的页面。一个未对齐的内存块需要k+ 1次访问主存，每一次访问对应一个包含它的页面。如果这个内存块与页面数的倍数对齐，那么它只能包含在k这会阻止对主存的访问，而主存在运行时是昂贵的。为了实现页面大小的对齐，Linux内核与POSIX库一起使用了一个名为posix_memalign的函数，类似于经典的malloc。它在运行时分配与指定大小的内存地址对齐的内存块，在本例中，指定大小为页面大小。算法3给出了通过转置矩阵和存储器访问中的位置所Algoritmo 3RTWM。版本2：缓存访问改进1：函数RTWM（y，n，N，β，τ0，tolerance，iterationsNumber）2：x 0;y′0;re 0;im 0;w′03：转置（英语：Transposed）4：阈值τ05：对于m=0，m个元素Num是r，m++do6：对于k=0，kN，k++do7：对于i=0，j=0，iN，i++do8：如果T[k][i] k=0，则y[i]−y'[i]T[k][i]10：w[j]T[k][i]11：j++12：z[j] ←013：w[j] ←阈值十四：J++c+x[k]15：x[k]←x[k]+getW eightedMedian（z，w，w′，re，im，j）16：y′←x第17章： 你是我的女人18：如果能量耐受，则<19：休息20：阈值阈值β21：返回x3.3第3版：根据最新可用资料作出的原始算法提出仅使用在先前迭代中估计的向量来估计每个分量，如等式（5）、（6）和（7）中可见。这种方法不使用算法可用的最新信息。当估计分量k时，已经估计了范围0i k中的所有分量xm这些值是比属于前一次迭代的值更好的解向量估计。建议使用具有可用于每个分量的最新信息的yJ所提出的解决方案包括从向量yJ中减去分量的先前值的贡献，并加上最后估计值的贡献。当对项进行分组时，这等效于通过缩放到对应的列向量yJ来添加分量的最后两个值之间的差。需要添加的差异是应用9：z[j]←90J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81←←← ǁǁ← ← ← ←←2012年2月2日←∗KK向量z上的加权中值算子具有权重w（参见等式（15））。yJ←yJ+（xm+1−xm）k（15）这通过简单地添加几个向量加法运算来保持向量y它还消除了在每次外部迭代结束时的矩阵-向量因此，消除了对原始矩阵的需要，能够仅与转置一起工作。因此，通过在相同的内存空间中转置矩阵，消除了版本2中引入的内存使用的算法4显示了使用获得的最新信息的估计。Algoritmo 4RTWM。版本3：使用获得的最新信息1：函数RTWM（y，n，N，β，τ0，tolerance，iterationsNumber）2：x 0;y′0;re 0;im 0;w′03：转置（英语：Transposed）4：阈值τ05：对于m=0，m个元素Num是r，m++do6：对于k=0，kN，k++do7：对于i=0，j=0，iN，i++do8：如果T[k][i] k=0，则y[i]−y'[i]T[k][i]10：w[j]T[k][i]11：j++12：z[j] ←013：w[j] ←阈值十四：J++c+x[k]15：diffX←getW eightedMedian（z，w，w′，re，im，j）16：x[k]←x[k]+diffX17：y′←y′+diffXx xxt[k]第18章： 你是我的女人19：如果能量耐受性，则<20：休息21：阈值阈值β22：返回x3.4版本4：正则化参数下降的加速计算已经受脉冲噪声的信号的变换的直接方式包括应用矩阵-向量乘法，如在向量未经受噪声的情况下将进行的那样。图1显示了误差的归一化能量作为色散的函数，应用此方法计算变换，并使用RTWM算法获得最佳结果可以看出，对于矩阵-向量乘法，误差随着色散而减小这自然是由于噪声和信号能量之间的比率，该比率随着变换中存在更大数量的非零分量而变得更低。此外，RTWM算法在估计误差方面具有相反的行为。与直接方法相比，它以非常高的误差开始，并且随着信号色散的增加而减小。这表明该算法在色散很小的信号中执行时不具有良好的性能根据图1，该算法与以下算法相比，9：z[j]←J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8191图1.一、对于b=1的拉普拉斯噪声，RTWM获得的最小误差。直接法从65%分散。由于该算法的这些限制，它仅适用于其变换具有高水平色散的信号图2和图3给出了基于当前算法在估计具有1000个输入的矢量时的迭代的收敛性，其中对于两个分散水平，算法超过了矩阵矢量乘法的性能 长度N =1000，β = 0。95，并且已经使用了尺度参数b= 1的拉普拉斯噪声它表明，对于第一次迭代，收敛没有取得任何进展。这可以归因于这样的事实，即在该区域中，正则化参数没有被减小到足以允许非零分量的出现，从而减小估计中的误差图二、基于所执行的迭代的归一化误差能量分散度：60%为了减少迭代次数，其中收敛是不先进的，它被建议修改的算法，以这种方式，前一次迭代的归一化误差如果当前迭代的标准化误差相对于前一次迭代没有减少至少百分比p，则正则化参数在S次迭代的等价物中自动减少，减少92J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81←←←∗←−← ← ← ← ←←← ǁǁ←∗←←2002年2月2日←∗上一页能源图3.第三章。基于所执行的迭代的归一化误差能量分散度：90%要执行的迭代次数相同。这减少了算法的执行时间，因为执行了较少数量的迭代，其中收敛性没有改善。值P和S是算法的参数，并且可以根据正则化参数的衰减中需要多少平滑度来选择在算法5中，给出了关于加速参数和迭代中的跳跃的修改。这种改进，像版本3一样，在结构上修改了原始算法。Algoritmo 5RTWM。版本4：使用获得的最新信息跳跃加速度1：函数RTWM（y，n，N，，τ0，tolerance，iterationsNumber）2：x 0;y′0;re 0;im 0;w′0;T转置（）3：阈值τ04：加速度15：对于i=0，iJUMP，i++do6：加速度β7：上一个能源18：对于m=0，m个迭代N_m =r，m++d9：对于k=0，kN，k++do10：对于i=0，j=0，iN，i++do11：如果n=T[k][i]n= 0，则y[i]−y'[i]T[k][i]13：w[j]T[k][i]14：j++15：z[j] ←016：w[j] ←阈值十七：J++c+x[k]18：diffX←getW eightedMedian（z，w，w′，re，im，j）19：x[k]←x[k]+diffX20：y′←y′+diffX[k]第21章： 能量←y−y'222：如果先前能量>0能量>最小改变，则23：阈值加速度24：m m+JUMP25：上一页能源能源26：阈值阈值β27：返回x12：z[j]←J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81934使用多个执行线程的并行化（版本5）提出的RTWM算法的并行化方案包括分布-ING执行线程之间的变换向量的分量的估计通过这种方式，在每次迭代中执行的内部循环被并行化。这意味着每个线程必须能够计算向量z和w，计算它们的加权中值，并更新向量x。此外，必须收集这些更新的结果以构造向量yJ，必须使用该向量检查当前外部迭代中达到每个线程都必须拥有私有和共享内存资源，以及允许在访问共享数据时避免竞争条件的同步机制。这应该尝试最小化私有存储器的量访问共享变量的代码段共享内存：在RTWM算法中，消耗最多资源的数据结构是逆变换矩阵。这是由N2对的浮动点数组成的。这个矩阵和y向量在执行过程中不会被修改，它们的条目仅用于读取。因此，这些数据结构可作为线程之间的共享内存供线程使用该算法的结果主要是包含估计变换的向量x和保持逆变换的估计的向量YJ向量yJ在迭代结束时被丢弃，然而，它保留了用于估计向量x的分量的信息。因此，向量yJ是线程在一起工作时可以公开其结果的主通道。因此，yJ和x向量存储在共享存储器中。然而，为了避免过多的同步指令，每个线程在其私有内存中保留yJ向量的副本，并且在每次外部迭代结束时，该副本向量与yJ交换，y j具有执行的最后一次迭代的结果最后，允许访问代码的关键部分（信号量和互斥量）的同步工具存储在共享内存中。bf私有内存：每个线程都应该能够执行操作来估计向量x的分量的值。这需要计算应用加权中值算子的向量z和w因此，这对向量在每个线程中都是必需的，并存储在私有内存中。为了收集向量中所有线程的估计结果，使用在最新可用信息的使用的优化中实现的相同思想。这涉及通过将yJ添加到由迭代中引入的差异缩放的向量列来并行化矩阵向量乘法。由于对向量yJ的访问必须同步，并且为了减少对它的访问量，每个线程的总和都累积在一个私有向量94J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81宽度←∗ ∗∗←∗←z[j]←−← ǁǁD.以这种方式，在对应于它们的分量的估计结束时，线程可以将它们在向量YJ内的累积贡献相加。在每次外部迭代之后，向量d必须重置为零要处理的数据的分布：每个线程都有一组要估计的组件。这些的分配包括将整个向量划分为连续的组件集，并为每个线程分配一个集合结构性改进：在正则化参数的衰减中加速，要求线程能够识别它们是否应该加速正则化参数的减小。为了实现这一点，在最后一次迭代中获得的误差能量被放置在共享存储器中。当线程执行能量检查时，它公开通过共享内存获得的值。多线程算法由初始化和控制部分以及线程执行部分组成。算法6和7分别呈现这些部分。Algoritmo 6RTWMC。版本5：多线程。加速度最新信息函数RTWMC（y，n，N，β，tolerance，iterationsNumber，τ0，threadsNumber）第二章：x←0;y′←0;转置（n）计数器←0;endCounter←04：能量y← −1;能量e←0N线数6：对于k=0，kthreadsNumber−1，k++ ddoCreateThreads8：L<$kwidth;R<$′ （k+1）最大宽度10点整：RTWMCthread（y，y，x，n，L，R，N，β，tolerance，iterationsNumber，τ0，energyy，energye，EnergyCounter，endCounter，threadsNumber）L←（threadsNumber −1）宽度R←N′RTWMCthread（y，y，x，n，L，R，N，β，tolerance，iterationsNumber，τ0，energyy，energye，EnergyCounter，endCounter，threadsNumber）12：joinThreads（）d等待线程完成运行return xd返回估计的变换RTWMC的Algoritmo 7线程。版本5：加速。 最新信息程序RTWMCtHRE ad（y，y′，x，n，L，R，N，β，tolerance，iterationsNumber，τ0，energyy，energye，n_counter，endCounter，threadsNumber）;previousEnergy<$−1;threshold<$τ0;acceleration<$14：对于i=0，iJUMP，i++do加速度β6：对于m=0，m个迭代Num是r，m++do差异08：对于k=L，kR，k++do对于i=0，j=1，iN，i++do10：如果k=0，则Y[i]privateY[i][k][i]12：w[j][k][i]J++14：z[j] ←0w[j] ←阈值十六：J++c+x[k]十八：XDiff←getW eightedMedian（z，w，w′，re，im，j）difficerence←difficerence+XDiff加权[k]privateY2：J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8195←∗∗ ← ∗∗2∗←∗∗ −电子邮件上一页能源←← ∗←∗∗2能量y20：x[k]x[k]+XDiffaquireMutex（）22：当计数器>0时，releaseMutex（）24：wait（）quireMutex（）26：y二十八：endCounterendCounter+1ifendCounter==threadsNumberthenifthreadenergyy==−1then第30章：你是我的女人电子能 ←y−y'232：如果能量容差大于E，则<第34章：你是谁？三十六：三十八：endCounter% 0SignalAll（）当endCounter>0时，releaseMutex（）wait（）40：getString（）四十二：如果endCounter==1，则signalAll（）releaseMutex（）第四十四章：突破其他46：如果线程计数器==threadsNumber，则48：如果五十：联系我们previousEnergy>0&&e> MINCHANGE则阈值←阈值加速度m←m+JUMP五十二：上一篇能源能源e隐私Y′y′SignalAll（）54：releaseMutex（）五十六：阈值β返回5实验结果本节介绍了为测量总执行时间以及所开发算法的不同版本的结果质量而执行的实验结果。使用增量表示法来比较每个版本与原始版本的执行时间。5.1所进行实验的描述对RTWM的原始版本进行了行为分析，得到了在100、200、300、400、e96J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）81500、600、700、800、900、1000、1500和2000个组件上执行的每个具有特定向量大小的测试执行20次，并取其所有执行时间的中位数。以这种方式，可以基于要估计的向量的分量的数量来获得描述算法的执行时间的图。此外，这样做是为了将算法暴露于与实际应用中类似的条件。为 了 使 模 拟 更 接 近实 际 情 况 ， 该 算 法被 用 来 计 算 离 散 傅 里 叶 变 换（DFT）。此外，已知在许多实际应用中，变换后的矢量通常具有相当大的失真水平J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8197∗是对称的。因此，为了获得在应用DFT时生成具有这些特征的变换的矢量，首先通过引入色散和对称性来生成变换矢量然后，使用逆变换，IDFT，计算表示没有噪声的信号的矢量。最后一步是将拉普拉斯噪声添加到按照前面的过程获得的向量的分量中。在涉及原始算法变化的优化情况下，给出了比较所获得的标准化误差的能量的图，以验证所做的修改保持了结果的质量。在估计1000个分量的矢量和使用参数β = 0时进行了数值试验。对于正则化参数的指数衰减，如[9]中所用。用于污染的噪声遵循具有零均值和尺度参数b=1的拉普拉斯分布。专用于估计的迭代次数后者允许更详细地理解估计的数值行为。最后，在0%至90%范围内的固定分散百分比上进行测试。实验在Intel Core i7- 7500 U计算机上进行，具有四个核心和16 GB RAM，使用Ubuntu。5.2原始RTWM图4示出了作为基于算法1估计的向量的长度的函数的执行时间。 可以看出，执行时间的增加取决于问题的大小，其行为对应于理论上的二次复杂度O（itmax N2）。在数千个组件的数量级的向量中的运行时间超过数百秒。估计2000个元素的矢量需要886秒。这揭示了在实时信号处理中使用这种实现的不可能性。见图4。 原始RTWM的执行时间。98J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）815.3版本1图5显示了在版本1和原始实现的实验中获得的执行时间。可以看出，在最坏的情况下，其中要估计的向量的长度是2000个分量，已经实现了执行时间的大约100秒的减少。相对于原始实现，平均性能提高了11%。这显示了显著的改善，正如预期的那样，减少了大量的停车点操作。图五、版本1和原始版本的性能5.4版本2图6显示了版本1、2和原始实现的执行时间正如预期的算法，使密集使用的存储器访问，通过充分利用分层存储器结构的相当大的平均性能的改善已获得相对于版本1和累积28%，相对于原始的实现。5.5版本3该版本修改了原始算法的数学程序，因此有必要验证结果的质量是否得到保持。图7显示了使用原始实现和版本3获得的最佳误差之间的比较可以看出，对于大于60%的色散水平，该版本实现了比原始算法更好的数值结果，获得高达1 dB的增益。图8显示了版本2、3和原始实现的执行时间可以看出，与原始实现相比，根据长度，它们在最坏情况下减少了300秒以上以百分比计算，相对于版本2，平均性能的改进为5%，而相对于原始实现，平均性能的改进为33%。对于长度100和J.E. Ramírez et al. /Electronic Notes in Theoretical Computer Science 349（2020）8199图第六章版本1、2和原始版本的性能见图7。 最佳误差的归一化能量（dB），版本3和原始。 拉普拉斯噪声，μ= 0，b = 1.200的情况下，可以看出性能降低了8%，然而对于其他长度，获得了7%注意到对于最新的优化，较短的长度比其他长度获得了更大的累积改进，这种减少与此相反，但保持了性能增长的平衡。出于这个原因，并为提高数值结果的质量，尽管缩短了长度，但采用这种优化是合理5.6版本4图9显示了版