Как выйти из цикла for в cilk?

Question

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

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_forcilk_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.