о, вот теперь осознал Вашу идею. проэкспериментирую завтра — в теории звучит очень хорошо, на практике пока несколько смущает:
в 4 раза меньше операций, да это несомненно плюс.
но большая часть операций — запись, соответственно тут встанет вопрос об эффективности переноса такого алгоритма на видеокарту, даже если забыть про синхронизацию потоков — запись затратна.
а ускорение на основном процессоре в 4 раза все равно не даст нужного времени.
когда попробую — расскажу о результатах.
по сути, примерно это и происходит, за счет использования близких кубиков к границе. к сожалению, вопрос о заполнении не всех точек пространства даже не стоит — результирующую карту расстояний «кушает» другое приложение, которому нужны значения во всех точках. Но так или иначе заполнение оставшихся кубиков существенно быстрее, чем файловые операции для них.
Использование CUDA в данном случае было моей инициативой, повезло что ее не «зарезали» сразу, пока не было результатов.
Да, убедить иногда очень сложно, какие-то здравые аргументы, что если картинка не влезает в память и ее придется свопить, а это очень медленно — не принимались…
Разные технологии существуют для того, чтобы применять их в нужных случаях.
мне несколько не понятно, что значит «сегмент» в вашем вопросе. по сути мы помним все внешние точки для всех контуров, и попадая на внешнюю — пропускаем до внешней точки того же контура, лежащей правее остальных для заданного Y, то есть во внутренние точки у нас никаких шансов попасть нет.
в диагоналях проблем нет, это, вовсе не очевидно из кода обхода, согласен, но все учтено :)
и кстати это не совсем правда, т.к. даже у считывания изображения из файла в «плоском формате» сложность width*height, просто можно замаскировать предварительные действия за считывание в нужный формат в памяти. действительно — для того чтобы обработать изображение, нужно просмотреть каждый его пиксель. вопрос в том, чтобы этих просмотров (а тем более измнений) было не более 1 за работу алгоритма — и здесь почти так.
все-таки внешних точек существенно меньше, чем размер изображения. но в целом, да, сложность O(n^2), но даже в худшем случае на фильтрованном изображении константа будет порядка 0.25.
Так и знал, что что-нибудь да забуду. После обхода по контуру точки контура желательно отсортировать по X, затем по Y, тогда в алгоритме получения начальных точек можно будет пропускать не отдельные точки, а целые группы точек, принадлежащие уже обсчитанному контуру. Найти соответствующий Y и пропустить до максимального X.
и кстати, в процессе решения одной задачи мы придумали забавный метод — наплевать на синхронизацию вовсе, а после вычисления свалидировать значения и где нужно подправить — конечно, специфика это.
не зная конкретной задачи могу только порассуждать о правильном использовании адресации, чтобы подзадачи пересекались по-минимуму.
есть такая интересная особенность, что потоки решающие одинаковую по размеру подзадачу обычно завершаются одновременно, этот факт можно косвенно использовать (например один идет с начала блока — второй с конца).
интересна примерная производительность i5/i7 в GFLOPS.
прогресс по обоим направлениям идет, однако пока видеокарты устойчиво выигрывают в отношении производительность/стоимость и производительность/энергопотребление. хотя, конечно, это может зависеть от задачи, в частности задачи, которые вообще не параллелятся, а одно ядро CPU все-таки значительно мощнее ядра GPU.
в общем-то спецификация __global__ позволяет выполнять одни и те же функции на CPU и GPU. но смысла в этом не очень много, мощностями CPU можно просто пренебречь.
а вот переписать код, который работает в рамках классической модели на видеокарты — задача, которая автоматически (пока) не разрешима — другая модель, все-таки.
интересно, а какое приблизительно получилось получить ускорение относительно CPU?
в задачах, которые мы решаем в основном очень большие объемы данных фигурируют, и единственная цель, написать их обработку, так чтобы время передачи на карточку было соизмеримо со временем работы алгоритма, так что конечно все эти 10-40 Гбайт/с больше, чем нужно. хотя многие алгоритмы работают в несколько проходов — там это важно.
Верно. Скажем так, за счет быстрой памяти можно эффективно обрабатывать очень большие объемы данных, при этом стараясь сделать так, чтобы обсчет не сильно испортил это время.
Про именно вычислительные задачи напишу потом, однако там не все так радужно.
в общем-то они и передаются (и используются, как же без них), но они не обязаны быть кратными размерности решаемой задачи, поэтому и передаю дополнительные параметры, которые можно как-то покрутить. в общем да, ничего серьезного, производительность отличается на единицы процентов.
в 4 раза меньше операций, да это несомненно плюс.
но большая часть операций — запись, соответственно тут встанет вопрос об эффективности переноса такого алгоритма на видеокарту, даже если забыть про синхронизацию потоков — запись затратна.
а ускорение на основном процессоре в 4 раза все равно не даст нужного времени.
когда попробую — расскажу о результатах.
спасибо за идею!
Да, убедить иногда очень сложно, какие-то здравые аргументы, что если картинка не влезает в память и ее придется свопить, а это очень медленно — не принимались…
Разные технологии существуют для того, чтобы применять их в нужных случаях.
в диагоналях проблем нет, это, вовсе не очевидно из кода обхода, согласен, но все учтено :)
есть такая интересная особенность, что потоки решающие одинаковую по размеру подзадачу обычно завершаются одновременно, этот факт можно косвенно использовать (например один идет с начала блока — второй с конца).
прогресс по обоим направлениям идет, однако пока видеокарты устойчиво выигрывают в отношении производительность/стоимость и производительность/энергопотребление. хотя, конечно, это может зависеть от задачи, в частности задачи, которые вообще не параллелятся, а одно ядро CPU все-таки значительно мощнее ядра GPU.
несколько не понятно — а в чем проблема, если производится только чтение… или имелась в виду проблема с чтением/записью?
а вот переписать код, который работает в рамках классической модели на видеокарты — задача, которая автоматически (пока) не разрешима — другая модель, все-таки.
в задачах, которые мы решаем в основном очень большие объемы данных фигурируют, и единственная цель, написать их обработку, так чтобы время передачи на карточку было соизмеримо со временем работы алгоритма, так что конечно все эти 10-40 Гбайт/с больше, чем нужно. хотя многие алгоритмы работают в несколько проходов — там это важно.
Про именно вычислительные задачи напишу потом, однако там не все так радужно.