Корректность

Корректная переносимая программа должна работать без дедлоков. Приводимые ниже примеры иллюстрируют опасность использования коллективных опраций.

Пример 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; 
}

Процесс ноль выполняет широковещательную рассылку (bcast), сопровождаемую блокирующей посылкой данных (send). Процесс один выполняет блокирующий прием (receive), который соответствует посылке с последующей широковещательной передачей, которая соответствует широковещательной операции процесса ноль. Такая программа может вызвать дедлок. Операция широковещания на процессе ноль может вызвать блокирование, пока процесс один не выполнит соответствующее широковещаельную операцию, так что посылка не будет выполняться. Процесс ноль будет неопределенно долго блокироваться на приеме и в этом случае никогда не выполнится операция широковещания.

Относительный порядок выполнения коллективных операций и операций парного обмена должен быть таким, чтобы даже в случае синхронизации не было дедлока.

Пример 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; 
}

Все три процесса учавствуют в широковещании (broadcast). Процесс 0 посылает сообщение процессу 1 после операции широковещания, а процесс 2 посылает сообщение процессу 1 перед операцией широковещания. Процесс 1 принимает данные перед и после операции широковещания, с произвольным номером процесса-отправителя.

У этой программы существует два возможных варианта выполнения, с разными соответствиями между отправлением и получением, как показано на рисунке 4.10. Заметим, что второй вариант выполнения имеет специфический эффект, заключающийся в том, что посылка, выполненная после операции широковещания, получена в другом узле перед операцией широковещания.

$\includegraphics[width=5.64in,height=3.49in]{Ch4figure8.eps}$

Наличие гонок в этом примере делает соответствие посылок и приемов неоднозначным. Не следует рассчитывать на синхронизацию от широковещания.

Этот пример показывает, что нельзя полагаться на специфические эффекты синхронизации. Программа, которая работает правильно только тогда, когда выполнение происходит по первой схеме (только когда операция широковещания выполняет синхронизацию) неверна.

В заключение отметим, что в многопоточных реализациях можно получить на процессе более, чем одну параллельно выполняемую операцию коллективного обмена. В таких ситуациях пользователь должен гарантировать, что тот же самый коммуникатор не используется одновременно двумя разными коллективными операциями, вызываемых из одного и того же процесса.

Совет разработчикам: Предположим, что операция широковещания выполнена на основе парных обменов MPI. Предположим также, что выполняются следующие два правила:

Тогда сообщения, принадлежащие к последовательным операциям широковещания, не могут быть перемешаны, поскольку сохраняется порядок сообщений парного обмена.

Чтобы гарантировать, что сообщения парного обмена не перемешаны с коллективными сообщениями, нужно всякий раз, когда коммуникатор создан, также создавать ``скрытый коммуникатор'' для коллективного обмена. Очевидно можно достичь подобного эффекта проще, например, используя скрытую отметку или контекстный бит, чтобы указать, используется ли коммуникатор для парного обмена или для коллективной коммуникации.[]