Сообщение Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад от 13.01.2021 1:19
Изменено 13.01.2021 2:08 xma
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад
Здравствуйте, watchmaker, Вы писали:
W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.
а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..
при n = 1000, sum1 более чем на четверть быстрее sum0
W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно
да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицнй) в 12 раз над sum0, (код выше) ..
при n=3000, sum0 — не дождался
P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..
W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.
при n = 1000, sum1 более чем на четверть быстрее sum0
Скрытый текст | |
| |
W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно
да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицнй) в 12 раз над sum0, (код выше) ..
при n=3000, sum0 — не дождался
P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиад
Здравствуйте, watchmaker, Вы писали:
W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.
а ты профи, не ожидал — что sum1 в 15 раз медленнее sum0 при n=3000 ..
при n = 1000, sum1 более чем на четверть быстрее sum0
W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно
да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицей) в 12 раз над sum0, (код выше) ..
при n=3000, sum0 — не дождался
P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..
W>Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
W>В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.
при n = 1000, sum1 более чем на четверть быстрее sum0
Скрытый текст | |
| |
W>Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
W>Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно
да, при n = 1000, ускорение в sum0_v2 (с транспонированной матрицей) в 12 раз над sum0, (код выше) ..
при n=3000, sum0 — не дождался
P.S.: если в MVS хотите запускать код — не забудьте стэк до гигабайта увеличить ..