Любые эффективные решения для решения проблемы зависимости, что «j-й шаг задачи i-й зависит от (J+1) -кого шага (i-1) -т ⇐ C++

[Anonymous]

У меня есть рабочая нагрузка, состоящая из ряда задач, и каждая задача может быть разделена на шаги K. До сих пор, J-й шаг задачи I-TH зависит от J-Th Step of (I-1) -6 задачи. Это может быть легко обработано с помощью трубопровода следующим образом (каждая стадия выровнен по размеру линии кэша, чтобы избежать ложного обмена): < /p>

Код: Выделить всё

void pipe(uint64_t j) {
uint64_t pred = 0;
for (uint64_t i = 1; i  0) { while (pred < i) { pred = load_consume(&pipes_[j-1].stage); } }
/* do something */
if (j < k-1) { store_release(&pipes_[j].stage, i); }
}
}
< /code>
Существуют k трубы, где J-й труба последовательно обрабатывает J-й шаг каждой задачи. Отслеживая идентификатор задачи, который выполняла каждая труба, труба J-гот может проверить, обрабатывает ли (J-1) -ная труба текущая задача. For example, with 3 pipes, the state of pipeline is:



pipe/time
1
2
 3 < /th>
 4 < /th>
 5 < /th>
 6 < /th>
< /tr>
< /thead>


 2 < /td>
 < /td>
1.2
2.2.2
3.3.2,2
4.2,2
>
>
>
>
/>  3 < /td>
 < /td>
 < /td>
td>1.3
2.3
> 33 /> < /tr>
< /tbody>
< /table> < /div>
Этот трубопровод быстр-на моем сервере, при оптимизации O3, 16 труб завершают 10 миллионов итераций примерно за 0,05 секунды. задача. To explain, with 3 pipes, the state of pipeline becomes:



pipe/time
1
2
3
4
5
6
7
8
9




 1 < /td>
td>>1.1
 < /td>
td>2.2 />4.4.1
 < /td>
5.5.1
< /tr>

 2 < /td>
 < /td>
. />  < /td>
>2.2,2,2,2,2,20/td>>>  < /td>
3.2,2
 < /td>
4.2,2>  < /td>

 style = "text-align: center;"> 3 
 
 
td>1.3
 
2.3
 
. />  < /td>
>4.3
< /tr>
< /tbody>
< /table> < /div>
Наивно, я могу добавить проверку на стадию следующей трубы, как: < /p>
void pipe(uint64_t j) {
uint64_t pred = 0;
uint64_t succ = 0;
for (uint64_t i = 1; i  0) { while (pred < i) { pred = load_consume(&pipes_[j-1].stage); } }
if (j < k-1) { while (succ < i-1) { succ = load_consume(&pipes_[j+1].stage); } }
/* do something */
if (j < k-1) { store_release(&pipes_[j].stage, i); }
}
}
< /code>
Теоретически, в исходном трубопроводе, каждая труба не имела простоя. В новом трубопроводе время холостого хода идентично рабочее время, тем самым удваивая общее время. Однако производительность становится ужасной (выше в 100 раз медленнее).  Затем я попытался решить эту проблему, используя циклический трубопровод следующим образом: < /p>
void pipe(uint64_t j) {
uint64_t pred = 0;
for (uint64_t i = 1; i 
Этот подход работает правильно, чтобы объяснить, с 3 трубами, состояние трубопровода будет: < /p>
 


  < /td>
1.2
2.2.1
 < /td>
 < /td>
 < /td>
td>3.33.333333333333333333333333333333333333333333333333333333333.333333.333.33333333.33333.333.333.33333.3333.3333.333.33333.33333.333.333.333.333.333.333.33333.333.33333 />5.5.1
< /tr>

 3 < /td>
 < /td>
 < /td>
td>1.3>  < /td>
/>3.3.1
 < /td>
 < /td>
 < /td>
4.3,3образно Каждая стадия трубы легко увидеть, что при обработке ряда P -задач общее время холостого хода циклического трубопровода совпадает с тем, что у наивного трубопровода. По сравнению с наивным трубопроводом, который требует двухэтапных проверок на шаг, этот подход нуждается только в одноэтажной проверке за шаг, который такой же, как и трубопровод для исходной проблемы. Однако при оптимизации O3 остается существенный разрыв производительности (приблизительно на 40 раз) между циклическим трубопроводом и исходным трубопроводом. Поэтому я развернул цикл, чтобы устранить операторы ветвления (а также удалить операцию модуля): < /p>
void pipe(uint64_t j) {
uint64_t i = 0;
uint64_t pred = 0;
uint64_t in  = j;
uint64_t out = (j+1)%k;

while (j < n + k) {
while (i < j) {
while (pred 
Тем не менее, развернутая реализация дала незначительный результат производительности по сравнению с его предшественником. Затем я пробую альтернативный подход планирования, который каждая поток выполняет целую задачу во время синхронизации с помощью этапов: < /p>
 

  2 
 
 
2.2.1
2.2 />2.2.6
5.5.1 >образно />  < /td>
 < /td>
3.3.1
3.2,2> /> < /tr>
< /tbody>
< /table> < /div>
Этот подход уменьшает время холостого хода, позволяя трем потокам выполнять задачи, которые требуют шести шагов, код следующим образом: < /p>
void work(uint64_t id) {
uint64_t pred = 0;
uint64_t in  = (id+k-1)%k;
uint64_t out = id;
uint64_t t = id*2;
store_release(&pipes_[out].stage, t);

for (uint64_t i = id; i 
Аналогично, в этом коде каждый шаг требует только одного проверки зависимостей и не содержит инструкций по филиалам.  Однако, по сравнению с циклическим трубопроводом, этот подход не показывает существенной разницы во время выполнения (преимущество в том, что количество потоков уменьшается вдвое). Однако при оптимизации O3, между двумя подходами возникает значительный разрыв в производительности.void pipe(uint64_t j, uint64_t p0) {
uint64_t pred = 0;
for (uint64_t i = 1; i  

Подробнее здесь: [url]https://stackoverflow.com/questions/79644893/any-efficient-solutions-to-address-the-dependency-that-the-j-th-step-of-the-i-t[/url]