Легкие потоки

Надоели политические срачи.
Хочется поговорить за программирование и о легких потоках.

Фактически меня больше интересует С и С++ (ну и матлаб, туда не сложно С либу подключить).

Сейчас есть несколько вариантов реализации легких потоков в виде coroutines в том числе и в бусте. Предполагается их появление с С++.
Еще тут на форуме приводили пример с Go, в котором это нативно в языке поддержано.
Есть варианты с CUDA и OpenCL.

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

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

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

Если на уровне идеи: Уильям Ричард Стивенс „Advanced programming in the Unix environment”; www.amazon.com/...​ronment-3rd/dp/0321637739

Если на уровне реализации — сырцы glibc, подсистема pthread

pthread точно не в счёт: никто не гарантирует их легковесность, и в большинстве современных систем они 1:1 с системными нитями, а не M:N.
Примером тех, кто долго тянул M:N, но таки сдался, служат Solaris и FreeBSD.

В Unix тут можно вспоминать XSIʼшные setcontext() с аналогами, но начиная с Posix.1-2008 они выброшены из стандарта, а во многих флаворах и не вводились.

В виде библиотеки это, например, GNU pth.

В виде библиотеки это, например, GNU pth.

Pth это N:1, корутины фактически.

Pthread содержит

механизмы взаимодействия программы с ОС на этапе выполнения
а «легковесные потоки» с ОС обычно не взаимодействуют никак.
Примером тех, кто долго тянул M:N, но таки сдался, служат Solaris и FreeBSD.

Они не сдались, они достигли понимания что в современных реалиях задача не имеет общего решения, а связыватся с частными решениями — не оправдано.

а «легковесные потоки» с ОС обычно не взаимодействуют никак.

Тут уже по-разному. Если тот же setcontext требует поддержки от ОС — будут взаимодействовать.

А libc_r времён FreeBSD4, например, врапила все блокирующие вызовы в цикл вокруг select+yield (тоже типичный ход для этого слоя средств).

Они не сдались, они достигли понимания что в современных реалиях задача не имеет общего решения, а связыватся с частными решениями — не оправдано.

Считаю это другой формулировкой того же утверждения :)

Если тот же setcontext требует поддержки от ОС — будут взаимодействовать.
По моей информации setcontext() абсолютно всегда тредует поддержки ОС, и как следственно может служить базой только для тяжелых потоков.

N шедулеров, по одному в треде, конкурентно выбирают готовые корутины из общей очереди.
См. clone(2), futex(2) для синхронизации очереди, и любой пример реализации корутин.
Слова для поиска: hybrid threading, n:m scheduling, thread pool

thttp://www.kegel.com/c10k.html#1:1
www.akkadia.org/...​drepper/glibcthreads.html

pthread делает только 1:1 scheduling.

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

Я понял в чём непонятка вы все путаете concurrency с parallel computing а это таки разные вещи оба два для первых как раз всякий разный async и акторы а вот второй каким был таким и остался там просто распараллеливание там между параллельными корреляции и конкуренции нет вот в чём цимес заблуждения.

ЗЫ: вот кстати и примечание в русской же ж википедии


Примечание — В русскоязычной литературе нередко путаются термины «параллелизм» и «конкурентность». Оба термина означают одновременность процессов, но первый — на физическом уровне (параллельное исполнение нескольких процессов, нацеленное только на повышение скорости исполнения за счёт использования соответствующей аппаратной поддержки), а второй — на логическом (парадигма проектирования систем, идентифицирующая процессы как независимые, что в том числе позволяет их исполнять физически параллельно, но в первую очередь нацелено на упрощение написания многопоточных программ и повышение их устойчивости).

А зачем изобретать новые термины? Давно же уже устоялось в computer science:

  • preemptive multitasking — это про все про threads с OS поддержкой
  • cooperative multitasking — это все про «green» threads, всякие async модели в JS и прочая
cooperative multitasking — это все про «green» threads, всякие async модели в JS и прочая

cooperative multitasking — это совсем не то, что ты написал.

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

Именно про то.

cooperative multitasking это способ обеспечения многозадачности когда разные ветки исполнения кооперируют друг с другом уступая (yield) управление другим веткам. Все эти promises, callbacks, async I/O это про это самое и есть. Первый же залетевший дятел по имени «while(true);» разрушает node.js цивилизацию как нечего делать.

И green threads это в принципе про то же. Только там в качестве кооператора выступает VM которая может schedule ветки исполнения на уровне bytecodes.

Т.е. threads (hardware interrupts + context switch OS support ) это про preemptive multitasking, но
fibers это именно cooperative multitasking и есть.

То, что всякуая шушера использует cooperative multitasking не делает его предназначение только этой шушеры, только и всего.

То, что твои устоявшиеся термины с multitasking не являются устоявшимися.

Ну не знаю... Эти термины были в ходу еще в НПО «Импульс» ( Северодонецк, ДОС АСПО и пр. ) еще во времена СССР когда там была солидная Школа ... Сейчас конечно модно всё переиначивать... но не настолько же.

Я тебе привел определения, в ответ же ... или давай свои определения cooperative multitasking или заканчиваем это «благорастворение на воздусех».

Тебе уже дали определение: dou.ua/...​rums/topic/20821/#1122668

Еще раз, смысл cooperative multitasking состоит в том что ветка исполнения должна уступить CPU ресурс либо:

  1. Явным вызовом yield из функции-генератора (есть green thread в терминах JS)
  2. Явным вызовом await из async функции (тоже green thread в терминах JS) .
  3. Либо скорейшим завершением (return) функции — event handler (также green thread фактически).

Execution scheduler в browser и node.js это message/event pump loop обрабатывающий event queue

while(var event = fetchNextEvent()) {
   if( event instanceof Timer ) event.handler();
   else if( event instanceof UIEvent ) dispatchEvent(event);
   else if( event instanceof AsyncTask ) event.restoreStateAndContinue();
   sleep(0); // yield execution to the OS
}

т.е. любая функция в JS должна кооперировать со всеми остальными — быть короткой — завершаться быстро. Чем быстрее return из функций тем «больше параллелизма». Все это и есть кооперативная многозадачность, но никак не вытесняющая многозадачность. Других вариантов в архитектуре фон Неймана не изобретено.

Других вариантов в архитектуре фон Неймана не изобретено.

Во многих языках c VM green threads реализованы как preemptive multitasking. В том же линуксовом ядре прекрасно живут тасклеты, которые складываются в очередь и не могут быть вытеснены — обычная cooperative multitasking. Даже если взять классическую preemptive multitasking, то в любой операционной системе, когда произошло принудительное вытеснение задачи — это исключительная ситуация (CPU hogging), которую все пытаются избежать используя кооперативную многозадачность, отдавая управление ядру по своему желанию или в силу необходимости при работе с API. Тот же sporadic scheduling приближается к кооперативной многозадачности и только в экстренных случаях срабатывает вытесняющая многозадачность. Вот поэтому я категорически против таких определений:


preemptive multitasking — это про все про threads с OS поддержкой
cooperative multitasking — это все про «green» threads, всякие async модели в JS и прочая
VM green threads реализованы как preemptive multitasking.

Давай тогда дадим определение green thread. Вот одно из них (вики наша педиа):

In computer programming, green threads are threads that are scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system.

Т.е. кооператор в данном случае это либо это некий код приложения (см. выше event pump loop ) или VM в процессе обработки потока bytecodes.

В случае VM, bytecodes должны быть «кооперируемы» ибо что-то типа

BC_LOAD blocking_socket;
BC_CALL  recv;
убьет ту green thread и иже с ней.

Т.е. green threads это тоже всё про cooperative multitasking, вместо I/O только async I/O, epolls, и прочие completion ports.

О чем я и говорил изначально.

Т.е. green threads это тоже всё про cooperative multitasking, вместо I/O только async I/O, epolls, и прочие completion ports.

Нет. Об этом даже написано той статье на педивикии, на которую ты ссылаешься. Green threads — это эмуляция потоков и cooperative multitasking ортогонален к этому.

Если эмуляция потока исполняется с помощью yield из самого потока то это и есть кооперация этого фрагмента кода со всем остальным. Quod erat demonstrandum пардоньте мой французский.

Ну да ладно это все терминология. Ты мне лучше скажи насколько рабочий OpenGL в QNX. Я у себя в Sciter умею рисовать в OpenGL и OpenGL ES. Например на Raspberry Pi 2. Но вот хочется чего-то попробовать на встраиваемой OS. И кроме Blackberry железа оно еще где-то работает?

Ты мне лучше скажи насколько рабочий OpenGL в QNX.

OpenGL ES только.

Например на Raspberry Pi 2.

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

И кроме Blackberry железа оно еще где-то работает?

Что за Blackberry железо? :) Тут список платформ:
www.qnx.com/...​nx/en/developers/bsp.html

Что за Blackberry железо?

А я знаю? :) QNX же вроде как собственность Blackberry и вроде как девайсы какие-то делают...

Preemptive: шедулер может переключить треды по своей инициативе.
Cooperative: треды сами должны инициировать переключение.

При желании можно сделать userspace preemptive multitasking. И наоборот, ядро с cooperative.

Cooperative: треды сами должны инициировать переключение.

И для этого тоже есть устоявшийся термин — not «threads» but «fibers».

Кстати, недавно смотрел доклад Шона Перента о различных реализациях систем тасков в C++ — он там особенно хвалил эппловский libdispatch. Приводил пример аналога std::async, построенного поверх вызовов libdispatch: www.youtube.com/...​I&feature=youtu.be&t=1864
Возможно, стоит попробовать такой подход, если на Вашей системе доступна эта библиотека.
Также можете посмотреть весь доклад, в целом он относится к поднятой здесь теме и есть шанс, что Вас заинтересует ещё что-то из упомянутого в нём.

Рекомендую в сторону модели акторов глянуть: www.slideshare.net/...​heniAkhotnikau/c-67520296 habrahabr.ru/post/322250
На с++ я еще не пробовала, а вот на c# фреймворк Akka.NET значительно упростил мне жизнь и благодаря ему справилась с курсачем за 5 дней(на что с обычными потоками ушло бы пару месяцев). Вообще, фреймворки реализующие модель акторов сейчас на всех или почти на всех популярных япах есть

Желательно избегать контор, в которых дают домашку

либо легкие на GPU но с большими объемами.

Нет точно такие же ж «тяжёлые» только там грануляция выше исходя из большего числа процессоров суть в том что твои задачи загружают именно процессор (как исполнительное ядро) на 100% и твоя задача стоит только правильно общую задачу на подзадачи разделить а потом собрать обратно «лёгкие» же ж потоки это для случая когда каждая в отдельности задачка с точки зрения процессорозависимости говно но самих по себе их +100500 и они никак с собой другом не связаны и вообще не представляют части единого целого а суть есть поток уже раздельных гранулярных сущностей изначально. Суть есть там вообще не стоит задача а) взять большой пакет данных б) подготовить его для обработки многими потоками в пакетном режиме в) запустить обработку в пакетном режиме г) собрать результат.

Но реальные задачи бывают разнообразнейшие.

По моему нескромному мнению следует ориентироваться на конкретные задачи класс мыслителей

задачи бывают разнообразнейшие

— следует оставлять для низших и прочих лохов от абстрактного и прочего мышления вообще. Переживать не стоит имя им легион тем более с учётом особенностей национального «в Родине есть две беды». (к) (тм)

Вот классическая задача pdist (pairwise distance). Видел-ли кто уже отлаженные решения с тайлингом и распараллеливанием?

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

к тормозам на синхронизации

Какой синхронизации? После разбиения на подзадачи синхронизировать там больше нечего каждая из отдельных задач полностью автономна.

ли закатыванию солнца ручками в ручной раскладе данных для CPU

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

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

Ну дык вот 2 вложенных цикла каждый проход уже пустить по отдельному потоку вычислений не? Я честно плохо понимаю во что именно ты упираешься ну кроме конечно

вероятно ты туп и делаешь что-то

Видимо начинать надо где-то оттуда )) и разбить задачу на подзадачи а если уже нет такой возможности (субъективной) то бросать лохматить бабушку и идти в охранники там всё линейно уборщики тоже можно но там сложнее. ))

ЗЫ: есть псевдокод этих «2 вложенных цЫкла»?

Вот расскажи, как бы ты делал pairwise distance

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

Если взять простое умножение матриц то утрировано NxN даст соотв. чисто вычислений отдельных ячеек результата каждое из которых простой N цикл никаких «синхронизаций» там нет если принять что входящие данные и результат всё отдельные матрицы при этом входящие только читаются а результат отдельной ячейки зависит только от входящих соотв. на входе «потокового вычислителя» получаем NxN простых задач из N циклов которые и скармливаем всем «потокам вычислителя» последовательно в пакетной обработке «выполнил текущий возьми следующий из общего пула на входе» простенкий пул потоков для такого можно написать «на коленке» либо использовать что-либо готовое под кодовым «thread pool» там основная задача чтобы у реализации было понимание реального числа реальных физических вычислителей доступных и соотв. открытие соотв. числа «вычислительных потоков» и всё.

Если предполагать что твоя задача pairwise distance подчиняется тем же ж критериям «исходящая матрица зависит только от входящих данных и не зависит от себя самой» в таком случае она разбивается точно так же ж на NxN ячеек с алгоритмами близкими к линейным и зависящим только от своего собственного набора входных данных и по сути будет функция типа число = функция (строка, столбец) и эта функция будет иметь соотв. NxN вычислений и просто последовательно скармливается на Х вычислителей результаты записываются каждый в свою ячейку отдельно никакой синхронизации нет от слова вообще.

Всё.

ЗЫ: по той же ж причине «исходящая матрица зависит только от входящих данных и не зависит от себя самой» никакая модель акторов тебе не нужна потому как она обратно таки для совершенно другого и важна совокупная реакция системы включая собственные состояния и порождённые новые объекты а в твоём случае простая числодробилка с одним входом и одним выходом никаких внутренних взаимодействий у неё нет и длительного времени жизни тоже нет «сосчитал кусочек записал результат умер всё» всё полностью из чистых функций состоит же ж.

Мне тоже кажется что никакая синхронизация тут не нужна. Максимум барьеры и сброс кешей.

Максимум барьеры

Дык и барьеры ему тоже не нужны потому как в процессе вычисления более никто уже вычисленными данными не пользуется сами локальные вычислители есть суть линейны и даже если они некой рекурсией своими результатами таки пользуются то обратно таки каждый своими никак не трогая «соседей по пакетному вычислителю» и никак евонных данных ни используя ни изменяя.

и сброс кешей

Что может влиять на общую производительность с памятью но это уже совсем другая история и не надо сюда «потоки вычисления» путать да.

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

ЗЫ: ну да выравнивание по разрядности памяти видимо х64 в общем случае и ещё може быть на следующем этапе выравнивание уже блоков по страницам но обратно таки там уже детально надо смотреть об чём речь на конкретных обсчётах сколько там данных и каких.

Что может влиять на общую производительность с памятью но это уже совсем другая история и не надо сюда «потоки вычисления» путать да.
На некоторых архитектурах потоки на разных ядрах не будут видеть данные других потоков до сброса кеша. Ситуацию на x86 я честно не помню.
потоки на разных ядрах не будут видеть данные других потоков

Так им и не надо же ж в этом же ж цимес чистого параллелизма на чистых функциях!

Так им и не надо же ж в этом же ж цимес чистого параллелизма на чистых функциях!
А результат как возвращать?

Складывать. В ячейки результирующей таблицы. [i, j]

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

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

старый добрый map-reduce подход

Мы говорим о нюансах реализации map-reduce

не будут видеть данные других потоков до сброса кеша

Не «сброса кэша» — полный сброс тут нафиг никому не нужен — а исполнения операции, которая называется write barrier. Кэш при этом остаётся: в реализациях типа MESI/etc. по общей шине идёт сигнал типа «я это модифицировал, всем обращаться за свежайшей версией к моему кэшу», запись же в DRAM может быть отложена на произвольное время.

Ситуацию на x86 я честно не помню.

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

в реализациях типа MESI/etc. по общей шине идёт сигнал типа «я это модифицировал, всем обращаться за свежайшей версией к моему кэшу», запись же в DRAM может быть отложена на произвольное время.
 а это работает только в пределах процессора или и между процессорами? и какими?

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

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

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

И там внизу три или четыре продолжения.

А брось мне сырцы? Я бы поковырялся вместо очередной партии героев. Если эта задача решаема то есть вероятность что я ее решу за 2-3 подхода к ноуту.

Реальный код, который можно скормить компилятору.

А какому компилятору его можно скормить и где потоки затыкающиеся на синхронизации?

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

И sqrt(sum(x.^2, y.^2)) это для С++ программистов нынче неподъемная задача.

А ты ж не веришь, когда говорю выкинь каку double. Хотя бы мат.часть почитал, КАК ИМЕННО процессор выполняет твою задачу. Последовательность действий.

Тебе точно позарез с точностью double надо вычислить этот квадратный корень? С точностью промежуточных вычислений примерно в 24 десятичных цифры?
Вот зачем тебе число 0.983508560923988620398403 и чем оно хуже 0,984? Вот возьми хоть раз РУКАМИ вычисли то, чем ты процессор напряг, всего одну итерацию. Потом расскажешь за «потоки», теоретик.

Что-то мне подсказывает, тебе 16 бит целочисленки — с головой. А то и 8, если это геолокация.

Мнэээ.
1.

Тебе точно позарез с точностью double надо вычислить этот квадратный корень? С точностью промежуточных вычислений примерно в 24 десятичных цифры?

double — это 15-16 точных десятичных цифр. Откуда рассказ про 24? Ты FPUʼшный 80-битный вспомнил? Так и там только 18-19 (смотря как оценивать граничные случаи).
2.

А то и 8, если это геолокация.

WAT? Геолокация до метра это уже 7 полных цифр, это минимум float32.

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

Если это танец с бубном, который ты сделаешь ОДИН РАЗ вместо танца с бубном для проца, который его миллиарды раз должен повторить — пиши код б...ть!

Я уж думал, эти танцы с целочисленкой остались в 90х. float32 вполне шустр

Деньги все еще крутятся только на целочисленке.

для денег давно еще BCD придуман, это особый случай

BCD — если речь про 4 бита на цифру, а не 10:3 Chen-Ho, как у IBM — это дорогой бессмысленный кошмар, который перестал быть выгодным по сравнению с честной двоичкой ещё где-то во времена i386.

fixed point без FPU? Редкий случай? Да большинство DSP до сих пор без FPU. всякие SIMD по большей частью без плавающей точки или с тормозами нереальными на плавающей точке. Как раз матлаб, по крайней мере 10 лет назад имел квантизатор, очень удобную штуку как раз для отладки фиксированной точки.

Да ничерта не ад. Я такое больше чем 10 лет назад делал. Если изначально не ложить себе граблей в виде IIR фильтров, то все нормально. Ставиться квантизатор и дальше не сложнее здравого смысла. Квантизатор говорит после каждого прогона сколько битов использовалось в целой и фракциональной части.

Не, если подрядиться на задачу типа «вот тебе программа, убери FPU», то да, можно вешаться.

Ну не совсем. IBM ввела в свои процессоры десятичный float, и пропихнула его в IEEE754-2008.

У него самое существенное преимущество по сравнению с двоичным — отсутствие вот этих вечных 0.1*3 != 0.3, которое сбивает с толку массу народу, и лёгкость контроля неточных операций там, где по сути требуются точные. И с таким (при разумной дисциплине) легко его использовать в финансах — сильно легче, чем двоичную.

Чуть более ранний Decimal в C# - тоже пример floatʼа для финансов (хотя в разы более кривой по всем параметрам).

Но очень многое, да, по-прежнему просто удобнее на fixed через целые — тут я безусловно согласен.

IBM ввела в свои процессоры десятичный float, и пропихнула его в IEEE754-2008.
Прям молодцы :-)
float32 вполне шустр

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

И координаты на Земле, например, во float32 представляются с точностью до двух метров. Если нужно точнее — переходить на float64.

А ещё только с ~2008 Intel & Co. начали избавляться от бреда в поддержке денормализованных и вводить методы, придуманные уже за много лет до того. У всех процессоров включительно до Nehalem можно было получить торможение в тысячи тактов на банальнейшую операцию. Да и сейчас стоит чуть выйти за пределы майнстрима и можно получить неожиданным мешком по голове.

Именно! У тебя есть конкретное вычисление каждой отдельной ячейки таблицы результата которое зависит только от входящих параметров. Всё.

На каждое вычисление строишь объект функтор который имеет данными конкретно i, j т.е. сам знает ячейку какую ему считать т.е. синхронизации между ними уже не нужно считать их можно каждый в раздельности в любом порядке из этих объект функторов строишь «многопоточную очередь» и отдаёшь её на вход Х «рабочим потокам» которые а) извлекают объект функтор из входящей очереди б) выполняют его. Всё.

ЗЫ: software.intel.com/...​default/files/fa/f5/22515
«Applying TBB on Strassen’s Matrix Multiplication — Intel® Software»

ЗЫ: вот чиёто практическое решение:

blog.speedgocomputing.com/...​-multiplication_8641.html
«Parallel Matrix Multiplication using TBB»

Основной цимес здесь:

class Multiply
{
public:
    void operator()(blocked_range<int> r) const {
        for (int i = r.begin(); i != r.end(); ++i) {
            for (int j = 0; j < size; ++j) {
                for (int k = 0; k < size; ++k) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
    }
};

И вот как он используется:

// C <- C + A x B
parallel_for(blocked_range<int>(0,size), Multiply());

Всё остальное несущественная обвязка единственное что я бы б настоятельно рекомендовал использовать double он в современных 64-битных системах имеет прямое преимущество а разница в скорости floating point operations между ними мизерна если вообще есть в современных системах (кстати надо бы б и себе обновить знание вдруг понадобится в CERN работать или где там студенточки годные).

ЗЫ: с переводами на ДОУ говно простите ну и х. с ним. ))

ЗЫ: соотв. в качестве вычислителя подствляешь «в качестве f евклидово расстоние между векторами размерности 67.» и стаёт тебе щасте всем пис и прочия излишества всякие нехорошие.

Изать GPU для небольших матриц бессмысленно.

Ты неправильно рассматриваешь GPU — выноси туда больше работы.

Кстати, а можешь дать ссылку где указаны временные затраты на эти операции?

Они зависят от GPU. Например, Intel Iris Skylake 540 (GT3e) имеет на чипе 128Mb L3 LLC кеша, что позволяет шарить данные между GPU и CPU с минимальными затратами. Ну и вся память — это системная память, доступ максимально быстрый. В nVidia ты можешь использовать как видео память, так и системную. В первой ты получаешь пеналти при доступе, во втором случае при работе с этой памятью со стороны GPU и т.д. Без знаний архитектур ты далеко не уедешь, общих подходов не существует.

Вот www.codeproject.com/...​ips/29524/Generators-in-C был написал coroutines/generators для C++ в 16 строках .h файла ... За небольшим ограничением покрывает значительное количество случаев когда coroutines действительно нужны.

Олдовый программист на всём умеет написать программу на фортране!

А он впринцыпе никогда не умирал, просто немного потерял в популярности.

C++ есть за что называть уродливым. Например, за «forwarding ссылки» (которые на первый взгляд неотличимы от обычных rvalue-ссылок) или за громоздкие плохочитаемые SFINAE-трюки через enable_if (с которыми как раз и должны бороться концепты). Это да, однозначно некрасивая муть.
Но называть язык уродливым из-за отсутствия в нём стандартных многомерных массивов, — сириусли? Недостаток стандартной библиотеки — да, вполне. Но это никак не уродство языка как такового.

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

Многомерные массивы в C/C++ есть. Никто не мешает декларировать многомерные массивы фиксированной размерности, типа int а[10][10][10]. Более того, никто не мешает декларировать многомерные массивы динамической размерности (то, о чём автор хабровской статьи пишет, как " размер матриц становится известен лишь в runtime") типа int*** а.

Но только ни один вменяемый C/C++ кодерок — такими извратами для многомерных массивов пользоваться не будет. Зачем, если массив любой размерности — это лишъ кусок памяти и, соответственно, для работы с таким массивом (куском памяти) достаточно лишь указателя на него.

Подход с int** хорош только при достаточно больших размерностях массивов. При небольших это лишние накладные расходы из-за множества аллокаций и индирекций. Впрочем, на хабре эту тему уже разжевали.

Кроме того... Как там ситуация с языком C, я не знаю, но в C++ такие вещи принято заворачивать в безопасные классы вместо прямой работы с указателями. Поэтому для плюсов независимо от способа реализации — через int***, или через единый динамический массив со сквозной индексацией, — ещё нужно будет написать обобщённые шаблонные обёртки, по-хорошему. Подобно тому, как шаблон std::vector заворачивает в себя одномерный динамический массив.
И речь шла о нехватке в стандартной библиотеке языка таких обёрток, если я правильно понял автора.

Подход с int** хорош только при достаточно больших размерностях массивов.

Для массивов он плох всегда, т.к. в нём нет смысла. Массивы любой размерности — отлично адресуются одиночным указателем.
Да и что касается сэйф/смарт-поинтеров — делать таким одиночный указатель куда легче, чем двойной (или там тройной) тоже.

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

В нём есть смысл, если память фрагментируется настолько, что выделить здоровенный массив требуемой размерности одним куском уже становится затруднительно. Можно и bad_alloc словить.

Ок, работа с такими размерами — это уже отдельная, очень специальная тематика. :) И там просто двойными/тройными указателями не отделываются.

Было бы очччень хорошо если ты иллюстрировал свои слова примерами кода ато у меня жуткое впечатление что ты путаешься в терминологии.

Гугли по „single pointer”, „double pointer”, „triple pointer”, „bounds checking”, „index checking”, „pointer to array” — это поможет тебе изучить матчасть.

Мое впечатление только усиливается.

Массивы любой размерности — отлично адресуются одиночным указателем.

Только вот писать каждый раз a[i*s1+j*s2+k] вместо a[i][j][k] — и задолбательно, и замыливает глаз, и мешает пониманию у тех, кто не системный программист.

Даже простая обёртка в виде класса, когда одномерность спрятана внутри, а наружу выставлен многомерный указатель с операцией [] над ним — будет однозначно полезна.

Да и что касается сэйф/смарт-поинтеров — делать таким одиночный указатель куда легче, чем двойной (или там тройной) тоже.

Сделать на весь объект-обёртку.

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

Можно с какой-то вероятностью и в релизе проверять, например :)

писать каждый раз a[i*s1+j*s2+k]

Так никто из толковых кодерков и не пишет. :)

когда одномерность спрятана внутри, а наружу выставлен многомерный указатель с операцией [] над ним

Это показывает, что тебе надо учить матчасть. А ещё лучше — не пользуйся C/C++. Пиши на C# - он для тех, кому плевать на быстродействие. Там тебе и индексы любые с обёртками, и даже рефлекшн. :)

Это показывает, что тебе надо учить матчасть. А ещё лучше — не пользуйся C/C++. Пиши на C# - он для тех, кому плевать на быстродействие.

Красивые пузырьки пошли из лужи.

А что ты ожидал услышать? Если ты рассказываешь, что тебе нужен некий враппер, который бы скрывал одномерность — это значит, ты не знаешь стоимость навигации по массиву индексированием типа «[i*s1+j*s2+k]» из твоего примера выше. И не знаешь, для чего применяются массивы, а для чего другие структуры данных (их много разных).

А значит, нужно учить матчасть, т.к. это базовые вещи.

А кто тебе сказал, что их нужно писать? :)

Вот, как выглядят правильные медоты работы с массивами:
software.intel.com/en-us/node/502101

Можно, конечно, пытаться это всё дело темплитизировать (как, к примеру, сделали в последних версиях OpenCV) — но получится хуже, во многих смыслах. А классы — это и вовсе для любителей C#.

Классы — это для любителей сохранять простые вещи простыми. Чтобы не писать фигню типа arr[i*numColumns + j] каждый раз, когда нужен элемент matr[i][j], раз уж в программе понадобился двумерный массив, который физически будет храниться как одномерный.

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

Вот, как выглядят правильные медоты работы с массивами:

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

Классы — это для любителей сохранять простые вещи простыми.

Я и предлагаю таким любителям писать на C#. Там всё просто. :)

А C/C++ сложные языки, для эффективных решений. Для таких решений классы вокруг массивов, содержащие что-либо кроме 1) указателя на область памяти 2) размера области памяти 3) может ещё, типа элемента массива — это лишь очередной (ненужный и даже вредный) уровень сложности.

Вы предлагаете — они не соглашаются. Особенно при отсутствии у Вас аргументов, что этот уровень сложности действительно «ненужный и даже вредный».
Сохранять вещи простыми (to some extent) можно и в плюсах, если понимать, что ты делаешь. При этом плюсы, в отличие от некоторых других высокоуровневых языков, позволяют не переплачивать перформансом за абстракции.

Хочу увидеть пруфы, что вот такая матрица, хранящая внутри простой вектор, действительно приведёт к ощутимым потерям производительности godbolt.org/g/uqOu18
Пока что по асму для меня это не очевидно.

Я имел в виду потери в производительности по сравнению с использованием голого вектора, не завёрнутого в темплейт matrix.

А так-то да, ясно что при реализации операторов *, + и т.д. «в лоб» будут лишние аллокации и прочие ненужные телодвижения, замедляющие работу программы. Но то же самое касается и простых векторов, если мы захотим выполнять арифметические операции с ними.

Для решения таких проблем в плюсах существует приём, который называется expression templates (en.wikipedia.org/...​wiki/Expression_templates). В частности, он реализован в Boost.uBLAS.

Я и предлагаю таким любителям писать на C#. Там всё просто. :)

А C/C++ сложные языки, для эффективных решений.

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

Покажи мне матрицы и матричную арифметику в C#?

www.nuget.org/...​/System.Numerics.Vectors

Пиши на C# - он для тех, кому плевать на быстродействие.

В C# оптимизации делаються там где они нужны
по производительности аналогичные C++. Операции с нулевыми аллокациями и без использования GC.
github.com/...​master/docs/specs/span.md
github.com/...​ster/docs/specs/memory.md

справедливости ради можно сказать, что это появилось не так недавно на уровне фреймворка, но unmanaged код на C# всегда можно было писать и кому надо было делали это.

Это шутка была.

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

А всё остальное на плюсах проще сделать, чем на шарпе. Ты и сам это подтверждаешь:

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

могу предположить, что для замены System.Drawing — который под виндой работал через p\invoke. ну т.е. они не собираются с плюсами конкурировать очевидно в этом.

Так и есть — ты путаешься в терминологии.

А что ты ожидал услышать? Если ты рассказываешь, что тебе нужен некий враппер, который бы скрывал одномерность

Да, нужен.

это значит, ты не знаешь стоимость навигации по массиву индексированием типа «[i*s1+j*s2+k]» из твоего примера выше.

Не значит. Знание стоимости навигации не связано с собственно вопросом о необходимости многомерного индексирования.

И не знаешь, для чего применяются массивы, а для чего другие структуры данных (их много разных).

Нет связи.

А значит, нужно учить матчасть, т.к. это базовые вещи.

Тебя явно Даннинг с Крюгером из-за угла стукнули.

Знание стоимости навигации не связано с собственно вопросом о необходимости многомерного индексирования.

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

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

Мы, к твоему сведению, завели этот разговор в контексте математических операций с объектами типа матриц (ТС начал с этого). Не знаю, что именно ты тут решил назвать «навигацией», но для операций с матрицами типичен перебор элементов по меняющемуся индексу, причём очень часто не младшему. Компилятор способен соптимизировать такой повторяющийся доступ в очень эффективный набор операций, но вот заставлять прикладного математика уплощать вручную индексы — только во вред.

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

«Другая структура данных» будет заведомо хуже в случае плотного многомерного массива чисел.

Разумеется, есть случаи для таких странностей — например, сильно разреженные матрицы. Но и оптимальные структуры для них никак не будут массивом раздельно аллоцированных массивов.

В доступе типа «[i*s1+j*s2+k]» — компилятор ничего не соптимизирует.

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

В доступе типа «[i*s1+j*s2+k]» — компилятор ничего не соптимизирует.

В одиночном операторе — да, не соптимизирует. В нескольких последовательных, в цикле — вынесет в одну операцию всё, что можно.

И да, если чел знает, как правильно пользовать многомерные массивы, для него нет никаких проблем делать навигацию эффективно по любым размерностям.

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

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

Это мягко говоря позавчерашний день, матрицу нужно гранить в тайловом виде для минимизации хаотичного хождения по памяти. Индексы нужны чтобы сохранить и выгрузить матрицу в human-readable формате, все внутренние операции только в тайловом виде, прикладной математик или принимает правила игры или идёт лесом. Morton order, 1966 год. Всё остальное, о чём вы тут все спорите не имеет особого практического значения :)

матрицу нужно гранить в тайловом виде для минимизации хаотичного хождения по памяти.
Morton order, 1966 год.

На пользу далеко не всегда, а усложнение заметное.
Для примера — в numpy+scipy на него смотрели — и отказались.

Всё остальное, о чём вы тут все спорите не имеет особого практического значения :)

По-прежнему имеет.

На помню еще одну гадость матриц — транспонирование.

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

Поэтому в armdillo попытались маскимально реализовать ленивые вычисления.

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

И теперь представь тот код и ужаснись.

Чего там представлять — я BLAS и LAPACK читал. В оригинале, извините за иронию :)

Ты пару лет пишешь либы на с++ для оптимизации всех операций и вычислений и забываешь про реальную задачу.

Вот потому, спускаясь на землю, всё не так. Я беру готовое привинчивание того же BLAS. На втором шаге я беру привинчивание GPU-переходников. И только если этого всё равно не хватает, я начинаю смотреть, что не так сделано :)

Причём в большинстве случаев язык клея над всем этим — Python. Ну, тебе не нравится, так ищи переходники под Matlab :)

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

Кстати, согласно Стандарту С++ вызов Ктулху является совершенно валидным поведением при UB.

there were arts which could revive Them when the stars had come round again to the right positions in the cycle of eternity

На самом деле я пишу на C++ в надежде когда-нибудь вызвать Ктулху.
Но пока не получалось :(
Максимум вышло заставить компилятор выбросить проверку i < 10 из условия цикла: ideone.com/pcXaQk

Не уверен.
Вообще, хороший вопрос для собеседования.

Нет — слишком тривиально.

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

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

Реализовать дженерик матрицу на плюсах как раз не сложно. Я как-то для себя (не для работы, просто игрался) велосипедил STL-совместимую матрицу, хранящую underlying vector и размерности. Трудности были только с написанием итераторов для строк (включая reverse итераторы и их const-версии) — слишком много boilerplate кода получается, — а также функций удаления/добавления строки/столбца (или целого диапазона строк/столбцов). Не думаю, что такое много кому нужно.
А остальные вещи там пишутся легко.

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

Кстати вот одна из прелестей уродства с++ habrahabr.ru/post/317300

"double a[n][n] и std::array<std::array<double, n>, n> "

Если это то, как чел привык работать с многомерными массивaми — то дальше в этой статье нечего читать.
Пускай сперва подучит даже не C++, а просто C — прежде чем писать о них.

И при всем этом чел смог найти решение одной из фундаментальных проблем. Я не в курсе разумных практик в С++, но то что он накопал — это дествительно круто.

1) Я себя не позиционирую как спеца в процах, и вообще не знаю ассемблер. Позиционирую как человека, который слегка читал в теории и слегка применял на практике многопоточность.
2) Стратегии отличаются для высокоуровневых языков, которые в 90х не были распространены. Для тебя уже писал, что если берешься за С++, то не боись делать все ручками. А если боишься — то не трогай С++.

Смотрели на Julia? Там они в коробке.

тоже поставил, хочу напилить для нее свой тест

Юля — это игрушка.
Там тебе советовали Erlang — стоящая штука.
При всех недостатках Питона — у него есть большой плюс — к нему куча официальных биндингов для тяжолой математики. И даже для символьной.

Мне нравилась Вала у нее какоето мрачноватое будущее :-(

Если тебе чисто заменить матлаб то скорее всего только Питон.

Ты немного загнул. В Питоне далеко не все так печально как в плюсах: довольно прямая реализация вполне консистентной идеи. Кроме того его суппортят конкретно для математики конторы типа Гугля и Интела.

А Юля — это типа поделка двух с половиной студентов. Идея довольно неплохая но реализация — никакая.

Разговаривал с одним из разработчиков.

Ты совсем напрасно сбрасываешь со счетов Питон.

У нас свои легкие потоки с блекджеком и своими механизмами синхронизации....

Сначала уточни — попарно это значит каждая с каждой из этих 30, или каждая из левого набора с каждой из правой, или каждая из левой с соответствующей из правой? Формулировка недоопределена.
Но вообще, при таком объёме я бы не параллелил это — затраты на межпроцессорную синхронизацию запросто превысят цену всего комплекса операций даже для самой дорогой из этих интерпретаций.
Рассмотрение стоит начинать с ситуаций типа
1. Не 30 матриц с каждой стороны, а миллион. Тогда задача превращается в легко параллелящиеся независимые действия.
2. Матрицы размера 1000*1000 и выше. Вот это уже серьёзная постановка, и тогда идём смотрим на реализации типа «параллельный LINPACK по MPI» и то, как именно они там реализуют матричные операции. Там эти операции превращаются в блочные (каждая матрица режется на строчные или прямоугольные блоки) и обмен результатами операций с блоками с соседями по сетке операций. Таким образом спокойно растягивают даже операции с матрицами с миллиардами по одному направлению, лишь бы диска хватило (ну и узлов для расчёта — на HPC на такое требуются тысячи узлов, если хочешь вменяемое время).

И получаем известную гифку про WoT.

Гифку не знаю, но идею, кажется, понял.

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

На такую задачу — да. Хотя, если она исполняется ну очень много раз в секунду и допускает параллеление, можно запускать независимо на разных ядрах. Но это я кэпствую.

31 можно увеличить до числа, когда в кеш первого уровня данные не влезут. Или размер матриц до 20-30.

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

Кроме кеша 1 уровня есть ещё SIMD-конвейр, и у каждого исполнителя есть свой регистр под конвейр на несколько элементов. То есть не кешем единым.

А ещё есть кеш 2 уровня, и он отдаст данные очень шустро, если только ты не натравишь РАЗНЫЕ ядра на ОДИН И ТОТ ЖЕ адрес памяти.

Понимаешь, для многоядерного проца есть огромная сложность поддерживать актуальность кеша. Он не понимает, что ты делаешь с данными. На такой скорости он не способен «понимать», всё что он делает — это БЛОКИРУЕТ ассоциативную дорожку кеша, и тем самым мешает другому ядру обратиться в те же адреса. Мешает — значит заставляет ждать. Если при этом размер кеша превышен, данные начинают ещё и с оперативой свопиться. И кстати говоря, видео-кодеки так и не могут эту проблему побороть, для них скорость линейного свопа по памяти критична.

Но скорость свопа по памяти тоже знаешь ли не узенькое место, она огромна. ЕСЛИ ТОЛЬКО ты распараллелил данные. Процессор кроме того что выполняет задачу, ещё имеет блок предсказания переходов. Пока ядро пилит одну задачу, кеш L2 уже подтягивает память на следующие команды. ЕСЛИ ТОЛЬКО ты написал в коде не for по циклу из 50 оборотов, а ПОСЛЕДОВАТЕЛЬНОСТЬ из 50 команд. Да, для человеческой логики звучит глупо, в коде выглядит монструозно, но процессор — это просто быстрый калькулятор. Худшая для него инструкция — «ЕСЛИ». А вот когда есть прямой поток, конвейр — он его колбасит сотнями миллионов в секунду и даже не греется по этому поводу.

Ради интереса, просто проведи эксперимент: скомпиль прогу которая перемножает в цикле некие пару массивов (предварительно покормленные случайными числами). А потом то ж самое распиши в последовательность команд с чётко заданными смещениями и УКАЗАТЕЛЯМИ (а не индексами массивов). Либо удостоверься что компилятор не делает проверку на выход за границы массива — помимо 2 сравнений, это ещё и 2 условных перехода, то есть тех самых мерзопакостных «если» которые срывают конвейр — и это на каждое обращение к каждому массиву!

Либо удостоверься что компилятор не делает проверку на выход за границы массива — помимо 2 сравнений, это ещё и 2 условных перехода, то есть тех самых мерзопакостных «если» которые срывают конвейр — и это на каждое обращение к каждому массиву!

Современные процессоры достаточно разумно с этим обходятся, и после нескольких первых попаданий «не туда», если они будут, маловероятные условные переходы не отработают.
А ещё им можно помогать с этим (на x86 >=Core, переход вперёд всегда изначально unlikely, а назад — likely; исполнение уже может уточнить это для конкретной команды). Если пометить как unlikely для компилятора, он даст код, что даже со старта не будет тормозить на этих проверках.

Понимаешь, для многоядерного проца есть огромная сложность поддерживать актуальность кеша. Он не понимает, что ты делаешь с данными. На такой скорости он не способен «понимать», всё что он делает — это БЛОКИРУЕТ ассоциативную дорожку кеша, и тем самым мешает другому ядру обратиться в те же адреса.

Да, для модифицируемых данных эта проблема в полный рост.

GCC имеет функцию __builtin_expect, которую можно использовать, например, как

#define likely(x) __builtin_expect(!!(x), 1)

это будет подсказкой типа «я считаю, что этот вариант вероятен, и рекомендую по умолчанию идти по нему». Дальше пишем в if

if (likely(p == this_task)) {
 ...
}

Для каждой архитектуры это транслируется по-своему. Например, в последних x86 переход назад — likely, а вперёд — unlikely; Pentium4 — перед командами условного перехода ставились однобайтные префиксы; MIPS, Power имеют специальный бит в условных командах.
Кроме того, это также может транслироваться не только в переходы, а в решения типа «эту переменную выселяем на стек».

Далее у процессора есть блок предсказаний. Подробности надо читать в соответствующих доках, но у последних x86 это выглядит так:

* есть кэш предсказаний, индексируемый последними k битами адреса команды условного перехода; обычно кэш минимум 2-путевой;
* хранится история N последних переходов (например, N до 16) и определяются циклы длины до N, из которых берётся 4 предсказания: совсем не, скорее не, скорее да, совсем да.

а на cuda это добро в лоб не ложиться? мне почему то кажется что должно

Пока не учитываешь время на передачу данных, вроде быстро)

Ага. Я начинаю понимать, откуда идея про лёгкие треды.

C = pairwisemul(A, B) + constmul(k, A) + ...

pariwisemul(A, B):
	for i in 0..30:
		go(R[i] = A[i]*B[i])
	wait_for_all_threads()
	return R

Алгоритм «векторизуется» по типу матричных операций в Матлабе, отдельные операции распараллеливаются по независимым элементам. Структура формулы используется чтобы убрать явную синхронизацию между тредами. Хорошие операции идут параллельно, всё остальное идёт в один поток. Тредов очень много но они короткие.

N:M scheduling, пул тредов, Go, boost.fiber — это всё оно. Успех практически полностью зависит от задачи. Библиотека чем проще, тем лучше, и они все будут почти одинаково работать.


for i in 0..30:
go(R[i] = A[i]*B[i])

не надо это параллелить

Было дело, векторизовал перемножение векторов на SandyBridge. С SSE (4 пары флоатов за раз) выигрыш был в 2.5 раза по сравнению со скалярным вариантом, при переходе на AVX (8 пар) прироста уже почти нет, упирается в память

Ага
Там было по сути перемножение вектора 200 на матрицу 200×80 или около того (подгонял размер чтоб делилось нацело на 4 или 8)
Промах в L1 и привет

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

Вроде бы начиная ещё с Core2 у них логика оптимизации не меняется? (Горчак тут недавно писал)

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

А если это даёт нужную скорость программы, почему бы и нет?

A[i], B[i] — матрицы 10×10 (или больше) по условию.

А же здесь не столько пытаюсь решить конкретную задачу, а хочу послушать кто и что предложит

Это понятно. Чтобы распараллеливание дало результат, даже на лёгких тредах, код каждого треда должен быть не слишком коротким. И не слишком длинным. Перемножение двух float’ов нет смысла параллелить, двух матриц 10×10 — возможно уже есть.

Может, ты пытаешься получить неверный ответ? А то, что все говорят, что не нужно такое параллелить, не слышишь?

Из того, что я помню, быстрее всего параллельность работает на CUDA.

Но перед тем как ее заюзать нужно 100 раз подумать, стоит ли гонять данные RAM <-> Video RAM.

Я смутно припоминаю куду, но когда я ее колупал (2012) уже было очень много прикладных и высокоуровневых либ.

Насколько мне известно рекурсивные операции на матрицах, это то чем КУДА рвет все остальную многопотоковость на х86.

Сам лично я написал сортировку (не помню пузырька или пирамидальную) на КУДЕ, и она уделала std::sort в 2.5 раза на 1000000 рэндомных эл-тах. (И это был i5 против какой то ужасной видухи за 25 баксов).

Заморачивать с ужасным (как по мне) синтаксисом КУДА практически не пришлось, я сходу заюзал вот это — (docs.nvidia.com/cuda/thrust/#abstract) что то типа объектной настройки аля stl.

Один поток на одном ядре.

На самом деле там все на порядки сложнее. Еще играет роль длина и «ширина» конвеера. Тоесть i7 будет быстрее i5 при прочих равных. А серверный Xeon будет быстрее десктопного аналога при прочих равных. Кроме того последние АМД тоже смотрятся очччень даже ниче на фоне десктопных интелов. Из обычных процов наиболее дружелюбны к распаралеливанию МИПС-ы — у них самые низкие накладные расходы на синхронизацию, но для дома это непрактично.

Хороший выбор, и зимой на отоплении можно съэкономить будет.

Стадо ядер зручно для звукорежисерського софта, там різні плагіни дуже активно використовують багатопоточність. Принаймні всі ядра мого Phenom Х6 дуже непогано навантажувало.

На самом деле твои ядра нагружены синхронизацией плагинов, а не собствеенно полезной работой.

Чому це? В мене в проекті припустимо 10 доріг, на кожній по купці плагінів, деякі з яких підтримують багатопоточність.

Мне так подсказывает интуиция. На самом деле обработка звука это довольно легкая задача, и так просто загрузить одно десктопное ядро не получится. А вот загрузить кучу ядер синхронизацией — плевое дело.

Впринцыпе я могу быть неправ ибо не знаю твоего контекста.

Так АМДшный проц на 8 ядер 16 потоков, столько же TDP имеет.

Я слышал много хорошего о этом процессоре в контексте ноутов, но как он поведет себя на десктопе — без понятия. У меня SkyLake.

Intel TBB посмотри они как раз под такие задачи зело точатся.

Надо признать с начала её появления на свет она весьма монстровидна была (по моему нескромному мнению) впрочем возможно это как из-за её заточенности скорее под такие задачи «перемножить матриц на ххх потоках».

Во первых надо придумать оптимальное представление матрицы, а это одномерный массив из 100 елементов. То есть у вас ваш набор будет int64_t[3100], что совсем немного. Зато мининизирует cache miss’ы.
Затем вам нужен пул тредов, поверх которого будут запускаться джобы, куда мы будем передавать указатели на начало матрицы А и B.

попарно перемножить, перемножить поэлементно, выполнить какие простые поэлементные операции

Результат положить в очередь и когда все джобы отработают — смерджить в одну матрицу.

Детская задача на самом деле. И никаких вы*бонов с технологиями не нужно, можете хоть на pthreads сделать.

Можно попробовать разработать лок-фри алгоритм. Тогда мьютексы непонадобятся.

Навряд. Тут скорее нужно уточнить какое именно понятие ты вкладываешь в легкие потоки. Если чисто ко-роутины — то тут рулят лисп, схема, и прочие языки умеяющие замыкания, а также setjmp()/longjmp() в контексте С.

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

Я о другом лок-фри ...

А какое тут другое?

Да никаких мьютексов, просто в очередь складываешь результат и все.

А что STL стал thread-safe уже?

а что нет в C++ реализаций thread safe очередей? Я STL кстати даже не упоминал

Есть, включая буст, но часто лекарство хуже болезни.

Попарно перемножить и тп. — это фактически замкнутая задача на на 300 элементов. И таких задач у тебя 481шт.
Как сделать НЕправильно: пойти циклом.
Как сделать правильно: РАЗМНОЖИТЬ данные. То есть создать копии, с целью получить 481 параллельную задачу со своим адресом памяти и потоком SIMD-инструкций. То что каждая задача будет работать со своей памятью, позволит выполниться очень быстро. Копирование линейного данных — тоже не ахти какая жуть. Скормить 384 Кб видяхе — говно вопрос.

И главное, никто не заставляет тебя ждать результат. Отправил — и верь что он готов, давай следующий набор. А если набор зависит от предыдущего — вероятно надо программить полностью только под видяху и держать данные только там на большом участке потока (пока в него не будет вмешательства).

Код ВСЕГДА будет зависеть от алгоритма. Малюсенькое «ЕСЛИ» в поток — и это уже катастрофа для параллелизации.

Смотри дальше: после того как первый этап пролетел, ты ж не думаешь, что составление матриц и поэлементный пробег будешь делать с теми же данными? И на с++, с пробегом по массиву, ага? ФИГВАМ! Ты СНОВА готовишь поток задач, например ЗАБЫВ о старых копиях данных и записывая поверх в памяти видяхи. И делаешь это не for (i=0....), а на ассемблере, указывая СМЕЩЕНИЕ в памяти куда ты положишь результат. Либо если есть фреймворк нормальный именно под SIMD, который в итоге скомпилит ассемблерный алгоритм.

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

Ну вот и приехали к раскрытию задачи.
У меня не «завышенное ЧСВ», а возможно непонимание задачи, потому что ты её не раскрываешь. Я не спорю, что в части теории — это твоя степь, и мы в неё не лезем. Потому тебе и приходится разжёвывать «очевидные» вещи. Но в части аппаратной оптимизации — ты просто не хочешь учить мат.часть. Суровую РЕАЛЬНОСТЬ вместо 10-этажных абстракций.

Между понятностью и скоростью — огромная пропасть. Потому приходится писать комментов столько же, сколько и кода. И это в прикладных вещах.

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

Так и здесь — к чёрту интуицию, она тебе бершет как сивый мерин. Но лишь до тех пор, пока не попробуешь понять, а что именно делает процессор. Про старые добрые биты и байты. Про параллелизацию, и как ядру процессора удаётся делать 6 задач в 1 такт. Про твой квадратный корень, который ты понятия не имеешь сколько времени занимает, пока не возьмёшь примерное преобразование, которое выполнится с приемлемой точностью раз в 40 быстрее.

Чтобы ты понимал, твой мозг работает на частоте до 150Гц. Не гигагерц, а герц. И вся его скорость — исключительно в пралеллизме. И поверь, следить за движущимися объектами он может просто таки прекрасно. А параллельно — ещё и управлять собственным, ну и по мелочи регулировать химические процессы и поддерживать условия реакции до десятых долей градуса. И сколько бы ты не рассказывал «ДАЙТЕ-ДАЙТЕ» ещё один уровень волшебной абстракции — абстракциями достигается упрощение алгоритма (и не всеми, а только удачными). Скорость же достигается КОНКРЕТИКОЙ, и построением собственных ШАБЛОНОВ свойственных конкретно твоему алгоритму.

Ничего универсального и быстрого — не бывает.
А чтобы уйти от абстрактых рассуждений, и чтобы не показалось что мы тут ЧСВ меряемся — возьми конкретный маленький пример: вычисление расстояния между двумя точками.
Задача: с приемлемой точностью (допустим, градация 0...255см) рассчитать расстояние. Как можно быстрее, считай что тебя убьют если ты не справился. И подумай, а сможешь ли ты на следующей итерации скорректировать результат. Если да — тогда тебе большая точность не нужна!

Так в этом же вся мета-задача. Оптимизировать алгоритм без конкретики — невозможно, чем более он абстрактен — тем больше де-факто ненужных (тебе) действий произведёт процессор на каждой итерации.

Задача оптимизации — обострения противоречия между скоростью, точностью, и ленью. Лень оптимизируется первой, либо никогда. Ты же хочешь похоронить месяцы в изучении документации к поделкам кого-то (угадай, мастер ли он в изложении смысла), вместо того чтобы искать короткий путь — сказать процессору что ты от него желаешь.

Хочешь скорости — бойся абстракций. На абстрактных моделях ты будешь делать всё остальное, например диалоги с юзером, API, обработку исключений и т.д., весь код который исполняется РЕДКО (в машинном понимании). Но АЛГОРИТМЫ — то что проц исполняет сотни миллионов в секунду. Здесь нужно чётко писать: А, Б, команда, куда результат. И не стесняться декомпилить чтобы увидеть, что именно тебе натворил компилятор.
Простейшая задача — список. Для тебя очевидно, что кусок данных можно положить в список, и будет ОК. Но это не так для проца, у него НЕТ списков, а есть — адрес и смещение. И на каждом обращении он должен туеву хучу времени выяснять, а где же в этом списке конкретный адрес массива, а где конкретное смещение, а не выйдет ли оно за границы, а потокобезопасно ли это, а не заблокировать ли чего-нибудь чтобы кто другой не влез — и это всё в малюсенькой команде обращения к одному элементу, а у тебя в каждой строчке кода таких по 3-4.

Правильную модель я тебе уже объяснил — worker. Когда у тебя есть малюсенькие независимые объекты, которые несут в себе и данные (не ссылки, не методы получения, а конкретные цифры — де-факто указатель на адрес памяти) и выделенный адрес памяти под результат. Есть и другие реализации, но суть одна и та же: КОНКРЕТИКА, без нелинейных операций. То есть без ветвления алгоритма.

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

Ну так позадавай на stackoverflow.com и отпиши потом сюда самое полезное, что там скажут. И нам почитать полезно будет что-то новое.

Так есть же и русскоязычный раздел ru.stackoverflow.com

Там не приемлют неконкретные вопросы. С неконкретными вопросами — только Лор, наверное ...

Боюсь, что сами знания в этом вопросе давно изучены в 60-е, и ничего нового ты не откроешь. Могу лишь констатировать, что чем больше дерьма «для облегчения» пишется — тем больше лет нужно похоронить на его изучение, и всё равно когда нужна скорость — вернёшься к азам.

Это та область, где за 5 лет меняется всё, а за 100 лет — ничего. Ты даже для себя не сможешь создать вменяемую библиотеку, а всё что будет работать — это снипеты. Кусочки алгоритма под копипасту.

Оно настолько же незыблемо, как армейский устав. И только когда задача становится массовой, появляются готовые решения в виде движков под конкретные задачи. Там где КОНКРЕТНУЮ работу уже кто-то выполнил за тебя. Под КОНКРЕТНЫЕ алгоритмы. А когда алгоритм свой — лучше потрать 2 месяца на написание кода, чем на изучение чужой свистопляски. Как минимум в тех случаях, когда не можешь эту свистопляску БЫСТРО ПРОВЕРИТЬ в эксперименте, ничего не изучая а взяв конкретный пример.

Интринсиков нужных ещё нет?

Пока что снобизм только у тебя, если тебе в простом прямом вопросе мерещатся черти.

Ты хочешь AVX. Если не использовать готовые решения (а тогда AVX или нет — вопрос внутренностей самого решения), то остаются или интринсики, или автовекторизация. Последнее — дело компилятора. Для собственного написания — интринсики. Что тебе не так и что именно ещё надо объяснять?

Ну в Go хорошо реализованы легковесные потоки, очевидно же. Если рассматривать концепцию лёгких потоков на уровне языка, в Lua очень хорошая реализация коротин. В любом случае, легковесные потоки будут увязаны с реализацией в языке замыканий и передачи контекста исполнения.

Горутины, вроде, пока лишь теоретически умеют работать с ядрами в отношениях M:N. А практически, работают максимум в отношениях М:М. В общем, без особых отличий от тредов.

Хотя, может быть конечно фичей «облегчённый контекст» (по-сравнению с тредами) — что должно облегчать/ускорять переключение между горутинами. Но надо тестить...

П.С. И да, использовать эту хрень в C/C++ должно быть несложно — наверняка уже есть куча библиотек под разные платформы. Но включать в стандарт языка, это будет напрасно.

Всё равно непонятно, что ж ты такое чудишь. Как по мне, ты поленился описать задачу в масштабе (потому что она явно содержит противоречие), и веришь что кто-то вместо тебя догадается как «замять» противоречие вместо того что сделать строго обратное: обострить.

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

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

Что нужно:
1) Параллелить задачи крупноблочно. Обработать сотню одинаковых значений — это не крупноблок, это конвейр.
2) Держись подальше от операции «ЕСЛИ», то есть ветви алгоритмы по-минимуму в критических задачах. Всё что можно — делай линейно.
3) Хорошо если добрался до ассемблера, и знаешь на чём это всё в итоге взлетит. Потому что если чё не так, перекомпиляцией не отделаешься.
0) А на кой ляд тебе эти double приснились? Целочисленная логика тебе понравится своей скоростью. А вот от плавающей точки — держись подальше. Или думаешь просто так графические процессоры всё втупую на целочисленке считают?

Графический ускоритель — это конечно хорошо. Но не так хорошо, как может показаться. Слишком уж задачи для него нужны характерные — малый цикл, независимые БОЛЬШИЕ массивы данных, конвейр.

Судя по твоему описанию, параллелизации поддаётся лишь небольшой этап, а далее всплывает необходимость объединять. СЛЕДОВАТЕЛЬНО это задача не под параллелизацию, а под оптимизацию конвейра. Вплоть до того, что ты в массивах, подаваемых на поток, предусмотришь место для результата в аккурат рядом с исходными данными, чтобы не метаться. Не c[i]=a[i]+b[i], но a[2]=a[0]+a[1], и вот массив этих самых «а», то есть микро-задач, ты подаёшь командами в линейный поток (без итераций, без циклов, можешь задать ему кратную размерность). А вот уже ФОРМИРОВАНИЕМ этого потока вполне может заняться и другое ядрышко. Вплоть до того, что вот эти самые векторы будешь кормить на GPU, а CPU будет строить очередь.

Идеальный вариант — если ты потом не нуждаешься в разгребании результата (большом перестраивании структур данных), а можешь использовать сырой поток обработанных данных для формирования нового потока, после чего просто выбросить его единым куском. Но это означает КОПИРОВАНИЕ данных, а не манипуляцию ссылками и адресами.

Я не знаю, чему тебя учили и ты учился, но просто представь себе повара, который за каждой картофелиной или щепоткой соли должен сбегать в магазин, притом каждый раз в разные. Как ты представляешь себе 8 поваров, готовящих это же самое блюдо, и ждущих друг друга чтобы синхронизировать действие? Я предлагаю, чтобы если блюдо простое (а 200 значений — это кот наплакал), но их много — у тебя был один повар, которому ты на конвейре подаёшь одновременно все ингредиенты набором, и так каждый раз. А отдельный работник формировал эти наборы, отдельный — отделял результат на готовое блюдо от кучек мусора и подавал его в заказ или следующему повару.

Твоя проблема — в дальних данных. И ты никогда не возьмёшь планку скорости, равно как и не получишь паралеллизма, пока не научишься формировать задачи под конвейр, а уже целые очереди (там где возможно) — разделять. Конвейр — это инструмент № 0 для скорости, и никакая паралеллизация тебя не спасёт, если ты его сломаешь.

Напомню, еще на EC 1060

Напомню, ЕС1060 не имело таких проблем с памятью, как сейчас — когда процессор в ~200 раз быстрее оперативки (в задачах доступа по произвольным адресам).
А ещё там не злоупотребляли многоядерностью (ну слишком уж дорогая была).

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

Задачи такого уровня никуда не делись. Просто их не дают в Украинду на аутсорс.

Хочешь скорости — формулируй приказ предельно чётко. А ты как хотел, написать CSS и чтобы тебе 60 fps каждый чих рендерился? Тогда тебе в Гугыл.

Уже неоднократно описывал все прелести этого инструмента, но он под JVM или .NET. На сколько понял тс интересуется чем-то что по ближе к железу, не дальше C++. Если нет — то ещё неплохо глянуть на Erlang — Akka оттуда «вдохновлялась». А вообще ходят легенды что эта вычислительная модель была реализована ещё в Smalltalk а вместе с ней и «правильное ООП».
По JVM в принципе — смотреть в сторону ForkJoinExecutor (для task-based параллелизма) и ThreadPoolExecutor (для data-based соответственно).
И последнее, но то с чего неплохо бы начать — Actor model и coroutine — это две принципиально разные вычислительные модели под разные задачи. Как параллелизм и конкурентность — разные вещи.

На сколько понял тс интересуется чем-то что по ближе к железу, не дальше C++

Ну он кресты лучше всего знает, потому и пытается подобрать инструменты по пути наименьшего сопротивления. Хотя я бы таки посоветовал потыкать палкой и шарп и жабу. По скорости нормально написанного кода в вычислительных задачах они от крестов не отличаются от слова совсем. Я в коментах статьи про котлин на ведроиде постил ссыль на гитхаб где сравнивал c#,f#,java,scala,kotlin,go и c на реальной задаче фильтрации сигналов. github.com/doomviruz/PerfTests

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

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

Со скалой как раз понятно.
Например for (i <- 0 to 100) {}, это на самом деле Range.foreach с лямбдой и доп оверхедом. Переделать в while и скорость сравнивается с джавой. C 2008 года тикет висит по этому поводу

о, сенкс, поправлю и посмотрим
не ожидал такой подлянки в простом вроде бы коде

Так-то оно так, но я с уверенностью могу добавлять только то с чем сталкивался сам, а у меня довольно специфический круг задач. 95% народа они будут неинтересны, да и непонятны без привязки к предметной области.

Язык выбирается исходя из того, что сам знаешь, а не из того, что на 15% быстрее работает. То, что знаешь, сможешь оптимизнуть. А в том, что не знаешь, заюзаешь неоптимальную конструкцию.

та это нормально. в каждом ЯП такие фокусы припрятаны.

помнится легендарное, как крестовики тесты писали.
Для джавы «ab» + «cd», в цикле. и конечно с выводом — какая ж вашая джава тормозная.

они ж привыкли что + переопределен. а про то что в Джаве, если перфоманс важен, такое надо делать StringBuilder’ом — не знали.

в каждом ЯП такие фокусы припрятаны.

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

попробовал
да, прирост скорости есть, и ощутимый, но до жабы все равно еще очень далеко...
было 390 секунд, стало 308, а жаба и шарп дают 170
видимо еще где-то есть неочевидные для «нескалолаза» вещи

array.sum и подобные вещи тоже. Я посидел с профайлером, посмотрел горячие методы и ускорил вдвое.

дык закоммить свои правки
и кстати — каким профайлером пользовался?

Я ж не стандартную библиотеку фиксил

Стандартным Flight Recorder
docs.oracle.com/...​leshoot/tooldescr004.html

Я ж не стандартную библиотеку фиксил

лень pull request сделать?))

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

хм, я тупанул, и сделал замер с запущеной отладкой
на самом деле после замены for на while получается 199 секунд, что уже гораздо ближе к лидерам

На 8 ядрах и 8 потоках.

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

Внутри — да, у меня он именно что хорошо на большом объёме в opencl распараллеливается

Нифига подобного- у меня честно выкидывает эксепшен. Видяха та же. Винда 10.

Ну не знаю, под линухом не сижу, ибо нет там студии. С виндой 8.1 тоже не было проблем.

В смысле код кернелов?

так сделай pull request для matlab
только все-таки прогони цикл 1000 раз и для матлаба и для go, тогда можно будет привести твой результат к остальным замерам привязавшись к результату go

Вот ДОУ предлагает сам в боковой панели похожих топиков:
dou.ua/...​e/?from=hover-news-widget

Как раз в ту — прямой ответ на Ваш вопрос:

Кстати, а вот что насчет этого:
www.dossier-andreas.net/...​ture/pipe_and_filter.html
суть в последовательном применении алгоритмов, меняющих данные. Например, обработка видео у робота, или скана у распознавалки текста.
en.wikipedia.org/wiki/Actor_model
суть в том, что важные куски системы выделяются в отдельные модули, не имеющие общих данных. Модули кидаются друг с другом неблокирующими сообщениями. Если есть длинные цепочки событий, превращается в ад и стейт машины.
Есть уже либы, что это реализуют?

И сколько раз это надо сделать (сколько наборов данных)?
Какое количество векторов в одном наборе данных?
Размер вектора = 20 * sizeof(int)?
Сколько оно бежит на одном ядре?

Запустить 8 процессов для разных видео.

Есть 3 варианта решения прикладных задач:
1) Написать на Питоне/Шелле/ВставьСвое
2) Написать на C/C++, это займет в разы больше времени, чем 1
3) Параллелить на С/С++, это займет существенно больше времени, чем 2, и потом прийдется долго выгребать повисания
Серьезность решения, в идеале, должна отвечать серьезности задачи

20*100-200 маловато для GPU
да и для 8 ядер тоже

Имхо, векторизация + опенмп тут максимум, куда стоит соваться

Обобщенно врядли получится. Сейчас выбор большой, включая HPX для распределенного запуска рабочих потоков на других сетевых машинах stellar-group.org/libraries/hpx. Можешь попробовать software.intel.com/...​/intel-parallel-studio-xe — тебе должно понравиться, не знаю, есть ли там трайал для персонального пользования.

Если раскидывать по стандартным потокам то тормозит на синхронизациях, если в одном потоке, то 1 ядро рабоатает только,

Корутины aka green threads никак не решат проблему синхронизации. И не помогут распараллелить. В них нет ничего сложного, но у них очень специфическая область применения. Когда «треды» нужны а параллельность нет.

c9x.me/...​icles/gthreads/code0.html

Есть некоторые вектора наблюдений. Из около 20. Есть некоторый набор операция над ними, в том числе и pdist. Торетически это все легко распараллеливается, но размера SIMD мало.

Тут надо смотреть на накладные расходы. Передача данных из CPU->GPU->CPU — это основная статья расходов как у OpenCL так и у ComputeShaders, т.е. заряженая числодробилка должна делать работу дольше, чем передача данных туда и назад. Если это очень короткие работы, то используй gcc autovectorization, чтобы C’шный код красиво ложился на SIMD: gcc.gnu.org/...​ee-ssa/vectorization.html и многопоточность — должно дать хороший результат. Возможно неплохо будет смотреться использование многопоточности через OpenMP, как надстройку над компилятором — во многих убунтах оно идёт по умолчанию с gcc ужe: bisqwit.iki.fi/story/howto/openmp — так что проблем с надстройкой быть не должно — почти тоже решение, что пул тредов.

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

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

Как я могу их привести, если ещё не знаю, что они выживут и станут определяющими? Читай внимательнее :)

Прошу перестать тормозить, или я закрою ветку. Изобретения есть, и про большинство мы знаем, но не в состоянии оценить, какие выживут как полезные.
И это показывает практика последних 50 лет IT и 150+ лет развития техники :)

конечно возникают.

попытки решить проблемы описанные Алексеем предпринимаются постоянно.

Вот например:
Intel: Larrabee, Itanium

А насчет «легких потоков», файберов и т.п. — то обычно программисты отождествляют удобство работы с железом, за то что свойства железа можно обойти, улучшить программно.

И получаются обсуждения, типа:
И сколько FLOPSов выдает твой код? А вот мой будет выдать на 30% больше!

если у железа нет каких-то возможностей, то их никак нельзя использовать.

но программисты верят что можно.

и пишут, или читают об этом использовании того чего нет в железе в фразах:

Ну в Go хорошо реализованы легковесные потоки, очевидно же.

то есть путают — флопсы с О большое :)

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

Можно в Го написать класс matrix и написать так:

Неможна, це ж «матан». golang.org/doc/faq#overloading

Якщо хочеться нормального Сі або С++, то раджу подивитися на Rust. Хз чи є там все, що тобі потрібно.

Вообще, судя по местным апологетам, обещают (в каком-то будущем). Но из-за тупизны языка это делается не библиотекой с переопределениями операторов, а встраиванием в сам язык.
Ну или писать именами функций —

c := a.AddCopy(b)
Но у Го есть куча других минусов в сравнении

про Го, Эрланг, нужно просто понимать что:

легкие потоки там дают выгоду, потому что есть такая давно придуманная штука — DMA. сам использовал, в 90ых :)
И когда задача ПО — обрабатывать тьму операций I/O — незачем использовать тяжелые, затратные средства CPU переключения потоков.

А вот если мы возьмем какие-то перемножения матриц, т.е. где DMA никак не поможет, потому что должен трудиться ALU, то тогда никаких преимуществ у зеленых, легких потоков перед честными не появляется.
причем это видно даже не на уровне алгоритмов, а на на уровне самого железа.

В целом неудачные AMD FX в некоторых, особых тестах, показывают работу на уровне Intel.
Потому что пусть хоть и «кукурзных» но все же 8 целочисленных ядер у 8300. а не 4 с гипер трейдингом у i7.

Есть там перегрузка операторов?

это вообще оффтоп.

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

попытки решить проблемы описанные Алексеем предпринимаются постоянно.

Вот например:
Intel: Larrabee, Itanium

Я говорил в более общем смысле. В случае же описанной тематики интереснее посмотреть на ранние попытки GPU (это сейчас мы имеем NVidia+ATI, а раньше был десяток, и те же S3 долго неплохо шли).

Itanium — занимательно, что его вообще вспоминают сейчас :)

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

Это неизбежно. Софт гибче надо порядки, и надо этим пользоваться.

Но и обратное есть (обновил процессор — то же самое стало работать вдруг в 2 раза быстрее).

Itanium — занимательно, что его вообще вспоминают сейчас :)

упомянул, для примера что проблема известна, а вот решить ее не так просто даже вбухивая в ее решение миллиарды.
погуглил — На Itanium решили потратить еще 10 000 000 000 долларов — 2006 год — www.ixbt.com/...​hard/index.shtml?05/45/69

и поэтому сомнительно что ее можно решить классным plain С кодом лежащим на гитхабе.

Но и обратное есть (обновил процессор — то же самое стало работать вдруг в 2 раза быстрее).

да. и О большое — тоже важно.
пыхери знают, по замене 5ой версии на 7ую :)

Itanium

так его вроде еще продолжают выпускать

погуглил — На Itanium решили потратить еще 10 000 000 000 долларов — 2006 год —

Я в очень многом не понимаю Intel, и это тоже пример. Вообще, такое впечатление, что именно та команда, которая планирует развитие процессоров на идейном уровне, у них состоит из кидателей монеток наугад. (Да-да, пусть Чижденко ещё раз скажет, что я сноб.) Каждое решение рассчитывается даже не на ход, а на пол-хода вперёд. Затем уже нижний слой начинает проявлять чудеса изобретательности в реализации безумных идей вождей. Но в случае x86 это ещё как-то проходит, пусть и со скрипом, а Itanium даже это не спасло, и Rambus от этого не стал работать.

Поэтому я те миллиарды вообще не считал бы показателем. Может, это был метод списать расходы :)

пыхери знают, по замене 5ой версии на 7ую :)

Я не в курсе. Но верю, в обе стороны :)

Какая команда маркетологов зарезала и почему, например, что сначала сделали одним расширением rdrand, а затем другим — rdseed? Маркетологи вообще таких слов не знают.
Какая команда маркетологов придумала дебильный стек для FPU?
Какая команда маркетологов не допускала cpuid/аналог аж до пентиума?
Какая команда маркетологов придумала, что OF за пределами младшего байта Flags?
Какая команда маркетологов расширила rcl, rcr на сдвиг на несколько бит?

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

«... Гениальный человек может быть так же неразвит, как последняя бездарность. Это очень важный момент!..»
А. Пятигорский

Маркетологи есть разные и вполне могут знать оное лучше большинства из нас тут.

Да. Но когда, например, маркетологи требовали сократить байт до 6 бит при разработке S/360 (для совместимости с существующими машинами) — это было понятно, хоть и недальновидно.
Но если бы они потребовали 7 бит — это была бы уже глупость маркетолога. А если бы кто-то потребовал 9 бит — это была бы глупость технарская.
Описанные решения Intel именно из серии 9-битного байта.

В общем, не зная деталей в Интеле мы угадать не сможем.

Конкретные имена — да, не можем. Характер их деятельности — вычисляется.

Я не в курсе.

да, за всем в айти не уследить.
наглядно вот, для эрудированности будет достаточно :)
www.symfony.fi/...​rks-php-56-hhvm-and-php-7
там еще и HHVM, то есть движок от Фейсбука, выросший с транспайлера HipPop.

Да, красивые графики. Непонятно, в каком именно месте улучшили алгоритм, но пусть будет тут :)

подробные описания есть в интернете.
но это уже если интересуетесь миром пыха.

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

мне вообще непонятно, как за столько лет этого не было сделано.

точно так же как и вам непонятно "

Какая команда маркетологов ...
"

Технари частенько преувеличивают свои возможности как комьюнити и в своих профессиональных областях.
Человеки же...

Синхронизации ручные или openmp с его же барьерами?

А также как вы работаете с OpenCL, есть-ли уже удобные IDE для этого с отладкой, профилированием и подготовкой кернелов для использования.

Я, кстати, практически полностью отказался от OpenCL и перешёл на OpenGL ComputeShaders, они гораздо ближе к CUDA, чем OpenCL и универсальнее, и latency запуска задачи минимальнейшая в отличии от OpenCL.

А красивыми примерчиками не поделишься?

malideveloper.arm.com/...​mulation-compute-shaders

А еще и удобной средой для написания оного?

Я пишу в mcedit :)

Потому что я думаю больше, чем пишу %) Мне редактор не так уж и важен.

а посему не в vim

Из вима тяжело выходить %)

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

В С++ это если и появится, то будет как всегда полным убожеством, потому что С++ не проедоставляет контроль над алгоритмами управления потоками (scheduling policy) и приоритезацией. При достаточно большом количестве потоков в пуле ты столкнёшься с тем, что управляющий поток будет неконтроллируемым из-за равенства с рабочими потоками. Готов ли ты открыть эту банку с червями? %)

У линуха есть real-time threads (pthread_attr_setschedparam()). У uC-OS2 — тоже приоритеты. Без этого надо либо отдельное ядро отдавть скедюлеру, либо может быть плохо.

Так если не ручками — зачем с С++ связываться?

Питон — универсальный язык на все случаи жизни, от переименовывания файлов, NLP и бекенда до автотестов.

Руки прочь от басика! Только в нем строки нумеровались!

в итоге Haskell ;)

По первому абзацу — теперешняя реализация многопоточности в осях получается до жути кривой и убогой?

У кого как. В QNX мы оптимизировали запуск потока до самых низких значений по времени, но не факт, что в других ОС запуск потока не будет стоить сотен миллисекунд.

Т.е. ты утверждаешь, что С и С++ не применимы для нормальной многопоточности?

Я против интерфейса многопоточности в том виде, в каком сделан стандарт С++, он не имеет ничего общего ни с POSIX ни с операционной системой. Абстракции такого вида обречены на провал, нет того уровня тюнинга, который зачастую необходим. А сами языки к многопоточности вообще не имеют никакого отношения.

но не факт, что запуск потока не будет стоить сотен миллисекунд.
скорее будет. И тут сразу маленький оффтоп: стандартный способ борьбы с этим — т.н. thread spinning т.е. когда тасок треду нет и мы вместо того чтоб этот тред парковать а потом будить 50 микросекунд говорим треду работать над не важной для нас задачей (да, жечь электроэнергию впустую). Как вы решаете такую проблему? Она, кажется, over-signalling называется.
а потом будить 50 микросекунд говорим треду работать над не важной для нас задачей (да, жечь электроэнергию впустую)

Это чистое OS design flaws или если её пытаются применят как РТОС вместо ОС общего назначения, которой начхать на время реакции. Обычно в таких используют MWAIT/MONITOR вместо HALT, разрешая процессору погружаться на разную глубину сна вместо С0<->C1 в случае с HALT.

Как вы решаете такую проблему?

Ответ будет удивителен по своей простоте — мы её просто не создаём, поэтому не решаем. Поток из состояния BLOCKED переходит в RUNNING за наносекунды. Создание — да, может быть дорогое, но просто отдать управление потоку — это копейки. А если у потока приоритет больше остальных, то его спиннинг приведёт к тому, что всё остальное ляжет. У нас даже классические спинлоки работают только на унипроцессорных микроядрах в SMP это всегда мьютексы с особым флагом, чтобы работать в обработчиках прерываний.

Не пробував (я С практично не знаю).
Модель — аналог шедулера в Go.
Здається, десь були тести на GitHub (кілька сішних бібліотек, Go, Java), зараз навскидку знайти не можу.

На чистом С, С++ потоки нормальные реализовать невозможно в принципе. Что ОС предоставляет, то оно и использует. Всякие «обертки» типа бустов не могут увеличить производительность в принципе. Куда и прочее, это совсем из другой «оперы».

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

А ОпенСЛ, это как ехать перед камазом, который везет 8 кубов щебня, на ланосе, указывая путь, и при этом думать о том, как классно вы ланос заапгрейдили.

Херню ты написал.

Конкретную задачу в студию.

Мне в общем-то интересно, услышать, а нафига та штука нужна. Ну вот ни разу не применял. Но у меня последние дофига лет C++ шел в тесной связки с QT, где даже STL был не нужен при наличии QString, которые тоже были нафиг не нужно в связи со спецификой задач.

Просто на C и С++ мало кто сейчас пишет, вот и мало комментов

Дык жаба, шарп, жабоскрипт etc
Теперь вот гоферы изо всех щелей лезть начинают))

практически да, юзается крайне редко

Есть, но это в основном легаси. Приходится обертки вокруг c/cpp либ рисовать и матюкать авторов оных)))

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

На конкретные вопросы идут более конкретные ответы (хотя шум, конечно, тоже будет).

Если твои задачи не приемлют распаралеливания на процессы то скорее всего распаралеливать на ЦПУ их вообще безсмысленно и нужно думать в направлении ГПУ или ФПГА со всей сопутствующей спецификой.

Что понимается под «чистым C»? Минимальная реализация требует всего лишь malloc, setjmp и longjmp.

Нет. Он низпослан нам Богом, за наши молитвы.

... в отличие от богомерзкого free()!

Его послал дьявол. Прислужник FreeBSD.

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

А кто и как вызовет main() если совсем без ассемблера?
Ну да, про неё самую.

язык Си не описывает crt0. Это как в автошколе не учат строить дороги и делать машины.

crt, malloc, setjmp, longjmp — я затрудняюсь провести границу, где заканчивается чистый C и начинается нечистый.

А где вы на Си пишите а где на ассмеблере можете?

Пофиг сишные функции должны вызываться на все готовое. Где проиничены глобальные переменные, где настроен стек итд. А main, или там abrakadabra, пофиг по стандарту.

А можно подробнее? Erlang может работать на bare metal (или его эмуляции)?

erlangonxen.org я сам не шарю ни в том, ни в другом, но народ радуется

Подписаться на комментарии