Data Decomposition
1.1 问题
如何将待解决的问题的数据分解为能够并行运行的数据单元(units)?
1.2 上下文
并行算法的设计者必须首先详细了解待解决的问题,除此之外,还必须识别如下几个关键因素:
1)计算强相关的部分:待解决问题中的哪部分需要进行大量运算;
2)关键数据结构:主要是对什么数据进行运算;如何进行运算。
当基本问题理解后,设计师必须考虑解决问题的需要完成哪些任务以及这些任务中包含哪些数据。为了创建并行算法,关键不是要进行哪种分解,而是首先从哪种分解开始,任务分解和数据分解都要进行。
什么情况下该首先采用基于数据的分解方式呢?如果存在以下场景,则从数据分解开始时比较好的选择:
1)待解决问题中计算强相关的部分都是围绕数据进行组织的;
2)同样的操作应用到数据结构的不同部分;
1.3 考虑因素
1.3.1 灵活
此时考虑灵活性主要是为了能够让设计能够满足不同的实现需求,这里的实现就是具体采用的技术,例如采用Java编程,采用多CPU的小型机运行等,如果客户不强制要求,在这个阶段就不要限制这些。当然如果问题里面本身已经包含了这种实现,那就必须考虑这种实现的限制了。例如客户要求只能运行在小型机上面,那么设计的时候就需要考虑小型机的特点对人物分解的影响了。
1.3.2 有效
并行程序只有在随着并行计算机的规模增大时效率能够按比例增长才有意义。对于任务分解来说,这就意味着我们需要足够的任务来使得所有计算机都处于忙碌的状态。
通过使每个任务有足够的工作(Work)来弥补管理任务间的依赖带来的效率损失才能达到这点。当然,效率提升会带来灵活性的降低。
1.3.3 简单
再怎么好的程序也要人维护吧,所以再怎么复杂怎么好都要考虑怎么维护。
以上三种因素互相制约,具体怎么平衡,还是要看设计师的水平。
1.4 解决方法
如果已经基于任务进行了分解,则可以针对每个任务进行数据分解。如果定义良好且清晰的数据能够和每个人物关联,则数据分解就简单了。
如果我们从数据分解开始进行分解,则这个时候还没有任务,因此我们不能盯着任务进行分解了,而应该盯住最主要的数据结构,然后考虑如何将数据结构分解为数据块,使得针对数据块的操作能够并行。一些常见的样例如下:
1)线性数据结构:可以采用“分段方式”对数据进行分解,针对不同的数据段进行并行操作;如果是一个多维的数据结构,则可以采用多种方式进行分解:按列、按行、按数据块。
2)递归数据结构:可以采用“递归方式”对数据进行分解,所谓“递归方式”就是指针对数据的一部分操作和针对整个数据的操作原理上是一样的。典型的样例就是“树”这种数据结构了,每个子树其实都是一颗树,可以先对子树进行计算,然后将子树合并起来又是一颗树,这样就能够通过并行来完成树的计算了。
分享到:
相关推荐
变分模式分解Variational Mode Decomposition源码
一个应用经验模式分解(empirical mode decomposition) 方法的matlab程序例子
矩阵分解 (decomposition, factorization)是将矩阵拆解为数个矩阵的乘积,可分为三角分解、满秩分解、QR分解、Jordan分解和SVD(奇异值)分解等,常见的有三种: (1)三角分解法 (Triangular Factorization) ...
EMD的改进方法的代码,局部均值分解(Local Mean Decomposition)算法MATLAB代码.
经验模式分解(Empirical Mode Decomposition,EMD)是一种新的信号处理技术,它是基于数据本身的,且能在空间域中将信号进行分解,从而可以区分噪声和有用信号。
按照算法步骤对IRIS数据进行仿真,IRIS数据是由鸢尾属植物的三种单独的花的测量结果所组成,模式类别数为3,特征维数是4,每类各有50个模式样本,共有150个样本。首先使用分解聚类算法分离出第一种鸢尾属植物,再对...
这是用MPI做的关于矩阵的qr分解的程序,程序中很好的实现了分解过程的并行性
介绍了一种新的非平稳信号分析方法———局部均值分解(Localmean decomposition,简称LMD) 。LMD方 法可以自适应地将任何一个复杂信号分解为若干个具有一定物理意义的PF ( Product function)分量之和,其中每个PF分 量...
其中FDM.example是主程序直接运行即可,共有五个例子。 参考文献:The Fourier decomposition method for nonlinear and non-stationary time series analysis
基于Matlab的一套经验模式分解代码、 % IMF = EMD(X) where X is a real vector computes the Empirical Mode % Decomposition [1] of X, resulting in a matrix IMF containing 1 IMF per row, the % last one ...
MPI 并行计算,处理经典QR分解问题,包含测试数据
变分模态分解,VMD(Variational mode decomposition)是一种新型的基于频域的完全非递归信号分解估计方法,它结合了经典的维纳滤波,Hilbert变换与频率混合。
经验模式分解(empirical mode decomposition, EMD)方法是Huang提出的,它是一种新的时频分析方法,而且是一种自适应的时频局部化分析方法:①IMF与采样频率相关;②它基于数据本身变化。这点是EMD优于傅立叶变换方法的...
1.CEEMD互补集合经验模态分解,运行主程序main即可,数据为一维时间序列信号数据。 2.互补集合模态分解(complementary ensemble empirical mode decomposition)时引入的是互补的噪声。这些噪声是独立同分布的,...
本程序输入一个矩阵及误差限,得出其几何均值分解,该算法广泛应用于通信系统中。
经验模态分解(Empirical Mode Decomposition,EMD)法是黄锷(N. E. Huang)在美国国家宇航局与其他人于1998年创造性地提出的一种新型自适应信号时频处理方法,特别适用于非线性非平稳信号的分析处理。
局部均值分解Local Mean Decomposition 用于振动信号的自适应分解,获得若干分量,非常实用。
经验模态分解(Empirical Mode Decomposition,简称EMD))方法被认为是2000年来以傅立叶变换为基础的线性和稳态频谱分析的一个重大突破 ,该方法是依据数据自身的时间尺度特征来进行信号分解,无须预先设定任何基函数...