ReSQL.ru
     
powered by simpleCommunicator - 2.0.28     © 2024 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Map
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Ускорить умножение квадратных матриц (продолжение темы с mutex)
25 сообщений из 165, страница 2 из 7
  2  все
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107506
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
бабушкин зайчикТак ты никуда не деваешь многопоточку. Один запрос пишет в контейнер, а
второй/третий/десятый запрос из него читает.

Зачем? Контейнер тут не нужен. Паттерн Producer-consumer делается на очереди со
строго очерёдным доступом к ней ровно на операцию добавления/выборки элемента,
которая размером в пару ассемблерных команд. Мутекс и эвент - более чем достаточно:
Код: sql
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.
void Queue::push(Request* item)
{
     item->next = nullptr;

     { // Scope of critical section
         CriticalSectionGuard lock(guard);

         if (head == nullptr) // tail == NULL is assumed as well
         {
             // This queue is empty
             head = item;
         }
         else
         {
             tail->next = item;
         }
         tail = item;
     }
     SetEvent(semaphore);
}

Request* Queue::pop(int timeout)
{
     do
     { // Scope
         CriticalSectionGuard lock(guard);
         Request* Result = head;
         if (Result != nullptr)
         {
             head = Result->next;
             if (tail == Result || head == nullptr) // Duplicate condition for 
bugs tolerancy
             {
                 tail = nullptr;
             }
             return Result;
         }
     }
     while (wait(timeout));
     return nullptr;
}



бабушкин зайчикКакие другие задачи?
Ты не поверишь, но настоящие приложения делают гораздо больше вещей
одновременно, чем это делает студенческая лаба. Один поток принимает пакеты из
сети, у него свои объекты, к которым больше никто не лезет. Пачка потоков
обрабатывает принятые первым запросы, выбирая их из вышеописанной очереди и у
каждого из них свои личные объекты, нужные им для работы. Ещё один-два потока
осуществляют фоновую работу по расписанию и они опять же замкнуты в себе. Число
объектов с общим доступом минимально и разводить их читателей с писателями не
имеет смысла, простого мутекса хватает.

бабушкин зайчикесли это mutex-блокировка, почему так и не назвать?

Потому что термин "mutex-блокировка" был выдуман тобой и никто больше его не
знает. Зато многие в курсе TIL "serializable", который был назван как раз в
честь сериализации доступа к данным.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.10.2021, 18:04
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107507
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
mayton
Concurrency - плохо.
+1
...
Рейтинг: 0 / 0
27.10.2021, 18:04
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107508
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
mayton, т.е. предлагаешь разбить контейнер на X контейнеров, и с каждым работать отдельным потоком?
А куда и как их мержить потом - не понял? В каждом запросе чтоли?
...
Рейтинг: 0 / 0
27.10.2021, 18:06
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107509
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
бабушкин зайчик
mayton, т.е. предлагаешь разбить контейнер на X контейнеров, и с каждым работать отдельным потоком?
А куда и как их мержить потом - не понял? В каждом запросе чтоли?

Ну смотри. Если у тебя контейнер содержит финансовую величину. Объем выручки за день.

А все потоки - считают кассовую ленту за день. То зачем тебе конкурировать в рил-тайме
когда можно спокойно в каждом потоке посчитать свой кассовый аппарат а потом просуммировать итог.

Я просто сумму в качестве примера привел. Разумеется пример с кассой - тоже сферический.
...
Рейтинг: 0 / 0
27.10.2021, 18:09
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107511
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
mayton,
Конечно.
Можно на стол поставить один казанок на семью. А можно каждому по тарелке.
...
Рейтинг: 0 / 0
27.10.2021, 18:11
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107521
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
Dimitry Sibiryakov
Зачем? Контейнер тут не нужен. Паттерн Producer-consumer делается на очереди со строго очерёдным доступом к ней ровно на операцию добавления/выборки элемента, которая размером в пару ассемблерных команд.

Затем, что элементы в контейнере находятся.
Producer/Consumer отправляет объект в специальную коллекцию, которая основана на BlockingQueue.
А потом раздаёт их желающим...
Ну и как туда заслать ячейки из контейнера? Да так, чтобы в них ничего не записало параллельно?
Ежели туда слать ссылку на весь контейнер, то это тоже не решает проблему чтения ячейки во время записи.

Dimitry Sibiryakov
Потому что термин "mutex-блокировка" был выдуман тобой и никто больше его не знает. Зато многие в курсе TIL "serializable", который был назван как раз в честь сериализации доступа к данным.

Любому скажи mutex и он поймёт, что речь о блокировках. Не надо ля-ля.
А вот то что ты "блокировку записи во время чтения" не можешь "уровнем изоляции" назвать - это проблема.
Да они вообще из БД, зачем они тут, где mutex обсуждают?!

Dimitry Sibiryakov
Число объектов с общим доступом минимально и разводить их читателей с писателями не имеет смысла, простого мутекса хватает.

т.е. всё-таки 1 поток = 1 контейнер
и на каждую операцию r/w блокировка??

Dimitry Sibiryakov
Ты не поверишь, но настоящие приложения делают гораздо больше вещей
одновременно, чем это делает студенческая лаба

тебе 40 то есть?
...
Рейтинг: 0 / 0
27.10.2021, 18:55
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107525
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
mayton
бабушкин зайчик
mayton, т.е. предлагаешь разбить контейнер на X контейнеров, и с каждым работать отдельным потоком?
А куда и как их мержить потом - не понял? В каждом запросе чтоли?

Ну смотри. Если у тебя контейнер содержит финансовую величину. Объем выручки за день.

А все потоки - считают кассовую ленту за день. То зачем тебе конкурировать в рил-тайме
когда можно спокойно в каждом потоке посчитать свой кассовый аппарат а потом просуммировать итог.

Я просто сумму в качестве примера привел. Разумеется пример с кассой - тоже сферический.

да это простейший пример, который пойди найди ещё в реальном мире
каждый кассовый аппарат живёт своей жизнью и никак не взаимодействует с другими
а вот контейнеры постоянно друг с другом пересекаются, и читать надо из разных, и писать надо в разные...
приходит запрос - прочитай отсюда и оттуда, запиши сюда и туда...
а потом ещё агрегировать данные из них в одном общем месте
...
Рейтинг: 0 / 0
27.10.2021, 18:59
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107528
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

а что просто, для начала, нормальный алгоритм не поискать?
...
Рейтинг: 0 / 0
27.10.2021, 19:05
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107531
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
бабушкин зайчик

а вот контейнеры постоянно друг с другом пересекаются, и читать надо из разных, и писать надо в разные...
приходит запрос - прочитай отсюда и оттуда, запиши сюда и туда...
а потом ещё агрегировать данные из них в одном общем месте

Вот капец я вообще не понимаю почему они обязательно пересекаются? Кто это решил?
...
Рейтинг: 0 / 0
27.10.2021, 19:13
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107533
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
бабушкин зайчик
т.е. всё-таки 1 поток = 1 контейнер
и на каждую операцию r/w блокировка??
а если пул потоков, то у тебя взрыв мозга будет?
...
Рейтинг: 0 / 0
27.10.2021, 19:20
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107535
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
бабушкин зайчик
контейнеры постоянно друг с другом пересекаются, и читать надо из разных, и писать надо в разные...
приходит запрос - прочитай отсюда и оттуда, запиши сюда и туда...
а потом ещё агрегировать данные из них в одном общем месте
СУБД пишем?
...
Рейтинг: 0 / 0
27.10.2021, 19:21
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107539
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mayton
Но какого размера брать слой?
Если можем "монополизировать" железо , то в размер кэша второго уровня. Который на ядро.
В современных условиях можно просто не выёживаться. Для начала.
А то получится как со скоростью xxhash, которая может превышать скорость чтения из памяти. Но там автор честно указывает, что "данные такого размера находятся в процессорном кэше".
...
Рейтинг: 0 / 0
27.10.2021, 19:46
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107543
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
mayton
бабушкин зайчик

а вот контейнеры постоянно друг с другом пересекаются, и читать надо из разных, и писать надо в разные...
приходит запрос - прочитай отсюда и оттуда, запиши сюда и туда...
а потом ещё агрегировать данные из них в одном общем месте

Вот капец я вообще не понимаю почему они обязательно пересекаются? Кто это решил?

ну на чтение они пересекаются, когда надо показать данные из разных контейнеров на одном экране, например

если прошла встреча с клиентом, то надо поставить отметку в контейнер встреч
затем поставить отметку в контейнер клиентов по итогу встречи
ещё поставить отметку в контейнер логов
т.е. они будут все заблокированы... А значит в агрегации данных кто-то будет ждать...
и в клиентах будут ждать, и в логах
...
Рейтинг: 0 / 0
27.10.2021, 20:04
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107545
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Встречи. Клиенты. Ты оперируешь временнЫми интервалами которые в миллион раз превышают
то что мы тут обсуждаем? Верно?
...
Рейтинг: 0 / 0
27.10.2021, 20:14
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107548
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
да это просто пример
контейнеров в разы больше, чем эти 3
а запросов может быть много
тысячи в секунду, десятки тысяч
и при этом, как я уже говорил, можно искусственно создать нагрузку на запись
...
Рейтинг: 0 / 0
27.10.2021, 20:19
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107549
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
бабушкин зайчикну на чтение они пересекаются, когда надо показать данные из разных контейнеров
на одном экране, например

Не надо. Контейнер для отображения на экране целиком и безраздельно принадлежит
потоку, обрабатывающему GUI и сообщения о том, что "прошла встреча" и
"выставлена оценка", которые, по его меркам, приходят в час по капле.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.10.2021, 20:23
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107559
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Подкину немножко. Для перемножения больших матриц по-хорошему надо использовать алгоритм Штрассена .
...
Рейтинг: 0 / 0
27.10.2021, 20:44
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107560
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру
с кешом.

Какие будут предложения?

Транспонировать Б и поменять местами X и Y при определении координат элемента.

PS Нас же не смущает что координаты точек экрана идут из верхнего левого угла вниз, а в алгебре/геометрии - вверх.
...
Рейтинг: 0 / 0
27.10.2021, 20:50
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107568
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T
mayton
Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру
с кешом.

Какие будут предложения?

Транспонировать Б и поменять местами X и Y при определении координат элемента.

PS Нас же не смущает что координаты точек экрана идут из верхнего левого угла вниз, а в алгебре/геометрии - вверх.

+1 да. Это первый шаг. Линеаризировать доступ.

И как справедливо заметил Василий... чортовы кеши. Надо укладывать хотя-бы 1 слой умножений в L2.
...
Рейтинг: 0 / 0
27.10.2021, 21:27
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107569
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот фрагмент спеки железа актуального на 2018 год (это мой AMD).

Код: plaintext
1.
2.
3.
4.
5.
6.
Thread(s) per core:	2
Core(s) per socket:	6
L1d cache:	32K
L1i cache:	64K
L2 cache:	512K
L3 cache:	8192K



512 килобайт L2 - это примерно соответсвует вектору double длиной 64 тыщи элементов. И еще надо заложить
минимум 3 слоя. А.B.C. Тоесть поделить на 3. Подровнять под кеш-линии и округлить правильно.
...
Рейтинг: 0 / 0
27.10.2021, 21:36
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107576
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

делали уже люди тынц
...
Рейтинг: 0 / 0
27.10.2021, 21:58
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107581
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

тут ещё вопрос,

стоит ли перебирать грубой силой грузить 30 ядер алгоритмом O(N^3)
или быстрее будет на одном проце посчитать O(N^log2(7))

как бы с ростом N непонятно кто выиграет
...
Рейтинг: 0 / 0
27.10.2021, 22:07
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107587
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это такая-себе софистическая задачка. Она идёт тестовым учебным примером в tutorials по OpenMP.
Ее также упоминает Грегори Эндрюс в своей книге по параллелизму.

Нужно ли выкинуть брутфорс и взять другой алгоритм? Я не знаю. Собсно матричное умножение это не основная
тема топика. Я просто хотел баб-зайчику показать как глубоко можно углубиться в задачу и где
параллелизм полезен и где лишняя коннкуренция вредна.

Я не против всяких Штрассенов. Просто это уже плоскость математики а я там не силён.
...
Рейтинг: 0 / 0
27.10.2021, 22:21
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107590
бабушкин зайчик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
бабушкин зайчик
Гость
хм, если у интелов кэш измеряется в мегабайтах, значит ли это, что они nodoubt лучше?
...
Рейтинг: 0 / 0
27.10.2021, 22:27
| Ответить | Цитировать | Написать  
Ускорить умножение квадратных матриц (продолжение темы с mutex)
    #40107594
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
PetroNotC Sharp
бабушкин зайчик
контейнеры постоянно друг с другом пересекаются, и читать надо из разных, и писать надо в разные...
приходит запрос - прочитай отсюда и оттуда, запиши сюда и туда...
а потом ещё агрегировать данные из них в одном общем месте
СУБД пишем?


такого сорта "субд" в конце 90х - середине 2000-х уже один раз не взлетели.
Пока не видно никаких причин, по которым они могли бы попытаться взлететь повторно.
Для этого есть существенное основание - субд вообще с другого конца начинаются.
Не только не с "контейнеров", но даже и не с "объектов", по крайней мере в оо-смысле.
...
Рейтинг: 0 / 0
27.10.2021, 22:37
| Ответить | Цитировать | Написать  
25 сообщений из 165, страница 2 из 7
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Ускорить умножение квадратных матриц (продолжение темы с mutex)
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
Start [/forum/topic.php?fid=57&msg=40107560&tid=2017148]:
 0ms
get settings:
 16ms
get forum list:
 9ms
check forum access:
 1ms
check topic access:
 1ms
track hit:
 50ms
get topic data:
 3ms
get forum data:
 1ms
get page messages:
 566ms
get tp. blocked users:
 0ms
others: 312ms
total:  959ms
созд. / загр.: 959ms
x
x
Закрыть


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