k*********g
发帖数: 791 | 1 并行计算
并行计算在科学、工程计算中是不可或缺的。通常人们认为，并行计算的瓶颈在于如何
实现不同处理器之间数据通信的时间远少于在当地处理器上的计算时间。本人的数值实
验和经验表明，这个根本不是并行计算的最大难点，这个其实这个很容易实现。假设我
们解决一个2维问题，N为一个方向上的未知数，把2维区域分成m^2个模块，每一个模块
由一个处理器管理。那么当地的计算量和N/m的平方成正比，而数据交换只跟N/m成正比
。对于典型的并行计算问题来说，N远比m要大，故通常的担忧、观点是偏颇的，没有抓
住问题要害。
数值实验表明，已经解决了人们关心的那个所谓瓶颈问题的现有软件的并行效果没有一
个是理想的。本人的研究表明，并行计算的瓶颈是，并行过程改变了原先的单处理器计
算的迭代结构，这种改变通常是往不利的方向改变的，并且跟处理器之间的数据依赖程
度有关，数据依赖程度越高，迭代的恶化程度越厉害。在有限元中，外来处理器在当地
处理器的渗透程度很高，而在谱元法中，外来处理器只允许影响本地处理器最表面的一
层。本人曾经的实验室同事的数值实验表明，谱元法能达到前所未有的并行效果。 |
j****x
发帖数: 943 | 2 "数据交换只跟N/m成正比" 不是吧？跟处理器之间的数据依赖程度有关吧? 根本用不到
的数据，不用传递.通信的cost既同算法有关，又和decomposition有关。 |
h*******x
发帖数: 347 | 3 原创？
整个一误导。改变了原先迭代结构就是改变数据通信。想吹谱元法不用贬有限元。 |
c***r
发帖数: 1570 | 4 任何并行算法都是要事先计算 O_comm() 和O_comp（）的大小的，
然后再动手编程，
当O_comp大于 O_comm 时，并行效果越好，
当O_comm 小于 O_comp时，并行效果越差，
这是做并行的常识。
并行算法要具体问题具体分析，
以上只适用于基于Mpi的并行。
shared memory的和 gpu fermi的下次有空再聊。 |
j****x
发帖数: 943 | 5 gpu如果要不同的multiprocessor之间传递数据，那就是一出悲剧。所以对nonlinear的
problem，一个gpu没有多大提高，除非你有n个gpu，那还不是要用mpi，不知道nvidia
的infiniband搞定了没。 |
c***r
发帖数: 1570 | 6 bus contention 永远存在，估计nvidia没那么块搞定。 |
k*********g
发帖数: 791 | 7 你们说的这些都不重要，都可以用“事先的估计”一个东西行不行。“数值计算中的并
行难点”，不是你们说的东西，而是原先的好迭代结构被破坏了。 |
k*********g
发帖数: 791 | 8 “原先的好迭代结构被破坏了”是无法事先估计的，因为是个非常复杂的数学系统。
还是仔细看看我写的吧，都是“第一手的数值实验结果+分析”的结果。 |
j****x
发帖数: 943 | 9 有一腚道理, 如果过于复杂，还是事先很难分析准的。 |
c***r
发帖数: 1570 | 10 并行能有多复杂？
线代系统不就是矩阵分块, 建立halo和ghost node吗，然后在allgather么，
unstructured mesh稍微麻烦点，也不见得多复杂。
粒子系统不就是求大质心么换算么，顶多来电quadtree什么的玩意。
图像处理的并行，就不说了，dependent相对少很多。
这些都是能求O（f(n)）的.
“原先的好迭代结构被破坏了” -- 迭代结构是可以改的，mpi并行的迭代当然要用并
行的迭代方式。“第一手的数值实验结果+分析”的结果 -- 恐怕只是某几个 非计算密
集型的实验，以偏盖全，以特殊代表广义是最可怕的研究方式。
以上只是说mpi的。 |
|
|
c*******h
发帖数: 1096 | 11 粒子系统如果要解线性方程组的话有没有什么好用的preconditioner？
最近想这玩意想到我头痛
【在 c***r 的大作中提到】
: 并行能有多复杂？
: 线代系统不就是矩阵分块, 建立halo和ghost node吗，然后在allgather么，
: unstructured mesh稍微麻烦点，也不见得多复杂。
: 粒子系统不就是求大质心么换算么，顶多来电quadtree什么的玩意。
: 图像处理的并行，就不说了，dependent相对少很多。
: 这些都是能求O（f(n)）的.
: “原先的好迭代结构被破坏了” -- 迭代结构是可以改的，mpi并行的迭代当然要用并
: 行的迭代方式。“第一手的数值实验结果+分析”的结果 -- 恐怕只是某几个 非计算密
: 集型的实验，以偏盖全，以特殊代表广义是最可怕的研究方式。
: 以上只是说mpi的。
|
c***r
发帖数: 1570 | |
c*******h
发帖数: 1096 | 13 矩阵的ij元就是粒子和粒子j之间的相互作用么
不用那么死的，思维开阔一点
【在 c***r 的大作中提到】
: 粒子系统哪里来的线代方程组？
: 我服了。。。。
|
c***r
发帖数: 1570 | 14 那不是把简单问题复杂化？
这样弄顶多算几千个粒子吧，而且可选用势能非常有限。
如果为了尺度耦合选择这种方法，到是有点新意，但编程上实现起来难，
而且很不稳定。
preconditioner不是万能钥匙， |
c*******h
发帖数: 1096 | 15 我的问题不是在物理上的，是在统计上的
几千乘几千的矩阵一个dense solver瞬间就能解出来
不过手头上的问题很大，至少是10^6级的，再上去就是10^9, 10^12级的
没有mesh（当然也不是不能造个mesh），所以基本上只能迭代
迭代的话没有preconditioner根本算不出来，做一万次迭代都不收敛
那不是把简单问题复杂化？
这样弄顶多算几千个粒子吧，而且可选用势能非常有限。
如果为了尺度耦合选择这种方法，到是有点新意，但编程上实现起来难，
而且很不稳定。
preconditioner不是万能钥匙，
【在 c***r 的大作中提到】
: 那不是把简单问题复杂化？
: 这样弄顶多算几千个粒子吧，而且可选用势能非常有限。
: 如果为了尺度耦合选择这种方法，到是有点新意，但编程上实现起来难，
: 而且很不稳定。
: preconditioner不是万能钥匙，
|
c***r
发帖数: 1570 | 16 preconditioner 来源于 Ax=b中的A,
但是如何决定 preconditioner 或者说 matrix P,
是有 tradeoff的，看书吧，不是一句话说的完的，
preconditioner 还有可能导致计算结果错误，用的时候要注意。
FGMRES应该是最好的了，不过编起来费事。
对称阵 用 PCG快一些，也好编。
迭代都不收敛 -- 不是所有Ax=b都有解的，不收敛也可能是本生无解。 |
c*******h
发帖数: 1096 | 17 矩阵是对称正定的，不需要gmres，cg就可以
只是条件数很大，所以跑几千步都不见收敛
没发现有哪本书讲粒子系统这样的矩阵的preconditioner
常用的稀疏矩阵的preconditioner基本不大合适
能想到的合适的只有approximate inverse，但也不是经常work
如果你碰巧知道有什么好的preconditioner的话请share一下
【在 c***r 的大作中提到】
: preconditioner 来源于 Ax=b中的A,
: 但是如何决定 preconditioner 或者说 matrix P,
: 是有 tradeoff的，看书吧，不是一句话说的完的，
: preconditioner 还有可能导致计算结果错误，用的时候要注意。
: FGMRES应该是最好的了，不过编起来费事。
: 对称阵 用 PCG快一些，也好编。
: 迭代都不收敛 -- 不是所有Ax=b都有解的，不收敛也可能是本生无解。
|
l*****i
发帖数: 3929 | 18 incomplete LU/Cholesky factorization?
【在 c*******h 的大作中提到】
: 矩阵是对称正定的，不需要gmres，cg就可以
: 只是条件数很大，所以跑几千步都不见收敛
: 没发现有哪本书讲粒子系统这样的矩阵的preconditioner
: 常用的稀疏矩阵的preconditioner基本不大合适
: 能想到的合适的只有approximate inverse，但也不是经常work
: 如果你碰巧知道有什么好的preconditioner的话请share一下
|
n*******0
发帖数: 2002 | 19 并行编译器编写人员表示不知道lz在说啥。
【在 k*********g 的大作中提到】
: 并行计算
: 并行计算在科学、工程计算中是不可或缺的。通常人们认为，并行计算的瓶颈在于如何
: 实现不同处理器之间数据通信的时间远少于在当地处理器上的计算时间。本人的数值实
: 验和经验表明，这个根本不是并行计算的最大难点，这个其实这个很容易实现。假设我
: 们解决一个2维问题，N为一个方向上的未知数，把2维区域分成m^2个模块，每一个模块
: 由一个处理器管理。那么当地的计算量和N/m的平方成正比，而数据交换只跟N/m成正比
: 。对于典型的并行计算问题来说，N远比m要大，故通常的担忧、观点是偏颇的，没有抓
: 住问题要害。
: 数值实验表明，已经解决了人们关心的那个所谓瓶颈问题的现有软件的并行效果没有一
: 个是理想的。本人的研究表明，并行计算的瓶颈是，并行过程改变了原先的单处理器计
|
c***r
发帖数: 1570 | 20 不了解这种粒子矩阵，感觉你的系统是无解的，
别再preconditioner上花时间了。
可以做的工作很多，应该选择有意义的
【在 c*******h 的大作中提到】
: 矩阵是对称正定的，不需要gmres，cg就可以
: 只是条件数很大，所以跑几千步都不见收敛
: 没发现有哪本书讲粒子系统这样的矩阵的preconditioner
: 常用的稀疏矩阵的preconditioner基本不大合适
: 能想到的合适的只有approximate inverse，但也不是经常work
: 如果你碰巧知道有什么好的preconditioner的话请share一下
|
|
|
c***r
发帖数: 1570 | 21 大哥，都说了是迭代求解器了
【在 l*****i 的大作中提到】
: incomplete LU/Cholesky factorization?
|
c***r
发帖数: 1570 | 22 总算遇到一个懂行的了，这年头连bbs都要打假。
【在 n*******0 的大作中提到】
: 并行编译器编写人员表示不知道lz在说啥。
|
c*******h
发帖数: 1096 | 23 正定的怎么可能无解。。
呵呵，做研究的乐趣就在这里。难，但是总能找到办法的
整个大问题是很有意义的，在这里碰上瓶颈，突破了之后能带来很大的影响
【在 c***r 的大作中提到】
: 不了解这种粒子矩阵，感觉你的系统是无解的，
: 别再preconditioner上花时间了。
: 可以做的工作很多，应该选择有意义的
|
c*******h
发帖数: 1096 | 24 preconditioner跟本身的solver没什么关系，不同种类可以互相搭配的
我的确在往incomplete cholesky的方向去想。当然因为矩阵是满的，得指定sparse
pattern。某种程度上思路有点像approximate inverse
【在 c***r 的大作中提到】
: 大哥，都说了是迭代求解器了
|
l*****i
发帖数: 3929 | 25 你是明白人，我觉得incomplete facrotization还是不错的
【在 c*******h 的大作中提到】
: preconditioner跟本身的solver没什么关系，不同种类可以互相搭配的
: 我的确在往incomplete cholesky的方向去想。当然因为矩阵是满的，得指定sparse
: pattern。某种程度上思路有点像approximate inverse
|
c*******h
发帖数: 1096 | 26 你有什么经验吗？
incomplete cholesky很容易break down
我以前老板就说，当初搞不完全分解的人都是冲着对角占优的矩阵去的
但是粒子系统的矩阵很少会对角占优的
真是头痛
【在 l*****i 的大作中提到】
: 你是明白人，我觉得incomplete facrotization还是不错的
|
c***r
发帖数: 1570 | 27 恩，不错，
查了查，incomplete factorization 是不错，
有成熟算法，可以直接拿来用。
还是劝你一句，别把这个preconditioner搞太深，难度大，debug周期长，而且没什么
意义 |
c*******h
发帖数: 1096 | 28 我见过一些做流体的人，他们的确不大相信preconditioner这一套
这可能是research philosophy，也有可能是现实的问题大家挖空了脑袋都想不出好的
preconditioner
恰巧我以前碰到过一个问题，preconditioner能够显著的提高收敛速度，所以我还是相
信的
【在 c***r 的大作中提到】
: 恩，不错，
: 查了查，incomplete factorization 是不错，
: 有成熟算法，可以直接拿来用。
: 还是劝你一句，别把这个preconditioner搞太深，难度大，debug周期长，而且没什么
: 意义
|
c***r
发帖数: 1570 | 29 preconditioner 是可以提高收敛速度，本来要200步迭代，加了p只要40步就能搞定了
，但也有风险，可能导致计算结果不真实，如果一个算法算出的结果是错的，那么速度
再快又有什么意义呢 |
c*******h
发帖数: 1096 | 30 这要看矩阵的性质和preconditioner的性质了。所以很多时候试出来work是不够的，要有
理论保证大家才相信
【在 c***r 的大作中提到】
: preconditioner 是可以提高收敛速度，本来要200步迭代，加了p只要40步就能搞定了
: ，但也有风险，可能导致计算结果不真实，如果一个算法算出的结果是错的，那么速度
: 再快又有什么意义呢
|
|
|
j****x
发帖数: 943 | 31 问个问题，很多library都有现成的preconditioner，为啥要自己写和debug呢？ |
c*******h
发帖数: 1096 | 32 有的都是现成容易套的，像ilu，像sor。大的solver一般都会留个接口
让用户提供一个preconditioner，因为不是现成的都是可以用到自己
的问题上的，留给用户自己设计的权利
【在 j****x 的大作中提到】
: 问个问题，很多library都有现成的preconditioner，为啥要自己写和debug呢？
|
t*****z
发帖数: 812 | 33 有限元并行不考虑i/o就什么都不是，管你multi-core, or GPU |
k*********g
发帖数: 791 | |
b****e
发帖数: 906 | 35 考虑一下实际计算中的roundoff error,还有，完全的正定矩阵它的condition number
也可以很小，cg的收敛速度为1/condition number
【在 c*******h 的大作中提到】
: 正定的怎么可能无解。。
: 呵呵，做研究的乐趣就在这里。难，但是总能找到办法的
: 整个大问题是很有意义的，在这里碰上瓶颈，突破了之后能带来很大的影响
|
