2-мерный алгоритм перемещения с ограничением

Question

Имеется двумерный массив шириной m и высотой n.

Я хочу поместить все ячейки в очередь, чтобы моя k -поточная программа могла их обработать.

Однако, одно важное ограничение заключается в том, что будут конфликты, когда обрабатываются две соседние ячейки в 8 направлениях (например, (2,3),(2,4), (2,3),(3,3) и (2,3),(3,4)).

Как мне найти алгоритм для генерации такой очереди, надеюсь, за O(m*n) время?

Кстати, мне удалось ограничить k < m*n/4 (если это уже безопасно или скажите мне, как мало я должен ограничить k, чтобы быть в безопасности), чтобы избежать таких случаев, как m=8,n=8,k=64.

Answer 1

IMO, эффективная стратегия состоит в том, чтобы разбить массив на k прямоугольников вдоль длинной стороны и заполнить их построчно вдоль короткой стороны. Заполните каждый другой прямоугольник в одном направлении и наоборот. Между двумя потоками, работающими вдоль общего ребра, будет долгая задержка, и если они это сделают, они будут делать это очень быстро в соседних ячейках (если я прав, они могут конфликтовать максимум в трех ячейках).

---

Если конфликты запрещены, разбейте их на k прямоугольников и дайте каждой нити заполнить нижнюю половину (любой порядок). Тогда пусть они ждут у барьера. Затем дайте им заполнить вторую половину.

Вы также можете реализовать мьютексы k-1, чтобы запретить парам соседних потоков воздействовать на соседние половины.

Answer 2

Для начала:

Разделите массив на k прямоугольных областей.

Сканирование всех областей по диагонали в зигзагообразном порядке из левого верхнего угла, например:

  (0,0)-(1,0)-(0,1)-(2,0)-(1,1)-(0,2)-(3,0)-(2,1)-(1,2)-(0,3)...

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