Параллельные вычисления

[sami]

Абсолютно согласен. Динамически создаваемые объекты с трудом параллелятся (а таких задач уйма).

О каких задачах собственно речь? Причем тут динамически создаваемые объекты? Какие проблемы с их распараллеливанием?

 

[@live]

О каких задачах собственно речь? Причем тут динамически создаваемые объекты? Какие проблемы с их распараллеливанием?

Например, те же разреженные матрицы. Допустим, при умножении формирование конечной матрицы происходит динамически. Следовательно, размер конечной матрицы (объекта, который формируется, например, массивом списков) не известен. Поэтому, попытки распараллеливания не дают результатов, так как каждой нити(thread) требуются сведения о текущем индексе в конечной матрице. Что требует постоянной синхронизации и дополнительного времени.
Решение проблемы заданием конечного размера результирующей матрицы приводят нас к задаче со статически создаваемыми матрицами, так как размер мы можем ограничить сверху лишь размером матрицы, представленной в стандартном виде (массив).

 

[sami]

Например, те же разреженные матрицы. Допустим, при умножении формирование конечной матрицы происходит динамически. Следовательно, размер конечной матрицы (объекта, который формируется, например, массивом списков) не известен. Поэтому, попытки распараллеливания не дают результатов, так как каждой нити(thread) требуются сведения о текущем индексе в конечной матрице. Что требует постоянной синхронизации и дополнительного времени.
Решение проблемы заданием конечного размера результирующей матрицы приводят нас к задаче со статически создаваемыми матрицами, так как размер мы можем ограничить сверху лишь размером матрицы, представленной в стандартном виде (массив).

Ну это как распараллеливать. Каждый thread может умножать строку первой матрицы на вторую матрицу для получения разреженной строки. Потом формировать разреженноую матрицу из отдельных строк результата. Никакой синхронизации. Плохой пример.

 

[@live]

Ну это как распараллеливать. Каждый thread может умножать строку первой матрицы на вторую матрицу для получения разреженной строки. Потом формировать разреженноую матрицу из отдельных строк результата. Никакой синхронизации. Плохой пример.

Прежде чем давать оценку моему примеру, следовало бы повнимательнее читать. Массив списков для компактного хранения содержит индексы не нулевого элемента и сам элемент. При этом, нужно бегать по всему списку и искать соответсвующие индексы, при этом запоминая(!) их, чтобы потом использовать для другой матрицы (где и происходит динамическое формирование результирующей матрицы), что одновременно без синхронизации всех нитей приведёт к ложному результату, о чём я писал выше. В вашем же случае приходиться перебирать заведомо нулевые элементы, что не сохраняет принцип работы с исходными матрицами. Ваш контрпример годится лишь для умножения обычных статических матриц, где умножение происходит по классическому алгоритму[O(n3)].
P.S. Ваше право назвать мой пример плохим, я способен отвечать за свои слова.

 

[sami]

Прежде чем давать оценку моему примеру, следовало бы повнимательнее читать.

Ща попробую

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

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

При этом, нужно бегать по всему списку и искать соответсвующие индексы, при этом запоминая(!) их

ну зачем же их запоминать, если они запомнены в списке?

чтобы потом использовать для другой матрицы (где и происходит динамическое формирование результирующей матрицы)

Зачем результирующей матрице индексы исходной матрицы?

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

При таком подходе - не сомневаюсь в этом.

В вашем же случае приходиться перебирать заведомо нулевые элементы, что не сохраняет принцип работы с исходными матрицами. Ваш контрпример годится лишь для умножения обычных статических матриц, где умножение происходит по классическому алгоритму[O(n3)] .

Откуда ж возьмутся заведомо нулевые, если в разреженной матрице они не хранятся? Последнее Ваше утверждение, пожалуй, опровергну:

Берутся такие же разреженные матрицы (массивы списков ненулевых элементов с их индексами). Далее создается число тредов, допустим по числу ядер. Делим строки первой матрицы между тредами.
Каждый тред в цикле умножает строки первой матрицы на вторую матрицу , вычисляя строки результирующей матрицы. Для перебора столбцов второй матрицы можно использовать сканирующую линию, но в ней двигать только те элементы, чьи индексы присутствуют в текущей строке умножаемой матрицы (естественно, для сканирующей линии списки непустых элементов должны быть отсортированы по индексу, но это будет следствием любой арифметической операции над записанной в таком виде матрицей). Результат умножения строки на матрицу формируется в виде списка ненулевых элементов, заранее расположенного в массиве списков результирующей матрицы.
Области ответственности тредов не пересекаются, т.к. каждый тред пишет только отведенные ему строки результатов => синхронизация не нужна.
Балансировать нагрузку можно и по-другому. Например, по мере выполнения тредом умножения очередной строки выдавать ему следующую. Здесь тоже не требуется синхронизация, достаточно interlocked инкрементирования индекса строки первой матрицы.
Алгоритм сканирующей линии можно легко модифицировать для упреждающего чтения индексов ненулевых элементов с целью пропуска нулевых столбцов во второй матрице.

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

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

P.S. Признаю, что существуют алгоритмы мало поддающиеся распараллеливанию, но они не характерны для вычислительных задач среднего потребителя, как то фотошоп, игры, работа с медиаконтентом и даже рендеринг 3D сцен. Даже задачи WEB серверов достаточно хорошо мастшабируются. А если не мастшабируются, то выручает виртуализация.
Системы инженерных расчетов я не отношу к используемым большинством. И тут проблема скорее в существующем софте, нежели в плохой масштабируемости алгоритмов.
А что такое динамически создаваемые объекты - я так и не понял

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

 

[Mek_ph]

P.S. Признаю, что существуют алгоритмы мало поддающиеся распараллеливанию, но они не характерны для вычислительных задач среднего потребителя, как то фотошоп, игры, работа с медиаконтентом и даже рендеринг 3D сцен. Даже задачи WEB серверов достаточно хорошо мастшабируются. А если не мастшабируются, то выручает виртуализация.
Системы инженерных расчетов я не отношу к используемым большинством. И тут проблема скорее в существующем софте, нежели в плохой масштабируемости алгоритмов.

Большинство инженерных расчетов, требующих больших вычислительных затрат, неплохо параллелится. А современные пакеты для инж. расчетов с большими вычислительными затратами (например МКЭ, Монте-Карло...) соответственно поддерживают многоядерность/многопроцессорность, ибо изначально создаются для многопроцессорных систем...

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

Открыл "страшную тайну".
Алгоритмы, оперирующие большими массивами данных, причем почти не производящие вычислений, не нагрузят даже одноядерный процессор... Вычислительные задачи прекрасно идут, и весь вопрос в данном случае в требуемом отношении производительности подсистемы памяти, и вычислительной нагрузки... Пока что используется не более 4х ядер, что с современной памятью позволяет вычислениями загрузить все ядра, дальнейшее развитие похоже идет в сторону интегрированных в процессор контроллеров памяти да еще в количестве больше одного, то есть проблема обмена данными с памятью осмыслена и решается...

 

[sami]

Дело не в реализации алгоритмов и соответственно ПО. Да, свертка матриц паралелится на ура. Все же рассмотрим такую утрированную гипотетическую ситуацию когда исходные данные (возъмем тип данных Dfloat - 64 бит) не "сидят" в кэше, а находится во внешней памяти (размер превышает объем кэш памяти, данные после DMA переноса или в результате предыдущих операций)....

Тут уже другое... Конечно, если элементы списка (я про представление разреженной матрицы еще) будут раскиданы по всей оперативке да еще и в свапе, то толку от многоядерности будет мало. Однако, если матрицы представить массивом массивов ненулевых элементов с индексами (усложнит модификацию такой матрицы), либо предусмотреть аллокатор для элементов списков, который будет заботиться о выделении памяти под элменты "рядом", то продувка будет огого!
Я занимался обработкой изображений... так вот, алгоритмы с условно последовательным доступом к памяти при отсутствии синхронизации масштабируются по ядрам будь здоров. Условно последовательно - это не совсем последовательно, иногда приходится скакать довольно далеко вперед и назад в границах снимка (~90Мб), но в основном последовательно... И обрабатывая разными ядрами разные куски, и даже подкачивая другие данные (тоже ~90Мб), оба ядра справлялись с задачей за 1.5 секунды в то время как одно - 3секунды.

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

Траблы в софте. Немало его написано под одно ядро, мало кто будет адаптировать его под многоядерные машины. Интел занимается потихоньку переводом старья, но много ли они потянут?

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

 

[sami]

Вот что думают об этом великие... [http://omega-it.blogspot.com/2008/06/25-2008.html]

О проблемах перехода обычного ПО на многоядерную архтектуру современных процессоров.

"Для меня это выглядит более или менее так: разработчики техники исчерпали идеи, и они дают разработчикам ПО компьютеры, которые работают быстрее всего на нескольких из ключевых тестов. Таким образом производители компьютеров пытаются переложить вину за будущую кончину закона Мура на программистов!"

"Я совершенно не буду удивлен, если вся идея мультитрединга обернется большей неудачей, чем направление "Itanium". Это направление предполагалось таким прекрасным - пока не выяснилось, что желанные компиляторы было попросту невозможно написать."

"Позвольте мне сказать так: в течение последних 50-ти лет, я написал более 1000 программ, многие из которых имели приличный размер. Я не думаю что даже 5 из них можно существенно улучшить, применив параллелизм или мультитрединг."

"Так почему я должен быть так доволен будущим, которое обещают производители компьютеров? Они думают, что "волшебная пуля" прилетит и сделает так, чтобы при помощи мультиядерности ускорились приложения, которые я использую?

Я думаю, что это несбыточная мечта (англ. pipe dream). Нет! Это неправильная метафора! "Pipeline"-ы действительно работают, а вот треды - нет. Возможно мне следовало использовать слово "пузырь"

Я с ним не согласен.

 

[@live]

Массив списков по своей природе может содержать только списки и больше ничего.

Вы в этом так уверены? Массив книг может содержать только книги, страницы он ну никак не может содержать.

Догадываюсь, что речь о том, что массив списков содержит списки.

Гениальная догадка.

Список содержит структуры...

Масло содержит масло - нельзя не согласиться.

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

cij =∑aik*bkj
k
Умножение происходит по равным (k) колоночным и строчным индексам соответственно элементов aik и bkj. Будем выбирать такие элементы, при этом запоминая индекс, который “помнит” строчные(i) и колоночные индексы(j). При этом он будет сохраняться в исходном состоянии, если (i) и (j) при следующих проходах цикла ему уже встречались. Индекс представлен на основе односвязного списка. Проход идёт по двойному циклу и через условие по не полному тройному... Но не об этом спор.

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

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

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

Здесь или прямой перебор(что требует знать полный размер и бегать по заведомо нулевым элементам) или запоминание. Понимаю, что на уровне форума лениво полностью писать весь алгоритм, поэтому вопросов "ну зачем?" и "зачем?" избегу.
Я не сомневаюсь, что вы способны расспараллелить параллелищейся алгоритм. Не в этом дело. Всегда ли его можно создать? Имеются оптимизированные для одного ядра алгоритмы, для которых приходится решать отдельную задачу (не теряя его временной сложности и размера), которая может оказаться на порядки сложнее, чем сама его разработка.

P.S.

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

 

[sami]

Массив книг может содержать только книги, страницы он ну никак не может содержать.

Это верно для компьютерной модели.
Допустим, что отношение вложенности элементов в контейнер транзитивно, как Вы полагаете. Рассмотрим список массивов списков (этот случай ближе к рассматриваемой ситуации, но можно было бы взять массив массивов или список списков). В списке создадим элемент типа массив списков, у которого единственный элемент - вышеописанный список. Тогда с учетом транзитивности отношения вложенности получается что и массив и список содержат сами себя, и более того, у каждого из них континуум элементов (это при ограниченном объеме физической памяти).
Меня эти факты не устраивают, потому я считаю предположение о транзитивности отношения вложенности ложным.

Умножение происходит по равным (k) колоночным и строчным индексам соответственно элементов aik и bkj. Будем выбирать такие элементы, при этом запоминая индекс, который “помнит” строчные(i) и колоночные индексы(j). При этом он будет сохраняться в исходном состоянии, если (i) и (j) при следующих проходах цикла ему уже встречались. Индекс представлен на основе односвязного списка. Проход идёт по двойному циклу и через условие по не полному тройному... Но не об этом спор.

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

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

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

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

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

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

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

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

 

[Mike22]

Анонсирован выход Intel Parallel Studio - инструмента параллельного программирования, специально для C/C++ Windows программистов.
http://www.developers.org.ua/archives/galy...tudio-announce/