Как вырваться из цикла в Cilk?

Question

Цикл for выглядит следующим образом:

cilk_for (int i=0; i<1000000; i++){
    do something;
    if(tag == 0){
        break;
    }
}

Затем при компиляции я получил эту ошибку:

error: break from parallel loop is not currently supported

Answer 1

Вы не можете вырваться из cilk_for потому что cilk_for не понимает порядок итераций. Итерации параллельного цикла в Cilk Plus (а также TBB и OpenMP и...) могут выполняться одновременно и / или не по порядку. Если программа не может предсказать будущее, как итерация 100 могла узнать, что в итерации 50 произошел перерыв, если итерация 100 выполняется до или одновременно с выполнением 50?

Если вам действительно нужно выйти из цикла на итерации i перед началом итерации i+1, то ваш алгоритм по своей сути последовательный и вы не можете использовать cilk_for, Однако если выход из цикла связан с производительностью (выполняющей меньше работы), а не с правильностью, то у вас есть класс проблем, известный как "спекулятивный параллелизм". В спекулятивном параллелизме вы готовы проделать некоторую дополнительную работу для преимуществ параллельной работы, но вы стараетесь избегать такой дополнительной работы, чтобы преимущества параллелизма были потеряны.

Cilk Plus не имеет каких-либо конструкций, специально предназначенных для спекулятивного параллелизма, но вы можете довольно легко их кодировать. Самое простое в этом случае было бы сделать tag в атомарную переменную вне цикла и измените ваше условие на:

if (tag == 0)
    continue;

Вы бы написали tag используя последовательно-последовательное упорядочение памяти, но вы можете прочитать его, используя упорядоченное упорядочение памяти, чтобы уменьшить конфликт памяти. Расслабленный порядок в памяти обычно рассматривается экспертами, но в этом случае вы находитесь на достаточно прочной основе. Более сложная система могла бы еще больше снизить конкуренцию за память путем разделения пространства цикла и использования древовидной структуры для распространения флага "выполнено" по итерациям.

Имейте в виду, что если вы сделаете то, что я предлагаю выше, то ВСЕ итерации, которые еще предстоит завершить, увидят изменения, даже те, которые последовательно были бы до итерации, которая устанавливает tag в ноль. Если вы хотите остановить только последующие итерации, не меняйте tag, но использовать отдельный атомный stop_i вместо переменной и измените логику на:

atomic_int stop_i(1000000);
cilk_for (int i=0; i<1000000; i++) {
    if (atomic_load(&stop_i, memory_order_relaxed) >= i)
        continue;
    do something;
    if(tag == 0){
        atomic_store(&stop_i, i, memory_order_seq_cst);
        continue;
    }
}

Заметьте, однако, что вы все равно получите умозрительное выполнение многих итераций за пределами попытки остановки. Только итерации, которые еще не начались при установке stop_i будут затронуты.