|
Работа с матрицей
|
|||
---|---|---|---|
#18+
Надо только заменить три нижних строки на: Код: plaintext 1. 2. 3. 4.
:) ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 16:24 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
rdb_dev, дело не только в регистрах. Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута Тогда модели памяти не предусматривали понятия "пропуск кеша". на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша на каждой следующей операции. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 17:15 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
booby rdb_dev, дело не только в регистрах. Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута Тогда модели памяти не предусматривали понятия "пропуск кеша". на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша на каждой следующей операции. Кстати да! Мой алгоритм тоже этим грешит. Сейчас перепишу. Точнее ещё один даимонд_н создам. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 17:25 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
boobyДвигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х Зато ничто не мешает двигаться навстречу друг другу с разных сторон матрицы по вертикали. На больших размерах каждая строка всё равно в линию не влезет. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 17:44 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
Ромбик - симметричен. И для мультипоточки к примеру гораздо оптимальнее заранее сделать некую декомпозицию или некий план разбиения tasks на суб-таски (по аналогии с ForkJoinPool) и работать сверху вниз везде. Да учитывая свойсвта ромбика можно предположить что у него серединка - мясная и там цикл будет чуть дольше считать если делать не 2 а 4 потока к примеру. Я исхожу из предпложения что каждый поток обрабатывает "трапецию". ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 17:54 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
вот еще немного потока сознания, навеянного алгоритмами инвертирования массива. Пусть задача не сумму получить, а инвертировать "очень большой" массив. Пропуск кеша неизбежен, но хочется его как-то компенсировать/минимизировать. Тогда инвертируют блоками (включая векторизацию). То есть, текущие края копируются в малые буферы, взаимно инвертируется содержание буферов, а затем каждый из буферов копируется целиком блоком на свое место. Когда в качестве буферов используются векторные регистры, векторизация получается сама-сама. Эту идею можно приспособить для данной задачи, если уж именно с двух сторон складывать. Можно и к одностороннему проходу пришить, с оговоркой на то, что нечетность задачи требует к себе уважения, и, может быть, заведенияе отдельного указателя на левый или правый нечетный элемент, с последующим самостоятельным сложением, а сам буфер сложения (четный) можно и скользящим окном видеть для зоны сложения, с обработкой правого края начале/конце траектории движения. Мне кажется какого-то такого рода ходы могли бы проверяться... ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 18:00 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
booby rdb_dev, дело не только в регистрах. Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута Тогда модели памяти не предусматривали понятия "пропуск кеша". на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша на каждой следующей операции. Я доработал свой алгоритм учитывая ваши замечания. Ожидаемо на больших матрицах выигрыш в примерно 1.4 раза, на маленьких проигрыш в 1.3. Привожу оба. summ_diamond_1() и summ_diamond_1a(). Кажется второй не очень написан, но лень думать, в индексах запутался. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44.
... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 18:08 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
petrav Кстати да! Мой алгоритм тоже этим грешит. Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 18:08 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
rdb_dev petrav Кстати да! Мой алгоритм тоже этим грешит. Строки вперёд, а столбцы на встречу. Первый алгоритм summ_diamond_1(). rdb_dev Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит. А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 18:19 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
petrav А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад. Я предлагаю краш-тест. Выдели 2Гига. И просто прочитай их спереди-назад. А потом сзаду-наперед. Ясно что здесь кеш-линия уже особ роли играть не будет. Но возможно мы не просекли еще какие-то эффекти оптимизаций? ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 18:40 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
Я наверное register с вашего позволения уберу. Код: plaintext 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 19:48 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
А есть здесь что-то специфичное, чего не знает gcc-4.6.3 (из сборки Rtools version 2.15.0.1919 для х32)? или специфичное для х64 (вместо х32) ? rdb_dev Benchmark Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.
error: expected initializer before 'noexcept' и далее очень много разных error: attribute(target("default")) is unknown error: attribute(target("default")) is unknown ..... ... |
|||
:
Нравится:
Не нравится:
|
|||
28.05.2020, 19:51 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
exp98, ещё более старый GNUC найти не получилось? Так-то уже версия 10+ :) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.05.2020, 00:54 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
petrav А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.05.2020, 09:08 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
exp98 А то gcc ругается и сразу на шаблон void volatilize(T &r) noexcept ... error: expected initializer before 'noexcept' и далее очень много разных error: attribute(target("default")) is unknown error: attribute(target("default")) is unknown ..... Выкиньте __target__("default")! В чём проблема? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.05.2020, 09:17 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
petrav Я доработал свой алгоритм учитывая ваши замечания. Ожидаемо на больших матрицах выигрыш в примерно 1.4 раза, на маленьких проигрыш в 1.3. Привожу оба. summ_diamond_1() и summ_diamond_1a(). Кажется второй не очень написан, но лень думать, в индексах запутался. На матрице 128x128 результат одного прогона очень нестабилен. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
против Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.05.2020, 09:53 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
rdb_dev petrav А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад. Да, вы правы. Я написал третью версию своего алгоритма summ_diamond_1b(). Только движение вперёд, никаких скачков вперёд-назад по столбцам. На больших матрицах она самая быстрая из моих алгоритмов. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.05.2020, 13:18 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
В общем убрал я всю ерундистику, что выше Сpp2003. Правда и с замерами возиться не стал, использовал обычный Clock() и без потоков. Да тут и отладчика нету. Ну да, фоновыые процессы есть и отнимают ~4% времени неизвестно в какие моменты. Компик 32x, 1 ядро, 1.6Ггц, винд-7, памяти 2 Г, но под задачку оставалось около 260 М. Конкретно для матрицы 11К*11К-1 все три диамонда около 750мс. И матрица int32. Для размерости 12К*12К-1 не дождался ответа. Возможно не хватило памяти. Если интересны замеры для мелких матриц на медленном компе, приложу позднее. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.05.2020, 23:44 |
|
Работа с матрицей
|
|||
---|---|---|---|
#18+
exp98, мой бенчмарк годится только для более-менее современных процессоров с ядром Nehalem и выше, так как в более ранних ядрах TimeStampCounter тикал по частоте процессора, которая могла меняться по Intel SpeedStep. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.06.2020, 12:48 |
|
|
start [/forum/topic.php?fid=57&gotonew=1&tid=2017415]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
46ms |
get topic data: |
12ms |
get first new msg: |
10ms |
get forum data: |
3ms |
get page messages: |
63ms |
get tp. blocked users: |
1ms |
others: | 11ms |
total: | 177ms |
0 / 0 |