powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Работа с матрицей
19 сообщений из 169, страница 7 из 7
Работа с матрицей
    #39963460
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Надо только заменить три нижних строки на:
Код: plaintext
1.
2.
3.
4.
  const char *p_middle = (const char*)matrix + m * row_size;
  for (const char* p = p_middle; p < p_middle + row_size; p += element_size)
    sum += *(const T*)p;
  return sum;

:)
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963491
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rdb_dev,

дело не только в регистрах.
Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута
Тогда модели памяти не предусматривали понятия "пропуск кеша".
на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша
на каждой следующей операции.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963494
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
rdb_dev,

дело не только в регистрах.
Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута
Тогда модели памяти не предусматривали понятия "пропуск кеша".
на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша
на каждой следующей операции.

Кстати да! Мой алгоритм тоже этим грешит. Сейчас перепишу. Точнее ещё один даимонд_н создам.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963510
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
boobyДвигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х

Зато ничто не мешает двигаться навстречу друг другу с разных сторон матрицы по вертикали.
На больших размерах каждая строка всё равно в линию не влезет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963514
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ромбик - симметричен. И для мультипоточки к примеру гораздо оптимальнее заранее сделать некую
декомпозицию или некий план разбиения tasks на суб-таски (по аналогии с ForkJoinPool) и работать
сверху вниз везде. Да учитывая свойсвта ромбика можно предположить что у него серединка - мясная
и там цикл будет чуть дольше считать если делать не 2 а 4 потока к примеру.

Я исхожу из предпложения что каждый поток обрабатывает "трапецию".
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963520
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот еще немного потока сознания, навеянного алгоритмами инвертирования массива.

Пусть задача не сумму получить, а инвертировать "очень большой" массив.
Пропуск кеша неизбежен, но хочется его как-то компенсировать/минимизировать.
Тогда инвертируют блоками (включая векторизацию).
То есть, текущие края копируются в малые буферы, взаимно инвертируется содержание буферов,
а затем каждый из буферов копируется целиком блоком на свое место.
Когда в качестве буферов используются векторные регистры, векторизация получается сама-сама.

Эту идею можно приспособить для данной задачи, если уж именно с двух сторон складывать.
Можно и к одностороннему проходу пришить, с оговоркой на то, что нечетность задачи требует к себе уважения, и,
может быть, заведенияе отдельного указателя на левый или правый нечетный элемент,
с последующим самостоятельным сложением, а сам буфер сложения (четный) можно
и скользящим окном видеть для зоны сложения, с обработкой правого края начале/конце траектории движения.
Мне кажется какого-то такого рода ходы могли бы проверяться...
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963523
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
Type summ_diamond_1(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }

    for (size_t i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}

Type summ_diamond_1a(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
        }
    }

    for (size_t i=0; i<=Half; ++i)
    {
        size_t const ii = Size-i-1;
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[ii][j];
        }
    }

    return res;
}
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963524
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav
Кстати да! Мой алгоритм тоже этим грешит.
Нет, твой алгоритм обходит элементы строки вперёд. Это нормально! booby имел в виду мой первый алгоритм в один цикл, который я накидал только ради того, чтобы было в один цикл. :)

Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963530
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rdb_dev
petrav
Кстати да! Мой алгоритм тоже этим грешит.
Нет, твой алгоритм обходит элементы строки вперёд. Это нормально! booby имел в виду мой первый алгоритм в один цикл, который я накидал только ради того, чтобы было в один цикл. :)

Строки вперёд, а столбцы на встречу. Первый алгоритм summ_diamond_1().

rdb_dev
Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит.

А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963539
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.

Я предлагаю краш-тест. Выдели 2Гига.

И просто прочитай их спереди-назад. А потом сзаду-наперед. Ясно что здесь кеш-линия уже особ роли играть не будет.
Но возможно мы не просекли еще какие-то эффекти оптимизаций?
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963590
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я наверное register с вашего позволения уберу.

Код: plaintext
1.
'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963593
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А есть здесь что-то специфичное, чего не знает 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.
#include <windows.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#include <windows.h>

# ifndef __INLINE
#   ifdef __GNUC__
#     define __INLINE inline __attribute__((always_inline, __target__("default")))
#   endif
# endif
...
...
...
...

А то gcc ругается и сразу на шаблон void volatilize(T &r) noexcept ...
error: expected initializer before 'noexcept'
и далее очень много разных
error: attribute(target("default")) is unknown
error: attribute(target("default")) is unknown
.....
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963779
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, ещё более старый GNUC найти не получилось? Так-то уже версия 10+ :)
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963866
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
По всей видимости, при движении назад плохо работает предсказание чтения кэшлайнов, а 64 битный регистр приходится дважды прогружать значением, так как чтобы получить сначала старший DWORD, нужно сдвинуть всё содержимое влево на 32 бита, что приводит к потере содержимого младшего DWORD.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963869
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
А то gcc ругается и сразу на шаблон void volatilize(T &r) noexcept ...
error: expected initializer before 'noexcept'
и далее очень много разных
error: attribute(target("default")) is unknown
error: attribute(target("default")) is unknown
.....
По-моему, встретившись в исходниках со спецификатором noexcept , становиться совершенно очевидно, что компилировать эти исходники надо с опцией компилятора -std=c++11 .

Выкиньте __target__("default")! В чём проблема?
...
Рейтинг: 0 / 0
Работа с матрицей
    #39963876
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
TSC calibrating, please wait...
TSC ticks per nanosec: 2.993169

Size of matrix: 65536

diamond_ptr
===========
SUM: 68173888
Elapsed time(nsec): 9468.558974

summ_diamond_1
==============
SUM: 68173888
Elapsed time(nsec): 5334.479416

summ_diamond_1a
==============
SUM: 68165697
Elapsed time(nsec): 7664.451199

против

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
TSC calibrating, please wait...
TSC ticks per nanosec: 2.993187

Size of matrix: 65536

diamond_ptr
===========
SUM: 68173888
Elapsed time(nsec): 9606.482488

summ_diamond_1
==============
SUM: 68173888
Elapsed time(nsec): 7364.390814

summ_diamond_1a
==============
SUM: 68165697
Elapsed time(nsec): 8551.753921
...
Рейтинг: 0 / 0
Работа с матрицей
    #39964042
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rdb_dev
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
По всей видимости, при движении назад плохо работает предсказание чтения кэшлайнов, а 64 битный регистр приходится дважды прогружать значением, так как чтобы получить сначала старший DWORD, нужно сдвинуть всё содержимое влево на 32 бита, что приводит к потере содержимого младшего DWORD.

Да, вы правы. Я написал третью версию своего алгоритма 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.
Type summ_diamond_1b(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
        }
    }

    for (size_t i=0; i<=Half; ++i)
    {
        for (size_t j=i; j<=Size-i-1; ++j)
        {
            res += arr[i+Half][j];
        }
    }

    return res;
}
...
Рейтинг: 0 / 0
Работа с матрицей
    #39964544
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В общем убрал я всю ерундистику, что выше Сpp2003.
Правда и с замерами возиться не стал, использовал обычный Clock() и без потоков. Да тут и отладчика нету. Ну да, фоновыые процессы есть и отнимают ~4% времени неизвестно в какие моменты.

Компик 32x, 1 ядро, 1.6Ггц, винд-7, памяти 2 Г, но под задачку оставалось около 260 М.
Конкретно для матрицы 11К*11К-1 все три диамонда около 750мс. И матрица int32.
Для размерости 12К*12К-1 не дождался ответа. Возможно не хватило памяти.

Если интересны замеры для мелких матриц на медленном компе, приложу позднее.
...
Рейтинг: 0 / 0
Работа с матрицей
    #39964985
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, мой бенчмарк годится только для более-менее современных процессоров с ядром Nehalem и выше, так как в более ранних ядрах TimeStampCounter тикал по частоте процессора, которая могла меняться по Intel SpeedStep.
...
Рейтинг: 0 / 0
19 сообщений из 169, страница 7 из 7
Форумы / C++ [игнор отключен] [закрыт для гостей] / Работа с матрицей
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]