Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Для "параллельных циклов" отдельные языки не нужны, достаточно библиотек. Например Intel TBB, Microsoft PPL, а начиная с C++17 — вообще в STL.
Там как раз те самые параллельные циклы, даже название соответствующее — parallel_for.
Здравствуйте, Khimik, Вы писали:
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика.
Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Khimik, Вы писали:
K>>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика.
EP>Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше.
А что будет, если в этом распараллеленном обычном цикле попробовать посчитать факториал?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
EP>>Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше. K>А что будет, если в этом распараллеленном обычном цикле попробовать посчитать факториал?
Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна:
template<typename T>
T factorial(T N)
{
T result = 1;
#pragma omp parallel for reduction(*:result)for(T i = 1; i <= N; ++i)
result *= i;
return result;
}
Но, опять таки, я вместо OpenMP предпочитаю библиотеки типа TBB, либо C++17 STL. При наличии лямбд, повсеместного вывода типов и т.п. трюки с прагмами не нужны.
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм?
Языки 4-го поколения например sql. Где компилятор сам синтезирует и распаралеливает алгоритм.
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
В таких языках циклов не нужно. Просто другие примитивы — выборки, свёртки и т.п.
Здравствуйте, Khimik, Вы писали:
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные.
Это такой детский, дилетантский взгляд. Он преобладал в 90-е. Тогда думали, что если сделать расширение императивных языков, то все срузу ускорится во столько раз, сколько у тебя есть процессоров.
В реальности, это самообман.
Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
В реальном мире есть задачи которые хорошо параллелятся и те что параллелятся плохо.
У большинства вычислений есть четкая последовательность. Чтобы вычислить Б нужно сначала вычислить А, и т.д.
Параллелить можно "в большом". Простой пример. Вот есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
На мой взгляд от языков программирования следующего поклонения нужно требовать не автоматического распараллеливания, а обеспечения гарантий корректности ручного распараллеливания.
Ну не может эффективно распараллеливать вычисления автомат (программа). А человек — может.
Значит нужно ему помочь.
Я считаю, что следующим шагом в развитии человечества будет обеспечение локальности данных и повышение эффективности изменения и "копирования" локальных данных.
Возвращаемся к тем же файлам. Вот отпарсили мы файл в отдельном потоке. Теперь надо сделать так, чтобы я мог обработать полученные данные ( а их очень много) параллельно с остальными данными (из других файлов) и при этом не иметь проблем с блокировками и не копировать все данные.
Для того нужно чтобы программист оперировал некими областями памяти которые можно изменят только из одного потока управления. И предоставить программисту дешевый способ передачи "замороженного слепа информации" из одного потока в другой.
Иными словами нужно сделать так, чтобы потоки не имели общих изменяемых данных, а передача данных из одного потока в другой была прозрачной и дешевой.
У меня есть масса мыслей по этому поводу. Но это требует разработки нового языка программирования. И нового рантайма для него.
Правильные мысли есть в Расте. Но там все слишком сложно для того чтобы это могло войти в мэйнстрим. Нужно научить языки манипулировать кучами. Научить передавать эти кучи между "виртуальными процессами" (в стиле Эрланг).
Для этого нужно создавать новые языки программирования.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна: EP>
EP>template<typename T>
EP>T factorial(T N)
EP>{
EP> T result = 1;
EP> #pragma omp parallel for reduction(*:result)
EP> for(T i = 1; i <= N; ++i)
EP> result *= i;
EP> return result;
EP>}
EP>
EP>Но, опять таки, я вместо OpenMP предпочитаю библиотеки типа TBB, либо C++17 STL. При наличии лямбд, повсеместного вывода типов и т.п. трюки с прагмами не нужны.
Сорри за профанство, но я не понимаю как этот код работает. Речь шла о том, что вычисление факториала как раз нельзя распараллелить. Или в этом коде оно паралеллится частично, типа цифры с 2 до 5 перемножаются в одном процессе, с 6 по 9 в другом, потом два результата перемножаются и получается факториал девяти?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
EP>>Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна: EP>>
EP>> #pragma omp parallel for reduction(*:result)
EP>> for(T i = 1; i <= N; ++i)
EP>> result *= i;
EP>>
K>Сорри за профанство, но я не понимаю как этот код работает. Речь шла о том, что вычисление факториала как раз нельзя распараллелить. Или в этом коде оно паралеллится частично, типа цифры с 2 до 5 перемножаются в одном процессе, с 6 по 9 в другом, потом два результата перемножаются и получается факториал девяти?
Да, именно так. Параллельная редукция это одна из базисных операций для параллельных алгоритмов, причём как для multi-core, для multi-node (а-ля MPI_Reduce), так и для GPGPU.
То есть нужно вычислить:
a * b * c * d
где a,b,c,d — произвольные данные, а * — произвольная ассоциативная бинарная операция. За счёт ассоциативности имеем возможность расставить скобки как нам требуется (что по сути уменьшает зависимости между данными):
(a * b) * (c * d)
И соответственно вычислять операции в скобках параллельно.
На самом деле это подходит и для операций с плавающей точкой, несмотря на то что они неассоциативные. Главное понимать что результат может зависеть от порядка вычислений, и часто эти различия допустимы (в случае floating point).
Здравствуйте, VladD2, Вы писали:
VD>В реальности, это самообман. VD>Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример:
VD>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример:
VD>>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
EP>Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи.
Это уже не циклы. Это уже структура программы.
Паралеленье циклов чуть менее чем полностью бесполезно.
Параллелить можно только сущности реально способные обрабатываться независимо. На сегодня, решить что можно параллелить может только лишь человек.
По сему от языка требуется позволять человеку определять что и как параллелить. А для повышения эффективности и безопасности предоставить ему механизмы контроля передачи данных между параллельными процессам (или иными единицами параллельного выполнения).
Грубо говоря нужны языки обеспечивающие дешевые паралельные процессы. И дешевую передачу данных между ними. Для этого нужны:
1. Гарантией неизменности данных разных "процессах".
2. Дешевизна передачи данных (заморозка графа объектов в одном процессе и передачи его в другой).
3. Средства контроля последовательности вычислений. Чтобы человек мог созерцать как расчеты распараллеливаются и возвращаются обратно к синхронным.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
Не факт.
Параллелизм — это высокоуровневая векторизация.
Высокоуровневая — потому, что цена за межпотоковое взаимодействие не должна превысить выгоды распараллеливания.
То есть, матрицы 10*10 перемножать на нескольких ядрах — смысла нет, а вот матрицы 10000*10000 — уже есть.
Здравствуйте, VladD2, Вы писали:
EP>>Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример: VD>>>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто. EP>>Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи. VD>Это уже не циклы. Это уже структура программы.
А выражается эта СТРУКТУРА каким образом? Не циклами ли случайно?
VD>Паралеленье циклов чуть менее чем полностью бесполезно.
Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce.
VD>А для повышения эффективности и безопасности предоставить ему механизмы контроля передачи данных между параллельными процессам (или иными единицами параллельного выполнения).
Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими.
Те же задачи в которых имеется постоянное взаимодействие между процессами обычно относятся не к parallel computing, а к concurrent.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>А выражается эта СТРУКТУРА каким образом? Не циклами ли случайно?
Нет. Но это не главное.
Главное то, что основная задача не распаралелить, а сделать так, чтобы распаралеленные вычисления не мешали друг другу (были изолированными). И в том как объединять результаты вычислений.
EP>Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce.
Эти библиотеки точно так же бесполезны. Они не более чем костыли не решающие проблему, а только лишь незначательно их облегчающие.
В плане языковых средств и библиотек можно выделить такие либы как Rx и ReactiveUI. Это более полезные костыли. И там нет никаких циклов.
Но даже эти продвинутые костыли не решают проблему конкурентного изменения данных.
Для решения этой проблемы нужно делать новые языки и новые рантаймы к ним.
EP>Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими.
Это 100% задач. Все задачи требуют работы с данными. Мап-редью — не более чем алгоритм для определенных задач. Гарантий он никаких не дает. А для безопасного и производительного программирования нужны гарантии и контроль.
EP>Те же задачи в которых имеется постоянное взаимодействие между процессами обычно относятся не к parallel computing, а к concurrent.
Да ты можешь хоть к черту лысому что хочешь относить. Это ничего не меняет. Основная проблема параллельных вычислений в том что нужно контролировать изменение данных. Если бы это было не так, то проблемы решали бы банальные функции.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
EP>>Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce. VD>Эти библиотеки точно так же бесполезны. Они не более чем костыли не решающие проблему, а только лишь незначательно их облегчающие.
Полезны, решают вполне реальные инженерные и научные задачи, причём успешно. Именно эти библиотеки и нагружают все вычислительные кластеры.
Ещё раз, речь про parallel computing, научные вычисления и инженерные расчёты. Ты же вещаешь больше про concurrency — это другая тема.
VD>В плане языковых средств и библиотек можно выделить такие либы как Rx и ReactiveUI. Это более полезные костыли. И там нет никаких циклов. VD>Но даже эти продвинутые костыли не решают проблему конкурентного изменения данных.
Во-во, о том и речь — это всё concurrency, и к сабжу имеет лишь опосредованное отношение
EP>>Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими. VD>Это 100% задач. Все задачи требуют работы с данными.
Да, с данными, но далеко не все с разделяемыми данными.
Здравствуйте, Кодт, Вы писали:
К>Высокоуровневая — потому, что цена за межпотоковое взаимодействие не должна превысить выгоды распараллеливания. К>То есть, матрицы 10*10 перемножать на нескольких ядрах — смысла нет, а вот матрицы 10000*10000 — уже есть.
Матрицы перемножать надо на GPU. Они для этого предназначены.
И вообще, такие вещи должны делать библиотеки. Не должен каждый писать свой вариант перемножения матриц.
В общем, пример из пальца высосан.
В реальности речь почти всегда идет о сложных задачах с кучей ветвлений и сложных данных. И вот в этих условиях распараллеливание цикла ничего не дает. Все существенно сложнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм?
Существует как минимум два разных класса задач. Про векторизацию (параллельные циклы) и соответствующие библиотеки уже несколько раз упомянули, параллельные коллекции есть практически везде.
Второй тип задач упоминал VladD2. Это более высокоуровневые (и более динамические) задачи. У него парсинг и обработка данных. В вебе может быть загрузка конфигов и потом дополнительных ресурсов из нескольких сервисов с разными зависимостями (пойти по конфигу в один сервис, потом по его ссылке в другой и т.п.). Для этой задачи тоже есть решения. Это Futures/Promises (еще deferred из той же серии). Называются по-разному в разных языках. Удобство зависит от конкретного API в конкретном языке. В языках с поддержкой монад вообще все прекрасно. Монадное/аппликативное API с функцией слева (в haskell-style fn :> v1 :> v2 :>> v3 и аналогичные) тоже нормально. А вот если разработчики осилили только функтор (aka map), то там больно. Пример — javascript. Без нормальных оберток (одной функции Async.apply(fn, arg1, arg2, ....)) что-либо нетривиальное на родных Promise делать очень неудобно (обертка делается легко, но почему не в стандарте то???).
Вот буквально вчера делал:
def deleteRecursive(path : Path) : Future[Unit] =
deleteNode(path) recoverWith {
/* Already deleted. */
case NoNodeException ⇒ Future.successfull(())
case NotEmptyException ⇒
val op = for {
children ← getChildren(path)
childOperations = children.map(child ⇒ deleteRecursive(path + child))
_ ← Future.sequence(childOperations)
_ ← deleteNode(path)
} yield ()
op recoverWith {
case NoNodeException ⇒ Future.successfull(())
}
}
Future.sequence делатет черную магию по преобразованию Seq[Future[Unit]] в Future[Seq[Unit]].
По сути аналогично deleteChildren отсюда. Пока оригинал дожидается ответа от сервера, мой отправляет стопку команд и потом потихоньку разгребает результат. На самом деле там не "многопоточность", а "асинхронность" (один поток обмена данными), но в использовании API этого факта просто не видно.
Перекуём баги на фичи!
