Мысли насчет распараллеливания маркировки связанных областей
Графики из предыдущей темы (блин, обнаружил, что я вчера все делал в /tmp, а перенести в ~/Dropbox забыл! Поэтому все изменения пошли коту под хвост, уцелело лишь то, что в ЖЖшке выложил, так что посчитать коэффициенты не могу, а тесты заново делать ломает) показывают, что зависимость скорости вычислений от количества пикселей на объекте (а также - количества объектов и их размера) имеет степенной вид, причем степень довольно плавно изменяется при изменении размера изображения.
Таким образом, если время вычислений T = Nm, где N - количество пикселей на изображении, то разбиение изображения на M кусков может позволить ускорить вычисления в том случае, если
T1 = M·[(N/M)m + t(sqrt(N/M))] < T.
Здесь t - время выполнения операции слияния границ соседних блоков с соответствующей ремаркировкой.
Понятно, что если блоки достаточно большие, второе слагаемое внутри скобок будет значительно меньше первого. Грубо пренебрегая им, получим в нулевом приближении, что разбиение изображения на M блоков ускоряет вычисления в Mm-1 раз. Однако, учитывая то, что второе слагаемое в скобках пропорционально своему аргументу, раскрытие скобок даст нам нечто вроде
M1-m + k·sqrt(MN)/T < 1,
где k - некий постоянный коэффициент. Таким образом, выигрыш в производительности очень сильно будет зависеть от m, k (при некоторых их комбинациях выигрыш вообще невозможен), а также собственном M (причем, учитывая то, что у нас получается степенное уравнение, оптимальных значений M может быть несколько, "смотря как карта ляжет").
Для того, чтобы в реальности оценить, что да как, необходимо реализовать распараллеливание "метода китайцев" (кстати, сами они писали, что распараллелили, причем даже попытались прикинуть оптимальное значение M) и, варьируя N и M, оценить, возможно ли вообще увеличение производительности при распараллеливании вычислений, а если оно возможно, то попытаться выявить зависимость оптимального значения M от N.
Само распараллеливание я себе представляю так. Разделим изображение на M кусков (полосами или прямоугольниками - зависит от размера изображения; но, скорее всего, все-таки прямоугольниками). Выделим глобальный массив для ремаркировок assoc[M][s];, где s - предельное количество ассоциаций в одном сегменте. Также выделим массивы размера M для хранения количества меток и количества объектов в каждом сегменте. Потом запустим M потоков выделения объектов в каждом сегменте. Внутри каждого сегмента оставим нетронутой пограничную область шириной в 1 пиксель: скажем, правый столбец и нижнюю строку.
После завершения всех потоков обновляем массивы ремаркировок: к номеру каждого объекта в очередном сегменте добавляем количество объектов в предыдущих сегментах.
Теперь нам нужно провести стыковку соседних областей. Этот процесс тоже допускает параллелизацию. Пробегая по пограничным областям каждого сегмента, устанавливаем ненулевой пиксель в значение ближайшего ненулевого пикселя этого сегмента или же новое значение, производя соответствующие ремаркировки. Самый худший вариант - отдельный объект в виде полосы шириной в 1 пиксель, находящийся точно на границе: никаких ремаркировок не будет, но счетчик объектов инкрементируется. А это приведет к тому, что нужно будет полностью обновить огромный общий массив ремаркировок, увеличив его размер на 1. Еще нужно не забывать, что в углах каждой области (кроме пограничных вариантов) необходимо проверить пиксели четырех областей (с соответствующими изменениями в массиве ремаркировок). В итоге коэффициент k в приведенной выше формулке может стать вполне приличным.
Однако, как я уже говорил, без проверки ничего точно сказать нельзя.
Таким образом, если время вычислений T = Nm, где N - количество пикселей на изображении, то разбиение изображения на M кусков может позволить ускорить вычисления в том случае, если
T1 = M·[(N/M)m + t(sqrt(N/M))] < T.
Здесь t - время выполнения операции слияния границ соседних блоков с соответствующей ремаркировкой.
Понятно, что если блоки достаточно большие, второе слагаемое внутри скобок будет значительно меньше первого. Грубо пренебрегая им, получим в нулевом приближении, что разбиение изображения на M блоков ускоряет вычисления в Mm-1 раз. Однако, учитывая то, что второе слагаемое в скобках пропорционально своему аргументу, раскрытие скобок даст нам нечто вроде
M1-m + k·sqrt(MN)/T < 1,
где k - некий постоянный коэффициент. Таким образом, выигрыш в производительности очень сильно будет зависеть от m, k (при некоторых их комбинациях выигрыш вообще невозможен), а также собственном M (причем, учитывая то, что у нас получается степенное уравнение, оптимальных значений M может быть несколько, "смотря как карта ляжет").
Для того, чтобы в реальности оценить, что да как, необходимо реализовать распараллеливание "метода китайцев" (кстати, сами они писали, что распараллелили, причем даже попытались прикинуть оптимальное значение M) и, варьируя N и M, оценить, возможно ли вообще увеличение производительности при распараллеливании вычислений, а если оно возможно, то попытаться выявить зависимость оптимального значения M от N.
Само распараллеливание я себе представляю так. Разделим изображение на M кусков (полосами или прямоугольниками - зависит от размера изображения; но, скорее всего, все-таки прямоугольниками). Выделим глобальный массив для ремаркировок assoc[M][s];, где s - предельное количество ассоциаций в одном сегменте. Также выделим массивы размера M для хранения количества меток и количества объектов в каждом сегменте. Потом запустим M потоков выделения объектов в каждом сегменте. Внутри каждого сегмента оставим нетронутой пограничную область шириной в 1 пиксель: скажем, правый столбец и нижнюю строку.
После завершения всех потоков обновляем массивы ремаркировок: к номеру каждого объекта в очередном сегменте добавляем количество объектов в предыдущих сегментах.
Теперь нам нужно провести стыковку соседних областей. Этот процесс тоже допускает параллелизацию. Пробегая по пограничным областям каждого сегмента, устанавливаем ненулевой пиксель в значение ближайшего ненулевого пикселя этого сегмента или же новое значение, производя соответствующие ремаркировки. Самый худший вариант - отдельный объект в виде полосы шириной в 1 пиксель, находящийся точно на границе: никаких ремаркировок не будет, но счетчик объектов инкрементируется. А это приведет к тому, что нужно будет полностью обновить огромный общий массив ремаркировок, увеличив его размер на 1. Еще нужно не забывать, что в углах каждой области (кроме пограничных вариантов) необходимо проверить пиксели четырех областей (с соответствующими изменениями в массиве ремаркировок). В итоге коэффициент k в приведенной выше формулке может стать вполне приличным.
Однако, как я уже говорил, без проверки ничего точно сказать нельзя.