Самый эффективный способ работы с ОГРОМНОЙ двоичной матрицей?
У меня есть огромная двоичная матрица, как 100000 х 100000.
Читать эту статью http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf, Я, кажется, понял, что лучший компромисс для запоминания и работы с двоичной матрицей использует повышение :: dynamic_bitsets.
Так как в «Таблица 2: Относительная временная производительность программ, в которых реализованы структуры данных» :
станд :: вектор<BOOL> находится в последней позиции, в то время как повышение :: dynamic_bitset находится на первой позиции.
И в «Таблица 3: Относительное использование памяти программами, которые реализовали структуры данных»:
станд :: вектор<BOOL> находится на первой позиции, но повышение :: dynamic_bitset находится на второй позиции.
Кроме того, в статье, на странице 7, есть следующее
заявление:
«Несмотря на впечатляющую производительность памяти в std :: vector, его удручающая производительность делает его непригодным для использования в крупных приложениях».
И в выводах:
«Мы показали, что boost :: dynamic_bitset значительно более эффективен, чем большинство других реализаций, с точки зрения скорости выполнения, тогда как реализация использует std :: vector<голец> превзошел другие реализации с точки зрения эффективности памяти «.
Теперь в моем случае моя целевая машина XEON PHI.
Мое целевое приложение Игра жизни.
Я представил бинарную матрицу в виде двоичного массива ячеек ROWS x COLS.
Я пробовал код с 3-мя различными конфигурациями, выполняя их ICPC компилятор с -O3 флаг оптимизации:
- Массив логических значений
- Массив логических значений + векторизация, изменение кода с использованием Обозначение массива как описано Вот
-
повышение :: dynamic_bitsets. В этом случае я не мог изменить код, используя обозначение массива, поскольку при попытке получить следующую ошибку:
error: base of array section must be pointer or array typeта же ошибка при использовании станд :: вектор<BOOL>.
Глядя на производительность всего лишь одной итерации основного цикла игры для матрицы размером 100000 x 100000, я обнаружил, что: решение 2 работает почти в шесть раз быстрее, чем решение 1, но неожиданно решение 1 работает в два раза быстрее чем Решение 3.
В заключение у меня есть следующие вопросы:
- Какова в целом наиболее эффективная структура данных для хранения / работы с ОГРОМНАЯ МАТРИЦА ?
- Могу ли я сделать лучше, чем «ответ 1» зная, что моя целевая машина XEON PHI ?
- Можно ли применить векторизации в вектор<BOOL> или же повышение :: dynamic_bitsets ?
Спасибо за ответ о конкретном целевом приложении: Game Of Life.
Но как насчет работы с огромная двоичная матрица в другом контексте ?
Решение
если ты ДЕЙСТВИТЕЛЬНО заботясь о производительности в игре жизни Конвея, вы должны переключиться на чисто параллельный логический математический дизайн. Простая задача подсчета 8 соседей раздражающе сложна, как параллельная логическая операция, но стоит того. Только 64-канальный прямой параллелизм окупает кратные затраты по битам.
Возможно, на некоторых процессорах с одинаковым базовым дизайном возможен прямой параллелизм 128 бит или выше.
Как только вы используете 64-разрядные или большие целые числа вместо bool, все проблемы эффективного хранения bool становятся неактуальными.
Когда я делал это в ассемблере несколько десятилетий назад, я обнаружил, что одной важной оптимизацией является обмен информацией между последовательными строками. При этом стало проще смотреть на блок из девяти ячеек, а не восьми соседей. Таким образом, это может помочь понять, что правила могут быть совместимо пересчитаны:
Когда в наборе 9 есть 3, включается ячейка (была ли она раньше или нет).
Когда в его наборе 9 есть 4, ячейка остается неизменной.
В противном случае он выключается.
То, как информация распределялась по строкам, сильно зависело от языка asm и набора регистров этой машины десятилетия назад. Таким образом, вы можете или не можете найти, что полный 9 (а не 8 соседей) поможет вам.
Другие решения
Других решений пока нет …