球面的分划方案

[Mingli Yuan]

嗨，各位，

因为这个题目涉及算法，也觉得本身还有趣，所以也发本讨论组一份。

我正开始研究怎样实现瓦克星天气计算的一个分布式算法， 但今天遇到的一个难题是球面的分划方案。 

球面的分划，特别是等面积分划有多种算法，本身是一个有趣的领域， 请参照下面的演讲和论文： 

* http://maths.anu.edu.au/~leopardi/Macquarie-sphere-talk.pdf 
* http://www.maths.unsw.edu.au/sites/default/files/amr05_18_0.pdf 

但等面积的要求，对分布式算法来说，是一个很强的条件。 

当你的分布算法事先知道计算节点数量且该数量不变化，那么等面积分划是可行的； 
这种情况是情形一。 

但如果你的计算节点数量是变动的，如p2p的情况， 那么等面积分划要求所有节点都同步，这几乎是不可能的； 
这种情况是情形二。 

另一方面，等面积划分又有很良好的性质，就是每个节点计算消耗的资源大致均衡。 
所以，我们寻找的分划方案，不一定等面积，但是要近似等面积。 

这个问题，我觉得本身可以作一个硕士论文了。如果比较难，我就先退而求其次。 
因为我现在在实验单机多核的计算方案，分划的数量不多， 
只有有限的情况，1、2、3、4、5、6， 
市面上常见的i7机型，最多8进程，留两个进程给其他任务， 
所以我目前最多考虑分划为6个区域。 

即便如此，分划为6个区域也有多种分法，哪种分法比较好还是可以探讨的。 

我先提出问题，欢迎大家讨论。 

[HaoPeiQiang]

数学不好，先不说算法。有点疑问。

第一、等面积是不是天气算法必须的。不懂啊，如果不是，那么经纬度系统很方便的。
第二、一般分布算法的逻辑都是不应该考虑节点的数量，如果你在乎节点数量，那么就很难保证灵活性。

一般的逻辑我觉得应该是这样的，首先把问题分解为N份，N远大于节点数。然后节点每次要n个块来运算，算完了再继续要任务。

2011/12/29 Mingli Yuan <mingl...@gmail.com>:

--
Tinyfool的Blog http://tiny4.org/blog/
Tiny4Cocoa http://tiny4.org/cocoa/
myTwitter: http://twitter.com/tinyfool

[Mingli Yuan]

多谢回复。

确实，等面积不是算法必须的。我是在均匀网格情况下，由计算节点之间的负载基本相同，推出来的面积也是近似相等的。

解算偏微分方程，首先要有差分所需的网格系统（规则、均匀的或者不规则的、不均匀的），这是球面的离散化。

每个格点都有临近格点，构成一定的拓扑和度量关系。计算之前，需要知道这些拓扑和度量关系，来决定一些计算的参数。

计算之中，每个节点也需要知道临近节点在相同时刻的状态，再联合本节点状态，计算本节点的下一状态，这是微分方程的本意。

如果采用显式算法，基本上网格的每一个节点都在反复施用同一套计算规则；所以很自然的想法是，分布就是把节点分划开。

而这个思路，也就是我前面说的，球面的分划。

你所说的把问题分解为N份，N远大于节点数，基本上就是我说的球面的离散化，或者网格。

而分布，还是要把N再分成M份，也就是我说的，球面的分划，或者网格的分划。

这样说，可能更清楚一些。

2011/12/29 HaoPeiQiang <HaoPe...@gmail.com>

[HaoPeiQiang]

均匀的假设，我们就不好叫分布了，叫并行吧。

2011/12/29 Mingli Yuan <mingl...@gmail.com>:

[Mingli Yuan]

即使是均匀网格，只是空间上的均匀。我理解的分布和并行的差异（可能不准确），很重要的是有没有全局同一的时间进度。

我们的多个进程，可能每个进程有自己的时间进度，需要计算彼此依赖的数据时，在通过某种算法和协议，来拉平进度。

2011/12/29 HaoPeiQiang <HaoPe...@gmail.com>

[Milo Yip]

在圖形學上，通常會用tessellation，不知道能不能解決你的問題。例如

https://ziyan.info/2008/11/sphere-tessellation-using-icosahedron/

--
Milo Yip

http://www.cnblogs.com/miloyip/
http://weibo.com/miloyip/
http://twitter.com/miloyip/

[Mingli Yuan]

多谢提示。tessellation用来生成均匀网格很方便。

我是这样考虑的。不是很确信，应该还需要更细的分析。

分划方案的拓扑关系决定了计算节点之间的彼此依赖，而依赖越多，则分布计算时需要的同步数据的操作就越多。

这是不利于计算速度的。

举例来说，像切西瓜一样，全部沿着经线切，把赤道切分成6等分，在两极点处重合。那么对这种方案：

6个计算节点全都因为重合的极点而彼此依赖，每一步计算都需要彼此同步，或者类似于同步的操作。

另一方案：先切两极出来两个盖A、B，再把余下的球台等切四分C、D、E、F。这时候的依赖关系是

A:CDEF

B:CDEF

C:ABDF

D:ABCE

E:ABDF

F:ABCE

2011/12/29 Milo Yip <mil...@gmail.com>

[Mingli Yuan]

哦，我明白了。不应该只考虑6块的彼此邻接情况，还要考虑块的边缘的长度。以下在均匀网格的前提下讨论。

计算任务可以分成主计算任务和数据交换、同步任务两种。

• 主计算任务的计算量正比于块的面积
• 数据交换、同步任务的计算量正比于边缘的边长
• 块的依赖关系由邻接关系决定

我再去算算上面两个方案的边长的比较。切西瓜方案比较简单，总边长是 6 \pi，带盖的方案我吃完饭再算。

2011/12/29 Mingli Yuan <mingl...@gmail.com>

[Mingli Yuan]

因为数据交换和同步有IO，是比较慢的；而主任务全部在内存，比较快。

这意味着，给定一定数量规模的均匀网格，比如有N个网点。

计算节点数量M并不是越多越好，因为M越多，边长就增加，计算反倒会被拖慢。

能发挥最大分布效果的节点数量应该是多少呢？弄清楚这个关系，很有趣呀。

可能说的不是很清楚，但我觉得思路是对的。

2011/12/29 Mingli Yuan <mingl...@gmail.com>

[Mingli Yuan]

我最终选用了NASA JPL的HEALPix系统的球面划分方案。

论文可以参见这里：http://arxiv.org/abs/astro-ph/0409513

另外，我已经开始用C++实做一个HEALPix系统的实现，仅仅刚刚开始。

代码在这里：https://github.com/Wahlque/sphere

我C与C++仅仅是初学，还请各位多多指教。

2011/12/29 Mingli Yuan <mingl...@gmail.com>