日期:2014-05-20  浏览次数:20746 次

提出一个挑战性问题请大家思考
提出一个问题请大家思考(问题与java无关,不过我正在使用java解决它)

假定现在有n台计算机(即n个计算节点)构成一个MPI   环境,现在给出一段MPI程序(这段程序在每台计算机上都会执行):

MPI_size(&n);

MPI_rank(&r);

if(r%2)   sendMessageTo(r+1);

else           recvMessageFrom(r-1);

显然,当n是偶数时,所有节点的程序都能顺利执行;当n是奇数时,必定有一个节点的程序不能执行完毕(呈现死锁等待状态)。

现在假定n等于100,那么我们可以构造一个模型,这个模型涵盖了100个节点的消息收发语句,此时,我们可以自动化判定所有节点的程序都不会死锁。

但是问题是n的值是不定的,那么有没有自动化方法判定呢?一种思路是穷举法,我们假定n有一个上界N,那么我们将n的值从1取到N,用n=100的方法就可以自动化判断了。

穷举方法使得我们必须判断N个模型来确定死锁,这显然是不理想的。我们希望能够有一种方法,使得我们不需要穷举所有n,而只需要取少量几个n的值就能确定这段程序的所有死锁特性。

当然,我们的方法不应该限制在上面这段程序上,而是所有类似的程序上。



------解决方案--------------------
up
------解决方案--------------------
可以考虑多维阵列。

拿2维阵列为例(多维不好画:P)

* * * * * ---正常?
* * * * * ---正常?
* * * * * ---正常?
* * * * * ---正常?
* * * * * ---正常?
| | | | |
? ? ? ? ?


100还不够大,维数越多支撑的越大。越可靠