Сегментация 4D данных на GPU
Проблема, с которой я сталкиваюсь, заключается в сегментировании больших наборов данных (до 2048x2048x40x10000 x,y,z,t == несколько терабайт распаковано, отдано или взято). С другой стороны, функции в этом наборе данных довольно малы; Макс 20x20x20x20 или около того.
Насколько я вижу, для этого нет готовых решений (поправьте меня, если я не прав). У меня есть несколько планов, как решить эту проблему, но я хотел бы получить ваши отзывы.
Один временной интервал составляет ~600 МБ максимум; меньше при типичных обстоятельствах; Я могу хранить кучу таких последовательных фрагментов в моей памяти 4 ГБ.
Учитывая небольшой размер моих функций, моя интуиция говорит, что лучше отказаться от всех форм ловкости сегментации и просто выполнить локальное итеративное обновление, похожее на заливку, над моими метками; если у вашего соседа более высокая метка, скопируйте его; итерации до сходимости. Количество итераций должно быть ограничено максимальным размером кластера в любом измерении, которое, опять же, должно быть небольшим.
CUDA имеет естественное предпочтение 3D, поэтому я мог бы сделать это как двухэтапный процесс; итерируйте все срезы 3d-тома, которые еще не сходятся. затем просто выполните поэлементный цикл по всем последовательным временным интервалам и выполните ту же логику заполнения.
Я мог бы инициализировать итерацию с помощью простого увеличивающегося уникального счетчика или сначала найти локальные максимумы и посеять метки там. Последнее должно быть предпочтительным, поэтому я могу сохранить индекс по метке для хранения минимального / максимального экстента всех областей по x, y, z, t (это можно сделать и в качестве постобработки). Если область не распространяется на последний временной интервал, он удаляется из данных, а его местоположение записывается в базу данных. Если конечный временной интервал был полностью обработан таким образом (сумма равна нулю), удалите его из памяти. (или, если память переполнена, отбросьте также последнюю версию; с таким приближением придется мириться)
Кажется, что это должно работать. Учитывая ограниченный размер z-измерения, думаете ли вы, что лучше запускать блоки потоков x, y, z или запускать блоки x, y и позволить каждому потоку проходить по циклу z? Это что-то типа "попробуй и посмотри", или есть ответ на этот вопрос?
Еще одна оптимизация, которая только что пришла мне в голову; если я загружу блок x, y, z в разделяемую память, не будет ли быстрее выполнить несколько обновлений залива, если у меня там все равно есть память? Возможно, даже лучше всего позволить локальной памяти итерироваться, а затем двигаться дальше... это связано с вышеупомянутой проблемой, я полагаю. поиск по максимуму одного соседа, вероятно, является субоптимальной интенсивностью вычислений, поэтому либо циклическая обработка по z, либо итерация несколько раз должны компенсировать это. Я думаю, что мне нравится последний лучше.
Другой вопрос; не похоже, что что-то подобное уже существует, но ссылки на проекты, содержащие шаблонный код, который делает подобные вещи, были бы высоко оценены (оптимизированный код 3D-заливки?), так как мои знания CUDA все еще не точны.
Заранее спасибо за ваши мысли и отзывы!
3 ответа
Для записи; у меня есть рабочее решение, которым я доволен; может выложить его где-нибудь в Интернете, когда он станет более зрелым. Вот описание:
Что я делаю сейчас:
- Найти максимумы.
- Маркируйте максимумы постепенно, используя атомику
- Создать изображение-указатель, где каждый пиксель указывает на себя
- Floodfill на изображении указателя: если сосед указывает на большее значение, скопируйте его указатель
Это дает изображение указателя с водоразделом, причем каждый указатель указывает на уникальную метку.
Затем я делаю шаг слияния; если соседние пиксели указывают на другую метку, и их значение превышает пороговое значение, я объединяю их метки, так что максимумы, которые "достаточно связаны", не образуют свою собственную область.
Затем я разыменую указатели, и у меня есть хорошее изображение метки. Поскольку я высевал метки только на максимумах, максимальная метка - это небольшое число; Я выделяю массив 6xN такого размера и использую атомарные вычисления для вычисления минимальных / максимальных экстентов каждой функции.
На данный момент не используется общая память, но это уже довольно быстро. Я случайно закончил тем, что делал полуумные вещи; Так как я сначала делаю водораздел, а затем объединяю соседние водораспределенные регионы, используя один разметку, я эффективно выполняю многоуровневый алгоритм. В производительности преобладает этот набор вызовов для заливки, а также два или три слияния. Правильное использование совместно используемой памяти может снизить требования к пропускной способности моей памяти в 5 раз, но я не буду ждать, пока она явно не проявится как узкое место. Я уже получаю сегментацию, которая больше похожа на то, что я хочу, чем то, что я мог бы извлечь из scipy, она быстрее и использует на порядок меньше памяти, поэтому я счастлив на данный момент.
Я бы предложил схему пирамидальной обработки: вы можете быстро вычислить уровни детализации в виде mipmap, где вы сохраняете максимальное / минимальное значение объединенных вокселей. Это должно привести к чему-то похожему на октри. Тогда вы сможете начать свою сегментацию только по интересующим областям, что может значительно ускорить процесс. Это должно работать очень хорошо, если у вас есть только несколько очень маленьких сегментов.
Я думаю, вы могли бы также использовать наборы уровней (которые могут быть реализованы на графическом процессоре), но я считаю, что это немного сложнее реализовать (Google для "Набор уровней CUDA").
Вы должны отслеживать свои сегменты с течением времени? У вас есть идеи, как это сделать?
Самый простой способ - использовать хранилище 1D и наложить поверх него схему индекса 4D.
адрес = x + y * ширина + z * высота * ширина + t * длина * высота * ширина;
Это означает, что
Данные ( 0,0, 0, 0) и данные ( 1, 0, 0, 0) находятся по последовательным адресам, но
Данные ( 0,0, 0, 0) и данные ( 0,0, 0, 1) - это ширина * высота * длина адреса части.
Но если ваш шаблон доступа обрабатывает ближайших соседей, вам нужна пространственная локальность для индексации.
Это может быть достигнуто с помощью Morton Z (Peano Key) упорядочения индексов. Он размещает ближайших соседей в тесные линейные адреса памяти. Этот линейный адрес Z-порядка получается путем перемежения чередующихся битов индексов x,y,z,t. Для 2D-примера см.