4.12 正确性(Correctness) BACKWARDFORWARD

无论集合通信是同步的还是异步的,一个正确的、可移植调用集合通信的程序都不应引起死锁.下面是一些调用集合例程的危险例子:

例4.23: 下列例子是错误的.

    switch(rank) {
        case 0:
            MPI_Bcast(buf1, count, type, 0, comm);
            MPI_Bcast(buf2, count, type, 1, comm);
            break;
        case 1:
            MPI_Bcast(buf2, count, type, 1, comm);
            MPI_Bcast(buf1, count, type, 0, comm);
            break;
    }

我们假设通信子comm的组是{0,1},两个进程按相反的顺序执行两个广播操作,如果操作是同步的话就会引起死锁.

在通信组所有成员上的集合操作必须按同一个顺序执行.

例4.24: 下列例子是错误的.

    switch(rank) {
        case 0:
            MPI_Bcast(buf1, count, type, 0, comm0);
            MPI_Bcast(buf2, count, type, 2, comm2);
            break;
        case 1:
            MPI_Bcast(buf1, count, type, 1, comm1);
            MPI_Bcast(buf2, count, type, 0, comm0);
            break;
        case 2:
            MPI_Bcast(buf1, count, type, 2, comm2);
            MPI_Bcast(buf2, count, type, 1, comm1);
            break;
    }

假设通信子comm0的组是{0,1},通信子comm1的组是{1,2},通信子comm2的组是{2, 0}.如果广播是同步操作,那么存在一个循环依赖:comm2中的广播通信中仅当comm0中的广播通信结束后才能结束;comm0中的广播通信中仅当comm1中的广播通信结束后才能结 束,comm1中的广播通信仅当comm2中的广播通信结束后才能结束,这样就会产生死锁.

例4.25: 下列例子是错误的.

    switch(rank) {
        case 0:
            MPI_Bcast(buf1, count, type, 0, comm);
            MPI_Send(buf2, count, type, 1, tag, comm);
            break;
        case 1:
            MPI_Recv(buf2, count, type, 0, tag, comm, status);
            MPI_Bcast(buf1, count, type, 0, comm);
            break;
    }

进程0执行一个广播操作,后面跟一个阻塞发送操作;进程1执行一个与进程0的发送操作相匹配的阻塞接收操作,后面跟一个与进程0广播相匹配的广播操作.这个程序会产生死锁,因为进程0上的广播通信调用可能被阻塞直到进程1执行了相应广播通信调用,所以发送不能执行,而进程1正是在接收处阻塞, 所以永远不可能执行广 播操作.

无论是集合通信还是点对点通信,即使是同步的也不应引起死锁.

例4.26: 一个正确的,但非确定性的程序.

    switch(rank) {
        case 0:
            MPI_Bcast(buf1, count, type, 0, comm);
            MPI_Send(buf2, count, type, 1, tag, comm);
            break;
        case 1:
            MPI_Recv(buf2, count, type, MPI_ANY_SOURCE, tag, comm, status);
            MPI_Bcast(buf1, count, type, 0, comm);
            MPI_Recv(buf2, count, type, MPI_ANY_SOURCE, tag, comm, status);
            break;
        case 2:
            MPI_Send(buf2, count, type, 1, tag, comm);
            MPI_Bcast(buf1, count, type, 0, comm);
            break;
    }

上述的三个进程都参与了广播通信,进程0在广播通信后向进程1发送了一条消息,进程2在广播通信前向进程1发送了一条消息,进程1在广播通信前后采用通配符进行接收操作.

这个程序有两种可能的执行方式,它们随发送和接收匹配的不同而不同,图4.10中说明了这一点.注意在第二种情况中有一个奇特的效果,那就是发送执行的条件是发出的广播消息在另一个节点的广播操作前被接收.这个例子说明这样一个事实,即编程时不应当依赖于集合通信函数所特有的同步作用.这个仅当第一种执行情况发生时(仅当广播通信是异步的)才能正确执行的程序是错误的.

图4.10: 发送与接收之间非确定性匹配.不应当依赖广播中的同步来保证程序的确定性

最后,如果采用多线索的实现技术,在一个进程中可能有多于一个的集合通信例程在并发的执行,在这种情况下,.用户应该保证在一个进程中一个通信子不能被两个不 同的集合操作同时使用.

对实现者的建议: 假设广播是用点对点的通信方式实现的,它应该遵守下面的两条规则.

这样,当点对点的消息顺序保持好后, 属于两个连续广播操作的消息就不能相互混淆.

保证点对点的通信消息不和集合通信消息相互混淆是实现者的责任.一种方法是:不论什么时候产生一个通信子,都要为集合通信产生一个隐含的通信子.还可以用一个更简便 的方法得到同样的效果,例如,用一个隐含的标记或一个上下文位(context bit)来表明一个通信子是为点对点通信使用还是为集合通信使用.(对实现者的建议结尾)

Copyright: NPACT BACKWARDFORWARD