提出一个挑战性问题请大家思考
提出一个问题请大家思考(问题与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还不够大,维数越多支撑的越大。越可靠