Ускорить умножение квадратных матриц (продолжение темы с mutex) / C++

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / C++ [игнор отключен] [закрыт для гостей] / Ускорить умножение квадратных матриц (продолжение темы с mutex)

165 сообщений из 165, показаны все 7 страниц

все

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107415

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

(Форварднул с другого топика)

Давайте я предложу искусственную синтетическую постановку.

И вы увидете как ее невозможно просто сделать идеальной без цифр.

Даны две матрицы вещественных чисел. A и B. Одинаковой размерности. Их надо перемножить. По правилам
матриц. Тоесть первая стока матрицы A уможается почленно на столбец матрицы B. И вектор суммируется.
Результат записывается в элемент матрицы С. И так далее для всех комбинаций строки А и столбца B.

Шаблон кода на сях.

Код: plaintext

1.
2.
3.
4.
5.
6.

double *A = ....
double *B = ....

double *C; // result will be here

// multiply

Это - классика параллелизма. И ее часто приводят в качестве тестовой задачи чтобы показать как может
быть проста постановка и какая может быть сложная реализация если глубоко копнуть.

====

Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру
с кешом.

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

...

Рейтинг:

0 / 0

27.10.2021, 15:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107420

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dimitry Sibiryakov

maytonсамый первый камень - это как распараллелить.

Самый простейший путь - распределением столбцов B между потоками.

maytonОсобенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает
крайне неудачную игру с кешом.

Сделать алгоритм "кэш-дружелюбным" это отдельная задача, к многопоточности
отношения не имеющая. Решается предварительным транспонированием В.

...

Рейтинг:

0 / 0

27.10.2021, 15:23

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107422

indigodye0

Гость

Архитектура зеленых потоков

Каждая таска берет себе кусочек из каждой из матриц и бегает по матрице последовательно

Возможно потребуется транспонирование

...

Рейтинг:

0 / 0

27.10.2021, 15:24

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107424

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хорошая идея с транспонированием. Но с какого размера матриц? 10х10 надо транспонировать?

...

Рейтинг:

0 / 0

27.10.2021, 15:25

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107428

бабушкин зайчик

Гость

mayton

Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру с кешом.

смотрю ты тоже не фанат ставить задачу чётко и ясно
что значит "неблагоприятным образом"?
а "неудачная игра с кешом" - какие предпосылки?

Я предлагал изолировать матрицы A и B (если в них могут писать), путём копирования их внутрь перемножающей ф-и, которая возвращает C.
Это должно быть быстрее (и надёжнее), чем блокировать/разблокировать каждый столб/строку в живой матрице (либо обе матрицы целиком), куда могут записать в соседний столб, а потом записать в посчитанный столб...

...

Рейтинг:

0 / 0

27.10.2021, 15:28

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107431

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Правда не понимаешь? Ну вот в цикле обхода матрицы B мы несколько раз обходим ее "по столбцам".
Матрица - любого размера. Может быть 100х100. 1000х1000. Неважно.

...

Рейтинг:

0 / 0

27.10.2021, 15:34

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107433

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

mayton10х10 надо транспонировать?

10x10 не надо даже распараллеливать. И 100х100 тоже не надо.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

27.10.2021, 15:38

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107434

indigodye0

Гость

Dimitry Sibiryakov

mayton10х10 надо транспонировать?

10x10 не надо даже распараллеливать. И 100х100 тоже не надо.

+1

...

Рейтинг:

0 / 0

27.10.2021, 15:39

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107435

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

А когда надо?

...

Рейтинг:

0 / 0

27.10.2021, 15:41

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107437

бабушкин зайчик

Гость

mayton

понятно, что любого размера. Но легче от этого не станет, если ты её всю заблокируешь на время перемножения. Она просто будет дольше ни для кого недоступна.

А насчёт "несколько раз" - возможно есть смысл все столбы сложить в один контейнер - последовательно, а строки - в другой.
Поскольку известен размер столба, это не будет проблемой.
Я не занимался матрицами, как-то не приходилось, так - мысли вслух...

...

Рейтинг:

0 / 0

27.10.2021, 15:42

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107439

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton,

вот аналогичная задача с исходниками и тестами
https://habr.com/ru/post/508004/

...

Рейтинг:

0 / 0

27.10.2021, 15:43

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107442

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

maytonА когда надо?

Когда скорости однопоточного перемножения реально не хватает.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

27.10.2021, 15:49

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107446

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Спасибо. Данный пост является просто примером к родительскому топику. Примером того что
мы не сможем обсудить сферический лок в вакууме без дополнительных сведений. Быть может
без примера того как много потоков будут хотеть получить этот лок. И без описания типичного
железа. Что это? Серверный Xeon с 4-головами и 24 тредами? Или просто ней-то ноутбучик?

И без понимания полезной работы мы тоже не придумаем ничего. Вот если-бы зайчик
сказал что в каждом контейнере лежит например счетчик. Или JSon документ. Или матрица
чисел и мы что-то с ней будем делать - вот тогда и пойдут более полезные предложения.

...

Рейтинг:

0 / 0

27.10.2021, 15:52

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107455

бабушкин зайчик

Гость

mayton

И без понимания полезной работы мы тоже не придумаем ничего. Вот если-бы зайчик
сказал что в каждом контейнере лежит например счетчик. Или JSon документ. Или матрица чисел и мы что-то с ней будем делать - вот тогда и пойдут более полезные предложения.

да говорил я, что что угодно может лежать - от int, до string
соот-но, есть контейнеры с цифрами, есть с документами (строками), есть и матрицы, и что угодно
но достаточно хотя бы цифры и строки рассмотреть

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

...

Рейтинг:

0 / 0

27.10.2021, 16:10

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107460

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикНа самом деле сабж уже перерос в более глобальную проблему - как вообще закрыть
вопрос о многопоточной конкурентной работе с контейнерами?

Лучший способ - полным её избеганием.
Простейший способ - полной её сериализацией.

Остальные способы - только если эти два обломались по каким-то причинам.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

27.10.2021, 16:14

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107461

бабушкин зайчик

Гость

Dimitry Sibiryakov

бабушкин зайчикНа самом деле сабж уже перерос в более глобальную проблему - как вообще закрыть
вопрос о многопоточной конкурентной работе с контейнерами?

Лучший способ - полным её избеганием.
однопоточно?

Dimitry Sibiryakov

Простейший способ - полной её сериализацией.

авторСериализация (в программировании) — процесс перевода структуры данных в последовательность байтов.
а это как тут применить?

...

Рейтинг:

0 / 0

27.10.2021, 16:16

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107463

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикоднопоточно?

Да. Другие потоки могут заниматься совсем другими задачами.

бабушкин зайчика это как тут применить?

Никак. Гугли другие значения этого слова. Похожие на "строгая очерёдность".
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

27.10.2021, 16:18

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107470

ну я

Участник

Откуда: Москва

Сообщения: 1 270

Рейтинг: 0 / 0

mayton,
1) i-я колонка матрицы C зависит от всей матрицы A и от i-й колонки матрицы B. Как бы если бы матрица A состояла из столбцов, каждый есть результат умножения матрицы на столбец.
Сколько есть потоков (n), столько и считают каждый свою колонку, после чего берут колонку на n больше если она есть и так далее.

2) i-я строка матрицы C зависит от i-й строки матрицы A и от всей матрицы B. Как если бы матрица A состояла из строк, каждая есть результат умножения строки на матрицу. Далее с потоками по аналогии.

С распараллеливанием-то просто, вопрос с кешированием матрицы. Скорее всего лучше отдать предпочтение строчному варианту.
В обоих случаях надо дергать какую-то одну из матриц целиком, но во втором случае можем отрабатывать построчно хотя бы матрицы C и A.

...

Рейтинг:

0 / 0

27.10.2021, 16:44

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107471

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Мы можем множить матрицы "слоями". Это естественным образом вытекает из самой формулы умножения.
Но какого размера брать слой?

...

Рейтинг:

0 / 0

27.10.2021, 16:47

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107478

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

mayton

да говорил я, что что угодно может лежать - от int, до string

Давай еще поговорим про жесткий синхронизм и спрведливость доступа.
Допустим внутри контейнера лежит string в котором - XML документ.
И работают с ним 10 Threads. Они - периодически захватывают контейнер
и что-то добавляют в документ. Возможно - обновляют.

Поскольку операция работы с XML-документом сложная и комплексная - его надо
парсить и сериализовать - то я вангую что время работы с документом будет порядка
нескольких милисекунд. Например 20 мс.

За эти 20 мс прочие 9 потоков могут встать в ожидание. Актуальный вопрос - кто первый получит
доступ? Технически - любой. Это не зависит от того кто кто раньше встал в монитор. Грубо говоря
у данного mutex нет fairness. Это ставит от меня следующий вопрос.

Мы в задании заявили строгую синхронность. Это - правда. By design. Но вот в чем штука.
Зачем нам требования строгой синхронности если у нас все равно нет справедливости в дележе
этого контейнера.

Это вопрос - более философский чем технический.

...

Рейтинг:

0 / 0

27.10.2021, 17:02

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107479

booby

Участник

Сообщения: 2 667

Рейтинг: 1 / 0

mayton,

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

В таком взгляде ответ на вопрос "когда пришла пора параллелить", вероятно, может звучать так:
не раньше чем появился смысл в переходе к поблочному умножению

...

Рейтинг:

0 / 0

27.10.2021, 17:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107482

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dimitry Sibiryakov

Да. Другие потоки могут заниматься совсем другими задачами.

+1
Параллелить нужно не доступ к одному ресурсу. А множить единицы работы.
А чтобы кинуть 500 землекопов на одну яму много ума не надо.

...

Рейтинг:

0 / 0

27.10.2021, 17:15

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107487

бабушкин зайчик

Гость

Dimitry Sibiryakov

бабушкин зайчикоднопоточно?

Да. Другие потоки могут заниматься совсем другими задачами.
Так ты никуда не деваешь многопоточку. Один запрос пишет в контейнер, а второй/третий/десятый запрос из него читает.
Какие другие задачи? Всё по-честному - 2 разных задачи.
Получается нужна блокировка. И где тут однопоточка?

"Множить единицы задач" - КАК, когда речь о контейнерах? Выдать одному потоку 1 контейнер?

Dimitry Sibiryakov

бабушкин зайчика это как тут применить?

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

...

Рейтинг:

0 / 0

27.10.2021, 17:33

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107498

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Есть concurrency. И есть параллелизм . Вот задача умножения матриц - это про параллелизм.
Это - хоршо. Это - good. А задача где много потоков сталкиваются в попытке обновить 1 поле
- это concurrency.

Concurrency - плохо. От нее избавляются обычно. Как? Пересмотром постановки задачи обычно.
Просто если мы уже докатились до ситуации что 10 или 100 потоков обновляют текстовое поле - что-то
у нас уже не в порядке. Поэтому я вот сопротивляюсь самой изначальной идее. Я ищу причины.

В том примере что я привел. У нес есть 10 потоков и некий кумулятивный документ в контейнере мютекса. Если логика позволяет
то мы должны были создать 10 потоков и 10 локальных документов. А по завершению работы всех - спокойно
смёржить все 10 документов в 1. Разумеется если логика позволяет.

...

Рейтинг:

0 / 0

27.10.2021, 17:56

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107505

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

"Множить единицы задач" - КАК, когда речь о контейнерах? Выдать одному потоку 1 контейнер?

неужели в ВУЗЕ не учат словам
Ресурс и Работа?

...

Рейтинг:

0 / 0

27.10.2021, 18:03

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107506

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикТак ты никуда не деваешь многопоточку. Один запрос пишет в контейнер, а
второй/третий/десятый запрос из него читает.

Зачем? Контейнер тут не нужен. Паттерн 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

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

mayton

Concurrency - плохо.

...

Рейтинг:

0 / 0

27.10.2021, 18:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107508

бабушкин зайчик

Гость

mayton, т.е. предлагаешь разбить контейнер на X контейнеров, и с каждым работать отдельным потоком?
А куда и как их мержить потом - не понял? В каждом запросе чтоли?

...

Рейтинг:

0 / 0

27.10.2021, 18:06

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107509

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

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

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

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

...

Рейтинг:

0 / 0

27.10.2021, 18:09

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107511

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

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

бабушкин зайчик

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

...

Рейтинг:

0 / 0

27.10.2021, 18:59

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107528

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

mayton,

а что просто, для начала, нормальный алгоритм не поискать?

...

Рейтинг:

0 / 0

27.10.2021, 19:05

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107531

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

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

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

...

Рейтинг:

0 / 0

27.10.2021, 19:13

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107533

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

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

а если пул потоков, то у тебя взрыв мозга будет?

...

Рейтинг:

0 / 0

27.10.2021, 19:20

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107535

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

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

СУБД пишем?

...

Рейтинг:

0 / 0

27.10.2021, 19:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107539

Basil A. Sidorov

Участник

Сообщения: 11 633

Рейтинг: 0 / 0

mayton

Но какого размера брать слой?

Если можем "монополизировать" железо , то в размер кэша второго уровня. Который на ядро.
В современных условиях можно просто не выёживаться. Для начала.
А то получится как со скоростью xxhash, которая может превышать скорость чтения из памяти. Но там автор честно указывает, что "данные такого размера находятся в процессорном кэше".

...

Рейтинг:

0 / 0

27.10.2021, 19:46

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107543

бабушкин зайчик

Гость

mayton

бабушкин зайчик

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

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

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

...

Рейтинг:

0 / 0

27.10.2021, 20:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107545

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Встречи. Клиенты. Ты оперируешь временнЫми интервалами которые в миллион раз превышают
то что мы тут обсуждаем? Верно?

...

Рейтинг:

0 / 0

27.10.2021, 20:14

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107548

бабушкин зайчик

Гость

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

...

Рейтинг:

0 / 0

27.10.2021, 20:19

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107549

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

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

Не надо. Контейнер для отображения на экране целиком и безраздельно принадлежит
потоку, обрабатывающему GUI и сообщения о том, что "прошла встреча" и
"выставлена оценка", которые, по его меркам, приходят в час по капле.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

27.10.2021, 20:23

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107559

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Подкину немножко. Для перемножения больших матриц по-хорошему надо использовать алгоритм Штрассена .

...

Рейтинг:

0 / 0

27.10.2021, 20:44

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107560

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton

Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру
с кешом.

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

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

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

...

Рейтинг:

0 / 0

27.10.2021, 20:50

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107568

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T

mayton

Ну... самый первый камень - это как распараллелить. Особенно с учотом того что доступ к матрице Б идет
неблагоприятным образом. Вертикальное сканирование double элементов - создает крайне неудачную игру
с кешом.

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

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

И как справедливо заметил Василий... чортовы кеши. Надо укладывать хотя-бы 1 слой умножений в L2.

...

Рейтинг:

0 / 0

27.10.2021, 21:27

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107569

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вот фрагмент спеки железа актуального на 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)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

mayton,

делали уже люди тынц

...

Рейтинг:

0 / 0

27.10.2021, 21:58

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107581

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

mayton,

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

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

как бы с ростом N непонятно кто выиграет

...

Рейтинг:

0 / 0

27.10.2021, 22:07

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107587

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Это такая-себе софистическая задачка. Она идёт тестовым учебным примером в tutorials по OpenMP.
Ее также упоминает Грегори Эндрюс в своей книге по параллелизму.

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

Я не против всяких Штрассенов. Просто это уже плоскость математики а я там не силён.

...

Рейтинг:

0 / 0

27.10.2021, 22:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107590

бабушкин зайчик

Гость

хм, если у интелов кэш измеряется в мегабайтах, значит ли это, что они nodoubt лучше?

...

Рейтинг:

0 / 0

27.10.2021, 22:27

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107594

booby

Участник

Сообщения: 2 667

Рейтинг: 1 / 0

PetroNotC Sharp

бабушкин зайчик

СУБД пишем?

такого сорта "субд" в конце 90х - середине 2000-х уже один раз не взлетели.
Пока не видно никаких причин, по которым они могли бы попытаться взлететь повторно.
Для этого есть существенное основание - субд вообще с другого конца начинаются.
Не только не с "контейнеров", но даже и не с "объектов", по крайней мере в оо-смысле.

...

Рейтинг:

0 / 0

27.10.2021, 22:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107747

бабушкин зайчик

Гость

mayton

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

параллелизм - ок, конкуренция - ниок. Ясно. Понятно.
Хотя при перемножении матриц в A и B тоже могут писать, ну да ладно...
В итоге весь контейнер блочится мьютексом на чтение И на запись?
Или самый идеал - множество контейнеров вместо одного?

...

Рейтинг:

0 / 0

28.10.2021, 14:33

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107752

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикВ итоге весь контейнер блочится мьютексом на чтение И на запись?

Контейнер не блочится. Блочится мутекс. А чем занимается его владелец - сугубо
его личное дело.

бабушкин зайчик

Или самый идеал - множество контейнеров вместо одного?

Идеал - отсутствие конкуренции. Как он достигается - сугубо всё равно.

...

Рейтинг:

0 / 0

28.10.2021, 14:50

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107767

бабушкин зайчик

Гость

Dimitry Sibiryakov, в смысле контейнер не блочится, если никто к нему доступа не имеет, кроме хозяина?

...

Рейтинг:

0 / 0

28.10.2021, 15:38

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40107793

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Дословно. Перечитай моё сообщение ещё раз. Любой может доступиться к контейнеру
если не будет предварительно пытаться заблокировать мутекс, наплевав на мнение
его хозяина.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

28.10.2021, 16:18

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108240

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

В итоге весь контейнер блочится мьютексом на чтение И на запись?
Или самый идеал - множество контейнеров вместо одного?

какие то узкие решения.
Не везет тебе с архитектурой.

...

Рейтинг:

0 / 0

30.10.2021, 09:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108244

бабушкин зайчик

Гость

критикуешь - предлагай

...

Рейтинг:

0 / 0

30.10.2021, 10:12

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108245

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

критикуешь - предлагай

вам выше давали ссылку что любое блокирование это компромисс.
Вы её не читали.
Компромиссы не очертили и не согласились "что-то терять при установке блокировки".
Итог - пустой тред о погоде.

...

Рейтинг:

0 / 0

30.10.2021, 10:28

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108255

бабушкин зайчик

Гость

выше ты мне дал ссылку на блокировки в БД
нахрена мне читать очередную статью про ACID и блокировки транзакций?
я с БД работаю уже 10+ лет, я разве про БД тут спрашиваю?
ты когда начнёшь по теме что-то говорить, а не умного из себя строить?
выцепил первую попавшую ссылку из гугла со словом "блокировки" и тычет мне её
уйди отсюда.

...

Рейтинг:

0 / 0

30.10.2021, 12:33

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108257

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикя с БД работаю уже 10+ лет

Если за это время до тебя не дошло, что блокировки и их применение везде
одинаковое - забей, займись чем-нибудь попроще.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

30.10.2021, 12:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108259

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

выше ты мне дал ссылку на блокировки в БД

смотрим:
22388622
авторТак чем же придется пожертвовать при использовании стратегии высокого параллелизма?
Параллелизм это не про БД.))

бабушкин зайчик

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

А кто тебя в теме поддержал? )))
Буквально все в теме сказали: "Борис ты не прав".
Вот твои слова:

бабушкин зайчик

В итоге весь контейнер блочится мьютексом на чтение И на запись?

Какой ВЕСЬ контейнер Карл?

бабушкин зайчик

Или самый идеал - множество контейнеров вместо одного?

ИДЕАЛ - ВЫСОКИЙ ПАРАЛЛЕЛИЗМ И ОТСУТСТВИЕ БЛОКИРОВОК.
ДОШЛО?
По архитектуре у тебя двойка - нет идеала в архитектуре.
Иди в школу.

...

Рейтинг:

0 / 0

30.10.2021, 12:45

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108260

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dimitry Sibiryakov

бабушкин зайчикя с БД работаю уже 10+ лет

Если за это время до тебя не дошло, что блокировки и их применение везде
одинаковое - забей, займись чем-нибудь попроще.
+1
Можно кодировать успешно. А можно программировать.
Вот во втором случае и решаешь каждый абзац кода с компромиссами.

...

Рейтинг:

0 / 0

30.10.2021, 12:46

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108274

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

бабушкин зайчик

выше ты мне дал ссылку на блокировки в БД
нахрена мне читать очередную статью про ACID и блокировки транзакций?
я с БД работаю уже 10+ лет, я разве про БД тут спрашиваю?

Почитай про NoSQL, весь этот зоопарк недоБД родился чтобы ACID обойти. Еще Теорема CAP . Может какие мысли появятся как их идеи применить в твоей задаче.

...

Рейтинг:

0 / 0

30.10.2021, 14:16

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108290

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

С пессиместичной блокировкой вроде все разобрались. Блочим. Читаем-пишем. Разблокируем
обратно. Всё уныло и понятно.

С оптимистичной что? Есть моё наивное предположение что она будет дешевле
но только при условии что читателей - статистически будет больше.

Пропорцию я могу предложить пареттовскую. На 20% писателей которые бьют по
блокировке - будет 80% читателей которые тоже ее бьют но контейнер при этом
не меняют.

Я не могу придумать алгоритм или какой-то стресс-тест чтобы явно показать преимущества
но на ум приходит Convays-Life на двумерном поле.

Потоки (штук 4-16) читают и пишут состояние ячеек. Причем по алгоритму конвея
надо читать 8 соседей чтобы установить свою одну ячейку.

Мне почему-то кажется что Жизнь Конвея будет эффективнее работать при
оптимистичных блокировках.

И если сердитый зайчик реализует оптимистик-режим то из сердитого
он может стать нормальным зайчиком.

...

Рейтинг:

0 / 0

30.10.2021, 17:38

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108295

бабушкин зайчик

Гость

PetroNotC Sharp

Какой ВЕСЬ контейнер Карл?

вот этот:

Dimitry Sibiryakov

бабушкин зайчикпоэтому мне по 5 раз приходится спрашивать, как же правильно с контейнером
работать конкурентно

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

Dimitry Sibiryakov

бабушкин зайчикя с БД работаю уже 10+ лет

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

Dimitry Sibiryakov

бабушкин зайчикЯ тебе описал реальный пример, как ты его без mutex решать хочешь?

Заявлю "это проблема СУБД, не моя" и вообще mutex использовать не буду по причине, описанной выше.
не будет он mutex использовать...
или только mutex будет использовать...
FastCGI туда приплёл... ты же даже не вникаешь в вопрос.

...

Рейтинг:

0 / 0

30.10.2021, 18:00

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108296

бабушкин зайчик

Гость

Dima T

бабушкин зайчик

вообще-то я смотрю в сторону CQRS
(щас вышепроцитированные товарищи совсем потеряются)

...

Рейтинг:

0 / 0

30.10.2021, 18:01

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108299

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

Dima T

пропущено...

Почитай про NoSQL, весь этот зоопарк недоБД родился чтобы ACID обойти. Еще Теорема CAP . Может какие мысли появятся как их идеи применить в твоей задаче.

вообще-то я смотрю в сторону CQRS
(щас вышепроцитированные товарищи совсем потеряются)

теорему САР уже прошел))))

...

Рейтинг:

0 / 0

30.10.2021, 18:08

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108300

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

PetroNotC Sharp

Какой ВЕСЬ контейнер Карл?

вот этот:

Dimitry Sibiryakov

пропущено...

Ну ок, раз ты хочешь абсолютного и простого ответа, получи: с контейнером надо работать в эксклюзивном режиме, под мутексом и никак иначе.

нафиг я тебя читаю вообще :закрытьлицоладошкой:
уходи говорю.

Dimitry Sibiryakov

пропущено...

Если за это время до тебя не дошло, что блокировки и их применение везде одинаковое - забей, займись чем-нибудь попроще.

а ты вообще в показаниях путаешься, тебя спрашивают про контейнеры, но ты отмазываешь БД, которая "не твоя проблема"

Dimitry Sibiryakov

пропущено...

Заявлю "это проблема СУБД, не моя" и вообще mutex использовать не буду по причине, описанной выше.

не будет он mutex использовать...
или только mutex будет использовать...
FastCGI туда приплёл... ты же даже не вникаешь в вопрос.

один флуд
... Зачем слушаю...
... Ты не вникаешь...
... Отмазываешь...
Ты точно инженер?

...

Рейтинг:

0 / 0

30.10.2021, 18:12

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108301

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

mayton,
Снимаю шляпу героическим попыткам повернуть топик к ТЗ или коду.

...

Рейтинг:

0 / 0

30.10.2021, 18:13

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108303

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

бабушкин зайчик

mayton

В данном случае вообще ничего не надо блочить, это и есть идеал распараллеливания, просто раздать потокам задания кто какой элемент результата считает и готово.

...

Рейтинг:

0 / 0

30.10.2021, 18:47

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108308

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dima T,
Совершенно верно.
Это раздать потокам работу.
Там подтянется позже менеджер потоков, пул потоков,...
А мембер мыслит узко в терминах "расшарить контейнер" ака "глобальная переменная".

...

Рейтинг:

0 / 0

30.10.2021, 19:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108311

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

mayton wroteС *оптимистичной* что? Есть моё наивное предположение что она будет дешевле
но только при условии что читателей - статистически будет больше.

Вопрос не в количестве, вопрос в качестве. Если зайчиков "контейнер" это
std::vector, а читатели достают один его элемент по индексу, то накладные
расходы на оптимистичную блокировку превысят таковые на пессимистичную при любом
количестве читателей.

У Жизни есть неочевидная особенность: новое состояние поля должно складываться в
новое поле, а старое состояние только читается. Поэтому как и в случае
перемножения матриц никакие блокировки не нужны от слова "совсем" (при условии
статичности целевого поля).
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

30.10.2021, 20:09

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108313

booby

Участник

Сообщения: 2 667

Рейтинг: 1 / 0

еще пару постов, и mvcc будет изобретен в очередной раз повторно, после первого изобретения в 1978 году.
Но там вполне допускается и наоборот.
Новое значение состояния пишется в старое поле, а старое значение уходит в новую историю состояний.
Как показывает Oracle, на живом собственном примере - тоже вполне удачный вариант (попробуй обгони).

Говорят, что любая из известных к настоящему моменту, и используемых в бд схем обслуживания concurrency,
в комбинации с параллельностью поступающих запросов, масштабируется в весьма ограниченном диапазоне конкурирующих запросов.

Кто-то лет 15-20 назад моделировал для классических disk oriented систем, что в любом случае, в районе 1000 процессов, какие схемы
ни катай, возникает гарантированный stop the world.

Просто у некоторых схем он возникает раньше, а других позже, какие-то третьи скатываются плавнее к состоянию непроходимости.

Что интересно, по какому-то совершенно случайному совпадению, число ядер в современных серверных процессорах
(~64 физических) практически совпадает с максимумом пропускной способности произвольной схемы обеспечения concurrency,
которая в тогда была оценена где-то в 128 конкурирующих процессов для любой схемы.

...

Рейтинг:

0 / 0

30.10.2021, 20:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108314

бабушкин зайчик

Гость

Dima T

Dimitry Sibiryakov

Поэтому как и в случае перемножения матриц никакие блокировки не нужны от слова "совсем" (при условии статичности целевого поля).

если там нет никаких потоков (которые пишут в A/B), то какой интерес вообще в этой задаче?
Что там решать то, и что она делает в теме с mutex?
Многопоточно сложил всё в раздельные строки (массивы) для C и собрал матрицу.

...

Рейтинг:

0 / 0

30.10.2021, 20:54

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108324

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

Dima T

Dimitry Sibiryakov

просто трудно забыть твой тред в той теме 22388433 .
То контейнеры, то запросы, то http server 22389971
Mayton тебе доказал что конкуренция и блокировка Г... а параллелизм здорово.
Ты же споришь))))

...

Рейтинг:

0 / 0

30.10.2021, 21:47

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108339

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Может Конвей - неудачный пример?

Давайте численные методы.

Кстати даже сам факт того что мы не можем придумать hiload задачу c интенсивным использованием разделяемых переменных говорит о том что сама постановка .. слишком натянута что-ли.

...

Рейтинг:

0 / 0

30.10.2021, 23:10

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108342

бабушкин зайчик

Гость

PetroNotC Sharp

Mayton тебе доказал что конкуренция и блокировка Г... а параллелизм здорово.

на задачке для 5-летних...
когда дорастёшь до реальных задач, тогда и приходи.

PetroNotC Sharp

То контейнеры, то запросы, то http server 22389971

http-сервер туда притащил тот же mayton...
какой же ты бесполезный

...

Рейтинг:

0 / 0

30.10.2021, 23:30

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108348

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

на задачке для 5-летних...
когда дорастёшь до реальных задач, тогда и приходи.

хорош щеки надувать.
Споришь там и тут а ТЗ нету.

бабушкин зайчик

http-сервер туда притащил тот же mayton...
какой же ты бесполезный

Ну притащил. А ты ответил, что внизу мы разгребаем запросы.
Вместо субд? Там твой ответ интересен брат))
Покажи опыт постановки задачи!

...

Рейтинг:

0 / 0

30.10.2021, 23:39

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108355

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

mayton,
Из мира шарпа или java можно.

Сессионный список объектов хранится в сессии веб сервера.

Под каждый запрос из веб контейнер веб сервера стартует новый поток и далее запрос уже в потоке.
Админ снаружи потока мониторит на sql.ru активными юзверями.
Банит/правит.
Внутри потока тоже чтение и правки списка обьектов User{id, name, role}
...
Типо так.

...

Рейтинг:

0 / 0

30.10.2021, 23:55

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108356

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

mayton,
https://stackoverflow.com/questions/616601/is-httpsession-thread-safe-are-set-get-attribute-thread-safe-operations
Совсем недавно разрабы веб серверов сказали - разработчики! Следите сами за потокобезопасностью! Синхронизируйте снаружи и в своем коде сами!)))
Веб сервер только стартует вам поток.

...

Рейтинг:

0 / 0

31.10.2021, 00:08

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108360

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

PetroNotC Sharp

mayton,
Из мира шарпа или java можно.

Я не хотел брать из Java. Во первых - многие С++ ники - не в теме и им придется объяснять зачем
и какие аналогии. Я не могу придумать аналогий для JSP/Servlets.

И я вообще не хотел брать сокетные приложения. Мы не сможем создать на них такую
нагрузку чтобы почувстовать все "квантовые эффекты" особенно Амдал и его расширенная
версия Universal Scalability Law c когерентностью.

А если мы не сможем создать нагрузку - то как мы покажем зайчику всю красоту
этой самой coherency. Ведь это самая вкусная и интересная часть дискуссии. Она
объясняет суть недостатка конкуренции на переменной.

Поэтому я и хотел синтетический тест где есть только процессор и память. Кстати optimistic
не устраняет мьютекс совсем. Он просто переносит его вглубь проверок условий и кроме того
если условия использования оптимистика ухудшаются - (потоки писатели сошли с ума и стали
постоянно что-то писать в контейнер) - то потоки читатели тоже сходят с ума и превращаются
в ... спинлоки и грузят CPU.

...

Рейтинг:

0 / 0

31.10.2021, 00:56

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108395

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

mayton,
Понимаю.
Для сишников более характерно отсутствие разделение системного кода и прикладного.
Поэтому выше ты верно сказал - сложно сделать постановку на расшаренную переменную))))
Таких задачек все меньше в IT

...

Рейтинг:

0 / 0

31.10.2021, 12:43

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108398

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Расшаренные переменные === глобальные переменные.
Глобальные переменные мастдай.

Два самых частых (R/W) их применения - кэш и пул. Оба решаются эксклюзивной
блокировкой при доступе к контейнеру и счётчиком ссылок на объекты внутри, без
хитроподвыподвертнутых схем типа RWLock.
Ещё частое применение - очередь, но о ней вообще можно не говорить, там
примитив, показанный в соседнем топике.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

31.10.2021, 12:56

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108399

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Хотя нет, с учётом развода писателей, для кэша как раз получается примерно RWLock.

А пул сводится к очереди.

...

Рейтинг:

0 / 0

31.10.2021, 13:13

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108400

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dimitry Sibiryakov

Расшаренные переменные === глобальные переменные.
Глобальные переменные мастдай.

я имел ввиду не расшаренные на область видимости application.
А расшаренные как в первом посту матрица на потоки работ или потоки читателПисатель.

...

Рейтинг:

0 / 0

31.10.2021, 13:27

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108403

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

По поводу optimistic контейнера. Тут надо быть еще аккуратнее.

Чтение может быть неконсистентным. Для int, char[] это не приводит ни к чему страшному.
Но если в контейнере лежит какая-то сложная структура. И если поток читатеть ее читает
надеясь что "проскочит" а в это время поток-писатель модифицирует какие-то сложные
структуры то есть ненулевая вероятность что читатель может зациклится или провалится
в бесконечную рекурсию. И до проверки атомик поля с номером версии он просто не дойдет
просто по причине того что завис.

...

Рейтинг:

0 / 0

31.10.2021, 13:36

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108407

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

PetroNotC Sharp

А в чём разница? Поток это процедура. Любая переменная, объявленная вне этой процедуры, к которой она доступается - по определению глобальная.

mayton

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

О чём это ты? Атомный счётчик ссылок этой структуры не имеет ничего общего с блокировками писателей, это просто вспомогательный элемент для автоматического управления памятью. Писатели используют COW и тем самым не пересекаются с читателями от слова "совсем".

...

Рейтинг:

0 / 0

31.10.2021, 13:59

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108413

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ты наверное говоришь о версионности.

...

Рейтинг:

0 / 0

31.10.2021, 14:33

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108414

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Да, copy-on-write и есть версионность. А о чём говоришь ты?
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

31.10.2021, 14:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108425

бабушкин зайчик

Гость

надо было закрыть тему про mutex, чтобы обсуждать mutex в теме про матрицы, где его, по сути, вообще нет

mayton

А если мы не сможем создать нагрузку - то как мы покажем зайчику всю красоту этой самой coherency. Ведь это самая вкусная и интересная часть дискуссии. Она объясняет суть недостатка конкуренции на переменной.

в твоей задаче нет никаких конкуренций
каждый пишет свою часть C (строку) и не парится.
И чем больше потоков, тем быстрее заполнится C.
Только это не работает в задаче, где куча клиентов дёргают самые разные части БД с целью почитать/пописать.
Но... я нашёл способ свести все заморочки с конкурентностью к минимуму. И почти без блоков.
Не знаю, вся это красота или нет, но я её постиг.

...

Рейтинг:

0 / 0

31.10.2021, 15:51

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108436

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

БД (даже версионник) косвенно использует блокировки для того чтобы не нарушить консистентность
db-block (это кусок таблички обычно длиной 4-8 К) который уже закеширован в данный момент.

В документации Oracle называет их latches. Чему соответсвтует летч в операционной системе - это
зависит от самой операционки. В Windows-Linux это может быть по разному реализовано.

Да. В моей задаче про умножение матриц нет конкуренций. Там - fork-join. И в фазе join
там есть просто ожидание слияния потоков в основной поток. Это может быть не нулевое
ожидание просто потому что один поток чуть быстрее закончил свою работу.

...

Рейтинг:

0 / 0

31.10.2021, 16:52

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108438

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

надо было закрыть тему про mutex, чтобы обсуждать mutex в теме про матрицы, где его, по сути, вообще нет

Замечание принято. Буду обсуждать тут - только матрицы.

...

Рейтинг:

0 / 0

31.10.2021, 16:54

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108453

бабушкин зайчик

Гость

mayton

И в фазе join
там есть просто ожидание слияния потоков в основной поток. Это может быть не нулевое
ожидание просто потому что один поток чуть быстрее закончил свою работу.

так выдели один поток, который будет собирать все результаты, а освободившиеся спокойно пойдут заниматься своим делом

...

Рейтинг:

0 / 0

31.10.2021, 17:42

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108454

бабушкин зайчик

Гость

mayton

бабушкин зайчик

надо было закрыть тему про mutex, чтобы обсуждать mutex в теме про матрицы, где его, по сути, вообще нет

Замечание принято. Буду обсуждать тут - только матрицы.

а тот зачем закрыл

...

Рейтинг:

0 / 0

31.10.2021, 17:43

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108456

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

его не надо персонально выделять. Он уже есть. И это мейн.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

// Верхняя половина матрицы А
t1 = pthread_create(...)
// Нижняя половина
t2 = pthread_create(...);

// ожидаем слияния двух половино-потоков с main.
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);

Красота? Никаких тебе явных мютексов. Никаких атомиков.

...

Рейтинг:

0 / 0

31.10.2021, 17:55

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108457

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

mayton

пропущено...

Замечание принято. Буду обсуждать тут - только матрицы.

а тот зачем закрыл

А вот когда мемберы на личности переходят - топик резко сам закрывается.

...

Рейтинг:

0 / 0

31.10.2021, 17:57

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108459

бабушкин зайчик

Гость

mayton

его не надо персонально выделять. Он уже есть. И это мейн.

где ты там нашёл проблему

mayton

ожидание слияния потоков в основной поток

если мейн вынужден ждать завершения всех и не может освободившийся поток запустить с другой задачей, то нафиг такой мейн
а если у него кроме этой матрицы задач нет, то откуда проблема возьмётся?

mayton

А вот когда мемберы на личности переходят - топик резко сам закрывается.

ага, то по кругу ходим, то на личности перешли ему...
ты тему зачем закрыл, в которой mutex обсуждали?!
в другой теме нельзя по кругу пойти или на личности переходить???
ГДЕ теперь mutex обсуждать

...

Рейтинг:

0 / 0

31.10.2021, 18:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108460

бабушкин зайчик

Гость

короче, hyperthreading - да или нет?
в задачах конкурентного r/w доступа к контейнерам

...

Рейтинг:

0 / 0

31.10.2021, 18:05

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108494

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик,
Чё ты на него напал?
В этом треде пока все спокойно.
Создай новую тему и обсуждай, без личностей).
Только тема про мьютекс это слишком мелко.

...

Рейтинг:

0 / 0

31.10.2021, 20:11

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108499

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

короче, hyperthreading - да или нет?
в задачах конкурентного r/w доступа к контейнерам

пора уже тебе код показать.

...

Рейтинг:

0 / 0

31.10.2021, 20:28

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108503

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

бабушкин зайчик

Но... я нашёл способ свести все заморочки с конкурентностью к минимуму. И почти без блоков.
Не знаю, вся это красота или нет, но я её постиг.

Поздравляю! На этом можно закончить и топик закрыть.

...

Рейтинг:

0 / 0

31.10.2021, 20:45

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108505

бабушкин зайчик

Гость

Dima T

бабушкин зайчик

Поздравляю! На этом можно закончить и топик закрыть.

да его уже закрыли
а тут про матрицы

...

Рейтинг:

0 / 0

31.10.2021, 21:25

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108520

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикосвободившийся поток запустить с другой задачей

Зачем повторно использовать туалетную бумагу? Новой задаче - новый поток.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

31.10.2021, 23:15

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108521

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Тема напомнила трассировщик луча. Я там как-раз хотел добавить параллелизм на потоках. Подниму-ка.

...

Рейтинг:

0 / 0

01.11.2021, 00:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108534

бабушкин зайчик

Гость

Dimitry Sibiryakov

бабушкин зайчикосвободившийся поток запустить с другой задачей

Зачем повторно использовать туалетную бумагу? Новой задаче - новый поток.
а затраты на создание нового потока? И убиение старого...

...

Рейтинг:

0 / 0

01.11.2021, 03:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108547

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

Dimitry Sibiryakov

пропущено...

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

а затраты на создание нового потока? И убиение старого...

ответ очевиден - посчитай затраты и делай через пул НЕ создавая.
))

...

Рейтинг:

0 / 0

01.11.2021, 08:34

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108586

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчика затраты на создание нового потока?

Грандиозно преувеличиваются новичками.

Если у вас затраты на создание потока сравнимы со временем выполнения его функции -
поток вообще не нужен.

...

Рейтинг:

0 / 0

01.11.2021, 13:26

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108591

бабушкин зайчик

Гость

Dimitry Sibiryakov

Грандиозно преувеличиваются новичками.

пулы потоков тоже новички пишут?

...

Рейтинг:

0 / 0

01.11.2021, 13:45

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108596

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикпулы потоков тоже новички пишут?

Нет, их пишут люди с весьма специфическими задачами. Ну или новички, неспособные
оценить их необходимость, да.

В зависимости от параметров входящего потока запросов есть четыре варианта
оптимальной их обработки:

1) Отсутствие потоков, запросы выполняет принимающий поток;
2) Очередь, которую разгребают несколько рабочих потоков;
3) Пул потоков;
4) Новый поток каждому запросу.

Второй и третий варианты хоть и звучат похоже, не взаимозаменяемы.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 13:50

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108607

бабушкин зайчик

Гость

Dimitry Sibiryakov

Нет, их пишут люди с весьма специфическими задачами.

а какие там специфические задачи?
ты либо много потоков туда-сюда создаёшь, либо мало
но пул можно заранее слабать, я так понимаю, что он универсальный

п.2 - эти потоки откуда возьмутся? "Повторно используют туалетную бумагу"?

...

Рейтинг:

0 / 0

01.11.2021, 14:58

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108616

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Померяйте накладные. Возможно старт Windows/POSIX потока стоит дёшево
а вы втащите в систему ненужный обвес. Задачу умножения матриц можно
решить и без пула.

А короткоживущие акторы можно просто запускать последовательно на 1 потоке.
Этим кстати пользуются все акторные библиотеки.

А пул, если вы его создатите - требует обслуживания. У него должен быть lifecycle.
Тоеть внятная точка на оси времени где он создается и где уничтожается. И политики
роста и деградации.

...

Рейтинг:

0 / 0

01.11.2021, 15:16

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108617

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчика какие там специфические задачи?

Неизвестное количество запросов в секунду (вариант 4 отпадает из-за того, что
сделает от такого БУМ), неизвестная комплексность отдельных запросов (вариант 1
отпадает из-за непредсказуемого времени обработки одного запроса), необходимость
выполнения определённых запросов строго последовательно и/или в определённом
контексте (вариант 2 отпадает из-за неконтролируемого распределения задач по
потокам).

Особенно специфично (и редко) последнее условие. В качестве примера, где оно
есть, на ум приходит только пул потоков-исполнителей в СУБД, неспособной к
внутреннему распараллеливанию (такой как Firebird).

бабушкин зайчикно пул можно заранее слабать, я так понимаю, что он универсальный

Можно, но накладные расходы и сложность реализации у него превышают все
остальные варианты вместе взятые.

бабушкин зайчикп.2 - эти потоки откуда возьмутся?

Созданы при старте, сразу все. Или созданы по необходимости до определённого
предела.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 15:16

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108618

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

maytonВозможно старт Windows/POSIX потока стоит дёшево а вы втащите в систему ненужный
обвес.

Писатели ОСей не дураки. Если бы пул потоков был дешевле создания нового потока,
они давно бы встроили его в ядро, уравняв их стоимости.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 15:35

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108619

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dimitry Sibiryakov

бабушкин зайчикно пул можно заранее слабать, я так понимаю, что он универсальный

Можно, но накладные расходы и сложность реализации у него превышают все
остальные варианты вместе взятые.
С++ не заточен под веб проекты.
А пул нужен для веб сервера.
Поэтому в шарпе и java слово пул изучают школьники.

...

Рейтинг:

0 / 0

01.11.2021, 15:41

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108620

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

PetroNotC SharpА пул нужен для веб сервера.
Поэтому в шарпе и java слово пул изучают школьники.

Пул коннектов к БД или чего-то такого же очень дорогого - верю.
Пул потоков - не верю.
Возможно, у этих школьников изучение пулов не идёт дальше написания этого слова.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 15:51

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108622

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

Dimitry Sibiryakov

Пул потоков - не верю.

в шарпе - класс ThreadPool АВТОМАТИЧЕСКИ увеличивает кол-во потоков подстраиваясь под НАГРУЗКУ.
Довольно умный алгоритм.
Слово школьники утрировано, но спрашивать писать ли пул самому приходит в голтову только у сишников.

...

Рейтинг:

0 / 0

01.11.2021, 16:04

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108623

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ограничения количества потоков пуле в Java имеют смысл т.к. 1 поток занимает 1 Мегабайт памяти и стека.
Поэтому их создают не с целью быстрого старта а с целью предотвращения OOM exception. Из консоли
можно этот размер регулировать но ... вот я щас не помню действует ли это на все потоки процесса?
Кажется на все.

Тоесть кажущаяся "легкость и зеленость" потоков Java может обернуться вполне себе материальными
проблемами.

Создают также для менеджмента джобов. Одно семейство джобов грузит CPU. Дать их 4-8 потоков.
Другое семейство работает с БД - создать им потоки по количеству степени параллелизма самой БД.
Третье семейство обслуживает веб - там можно дать побольше.

...

Рейтинг:

0 / 0

01.11.2021, 16:05

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108624

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton

... т.к. 1 поток занимает 1 Мегабайт памяти и стека...

Обычно пишут "1 Мегабайт памяти под стек", только тут я не согласен - это же виртуальная память, да выделили под стэк 1 Мб, но реально занято 1-2 страницы по 4 кб, остальное будет занято если реально потребуется.

...

Рейтинг:

0 / 0

01.11.2021, 16:11

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108625

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

maytonТоесть кажущаяся "легкость и зеленость" потоков Java может обернуться вполне
себе материальными проблемами.

Для "универсального решателя проблем" выбор между производительностью и
дуракоустройчивостью очевиден.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 16:11

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108627

бабушкин зайчик

Гость

Dimitry Sibiryakov

бабушкин зайчикосвободившийся поток запустить с другой задачей

Зачем повторно использовать туалетную бумагу? Новой задаче - новый поток.
так почему не использовать существующий поток, вместо каких-то там пулов
зачем каждый раз новый?

...

Рейтинг:

0 / 0

01.11.2021, 16:16

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108629

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Dima Tда выделили под стэк 1 Мб, но реально занято 1-2 страницы по 4 кб, остальное
будет занято если реально потребуется.

Со стэком проблема не в физической памяти, а именно в виртуальном адресном
пространстве. Стэк не переместишь и не расширишь по необходимости, он должен
быть с фиксированным адресом и непрерывным участком. Тысяча виртуальных кусков
по мегабайту и гигабайта нет. А это половина всего пространства, доступного 32-х
разрядному процессу. В реальности ООМ часто приходит уже в районе 800, поскольку
стэки доползают до кучи, которая тоже растёт.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 16:18

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108633

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

Dimitry Sibiryakov

пропущено...

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

так почему не использовать существующий поток, вместо каких-то там пулов
зачем каждый раз новый?

Компромиссы карл! Запомни это слово)
- один поток на всё - это синхронность
- много на каждую задачу - конец ресурсам
промежность между двумя архитектурами - ПУЛ

...

Рейтинг:

0 / 0

01.11.2021, 16:19

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108635

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

бабушкин зайчик

Dimitry Sibiryakov

пропущено...

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

так почему не использовать существующий поток, вместо каких-то там пулов
зачем каждый раз новый?

Ну.. если ты программировал мультипоточность - то у тебя обычно есть не 1 а целый сет работающих
потоков. И их диаграмма активности напоминает обычно хаос. И вот менеджментом этого хаоса и занимается
пул. Но опять-же. Поскольку твои вопросы очень краткие - то и ответы получаются либо не в тему либо
люди отвечают по своим проблемам с которыми сталкивались.

...

Рейтинг:

0 / 0

01.11.2021, 16:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108636

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикзачем каждый раз новый?

Простота кодирования. Создать новый поток - одна строчка. Использовать старый -
несколько экранов зубодробительного кода с синхронизацией и вытекающими
укрытиями для багов.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 16:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108643

бабушкин зайчик

Гость

mayton

Поскольку твои вопросы очень краткие - то и ответы получаются либо не в тему либо
люди отвечают по своим проблемам с которыми сталкивались.

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

...

Рейтинг:

0 / 0

01.11.2021, 16:35

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108652

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчиккак кто юзает и почему - никто не написал.

Потому что use case для каждого из четырёх вышеперечисленных случаев легко
выводится простой логикой:

1) Стоимость выполнения запросов предсказуема и лучше всего O(1) (например - DNS);
2) Запросы не имеют взаимозависимостей (например - HTTP);
3) Всё остальное;
4) Поток запросов предсказуем и ограничен (например - перемножение матриц).
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 16:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108656

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик

какие ответы? тут кто-то написал........?

"какие вопросы, такие и ответы" (с)

...

Рейтинг:

0 / 0

01.11.2021, 16:53

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108659

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Можно создать топик под названием Нужен ли Зайчику пул?

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

...

Рейтинг:

0 / 0

01.11.2021, 16:56

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108666

бабушкин зайчик

Гость

в http сам FastCGI или HTTP-сервер потоками рулит
ему прилетает запрос -> он ему поток -> разбирает -> грузит логику
там 1 запрос всегда = 1 поток, как я понимаю

...

Рейтинг:

0 / 0

01.11.2021, 17:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40108682

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчиктам 1 запрос всегда = 1 поток, как я понимаю

Это сугубо на фантазии разработчика.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

01.11.2021, 18:52

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113287

booby

Участник

Сообщения: 2 667

Рейтинг: 1 / 0

случайно набрел - какого жару, оказывается, поддал Торвальдс в тему использования спинлоков в пользовательском режиме
в январе 20го года:

...
I repeat: do not use spinlocks in user space, unless you actually know what you're doing . And be aware that the likelihood that you know what you are doing is basically nil.
...
Because you should never ever think that you're clever enough to write your own locking routines.. Because the likelihood is that you aren't (and by that "you" I very much include myself - we've tweaked all the in-kernel locking over decades, and gone through the simple test-and-set to ticket locks to cacheline-efficient queuing locks, and even people who know what they are doing tend to get it wrong several times).
...

https://www.opennet.ru/opennews/art.shtml?num=52140

https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723

...

Рейтинг:

0 / 0

20.11.2021, 01:50

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113297

бабушкин зайчик

Гость

хм, как в C выглядит "честное распределение ресурсов"
отсюда

Код: 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.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.

Код на C для gcc gcc -o rw -lpthread -lm rewr.c

#include <pthread.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <semaphore.h>
#define M 4 //num of WR
#define N 3 //num of RE
unsigned int iter; //iteration
sem_t accessM,readresM,orderM; //sem.
unsigned int readers = 0;	// Number of readers accessing the resource

void *reader(void *prm)
{
	int num1=*(int*)prm;
	int i=0,r;
	for(i;i<iter;i++)
	{
		
		if (sem_wait(&orderM)==0) printf("%d Читатель %d в очереди__________Ч%d\n",i,num1,num1);	// Remember our order of arrival
		sem_wait(&readresM);				 // We will manipulate the readers counter
		if (readers == 0)				// If there are currently no readers (we came first)...
			sem_wait(&accessM);				// ...requests exclusive access to the resource for readers
		readers++;							 // Note that there is now one more reader
		sem_post(&orderM);					 // Release order of arrival semaphore (we have been served)
		sem_post(&readresM);				 // We are done accessing the number of readers for now

		printf("%d Работает читатель %d________________Ч%d\n",i,num1,num1);				// Here the reader can read the resource at will
		r=1+rand()%4;
		sleep(r);
		sem_wait(&readresM);				 // We will manipulate the readers counter
		readers--;							 // We are leaving, there is one less reader
		if (readers == 0)				// If there are no more readers currently reading...
			sem_post(&accessM);				// ...release exclusive access to the resource
		sem_post(&readresM);				 // We are done accessing the number of readers for now
	}
}

void *writer(void *prm)
{
	int num2=*(int*)prm;
	int j=0,r;
	for(j;j<iter;j++)
	{
		if(sem_wait(&orderM)==0) printf("%d Писатель %d в очереди__________П%d\n",j,num2,num2); // Remember our order of arrival
		sem_wait(&accessM);					// Request exclusive access to the resource
		sem_post(&orderM);					 // Release order of arrival semaphore (we have been served)

		printf("%d Работает писатель %d________________П%d\n",j,num2,num2);				 // Here the writer can modify the resource at will
		r=1+rand()%4;
		sleep(r);
		sem_post(&accessM);					// Release exclusive access to the resource
	}
}

void main()
{	
	pthread_t threadRE[N];
	pthread_t threadWR[M];
	sem_init(&accessM,0,1);
	sem_init(&readresM,0,1);
	sem_init(&orderM,0,1);

	printf("Введите количество итераций: ");
	scanf("%d",&iter);
	printf("Iter                         ОЧЕРЕДЬ/ВЫПОЛНЕНИЕ\n");
	int i;
	for(i=0;i<M;i++)
	{
		pthread_create(&(threadWR[i]),NULL,writer,(void*)&i);
	}
	for(i=0;i<N;i++)
	{
		pthread_create(&(threadRE[i]),NULL,reader,(void*)&i);
	}
	

	for(i=0;i<N;i++)
	{
		pthread_join(threadRE[i],NULL);
	}
	for(i=0;i<M;i++)
	{
		pthread_join(threadWR[i],NULL);
	}
	
	sem_destroy(&accessM);
	sem_destroy(&readresM);
	sem_destroy(&orderM);
}

и как оно выглядит в C++

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.

shared_mutex m;                 // a mutex that can be shared

void reader()
{
    shared_lock lck {m};        // willing to share access with other readers
    // ... read ...
}

void writer()
{
    unique_lock lck {m};        // needs exclusive (unique) access
    // ... write ...
}

...

Рейтинг:

0 / 0

20.11.2021, 04:39

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113325

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Так ты из тех, кто думает, что заметание кода под коврик библиотеки делает его
лучше?..
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

20.11.2021, 13:47

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113329

PetroNotC Sharp

Участник

Сообщения: 10 098

Рейтинг: 0 / 0

бабушкин зайчик,
Этот пример ни о чем не говорит.
Лучше сравнивай С++ с С++

...

Рейтинг:

0 / 0

20.11.2021, 14:02

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113371

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

20.11.2021, 18:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113407

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

это кризис жанра ....
возьмите матрицу 10х10 чтобы не плодить воображение.
И подумайте пошагово - как же устроить перемножение матрицы да еще и ускорить......
=Никак.

Я - Вася, по фотке со спутника полетел смотреть квадрат
А Петя который типа лихой - все будет портить? Нет. У него нет такого права.

Что вы пытаетесь крутить?

...

Рейтинг:

0 / 0

20.11.2021, 20:11

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113420

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не беспокойся сильно.

...

Рейтинг:

0 / 0

20.11.2021, 21:18

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113428

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

Полезно переносить логику на обычные жизненные ситуации.
И не будет никакого беспокойства.

...

Рейтинг:

0 / 0

20.11.2021, 21:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113431

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Задача обедающих философов.

Жизненная?

...

Рейтинг:

0 / 0

20.11.2021, 21:40

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113435

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

в данном топике и в данной постановке - абсолютно Нет.

...

Рейтинг:

0 / 0

20.11.2021, 21:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113439

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

вообще - хейтерская викепедийная задача
причем там философы....

Дурдом как и Пирамида Маслоу.

...

Рейтинг:

0 / 0

20.11.2021, 21:59

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113451

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Философы, матрицы - это просто учебные задачи на параллелизм и дедлоки которые просто рассматриваются в учебниках.

Но если вы знаете более интересные и самодостаточные задачи, которые не зависят от I/O - прошу. Публикуйте.

...

Рейтинг:

0 / 0

20.11.2021, 23:11

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113458

бабушкин зайчик

Гость

Dimitry Sibiryakov

Так ты из тех, кто думает, что заметание кода под коврик библиотеки делает его лучше?..

я из тех, кто думает, что писать новый код = всегда ошибки
меньше кода = меньше ошибок

...

Рейтинг:

0 / 0

21.11.2021, 00:40

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113459

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

mayton,

дело в том что в данном топике мы умножаем А на В,
где априори А и В - унитарные объекты,
иначе событие А*В не состоится .

Причем здесь задача голодных студентов с двумя вилками у каждого?

Изначальный вопрос - Как ускорить

...

Рейтинг:

0 / 0

21.11.2021, 01:13

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113461

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

бабушкин зайчикя из тех, кто думает, что писать новый код = всегда ошибки
меньше кода = меньше ошибок

А в результате мы видим приложения, где куча готовых библиотек, каждая из
которых делает чуть-чуть не совсем то, что нужно, смотана изолентой и подпёрта
костылями. Работают они соответственно.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

21.11.2021, 01:38

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113462

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Унитарные? Это термин из какой предметной области?

...

Рейтинг:

0 / 0

21.11.2021, 01:39

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113506

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

21.11.2021, 12:01

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113510

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Alex_Ustinov, если я заменю на атомарное - это будет соответствовать вашему предлагаемому смыслу?

...

Рейтинг:

0 / 0

21.11.2021, 12:21

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113525

бабушкин зайчик

Гость

Dimitry Sibiryakov

бабушкин зайчикя из тех, кто думает, что писать новый код = всегда ошибки
меньше кода = меньше ошибок

А в результате мы видим приложения, где куча готовых библиотек, каждая из
которых делает чуть-чуть не совсем то, что нужно, смотана изолентой и подпёрта
костылями. Работают они соответственно.
я уже написал 2 своих фреймворка с нуля (на PHP правда)
чё-то пас

...

Рейтинг:

0 / 0

21.11.2021, 14:23

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113528

Basil A. Sidorov

Участник

Сообщения: 11 633

Рейтинг: 0 / 0

Alex_Ustinov

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

Вот только не надо на физику наговаривать: "квантовые" (физическое) и "унитарное" (организационно-правовая форма) - не имеют между собой ничего общего.в математике строгого понятия нет, разве что "простые числа"Зачем вы натянули сову на ещё один глобус?"унитарное" - значит "неделимое" предприятие. Унитарным предприятием признается коммерческая организация, не наделенная правом собственности на закрепленное за ней собственником имущество .

...

Рейтинг:

0 / 0

21.11.2021, 14:56

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113529

Basil A. Sidorov

Участник

Сообщения: 11 633

Рейтинг: 0 / 0

mayton

Alex_Ustinov, если я заменю на атомарное - это будет соответствовать вашему предлагаемому смыслу?

Вообще никак.
Матрицы, просто по определению, состоят из элементов. Элементы могут обладать свойством атомарности доступа.
В отношении всей матрицы глупо говорить и об "атомарности" и об "унитарности".

...

Рейтинг:

0 / 0

21.11.2021, 15:00

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113532

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

как раз таки в отношении Действий над матрицами - условие Атомарности Операции применимо на 100%
Иначе эта Операция не имеет смысла.

...

Рейтинг:

0 / 0

21.11.2021, 15:13

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113535

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Таки Вы настаиваете, что перемножение матриц должно производиться транзакционно,
с откатом к исходному состоянию если в процессе произошла ошибка?..
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

21.11.2021, 15:18

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113536

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

авторУнитарным предприятием признается коммерческая организация,
не наделенная правом собственности на закрепленное за ней собственником имуществоосновная цель этого понятие в строках дальше. Именно для чего это создавалось. Читать надо до конца.
Любая организация, обслуживающая какие то объекты - не собственник этих объектов. Но не все такие предприятия содержат в названии "унитарное".
Я работал в администрации города N, поэтому это утверждаю.
И коммерческая организация - НЕобязательно. Бюджетное - не коммерческое, но может быть унитарное.
Не знаю почему так звучит в ГК. Хотя это не столь важно.

...

Рейтинг:

0 / 0

21.11.2021, 15:24

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113537

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

Dimitry Sibiryakov,

перефразирую -
в процессе перемножения матрицы ее элементы должны быть неизменны. Так как при изменеии 1 элемента изменится результат во всей строке и столбце
Про откат ни слова
------------------
мда, замудренно. При вычислении i,j элемента A*B мы не можем менять i-строку A и j-тый столбец B

...

Рейтинг:

0 / 0

21.11.2021, 15:31

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113538

Basil A. Sidorov

Участник

Сообщения: 11 633

Рейтинг: 0 / 0

Alex_Ustinov

Любая организация, обслуживающая какие то объекты - не собственник этих объектов.

Вы опять выдернули совсем не то.
Есть собственник некоторого имущества. Есть организация, которая распоряжается этим имуществом распоряжается, но не владеет.
Например - здание в муниципальной собственности и (муниципальная) организация здравоохранения, которая в этом здании расположена.
Нельзя сказать, какая-нибудь поликлиника обслуживает здание, в котором она работает. Наоборот - эта поликлиника заключает договора на обслуживание со всякими водоканалами и ГУП охраны.
Точно так же нельзя сказать, что Г(осударственное)У(нитарное)П(редпиятие) охраны владеет территорией, на которой находятся его здание с оружейкой, караулкой, пультовой и "вот этим вот всем".

...

Рейтинг:

0 / 0

21.11.2021, 15:39

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113541

Basil A. Sidorov

Участник

Сообщения: 11 633

Рейтинг: 0 / 0

Alex_Ustinov

Я работал в администрации города N, поэтому это утверждаю.

А у меня - вполне солидный стаж гражданской государственной службы в органах государственной исполнительной власти.
Будем и дальше пиписьками меряться?И коммерческая организация - НЕобязательно. Бюджетное - не коммерческое, но может быть унитарное.
Не знаю почему так звучит в ГК. Хотя это не столь важно.А это вам надо бы с бюджетным кодексом ознакомиться.
И автономные и бюджетные организации создаются именно, что для коммерческой деятельности.
Казённые учреждения не имеют права заниматься коммерческой деятельностью, но даже они могут взимать государственные пошлины и иные законные сборы. Просто деньги эти пойдут не в бюджет предприятия, а сразу на (казначейские) счета, определённые органами власти.

...

Рейтинг:

0 / 0

21.11.2021, 15:48

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113557

Alex_Ustinov

Участник

Откуда: Nickel

Сообщения: 3 965

Рейтинг: 0 / 0

За пиписьками - попрошу в другое место
"комерческое" - Я же дополнил - не столь важно.

Унитарное - основной посыл - неделимое.

...

Рейтинг:

0 / 0

21.11.2021, 17:07

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113572

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Alex_UstinovУнитарное - основной посыл - неделимое.

Это если оно от слова united. Как унитарный выстрел, например.
А если оно от слова unit, то к неделимости отношения обычно не имеет.

Вывод: не надо применять многозначительные слова.
Posted via ActualForum NNTP Server 1.5

...

Рейтинг:

0 / 0

21.11.2021, 18:02

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113588

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Разобрались вроде.

Вернёмся к матрицам?

...

Рейтинг:

0 / 0

21.11.2021, 18:49

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113735

love_bach

Участник

Сообщения: 687

Рейтинг: 0 / 0

Alex_Ustinov

это кризис жанра ....
возьмите матрицу 10х10 чтобы не плодить воображение.
И подумайте пошагово - как же устроить перемножение матрицы да еще и ускорить......
=Никак.

вроде в численной алгебре есть такие алгоритмы
но, они приближенные

...

Рейтинг:

0 / 0

22.11.2021, 13:25

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40113739

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Блин. Статья на хабре была. Про ускорение. И кеши. И AVX2.

А я еще хотел свой вопрос спросить. Про обучение двухслойной простейшей НС прямого распространения.

...

Рейтинг:

0 / 0

22.11.2021, 13:30

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40116486

rdb_dev

Участник

Откуда: с болот

Сообщения: 3 797

Рейтинг: 0 / 0

mayton

Даны две матрицы вещественных чисел. A и B. Одинаковой размерности. Их надо перемножить...

mayton, для начала, я бы развернул матрицу B на 90° против часовой стрелке так, чтобы первые элементы столбцов стали первыми элементами строк и тогда нужно лишь умножить первую строку матрицы A на последнюю строку матрицы B, а затем использовал бы OpenMP для распараллеливания процесса.

...

Рейтинг:

0 / 0

01.12.2021, 17:15

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40116528

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

rdb_dev

mayton

Даны две матрицы вещественных чисел. A и B. Одинаковой размерности. Их надо перемножить...

Да. Верно. Только почему на последнюю?

Там вообще надо все-со-всеми. Для примера - пускай будут не квадратные а прямоугольные.

Матрица A(3:4), Матрица B(4,5), ..... Результирующая C будет иметь размеры (3,5). Тоесть каждая строчка
матрицы А будет скалярно перемножена со столбцом B и результат - скаляр будет вписан в соответсвующий
элемент матрицы С.

Но поскольку оперативная память не любит рандомного доступа а любит более менее линейный - то да...
матрицу B мы разворачиваем и слегка меняем алгоритм.

Ну и в идеале... можно пробовать fork-join для скалярных умножений... или если это слишком мелко - то
лучше не для отдельных столбцов а для прямоугольных областей.

...

Рейтинг:

0 / 0

01.12.2021, 19:37

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40116701

бабушкин зайчик

Гость

нужно ли распараллеливание, если обе матрицы помещаются в кэше?

...

Рейтинг:

0 / 0

02.12.2021, 12:47

| Ответить | Цитировать | Написать

Ускорить умножение квадратных матриц (продолжение темы с mutex)

#40116734

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я думаю на это может ответить эксперимент. В кешах L1 могут лежать копии матрицы A.

...

Рейтинг:

0 / 0

02.12.2021, 15:14

| Ответить | Цитировать | Написать

165 сообщений из 165, показаны все 7 страниц

все

Форумы / C++ [игнор отключен] [закрыт для гостей] / Ускорить умножение квадратных матриц (продолжение темы с mutex)

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=57&tid=2017148]:	0ms
get settings:	10ms
get forum list:	13ms
check forum access:	4ms
check topic access:	4ms
track hit:	25ms
get topic data:	10ms
get forum data:	2ms
get page messages:	137ms
get tp. blocked users:	2ms
others:	264ms

total:	471ms