Вопрос или проблема
У меня есть код для транспонирования матрицы, который выглядит так:
for (size_t ii = 0; ii < ii_end; ii+=TILE_SIZE) {
for (size_t jj = 0; jj < jj_end; jj+=TILE_SIZE) {
for (size_t i = 0; i < TILE_SIZE; i++) {
for (size_t j = 0; j < TILE_SIZE; j++) {
out[(jj + j)* n + ii + i] = in[(ii + i) * n + jj + j];
}
}
}
}
Это версия с плиткой, где указатель in последовательно считывает данные из памяти, а указатель out записывает их с пропуском.
Вторая версия того же алгоритма работает наоборот: out последовательно записывает в память, а in считывает с пропуском. Она выглядит так:
for (size_t ii = 0; ii < ii_end; ii+=TILE_SIZE) {
for (size_t jj = 0; jj < jj_end; jj+=TILE_SIZE) {
for (size_t i = 0; i < TILE_SIZE; i++) {
for (size_t j = 0; j < TILE_SIZE; j++) {
out[(ii + i)* n + jj + j] = in[(jj + j) * n + ii + i];
}
}
}
}
Вторая версия всегда быстрее для всех размеров матриц (я тестировал размеры 20, 50, 100, 200, 500, 1000, 2000 и 5000). Обе версии выполняют похожее количество инструкций. Я также измерял общий объем данных в памяти (чтения и записи) с помощью LIKWID, и первая версия передает немного меньше данных из памяти в ЦП.
Ускорение, как правило, больше для больших матриц. Я не понимаю, что происходит. Я бы предположил, что оборудование выполняет какой-то вид комбинирования записи, но я ожидал бы, что общий объем данных для второй версии будет значительно ниже — потому что она модифицирует целые кэш-строки.
Я работаю на ноутбуке Intel(R) Core(TM) i5-10210U. LIKWID использует счетчики событий DRAM_READS и DRAM_WRITES для расчета общего объема памяти.
Буду благодарен за любую информацию. Также, если вы можете указать мне ресурсы о технологиях оптимизации в подсистемах памяти современных процессоров, я буду очень признателен.
Ответ или решение
Почему последовательные чтения быстрее последовательных записей
Введение
В условиях работы с алгоритмами обработки данных, таких как транспонирование матриц, важно учитывать не только сложность алгоритма, но и то, как именно организована память и взаимодействие процессора с ней. В вашем случае, присутствует явное различие в производительности двух подходов: один выполняет последовательные чтения и неравномерные записи, а другой — наоборот. Это поведение может быть объяснено несколькими ключевыми аспектами архитектуры современных процессоров и систем памяти.
Архитектура кеша
Современные процессоры имеют несколько уровней кеша (L1, L2, L3), которые значительно уменьшают время доступа к данным. Кеширование работает таким образом, что данные, которые недавно были использованы, будут изолированы в быстрое хранилище рядом с процессором. Когда происходит чтение данных, кеш контролирует, есть ли данные уже в нем. Если они находятся в кеше, чтение будет происходить почти мгновенно, следовательно, производительность возрастает.
Однако, для записей, даже если кеш оптимизирован для увеличение скорости, процессоры могут использовать технику, называемую write-back, чтобы подождать с записью данных обратно в основную память. Если записи происходят не последовательно, существует вероятность того, что кэш-ячейки могут быть неэффективно использованы, в то время как чтения, производимые последовательно, более вероятно будут эффективны благодаря другому алгоритму работы кеша.
Принципы работы с памятью
При выполнении первой версии вашего алгоритма, где данные читаются последовательно, а записи имеют стрельчатый характер, происходит большее количество конфликтов кеша (cache thrashing). Это объясняется тем, что высоко вероятно, что операции записи могут затруднять операции чтения из-за высоких временных затрат на кэширование и обновление кеша.
Во второй версии, где происходит последовательная запись, данные эффективно упаковываются в кеш и сразу же записываются в основную память. Это создает больше возможностей для write combining, когда несколько данных могут быть объединены в один кеш-линию, позволяя процессору экономить время на взаимодействии с памятью.
Проблемы производительности
Вы упоминаете, что объем передаваемых данных в первой версии немного меньше, но это не является единственным фактором, определяющим производительность. Кроме объема передаваемых данных, стоит обращать внимание на следующие аспекты:
- Латентность доступа к памяти: последовательные чтения могут обрабатывать данные быстрее, потому что они могут значительно снизить число обращений к основной памяти.
- Параллелизм операций: при записи данных в потоках, которые не перекрываются, происходит блокировка, что увеличивает общее время выполнения.
- Кэширование: фрагментированная запоминаемость при записи влияет на скорость, в отличие от последовательного чтения, которое более эффективно использует кеш.
Заключение
В итоге, в современных процессорах выполнение последовательных операций чтения более эффективно, чем записи, из-за различий в управлении кэшем, взаимодействиями с памятью, а также способами обработки данных. Если вы хотите углубить свои знания в области оптимизации систем памяти и архитектуры процессоров, рекомендую ознакомиться с такими ресурсами, как:
- Intel Software Developer’s Guide
- Computer Architecture: A Quantitative Approach от Hennessy и Patterson
- High-Performance Memory Systems от Vassiliadis и других
Эти источники помогут лучше понять механизмы, стоящие за эффективностью работы с памятью и архитектурой вычислительных систем.