y**b
发帖数: 10166 | 1 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
想到以下几个方案：
1。上述的主进程读取初始数据文件，然后切割分发到各进程。
2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
从接收到的数据文件寻找相应颗粒。与方案1相比，避免了双重循环。
3。各进程都读取初始数据文件，然后自行从接收到的数据文件寻找相应颗粒。也避免
了双重循环。
4。进行预处理将初始数据文件分割成大约50k个文件，各进程按文件编号进行读取。
5。将该数据文件完全parallel io化。注意输出文件并不会含有各进程占有多少纪录
或颗粒的信息，因此无法保证可以实现具有正确空间划分的并行输入。
方案2和3理论可行，实际上由于受到节点内存容量的限制，并非实际可行。现在一般
计算节点有128GB内存，大内存节点有512GB~1024GB内存。以一个节点36核（或进程）
为例，单节点需要内存30GBx36才能完成方案2或3。方案2也许可以改成异步broadcast，
让每个节点上的36个进程在不同时间接受数据、处理数据并释放内存，从而避免消耗巨
大内存。方案3也许可以改成让每个节点上的36个进程依次读取数据、处理数据并释放内
存，从而避免消耗巨大内存。这两个改进可能需要特别的进程控制和时序控制，并非易
事。
6。还有个方案是让每个节点的36个进程共享部分内存区域，其中一个进程读取数据，
其它进程自动获得这些数据。按方案2，主进程只需向各个节点的某一进程broadcast
数据；按方案3，各节点只需某一个进程读取数据文件。
请建议，谢谢。
补充说明：
先说明一下问题，用离散单元法（DEM）模拟颗粒行为，比如这种：https://www.
youtube.com/playlist?list=PL0Spd0Mtb6vVeXfGMKS6zZeikWT55l-ew
该方法原理非常简单，主要是颗粒形状的表达、颗粒之间的接触侦测和解析、颗粒之间
的接触模型的精度这些因素很消耗cpu。并行算法的基本思想就是用3d box/block划分
空间，各个颗粒按其质心所在位置划分到不同box。每个box及所含颗粒信息发送到对应
的cpu/core，各个box与相邻的boxes通过ghost layer(包含至少一层颗粒)交换接触
信息，每个box得与周边的26个邻居交换信息，视频中绿色网格就是用于空间划分的
boxes。动态过程中某个颗粒可能从一个box迁移到另一个box。
可以将上面视频得到的样本(1 million particles)进行复制，这样可以得到非常巨大
的样本，目标是100M或1 billion，作为初始计算数据。
原来用方案1处理1M左右的颗粒并没有遇到困难，但是处理50M用到更多cpu后就出现了
上述困难。 |
m******r
发帖数: 1033 | |
w***g
发帖数: 5958 | 3 几个建议：
1. 任务划分，我估计就是个hash函数。如果是我，我会在内存中建一个
50K个元素的hash表。然后把50M个颗粒往这个hash表里放。这个操作就是
一重循环。然后再把hash表里的50K个元素往外发，也就是发50K次，
肯定能完成了。
因为hash表里的元素长度不一，对应的计算量也是不确定的。所以随机
把50K个元素对应到n个节点，n越大负载就会越不均衡。所以可以在
头节点大致优化一下，想一个heuristic把50K个颗粒表划分到n个节点。
这样划分后，每次只要往一个节点发一个比较大的数据块就行，数据划分
的问题就解决了。
2. 因为数据本身也不是那么大，用2或者3应该也可以。就是稍微浪费点。
3. 你的每个计算机节点是多核，所以这种架构最好是MPI-OpenMP。
就是每个计算机内部用OpenMP写，共享内存。
4. 你这个问题我感觉不会是linearly scalable的。感觉会涉及到相邻颗粒
之间的interaction。这样的话估计也不是节点越多越好。我估计有个
十来台机器，算是320个节点，也就差不多了。节点再多估计也没用。
如果是我，我会试着先用一台机器算。
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
x****u
发帖数: 44466 | 4 这几种方案不应该有区别，楼主用错了什么东西吧
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
b*******s
发帖数: 5216 | 5 visitor pattern + mmap
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
e*******s
发帖数: 1979 | 6 用hadoop不好吗 一定要自己造轮子
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
h*****g
发帖数: 15 | 7 为什么不能并行读写？不同的进程读文件的任何位置都不会干扰。如果是要写到同一个
文件里面的话，那么每个进程写在自己所划分的一块区间就行了。 |
d***a
发帖数: 13752 | 8 单节点的内存是够了。瓶颈很有可能在盘I/O和网络I/O。
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
a*******3
发帖数: 220 | 9 是做分子动力学么，如果相互作用是近程（有cut-off distanve)的话还是可以scale得
很好的。如果是长距就得考虑一些special technique比如傅立叶变换了. 可以参考一
下LAMMPS的documentation
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
c*******v
发帖数: 2599 | 10 他要的“相应颗粒“这步如果是严格的话。启发式似乎无法解决。缺点类似
于5。
他还是要把划分的逻辑说一下。不然无法解决的。
: 几个建议：
: 1. 任务划分，我估计就是个hash函数。如果是我，我会在内存中建一个
: 50K个元素的hash表。然后把50M个颗粒往这个hash表里放。这个操作就是
: 一重循环。然后再把hash表里的50K个元素往外发，也就是发50K次，
: 肯定能完成了。
: 因为hash表里的元素长度不一，对应的计算量也是不确定的。所以随机
: 把50K个元素对应到n个节点，n越大负载就会越不均衡。所以可以在
: 头节点大致优化一下，想一个heuristic把50K个颗粒表划分到n个节点。
: 这样划分后，每次只要往一个节点发一个比较大的数据块就行，数据划分
: 的问题就解决了。
【在 w***g 的大作中提到】
: 几个建议：
: 1. 任务划分，我估计就是个hash函数。如果是我，我会在内存中建一个
: 50K个元素的hash表。然后把50M个颗粒往这个hash表里放。这个操作就是
: 一重循环。然后再把hash表里的50K个元素往外发，也就是发50K次，
: 肯定能完成了。
: 因为hash表里的元素长度不一，对应的计算量也是不确定的。所以随机
: 把50K个元素对应到n个节点，n越大负载就会越不均衡。所以可以在
: 头节点大致优化一下，想一个heuristic把50K个颗粒表划分到n个节点。
: 这样划分后，每次只要往一个节点发一个比较大的数据块就行，数据划分
: 的问题就解决了。
|
|
|
c*******v
发帖数: 2599 | 11 楼主标题没写清楚。我的理解是，一个节点读了一条记录后，
只能接受这个初始节点按照某个算法（空间毗邻）挑出来的那些记录。
不是任意读写的问题。
: 为什么不能并行读写？不同的进程读文件的任何位置都不会干扰。如果是要写到
同一个
: 文件里面的话，那么每个进程写在自己所划分的一块区间就行了。
【在 h*****g 的大作中提到】
: 为什么不能并行读写？不同的进程读文件的任何位置都不会干扰。如果是要写到同一个
: 文件里面的话，那么每个进程写在自己所划分的一块区间就行了。
|
p**********j
发帖数: 30 | 12 用的是什么io library；(可用parallel hdf5)
用的是什么文件系统；
这些都挺关键。
文件是一个？直接并行读即可. |
c*******v
发帖数: 2599 | 13 采用2或者3。例如可以用方案2一次一批数据的来解决。
例如分十块，每块同步一次广播。
不需要考虑特别复杂的时序。等待其他节点处理完即可。 |
c*******v
发帖数: 2599 | 14 他不是卡在读写。他要分类
: 用的是什么io library；(可用parallel hdf5)
: 用的是什么文件系统；
: 这些都挺关键。
: 文件是一个？直接并行读即可.
【在 p**********j 的大作中提到】
: 用的是什么io library；(可用parallel hdf5)
: 用的是什么文件系统；
: 这些都挺关键。
: 文件是一个？直接并行读即可.
|
w***g
发帖数: 5958 | 15 有可能。应该用MPI_Scatterv的地方用了for (;;) {MPI_Send}?
卡在延时了。
【在 x****u 的大作中提到】
: 这几种方案不应该有区别，楼主用错了什么东西吧
|
p***o
发帖数: 1252 | 16 楼主以前的文章看起来写C++也有几年了，不至于不知道这个吧 ...
不过前面文章里没有提到数据量广播模式网速这些重要参数，也没法判断到底有多慢。
【在 w***g 的大作中提到】
: 有可能。应该用MPI_Scatterv的地方用了for (;;) {MPI_Send}?
: 卡在延时了。
|
y**b
发帖数: 10166 | 17 先谢谢大家，我一个一个来回答。先说明一下问题，用离散单元法（DEM）模拟颗粒行
为，比如这种https://www.youtube.com/playlist?list=
PL0Spd0Mtb6vVeXfGMKS6zZeikWT55l-ew
该方法原理非常简单，主要是颗粒形状的表达、颗粒之间的接触侦测和解析、颗粒之间
的接触模型的精度这些因素很消耗cpu。并行算法的基本思想就是用3d box/block划分
空间，各个颗粒按其质心所在位置划分到不同box。每个box及所含颗粒信息发送到对应
的cpu/core，各个box与相邻的boxes通过ghost layer(包含至少一层颗粒)交换接触
信息，每个box得与周边的26个邻居交换信息，视频中绿色网格就是用于空间划分的
boxes。
可以将上面视频得到的样本(1 million particles)进行复制，这样可以得到非常巨大
的样本，目标是100M或1 billion，作为初始计算数据。
原来用方案1处理1M左右的颗粒并没有遇到困难，但是50M用到更多cpu后就出现了上述
困难。 |
y**b
发帖数: 10166 | 18 非常感谢。
1. hash表可能是个非常好的建议，我先想想。
2. MPI-OpenMP这个hybrid模式做过仔细研究，对我这个特定问题其计算效率远不如
pure MPI，hybrid模式的效率收敛于pure MPI模式。
3. 没错，并非节点越多越好，大致每个core算几百个颗粒是最优计算尺度。并行通讯的
overhead也算比较高的，能达到10-15%，毕竟要交换很多颗粒。
4. 我在16核工作站上测试了方案2，boost.mpi 1.65.1版本显示调用isend出现错误，
但boost.mpi 1.70.0工作正常，不会很快就耗尽了192GB内存。
【在 w***g 的大作中提到】
: 几个建议：
: 1. 任务划分，我估计就是个hash函数。如果是我，我会在内存中建一个
: 50K个元素的hash表。然后把50M个颗粒往这个hash表里放。这个操作就是
: 一重循环。然后再把hash表里的50K个元素往外发，也就是发50K次，
: 肯定能完成了。
: 因为hash表里的元素长度不一，对应的计算量也是不确定的。所以随机
: 把50K个元素对应到n个节点，n越大负载就会越不均衡。所以可以在
: 头节点大致优化一下，想一个heuristic把50K个颗粒表划分到n个节点。
: 这样划分后，每次只要往一个节点发一个比较大的数据块就行，数据划分
: 的问题就解决了。
|
y**b
发帖数: 10166 | 19 能否简单描述一下？谢谢。模式我很陌生，只用过singleton。
【在 b*******s 的大作中提到】
: visitor pattern + mmap
|
y**b
发帖数: 10166 | 20 不懂hadoop啊
【在 e*******s 的大作中提到】
: 用hadoop不好吗 一定要自己造轮子
|
|
|
y**b
发帖数: 10166 | 21 我在工作站（16核，192GB内存）上测试了一下方案1，只分发到16个进程，主进程读文
件用了700秒，分发用了200秒，看着挺好。
可是在超算上分发到50k个进程，根本没法完成似的。
【在 d***a 的大作中提到】
: 单节点的内存是够了。瓶颈很有可能在盘I/O和网络I/O。
|
y**b
发帖数: 10166 | 22 方案3就是各进程同时读，尚未测试。
但是提到了，由于受到节点内存容量的限制，并非实际可行。现在一般
计算节点有128GB内存，以一个节点36核（或进程）为例，单节点需要
内存30GBx36才能完成方案3。
【在 h*****g 的大作中提到】
: 为什么不能并行读写？不同的进程读文件的任何位置都不会干扰。如果是要写到同一个
: 文件里面的话，那么每个进程写在自己所划分的一块区间就行了。
|
y**b
发帖数: 10166 | 23 是DEM，不是MD。最大的区别就是前者的瓶颈是颗粒形状表述和接触解析，以及高精度
尤其是history-dependent的接触模型。
【在 a*******3 的大作中提到】
: 是做分子动力学么，如果相互作用是近程（有cut-off distanve)的话还是可以scale得
: 很好的。如果是长距就得考虑一些special technique比如傅立叶变换了. 可以参考一
: 下LAMMPS的documentation
|
y**b
发帖数: 10166 | 24 重新写了一段，希望能说清楚。
【在 c*******v 的大作中提到】
: 他不是卡在读写。他要分类
:
:
: 用的是什么io library；(可用parallel hdf5)
:
: 用的是什么文件系统；
:
: 这些都挺关键。
:
: 文件是一个？直接并行读即可.
:
|
y**b
发帖数: 10166 | 25 方案1用的是isend/waitall，不应该卡住（用了很多年算了无数算例），而是双重循环
的（50k by 50M）效率太低。
方案2 boost.mpi broadcast调用的也是isend。
【在 w***g 的大作中提到】
: 有可能。应该用MPI_Scatterv的地方用了for (;;) {MPI_Send}?
: 卡在延时了。
|
y**b
发帖数: 10166 | 26 对，是这样的，颗粒只跟周围的颗粒发生接触，空间划分就是为了把相邻的颗粒分发到
某cpu。
【在 c*******v 的大作中提到】
: 楼主标题没写清楚。我的理解是，一个节点读了一条记录后，
: 只能接受这个初始节点按照某个算法（空间毗邻）挑出来的那些记录。
: 不是任意读写的问题。
:
:
: 为什么不能并行读写？不同的进程读文件的任何位置都不会干扰。如果是要写到
: 同一个
:
: 文件里面的话，那么每个进程写在自己所划分的一块区间就行了。
:
|
p***o
发帖数: 1252 | 27 MPI_Bcast各种优化，你循环调用isend差太远了。
【在 y**b 的大作中提到】
: 方案1用的是isend/waitall，不应该卡住（用了很多年算了无数算例），而是双重循环
: 的（50k by 50M）效率太低。
: 方案2 boost.mpi broadcast调用的也是isend。
|
y**b
发帖数: 10166 | 28 这是自然。问题是Bcast只能发送同一个内容，循环调用isend每次发送不同内容（而这
是我需要的）。
【在 p***o 的大作中提到】
: MPI_Bcast各种优化，你循环调用isend差太远了。
|
c*******v
发帖数: 2599 | 29 我有一事不明。为什么循环次数会是50K 乘以50M。极端情况下，假如第一个node拿走
了50M,其他的node不就结束了吗。
所以你这个基础计算模型似乎有点问题？
所以我认为2是可以的。按照2每次处理5M记录。完事后数据归并。再次执行2。
: 方案1用的是isend/waitall，不应该卡住（用了很多年算了无数算例），
而是双
重循环
: 的（50k by 50M）效率太低。
: 方案2 boost.mpi broadcast调用的也是isend。
【在 y**b 的大作中提到】
: 这是自然。问题是Bcast只能发送同一个内容，循环调用isend每次发送不同内容（而这
: 是我需要的）。
|
p***o
发帖数: 1252 | 30 听起来50k的rank你有差不多40x40x40个格子，每个格子需要有自己要算的一份数据。
按你说的所有数据一共30G，每份数据1M都不到。
按3x3x3的neighbor算，每个格子还要加上相邻26个格子的数据，那么同一份数据要
分到27个rank。你用isend大约就是个50k by 27的循环，你说50k by 50M的循环不是
要把每个点的数据都用isend单独送吧？
50k by 27的循环也可以进一步用bcast优化。你把每份数据分到的rank加到一个comm
里然后用bcast，这样只要50k的循环就好。按照每份数据1M算，27个rank的话在IB上
做一次bcast估计1ms这个量级，50k个循环真的是分分钟就能搞完。
【在 y**b 的大作中提到】
: 这是自然。问题是Bcast只能发送同一个内容，循环调用isend每次发送不同内容（而这
: 是我需要的）。
|
|
|
y**b
发帖数: 10166 | 31 多谢提醒。这个我真是糊涂了，应该分发多少出去，就从总数中减去多少。因为后面还
用到了全部信息（这个可以暂时不用考虑），所以没有做减法。
【在 c*******v 的大作中提到】
: 我有一事不明。为什么循环次数会是50K 乘以50M。极端情况下，假如第一个node拿走
: 了50M,其他的node不就结束了吗。
: 所以你这个基础计算模型似乎有点问题？
: 所以我认为2是可以的。按照2每次处理5M记录。完事后数据归并。再次执行2。
:
:
: 方案1用的是isend/waitall，不应该卡住（用了很多年算了无数算例），
: 而是双
: 重循环
:
: 的（50k by 50M）效率太低。
:
: 方案2 boost.mpi broadcast调用的也是isend。
|
y**b
发帖数: 10166 | 32 对颗粒质心坐标(x,y,z)用什么hash function比较好,
unordered_map似乎不支持tuple
【在 w***g 的大作中提到】
: 几个建议：
: 1. 任务划分，我估计就是个hash函数。如果是我，我会在内存中建一个
: 50K个元素的hash表。然后把50M个颗粒往这个hash表里放。这个操作就是
: 一重循环。然后再把hash表里的50K个元素往外发，也就是发50K次，
: 肯定能完成了。
: 因为hash表里的元素长度不一，对应的计算量也是不确定的。所以随机
: 把50K个元素对应到n个节点，n越大负载就会越不均衡。所以可以在
: 头节点大致优化一下，想一个heuristic把50K个颗粒表划分到n个节点。
: 这样划分后，每次只要往一个节点发一个比较大的数据块就行，数据划分
: 的问题就解决了。
|
d***a
发帖数: 13752 | 33 你可能要多说说你的系统配置和运行环境，要不大家都得猜。你是用了MPI来写并行程
序，用MPI函数来发放吗？超算上用了多个节点？
假设是用MPI，超算上用了多个节点。单机上不会走网络I/O，超算上就会了。网络I/O
传数据，比通过内存交换数据，慢得太多了。
update: 刚刚看到，你用的是MPI_Isend。
【在 y**b 的大作中提到】
: 我在工作站（16核，192GB内存）上测试了一下方案1，只分发到16个进程，主进程读文
: 件用了700秒，分发用了200秒，看着挺好。
: 可是在超算上分发到50k个进程，根本没法完成似的。
|
w***g
发帖数: 5958 | 34 我说的hash function其实就是你的grid划分。
【在 y**b 的大作中提到】
: 对颗粒质心坐标(x,y,z)用什么hash function比较好,
: unordered_map似乎不支持tuple
|
c*******v
发帖数: 2599 | 35 假设每个颗粒只能属于一个节点。外循环用50M,内循环找到节点后立即break。这样省
一半时间。内循环用0,12,...的随机shuffle走，应该可以看到较稳定省一半。
但如果你的两个索引寻找的函数s(I,j)不是纯函数。就不知如何了。
: 多谢提醒。这个我真是糊涂了，应该分发多少出去，就从总数中减去多少。因为
后面还
: 用到了全部信息（这个可以暂时不用考虑），所以没有做减法。
【在 y**b 的大作中提到】
: 对颗粒质心坐标(x,y,z)用什么hash function比较好,
: unordered_map似乎不支持tuple
|
b***i
发帖数: 3043 | 36 感觉你说的这个才是关键。开始就不懂，为什么要50k x 50M
【在 p***o 的大作中提到】
: 听起来50k的rank你有差不多40x40x40个格子，每个格子需要有自己要算的一份数据。
: 按你说的所有数据一共30G，每份数据1M都不到。
: 按3x3x3的neighbor算，每个格子还要加上相邻26个格子的数据，那么同一份数据要
: 分到27个rank。你用isend大约就是个50k by 27的循环，你说50k by 50M的循环不是
: 要把每个点的数据都用isend单独送吧？
: 50k by 27的循环也可以进一步用bcast优化。你把每份数据分到的rank加到一个comm
: 里然后用bcast，这样只要50k的循环就好。按照每份数据1M算，27个rank的话在IB上
: 做一次bcast估计1ms这个量级，50k个循环真的是分分钟就能搞完。
|
c*******v
发帖数: 2599 | 37 25k*50M
【在 b***i 的大作中提到】
: 感觉你说的这个才是关键。开始就不懂，为什么要50k x 50M
|
n******t
发帖数: 4406 | 38 不清楚你爲什麼需要30GB x 36才能完成。
你實際上只需要傳給每個進程節點數據的id，50Mx8byte x ncore = 400MB x 36 就行
了(這個數稍微優化一下肯定還可以降低)。
此外機器上維持30GB的數據的池子共享，讓各進程依據id拿數據即可。這樣總共內存消
耗肯定不到64GB.
【在 y**b 的大作中提到】
: 方案3就是各进程同时读，尚未测试。
: 但是提到了，由于受到节点内存容量的限制，并非实际可行。现在一般
: 计算节点有128GB内存，以一个节点36核（或进程）为例，单节点需要
: 内存30GBx36才能完成方案3。
|
c*******v
发帖数: 2599 | 39 From the mathematical perspective, I guessed that:
(1) A pure function S(i,j,context) needed to be evaluated about 25k*50M
times;
(2) The context need to be accessed while the S is evaluated.
For saving memory, I would prefer to split the context into context1,
context2,contxt3,context4 to saving the memory.
【在 n******t 的大作中提到】
: 不清楚你爲什麼需要30GB x 36才能完成。
: 你實際上只需要傳給每個進程節點數據的id，50Mx8byte x ncore = 400MB x 36 就行
: 了(這個數稍微優化一下肯定還可以降低)。
: 此外機器上維持30GB的數據的池子共享，讓各進程依據id拿數據即可。這樣總共內存消
: 耗肯定不到64GB.
|
n******t
发帖数: 4406 | 40 我不認爲你搞懂了我的意思，需要context與否和該不該吧30G的數據拷貝36次沒有關係。
【在 c*******v 的大作中提到】
: From the mathematical perspective, I guessed that:
: (1) A pure function S(i,j,context) needed to be evaluated about 25k*50M
: times;
: (2) The context need to be accessed while the S is evaluated.
: For saving memory, I would prefer to split the context into context1,
: context2,contxt3,context4 to saving the memory.
|
|
|
p***o
发帖数: 1252 | 41 你这个和前面wdong的MPI+OpenMP的方案都需要大改已有的程序，估计楼主没预算/没时
间。
【在 n******t 的大作中提到】
: 不清楚你爲什麼需要30GB x 36才能完成。
: 你實際上只需要傳給每個進程節點數據的id，50Mx8byte x ncore = 400MB x 36 就行
: 了(這個數稍微優化一下肯定還可以降低)。
: 此外機器上維持30GB的數據的池子共享，讓各進程依據id拿數據即可。這樣總共內存消
: 耗肯定不到64GB.
|
p***o
发帖数: 1252 | 42 他一共就30G的数据，还分啥context，进程间找个方法共享就好。
【在 c*******v 的大作中提到】
: From the mathematical perspective, I guessed that:
: (1) A pure function S(i,j,context) needed to be evaluated about 25k*50M
: times;
: (2) The context need to be accessed while the S is evaluated.
: For saving memory, I would prefer to split the context into context1,
: context2,contxt3,context4 to saving the memory.
|
n******t
发帖数: 4406 | 43 加一個進程讀數據，pin shared memory, 計算函數入口改成id （或者指針，引用
whatever)。沒了。這種改動都不像搞的話，說實話，也沒什麼必要去搞什麼大規模的
計算負載了。
【在 p***o 的大作中提到】
: 你这个和前面wdong的MPI+OpenMP的方案都需要大改已有的程序，估计楼主没预算/没时
: 间。
|
p***o
发帖数: 1252 | 44 很多买得起HPC的地方养不起能写MPI代码的人的。
【在 n******t 的大作中提到】
: 加一個進程讀數據，pin shared memory, 計算函數入口改成id （或者指針，引用
: whatever)。沒了。這種改動都不像搞的話，說實話，也沒什麼必要去搞什麼大規模的
: 計算負載了。
|
c*******v
发帖数: 2599 | 45 It might be very slow if visiting the sharing data(context) through network
for all iterations (25k*50M).
The best solution might be: sharing some data + local copy some data
【在 p***o 的大作中提到】
: 他一共就30G的数据，还分啥context，进程间找个方法共享就好。
|
p***o
发帖数: 1252 | 46 你还是没明白。进程间共享的意思就是先网络bcast到每个node。然后每个node上的进
程间用mmap之类的共享数据，这一步跟网络没关系。
network
【在 c*******v 的大作中提到】
: It might be very slow if visiting the sharing data(context) through network
: for all iterations (25k*50M).
: The best solution might be: sharing some data + local copy some data
|
c*******v
发帖数: 2599 | 47 Can you elaborate more? It seems that he explained the reason of not using
the bcast.
I assume the model is:
(0)There were 50M records that was saved in the major node.
(1) For the 50k nodes, different boxes' definition(50k) are saved as the
init_data in each nodes.
(2) For each boxes, we need to find which records belongs to the boxes.
Save the belonging records to the correct node.
【在 p***o 的大作中提到】
: 你还是没明白。进程间共享的意思就是先网络bcast到每个node。然后每个node上的进
: 程间用mmap之类的共享数据，这一步跟网络没关系。
:
: network
|
p***o
发帖数: 1252 | 48
Yes, these are the 30GB data. So each record is 600 bytes,
which sounds reasonable.
There are 50k cores not 50k nodes. LZ said each node has 36 cores so
there probably about 2000 nodes, which is also reasonable. Each core
will run one process, and will need data from its "26" neighbors.
Here are two ways to do this.
LZ's method: ask major node to do this partitioning and then a lot of
network transactions to send the partitioned data to each core.
wdong/netghost/etc: do a broadcast so each node will have all the 30GB
of data, and then ask each node to partition for its own cores.
Yes there are more data sending over the network but since MPI will
optimize broadcast, this could be faster.
【在 c*******v 的大作中提到】
: Can you elaborate more? It seems that he explained the reason of not using
: the bcast.
: I assume the model is:
: (0)There were 50M records that was saved in the major node.
: (1) For the 50k nodes, different boxes' definition(50k) are saved as the
: init_data in each nodes.
: (2) For each boxes, we need to find which records belongs to the boxes.
: Save the belonging records to the correct node.
|
c*******v
发帖数: 2599 | 49 I got it.
The below sentence is questionable:
"以一个节点36核（或进程）为例，单节点需要内存30GBx36才能完成方案2或3。"
What we can do are:
Step 1: bcast the 30G data to each node.
Step 2: On each node, the 30G local data should be shared by its 36 cores(
processes).
Thus, the requirement of 30G*36 is wrong.
【在 p***o 的大作中提到】
:
: Yes, these are the 30GB data. So each record is 600 bytes,
: which sounds reasonable.
: There are 50k cores not 50k nodes. LZ said each node has 36 cores so
: there probably about 2000 nodes, which is also reasonable. Each core
: will run one process, and will need data from its "26" neighbors.
: Here are two ways to do this.
: LZ's method: ask major node to do this partitioning and then a lot of
: network transactions to send the partitioned data to each core.
: wdong/netghost/etc: do a broadcast so each node will have all the 30GB
|
m*****p
发帖数: 39 | 50 純MPI有shared memory優化，用不著OpenMP；30GB很小，用EDR幾秒鐘就傳完了；MPI沒
有你們想像的那麼難。 |
|
|
n******t
发帖数: 4406 | 51 這個和MPI沒關係。這就是一個C/C++的問題。
【在 p***o 的大作中提到】
: 很多买得起HPC的地方养不起能写MPI代码的人的。
|
y**b
发帖数: 10166 | 52 对，这就是方案6，可能大家都没看到。
【在 c*******v 的大作中提到】
: I got it.
: The below sentence is questionable:
: "以一个节点36核（或进程）为例，单节点需要内存30GBx36才能完成方案2或3。"
: What we can do are:
: Step 1: bcast the 30G data to each node.
: Step 2: On each node, the 30G local data should be shared by its 36 cores(
: processes).
: Thus, the requirement of 30G*36 is wrong.
|
y**b
发帖数: 10166 | 53 这些前面都写了，大约2k到5k个节点的不同超算，每个节点32到44个core。
我一般使用不超过2048个节点。软件环境如下：
Thunder mpt/2.20 intel-compilers/17.0.2
Centennial mpi/sgimpt/2.17 compiler/intel/18.0.1.163
Onyx cray-mpich/7.7.8 PrgEnv-intel/6.0.4 (intel19.0.1.144)
Excalibur cray-mpich/7.1.0 PrgEnv-intel/5.2.40
GCC也用，效果差不多。
O
【在 d***a 的大作中提到】
: 你可能要多说说你的系统配置和运行环境，要不大家都得猜。你是用了MPI来写并行程
: 序，用MPI函数来发放吗？超算上用了多个节点？
: 假设是用MPI，超算上用了多个节点。单机上不会走网络I/O，超算上就会了。网络I/O
: 传数据，比通过内存交换数据，慢得太多了。
: update: 刚刚看到，你用的是MPI_Isend。
|
y**b
发帖数: 10166 | 54 我在工作站测试了一下边分发边减少的方法。
a. 原来是使用vector来存储颗粒对象的指针，这个对边分发边减少慢不可言，
想象之中吧。
b. 改成使用list来存储颗粒对象的指针，快得多。
在工作站（16核，192GB内存）上测试了只分发到16个进程的情况，对方法b，
主进程读文件用了650秒，分发用了170秒。
前面在工作站测试方案1，也只分发到16个进程，主进程读文件用了700秒，
分发用了200秒。差不多吧。方法b应该不足以解决在超算上分发到50k个进程
的情况。
【在 c*******v 的大作中提到】
: 假设每个颗粒只能属于一个节点。外循环用50M,内循环找到节点后立即break。这样省
: 一半时间。内循环用0,12,...的随机shuffle走，应该可以看到较稳定省一半。
: 但如果你的两个索引寻找的函数s(I,j)不是纯函数。就不知如何了。
:
:
: 多谢提醒。这个我真是糊涂了，应该分发多少出去，就从总数中减去多少。因为
: 后面还
:
: 用到了全部信息（这个可以暂时不用考虑），所以没有做减法。
:
|
y**b
发帖数: 10166 | 55 这就是原帖里面提到的方案6？
关键这50M个或更多颗粒基本是是空间乱序的（不存在进程节点数据id），
得进行进程空间划分后，才能分发给各进程。
【在 n******t 的大作中提到】
: 不清楚你爲什麼需要30GB x 36才能完成。
: 你實際上只需要傳給每個進程節點數據的id，50Mx8byte x ncore = 400MB x 36 就行
: 了(這個數稍微優化一下肯定還可以降低)。
: 此外機器上維持30GB的數據的池子共享，讓各進程依據id拿數據即可。這樣總共內存消
: 耗肯定不到64GB.
|
y**b
发帖数: 10166 | 56 这不就是方案6吗？我就是询问这种可能性。
【在 p***o 的大作中提到】
: 你还是没明白。进程间共享的意思就是先网络bcast到每个node。然后每个node上的进
: 程间用mmap之类的共享数据，这一步跟网络没关系。
:
: network
|
y**b
发帖数: 10166 | 57 50M个空间乱序的颗粒，要切割成40x40x40的网格，分发到各个网格（也即各进程），
不就是50k x 50M。
【在 b***i 的大作中提到】
: 感觉你说的这个才是关键。开始就不懂，为什么要50k x 50M
|
c*******v
发帖数: 2599 | 58 不用减少颗粒。
50M颗粒作为外循环，对每个颗粒，检查和50K的盒子是不是match，match到就break，
这样就不需要50M×50k的全部循环了。这样不知是否可行。
【在 y**b 的大作中提到】
: 我在工作站测试了一下边分发边减少的方法。
: a. 原来是使用vector来存储颗粒对象的指针，这个对边分发边减少慢不可言，
: 想象之中吧。
: b. 改成使用list来存储颗粒对象的指针，快得多。
: 在工作站（16核，192GB内存）上测试了只分发到16个进程的情况，对方法b，
: 主进程读文件用了650秒，分发用了170秒。
: 前面在工作站测试方案1，也只分发到16个进程，主进程读文件用了700秒，
: 分发用了200秒。差不多吧。方法b应该不足以解决在超算上分发到50k个进程
: 的情况。
|
y**b
发帖数: 10166 | 59 对，50k大约是40x40x40个格子或进程（对pure MPI模式，就是一个格子对应一个
进程）。
在方案1里面，主进程读完数据，然后针对每个进程，从所有颗粒中搜索该进程含有
的颗粒（这就导致50k by 50M的循环，效率很低），然后再将每个进程含有的颗粒
isend分发给各个进程（这是个50k的单循环）。在数据量不大的情况下，方案1还能
工作。
并不存在50k by 27的循环。而且上面的分发过程是一次性的，分发以后各进程会
自动搜索26个邻居以及传递很薄一层颗粒给邻居（这个跟简单网格并行CFD类似，
稍微复杂一些）。
总之，全局分发只有一次，后面就是local communication了。现在的问题是这个
全局分发在颗粒很多的时候有困难。提的几个方案都是为了解决这个全局分发的问题，
其中方案6就是你说的MPI_Comm_split吧。
我贴一下这个原始分发代码的screenshot吧，emacs里面的对齐可能拷贝出来很难看。
简单说明：主进程读完数据构造出50M个颗粒，allParticleVec用于存储这些颗粒的
指针（allParticleVec只对主进程有意义），particleVec是各进程存储自己所拥有
的颗粒的指针。各进程之间需要交换边界附近颗粒的指针以及处理可能发生的迁移颗粒
现象，通过boost.mpi完成，不赘述。
【在 p***o 的大作中提到】
: 听起来50k的rank你有差不多40x40x40个格子，每个格子需要有自己要算的一份数据。
: 按你说的所有数据一共30G，每份数据1M都不到。
: 按3x3x3的neighbor算，每个格子还要加上相邻26个格子的数据，那么同一份数据要
: 分到27个rank。你用isend大约就是个50k by 27的循环，你说50k by 50M的循环不是
: 要把每个点的数据都用isend单独送吧？
: 50k by 27的循环也可以进一步用bcast优化。你把每份数据分到的rank加到一个comm
: 里然后用bcast，这样只要50k的循环就好。按照每份数据1M算，27个rank的话在IB上
: 做一次bcast估计1ms这个量级，50k个循环真的是分分钟就能搞完。
|
y**b
发帖数: 10166 | 60 问题很简单，就是在工作站上按16个进程分发，为16 by 50M，只需要200秒；在2000个
节点上按50k个进程进行分发，为50k by 50M，没法完成。 |
|
|
p***o
发帖数: 1252 | 61 根据你的代码，按你这么说，一共就是50k个isend 30GB的数据，瓶颈不在网络上。
看你老提50k by 50M的循环，我猜你在findParticleInRectangle里就是一个循环
套一个if，这能不慢吗 ... 不过这跟MPI没有任何关系。如果Grid划分比较规律，
你需要的是建50k个vec，然后写一个循环把50M个点根据每个点的坐标直接分到
相应Grid的vec里。如果Grid划分没啥规律，你得弄个8叉树之类的数据结构优化
findParticleInRectangle。
)。
isend
【在 y**b 的大作中提到】
: 对，50k大约是40x40x40个格子或进程（对pure MPI模式，就是一个格子对应一个
: 进程）。
: 在方案1里面，主进程读完数据，然后针对每个进程，从所有颗粒中搜索该进程含有
: 的颗粒（这就导致50k by 50M的循环，效率很低），然后再将每个进程含有的颗粒
: isend分发给各个进程（这是个50k的单循环）。在数据量不大的情况下，方案1还能
: 工作。
: 并不存在50k by 27的循环。而且上面的分发过程是一次性的，分发以后各进程会
: 自动搜索26个邻居以及传递很薄一层颗粒给邻居（这个跟简单网格并行CFD类似，
: 稍微复杂一些）。
: 总之，全局分发只有一次，后面就是local communication了。现在的问题是这个
|
c*******v
发帖数: 2599 | 62 改成 findRectangleforParticle.
For each particle,找到Rectangle之后就break，可省一半时间。
除此而外，似乎没有一般可用的办法。
【在 p***o 的大作中提到】
: 根据你的代码，按你这么说，一共就是50k个isend 30GB的数据，瓶颈不在网络上。
: 看你老提50k by 50M的循环，我猜你在findParticleInRectangle里就是一个循环
: 套一个if，这能不慢吗 ... 不过这跟MPI没有任何关系。如果Grid划分比较规律，
: 你需要的是建50k个vec，然后写一个循环把50M个点根据每个点的坐标直接分到
: 相应Grid的vec里。如果Grid划分没啥规律，你得弄个8叉树之类的数据结构优化
: findParticleInRectangle。
:
: )。
: isend
|
y**b
发帖数: 10166 | 63 问题是50k个vec仍然是双重循环，很难改善性能吧。
前面体到的hash表应该是把这个搜索划分变成单层循环的有效办法？
对颗粒质心坐标(x,y,z)也不好找hash function，
unordered_map似乎不支持tuple。
Octree我看看。
【在 p***o 的大作中提到】
: 根据你的代码，按你这么说，一共就是50k个isend 30GB的数据，瓶颈不在网络上。
: 看你老提50k by 50M的循环，我猜你在findParticleInRectangle里就是一个循环
: 套一个if，这能不慢吗 ... 不过这跟MPI没有任何关系。如果Grid划分比较规律，
: 你需要的是建50k个vec，然后写一个循环把50M个点根据每个点的坐标直接分到
: 相应Grid的vec里。如果Grid划分没啥规律，你得弄个8叉树之类的数据结构优化
: findParticleInRectangle。
:
: )。
: isend
|
y**b
发帖数: 10166 | 64 是，这也常见，会好一些。
【在 c*******v 的大作中提到】
: 改成 findRectangleforParticle.
: For each particle,找到Rectangle之后就break，可省一半时间。
: 除此而外，似乎没有一般可用的办法。
|
c*******v
发帖数: 2599 | 65 Step 1: bcast the 30G data to each node.
Step 2: On each node, the 30G local data should be shared by its 36 cores(
processes).
也就是你的方案6,可行吗？
wdong说的hash，和pptwo说的树，其实都是挖掘数据已有特性。
比较精巧，我认为开发新的不容易。恐怕单机研究算法也要一两星期。
（数据库检索多用树，数据文件检索多用hash）
【在 y**b 的大作中提到】
: 是，这也常见，会好一些。
|
c*******v
发帖数: 2599 | 66 树相当于running index跳着走,不同于穷举。
但并不是对所有数据都适用。
【在 y**b 的大作中提到】
: 问题是50k个vec仍然是双重循环，很难改善性能吧。
: 前面体到的hash表应该是把这个搜索划分变成单层循环的有效办法？
: 对颗粒质心坐标(x,y,z)也不好找hash function，
: unordered_map似乎不支持tuple。
: Octree我看看。
|
p***o
发帖数: 1252 | 67 hash和树都是针对一般数据的索引算法，方案6暴力并行化，我感觉要花的时间差不多。
楼主这个听起来就是简单画个格子:
ix = (x-x_min)/(x_max-x_min)*Nx;
iy = (y-y_min)/(y_max-y_min)*Ny;
iz = (z-z_min)/(z_max-z_min)*Nz;
rank = ix*Ny*Nz+iy*Nz+iz;
O(1)就能知道(x,y,z)属于那个进程。
【在 c*******v 的大作中提到】
: Step 1: bcast the 30G data to each node.
: Step 2: On each node, the 30G local data should be shared by its 36 cores(
: processes).
: 也就是你的方案6,可行吗？
: wdong说的hash，和pptwo说的树，其实都是挖掘数据已有特性。
: 比较精巧，我认为开发新的不容易。恐怕单机研究算法也要一两星期。
: （数据库检索多用树，数据文件检索多用hash）
|
n******t
发帖数: 4406 | 68 不管你如何排序這50M個節點,你沒有必要拷貝所有的節點內容去各個進程。
你只需要指針，或者叫ID也行。這是最基本的C語言概念。
~~~~~~~~~~~~~~~~~~~~~~~~~~~
我不知道你說的什麼是方案6.我只是告訴你你說的內存30Gx36完全沒有必要。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
這個和30Gx36有關係嗎？
【在 y**b 的大作中提到】
: 这就是原帖里面提到的方案6？
: 关键这50M个或更多颗粒基本是是空间乱序的（不存在进程节点数据id），
: 得进行进程空间划分后，才能分发给各进程。
|
c*******v
发帖数: 2599 | 69 Below algorithm may work for arbitrary grids:
(1)假设网格坐标定义的intervals不交叉。
(2)40×40×40的网格，把单个坐标的网格有40个，其序号看作40进制数。
盒子的标签就是40进制数abc.
(3)对每个颗粒,每个坐标的网格边界二分搜索或者二分树，这样8分树找到x，y，z的序
号abc。
(4)按照abc分发给40×40×40进程。
ln(40)**3 = 50.2
大概需时间为50M×50.2
多。
【在 p***o 的大作中提到】
: hash和树都是针对一般数据的索引算法，方案6暴力并行化，我感觉要花的时间差不多。
: 楼主这个听起来就是简单画个格子:
: ix = (x-x_min)/(x_max-x_min)*Nx;
: iy = (y-y_min)/(y_max-y_min)*Ny;
: iz = (z-z_min)/(z_max-z_min)*Nz;
: rank = ix*Ny*Nz+iy*Nz+iz;
: O(1)就能知道(x,y,z)属于那个进程。
|
g****t
发帖数: 31659 | 70 Btw,一维 line search 算法如下：
假如有41 grids:
x0,x1,...,x40
要找Px在哪个interval。
Step 1. Left =0, Right = 40
验证Px-Left和Px-Right不同符号
Step 2. Mid = 20
如果Px - Left和Px-Mid不同号，Right := Mid
不然Left := Mid
继续下去，直到 Right-Left =1
x(Left)， x(Right)即为所求区间。
这个算法和bisection求f(x)=0完全平行。所以很强壮。
我用过，除了符号判断可以加一个小死区管理浮点数截断误差，没什么问题。
除了处理x,y,z的box,也可以推广到更高维空间。
: Below algorithm may work for arbitrary grids:
: (1)假设网格坐标定义的intervals不交叉。
: (2)40×40×40的网格，把单个坐标的网格有40个，其序号看
作40进制数。
: 盒子的标签就是40进制数abc.
: (3)对每个颗粒,每个坐标的网格边界二分搜索或者二分树，这样8分树找
到x，y
，z的序
: 号abc。
: (4)按照abc分发给40×40×40进程。
: ln(40)**3 = 50.2
: 大概需时间为50M×50.2
: 多。
【在 c*******v 的大作中提到】
: Below algorithm may work for arbitrary grids:
: (1)假设网格坐标定义的intervals不交叉。
: (2)40×40×40的网格，把单个坐标的网格有40个，其序号看作40进制数。
: 盒子的标签就是40进制数abc.
: (3)对每个颗粒,每个坐标的网格边界二分搜索或者二分树，这样8分树找到x，y，z的序
: 号abc。
: (4)按照abc分发给40×40×40进程。
: ln(40)**3 = 50.2
: 大概需时间为50M×50.2
:
|
|
|
y**b
发帖数: 10166 | 71 多谢提醒！因为同cfd耦合变成了非均匀网格，竟然忘了这个以前用过的O(1)算法。
但对于纯颗粒计算这个O(1)算法完全可以应用，效率大增，暂时不去考虑Octree等了。
测试了一下O(1)算法，用秒如下：
在Cray上(85184个进程，1936个节点)：
readFile 5.747571e+02 scatterPtcl 7.918455e+03
在SGI上(46656个进程，1296个节点)：
readFile 6.398981e+02 scatterPtcl 2.092724e+02
Cray这个分发似乎慢得不正常？
多。
【在 p***o 的大作中提到】
: hash和树都是针对一般数据的索引算法，方案6暴力并行化，我感觉要花的时间差不多。
: 楼主这个听起来就是简单画个格子:
: ix = (x-x_min)/(x_max-x_min)*Nx;
: iy = (y-y_min)/(y_max-y_min)*Ny;
: iz = (z-z_min)/(z_max-z_min)*Nz;
: rank = ix*Ny*Nz+iy*Nz+iz;
: O(1)就能知道(x,y,z)属于那个进程。
|
y**b
发帖数: 10166 | 72 这个也应该比较快。
【在 g****t 的大作中提到】
: Btw,一维 line search 算法如下：
: 假如有41 grids:
: x0,x1,...,x40
: 要找Px在哪个interval。
: Step 1. Left =0, Right = 40
: 验证Px-Left和Px-Right不同符号
: Step 2. Mid = 20
: 如果Px - Left和Px-Mid不同号，Right := Mid
: 不然Left := Mid
: 继续下去，直到 Right-Left =1
|
y**b
发帖数: 10166 | 73 6。还有个方案是让每个节点的36个进程共享部分内存区域，其中一个进程读取数据，
其它进程自动获得这些数据。按方案2，主进程只需向各个节点的某一进程broadcast
数据；按方案3，各节点只需某一个进程读取数据文件。
一般来说，(2)主进程向各节点广播数据，(3)各节点读取相同数据文件，哪个更好些？ |
g****t
发帖数: 31659 | 74 我这个算法是用在不等距离的格点的。
如果格点等距离，pptwo的算法是显然最快的。
Pptwo的算法在一维，例如0到10这样11个等距离，
6.5这个颗粒属于第七个盒子。此事实用除法算一下即可判定。
三维坐标就是算三次除法。
(因为已知格点等距离，所以只需要知道端点就可以了。)
但是假如格点不是等距离的。那么必然要把格点的具体坐标注入算法。我写的这个二分
法可能是头
一个可以试一下的。
: 这个也应该比较快。
【在 y**b 的大作中提到】
: 6。还有个方案是让每个节点的36个进程共享部分内存区域，其中一个进程读取数据，
: 其它进程自动获得这些数据。按方案2，主进程只需向各个节点的某一进程broadcast
: 数据；按方案3，各节点只需某一个进程读取数据文件。
: 一般来说，(2)主进程向各节点广播数据，(3)各节点读取相同数据文件，哪个更好些？
|
y**b
发帖数: 10166 | 75 更新一下：
1. Cray X40/X50的系统真是有问题啊，分发速度慢40倍。
另外，我们小中大规模的多平台模拟测试都表明其计算速度只有SGI ICE X/XA
系统的一半，SGI上面50 million allocation的计算能力相当于Cray上100
million core-hours！
美国三台Exascale超算都由Cray承建，令人担心。
2. dem-cfd resolved耦合计算，为了提高load balance，mpi网格变成了非均匀网格。
但是，cfd具备非常细密的的均匀网格，可以使用O(1)算法确定一个dem颗粒质心所处于
的cfd网格，然后由该cfd网格推算dem颗粒所属进程，这样，dem-cfd resolved耦合计
算的初始分发过程，仍然可以使用O(1)算法！
【在 y**b 的大作中提到】
: 多谢提醒！因为同cfd耦合变成了非均匀网格，竟然忘了这个以前用过的O(1)算法。
: 但对于纯颗粒计算这个O(1)算法完全可以应用，效率大增，暂时不去考虑Octree等了。
: 测试了一下O(1)算法，用秒如下：
: 在Cray上(85184个进程，1936个节点)：
: readFile 5.747571e+02 scatterPtcl 7.918455e+03
: 在SGI上(46656个进程，1296个节点)：
: readFile 6.398981e+02 scatterPtcl 2.092724e+02
: Cray这个分发似乎慢得不正常？
:
: 多。
|
m**u
发帖数: 541 | |
m**u
发帖数: 541 | 77 这个和钱没有啥关系， 估计1千万美刀解决不了这个问题
有些东西，没办法就是没办法，至少暂时没办法。DEM 出来N年了，还是那个鸟样，俺
15年前搞过，这个方法的计算过程中的不可扩展性导致颗粒/node 数量达到一定程度后
，没法解决。过去N年中，一直卡在这里。
当然俺不否认您可能是超级牛人，比过去几十年的哪些搞DEM的强10条街，可能会搞出
牛方法来解决计算复杂性问题。那也是巨大贡献。 这个DEM对解决不连续体系很有意义
， 就是计算上搞不定。 |
g****t
发帖数: 31659 | 78 Better machines often brought better results. Money matters.
It was reported that GPU matters for DEM,FEM, etc.
https://www.researchgate.net/publication/318072393_BlazeDEM3D-GPU_A_Large_
Scale_DEM_simulation_code_for_GPUs
: 这个和钱没有啥关系， 估计1千万美刀解决不了这个问题
: 有些东西，没办法就是没办法，至少暂时没办法。DEM 出来N年了，还是
那个鸟
样，俺
: 15年前搞过，这个方法的计算过程中的不可扩展性导致颗粒/node 数量达
到一定
程度后
: ，没法解决。过去N年中，一直卡在这里。
: 当然俺不否认您可能是超级牛人，比过去几十年的哪些搞DEM的强10条街
，可能
会搞出
: 牛方法来解决计算复杂性问题。那也是巨大贡献。 这个DEM对解决不连续
体系很
有意义
: ， 就是计算上搞不定。
【在 m**u 的大作中提到】
: 这个和钱没有啥关系， 估计1千万美刀解决不了这个问题
: 有些东西，没办法就是没办法，至少暂时没办法。DEM 出来N年了，还是那个鸟样，俺
: 15年前搞过，这个方法的计算过程中的不可扩展性导致颗粒/node 数量达到一定程度后
: ，没法解决。过去N年中，一直卡在这里。
: 当然俺不否认您可能是超级牛人，比过去几十年的哪些搞DEM的强10条街，可能会搞出
: 牛方法来解决计算复杂性问题。那也是巨大贡献。 这个DEM对解决不连续体系很有意义
: ， 就是计算上搞不定。
|
m**u
发帖数: 541 | 79 也许钱多能解决；DEM 就是计算方法上卡脖子，否则是个不错的方法，能解决很多数学
上不连续（不能积分）的问题。 |
g****t
发帖数: 31659 | 80 Had u tried to leverage modern AI? For example:
https://arxiv.org/abs/1911.04240
In theory, all PDEs can be simulated by ANN. I worked on this direction many
years ago.
: 听你的？我一千多万刀的经费白拿啊，真是笑话。
【在 y**b 的大作中提到】
: 更新一下：
: 1. Cray X40/X50的系统真是有问题啊，分发速度慢40倍。
: 另外，我们小中大规模的多平台模拟测试都表明其计算速度只有SGI ICE X/XA
: 系统的一半，SGI上面50 million allocation的计算能力相当于Cray上100
: million core-hours！
: 美国三台Exascale超算都由Cray承建，令人担心。
: 2. dem-cfd resolved耦合计算，为了提高load balance，mpi网格变成了非均匀网格。
: 但是，cfd具备非常细密的的均匀网格，可以使用O(1)算法确定一个dem颗粒质心所处于
: 的cfd网格，然后由该cfd网格推算dem颗粒所属进程，这样，dem-cfd resolved耦合计
: 算的初始分发过程，仍然可以使用O(1)算法！
|
|
|
y**b
发帖数: 10166 | 81 我不是牛人，既然曾经是同行，欢迎交流，我也简单说一下，不全见谅。就我的认识而
言，dem正在发生深刻变化，十年前我们只能计算几千个复杂形状颗粒，现在计算5
million个颗粒完全没有问题，今后几年随着支持我们项目的Exascale computing慢慢
登场，billion或更多都不应该有问题。注意我们采用相对非常严格的模型（非线性，
history-dependent模型等等），要求精确复制动静力实验结果，因此计算消耗非常大
，使用几千个节点的计算很常见。如果按照那些进行了惊人简化的粗糙模型、玩具模型
，早就能超过billion了，所以说不能光看数目和形状，更要看模型精度。实际上DEM计
算的可扩展性是非常不错的，strong scaling measurment表现出令人吃惊的
superlinear speedup特点，模型本身出现的一些计算方法如Level-set, clustered
particles等，实验方法如3d 扫描，3d打印和复制等，算是很不错的进展了。当然DEM
永远也不可能也无必要取代连续介质方法，但是可以通过不同形式来通知和改进连续介
质方法，比如micropolar/micromorphic等理论（这些理论几十年前就深刻洞悉了颗粒
材料的特殊性，苦于计算能力不足和非连续介质模型的弱势得不到下一层检验而不能大
行其道，但是近年来国防部和能源部都开始意识到了）；dem对探索颗粒材料本身的特
性之重要自不待言，尤其是在非连续区域进行高精度模拟，可以探索连续介质方法无力
解决的很多问题，这在研究上也是了不起的，具体的研究和描述方法也开始出现一些进
展。
过去几十年DEM大都是采用超级简化模型，几乎到了令人咋舌的地步，这里面既有过渡
到工程应用的不得已而为之，也就很多人的不明就里。如果看鼻祖Peter Cundall等在
Itasca商业代码里面采用的阻尼模型，简直令人要哭了，完全失真啊，也不知他怎么能
够容忍。
以dem为核心进行一些扩展，我们拿到两个千万级别的项目，有竞争对手用contact
dynamics也拿到千万级别的项目，Level-set一套东西从NASA也拿到不小项目，作为研
究还是很可观的。
【在 m**u 的大作中提到】
: 这个和钱没有啥关系， 估计1千万美刀解决不了这个问题
: 有些东西，没办法就是没办法，至少暂时没办法。DEM 出来N年了，还是那个鸟样，俺
: 15年前搞过，这个方法的计算过程中的不可扩展性导致颗粒/node 数量达到一定程度后
: ，没法解决。过去N年中，一直卡在这里。
: 当然俺不否认您可能是超级牛人，比过去几十年的哪些搞DEM的强10条街，可能会搞出
: 牛方法来解决计算复杂性问题。那也是巨大贡献。 这个DEM对解决不连续体系很有意义
: ， 就是计算上搞不定。
|
y**b
发帖数: 10166 | 82 GPGPU这个我是晚了，不得不追啊，新出的超算都是heterogeneous architecture.
【在 g****t 的大作中提到】
: Better machines often brought better results. Money matters.
: It was reported that GPU matters for DEM,FEM, etc.
: https://www.researchgate.net/publication/318072393_BlazeDEM3D-GPU_A_Large_
: Scale_DEM_simulation_code_for_GPUs
:
:
: 这个和钱没有啥关系， 估计1千万美刀解决不了这个问题
:
: 有些东西，没办法就是没办法，至少暂时没办法。DEM 出来N年了，还是
: 那个鸟
: 样，俺
:
: 15年前搞过，这个方法的计算过程中的不可扩展性导致颗粒/node 数量达
|
y**b
发帖数: 10166 | 83 非cs出身，这方面跟进太慢，虽然proposal里面也扯了一些（不扯不行）。
谢谢推荐文章，以后还要多请教。
many
【在 g****t 的大作中提到】
: Had u tried to leverage modern AI? For example:
: https://arxiv.org/abs/1911.04240
: In theory, all PDEs can be simulated by ANN. I worked on this direction many
: years ago.
:
:
: 听你的？我一千多万刀的经费白拿啊，真是笑话。
:
|
c*******v
发帖数: 2599 | 84 I did not major in CS too.
EE bs and master.(Genetic algorithm and neural network)
ME phd.(spectrum method with symbolic computation)
In this board, there were several ME phd.
【在 y**b 的大作中提到】
: 非cs出身，这方面跟进太慢，虽然proposal里面也扯了一些（不扯不行）。
: 谢谢推荐文章，以后还要多请教。
:
: many
|
c*******v
发帖数: 2599 | 85 Were I u, I would like to setup a meeting of "deep DEM" and
focus on ppt first.Then outsource the work to some engineers.
(I assumed it was R and D type of work. It would be a different story if you
aimed to develop a business )
【在 y**b 的大作中提到】
: GPGPU这个我是晚了，不得不追啊，新出的超算都是heterogeneous architecture.
|
y**b
发帖数: 10166 | 86 business不行啊，这些对计算能力要求太高，小企业没法承受。
前几年tecplot公司来征求我对后处理软件的使用意见，看我展示
的东西，还问我对商业化的兴趣，我开玩笑说如果pc计算能力提高
1000倍我会的。wish GPU can make it. |
F****n
发帖数: 3271 | 87 你这个的bottleneck主要是在IO
比如你的文件如果存在一个硬盘上，
你开再多的节点也没用，因为磁头只有一个
这是为什么很多大数据分析都是基于顺序存取。
一般来说，分析进程比特率的上限就是顺序读存储的比特率
你的方案1可行，看上去简单但其实比大多数回帖的都靠谱
主要还是I/O bottleneck, 因为主进程作为Distributor需要建立的连接太多，
解决方案很简单，多加几个Distributors就行了：
假设你的文件大小为M，每个节点建立N个链接总比特率最优，
那么你应该把文件分割为M/N 大小的packages, 让后传给N个Distributor
按以上递归，直到传到计算节点。
【在 y**b 的大作中提到】
: 通常，主进程读取初始数据文件并切割分发到各进程，然后开始计算。对这种模式
: 测试了两千个节点规模的计算，发现：对中小规模数据可行，但是数据规模大到一
: 定程度，这个主进程切割并分发数据就慢得无法接受。例如，数据文件有50 million
: 个或更多记录（每个记录包含一个颗粒的大小，形状，空间位置，空间方向，运动状
: 态等等，全部读入消耗大约30GB内存），主进程将这50 million个颗粒进行三维毗邻
: 空间划分（也即计算各进程的初始空间和相应所含颗粒），并分发到相应的大约50k个
: 并行进程，主进程的这个双重循环过程（50k by 50M）基本无法完成。
: 想到以下几个方案：
: 1。上述的主进程读取初始数据文件，然后切割分发到各进程。
: 2。主进程读取初始数据文件，然后将整个数据文件broadcast到各进程，各进程自行
|
c*******v
发帖数: 2599 | 88 From my understanding, his bottleneck is in the double loop that has been
solved by using pptwo's algorithm.
【在 F****n 的大作中提到】
: 你这个的bottleneck主要是在IO
: 比如你的文件如果存在一个硬盘上，
: 你开再多的节点也没用，因为磁头只有一个
: 这是为什么很多大数据分析都是基于顺序存取。
: 一般来说，分析进程比特率的上限就是顺序读存储的比特率
: 你的方案1可行，看上去简单但其实比大多数回帖的都靠谱
: 主要还是I/O bottleneck, 因为主进程作为Distributor需要建立的连接太多，
: 解决方案很简单，多加几个Distributors就行了：
: 假设你的文件大小为M，每个节点建立N个链接总比特率最优，
: 那么你应该把文件分割为M/N 大小的packages, 让后传给N个Distributor
|
