Сообщение Re: Языки для распараллеленных вычислений от 28.09.2016 6:48
Изменено 28.09.2016 6:51 chaotic-kotik
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Существует много всего. В своем комментарии ты описал OpenMP (расширение для С++). OpenMP позволяет решать такие задачи (это называется data parallel — когда каждый поток работает со своей независимой памятью, а потом все объединяется), но помимо этого, он позволяет задействовать task parallelism (это когда вычисление может быть представлено как ациклический направленный граф задач, т.е. стартует первая задача, порождает несколько новых, те порождают еще ряд задач и тд., расчет факториала или параллельный quicksort это как раз оно).
Помимо этого, есть еще такое расширение языка как Cilk (https://www.cilkplus.org/). Это тоже task level parallelism. Еще MIT недавно представили Milk (этот призван исправлять data access patterns в параллельных приложениях).
В принципе, все это можно делать на уровне библиотек (кроме того что делает Milk). Существуют высокоуровневые тулкиты, вроде Intel TBB, которые позволяют описывать топологию вычислений и запускать их. Для task level подхода достаточно иметь хорошую реализацию task pool-а (work stealing например). Вообще, одна из серьезных проблем обоих подходов (data parallel и task parallel — балансировка нагрузки, наивный подохд — разделить заранее все между потоками, работает только в простых случаях).
Еще можно посмотреть в сторону dataflow языков программирования, например StreamIt (на MIT open courseware есть серия лекций по параллельному программированию, в которых про него рассказывают). Примерно того же самого пытаются добиться с помощью библиотек, пример — http://www.raftlib.io/
Принцип, лежащий в основе dataflow подхода похож на task level подход. У нас тут тоже есть ациклический направленный граф каких-нибудь задач, вот только топология не incidential а строится заранее. Пример: мы пишем скан для СУБД, (упрощенно) скан перебирает блоки Б+дерева хранящиеся на диске, каждый блок должен быть прочитан, распакован, данные должны быть десериализованы, потом идет фильтрация (т.к. у нас есть where clause в запрсое), далее оно должно быть преобразовано в соответствии с projection в немного другую форму.
Data parallel подход тут работать не будет, так как scan должен обрабатывать данные в определенном порядке.
Task parallel как-то очень сложно и криво выглядит для этого случая.
Dataflow подход: строим такую топологию
Казалось бы тут нет параллелизма, но если все это реализовать с помощью RaftLib, то оно будет выполняться параллельно, будет построен конвейер, блоки будут читаться в буфер в одном потоке, второй поток будет брать блоки по очереди, распаковывать и передавать на десериализацию во второй поток (можно буферизовать данные между потоками, опять же), далее данные будут фильрроваться в еще одном потоке и тд. Количество потоков и распределение задач по потокам будет определяться библиотекой, например, если filter выполняется очень быстро то он не будет выноситься в отдельный поток а будет выполняться в том же потоке что и deserialization step для балансировки нагрузки.
Можно сделать то же самое для merge join-а двух деревьев:
Тут scan каждого дерева (таблицы) может быть распараллелен через конвейерную обработку, плюс возможно выполнять параллельное сканирование двух таблиц, плюс конвейерная обработка (сканирование) -> (kway merge) -> (output).
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Существует много всего. В своем комментарии ты описал OpenMP (расширение для С++). OpenMP позволяет решать такие задачи (это называется data parallel — когда каждый поток работает со своей независимой памятью, а потом все объединяется), но помимо этого, он позволяет задействовать task parallelism (это когда вычисление может быть представлено как ациклический направленный граф задач, т.е. стартует первая задача, порождает несколько новых, те порождают еще ряд задач и тд., расчет факториала или параллельный quicksort это как раз оно).
Помимо этого, есть еще такое расширение языка как Cilk (https://www.cilkplus.org/). Это тоже task level parallelism. Еще MIT недавно представили Milk (этот призван исправлять data access patterns в параллельных приложениях).
В принципе, все это можно делать на уровне библиотек (кроме того что делает Milk). Существуют высокоуровневые тулкиты, вроде Intel TBB, которые позволяют описывать топологию вычислений и запускать их. Для task level подхода достаточно иметь хорошую реализацию task pool-а (work stealing например). Вообще, одна из серьезных проблем обоих подходов (data parallel и task parallel — балансировка нагрузки, наивный подохд — разделить заранее все между потоками, работает только в простых случаях).
Еще можно посмотреть в сторону dataflow языков программирования, например StreamIt (на MIT open courseware есть серия лекций по параллельному программированию, в которых про него рассказывают). Примерно того же самого пытаются добиться с помощью библиотек, пример — http://www.raftlib.io/
Принцип, лежащий в основе dataflow подхода похож на task level подход. У нас тут тоже есть ациклический направленный граф каких-нибудь задач, вот только топология не incidential а строится заранее. Пример: мы пишем скан для СУБД, (упрощенно) скан перебирает блоки Б+дерева хранящиеся на диске, каждый блок должен быть прочитан, распакован, данные должны быть десериализованы, потом идет фильтрация (т.к. у нас есть where clause в запрсое), далее оно должно быть преобразовано в соответствии с projection в немного другую форму.
Data parallel подход тут работать не будет, так как scan должен обрабатывать данные в определенном порядке.
Task parallel как-то очень сложно и криво выглядит для этого случая.
Dataflow подход: строим такую топологию
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] -> (output to cursor)
Казалось бы тут нет параллелизма, но если все это реализовать с помощью RaftLib, то оно будет выполняться параллельно, будет построен конвейер, блоки будут читаться в буфер в одном потоке, второй поток будет брать блоки по очереди, распаковывать и передавать на десериализацию во второй поток (можно буферизовать данные между потоками, опять же), далее данные будут фильрроваться в еще одном потоке и тд. Количество потоков и распределение задач по потокам будет определяться библиотекой, например, если filter выполняется очень быстро то он не будет выноситься в отдельный поток а будет выполняться в том же потоке что и deserialization step для балансировки нагрузки.
Можно сделать то же самое для merge join-а двух деревьев:
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] (k-way merge) -> (output to db-cursor)
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] /
Тут scan каждого дерева (таблицы) может быть распараллелен через конвейерную обработку, плюс возможно выполнять параллельное сканирование двух таблиц, плюс конвейерная обработка (сканирование) -> (kway merge) -> (output).
Re: Языки для распараллеленных вычислений
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Существует много всего. В своем комментарии ты описал OpenMP (расширение для С++). OpenMP позволяет решать такие задачи (это называется data parallel — когда каждый поток работает со своей независимой памятью, а потом все объединяется), но помимо этого, он позволяет задействовать task parallelism (это когда вычисление может быть представлено как ациклический направленный граф задач, т.е. стартует первая задача, порождает несколько новых, те порождают еще ряд задач и тд., расчет факториала или параллельный quicksort это как раз оно).
Помимо этого, есть еще такое расширение языка как Cilk (https://www.cilkplus.org/). Это тоже task level parallelism. Еще MIT недавно представили Milk (этот призван исправлять data access patterns в параллельных приложениях).
В принципе, все это можно делать на уровне библиотек (кроме того что делает Milk). Существуют высокоуровневые тулкиты, вроде Intel TBB, которые позволяют описывать топологию вычислений и запускать их. Futures/promises это по сути просто удобный интерфейс для реализации task parallelism-а. Для task level подхода достаточно иметь хорошую реализацию task pool-а (work stealing например). Вообще, одна из серьезных проблем обоих подходов (data parallel и task parallel — балансировка нагрузки, наивный подохд — разделить заранее все между потоками, работает только в простых случаях).
Еще можно посмотреть в сторону dataflow языков программирования, например StreamIt (на MIT open courseware есть серия лекций по параллельному программированию, в которых про него рассказывают). Примерно того же самого пытаются добиться с помощью библиотек, пример — http://www.raftlib.io/
Принцип, лежащий в основе dataflow подхода похож на task level подход. У нас тут тоже есть ациклический направленный граф каких-нибудь задач, вот только топология не incidential а строится заранее. Пример: мы пишем скан для СУБД, (упрощенно) скан перебирает блоки Б+дерева хранящиеся на диске, каждый блок должен быть прочитан, распакован, данные должны быть десериализованы, потом идет фильтрация (т.к. у нас есть where clause в запрсое), далее оно должно быть преобразовано в соответствии с projection в немного другую форму.
Data parallel подход тут работать не будет, так как scan должен обрабатывать данные в определенном порядке.
Task parallel как-то очень сложно и криво выглядит для этого случая.
Dataflow подход: строим такую топологию
Казалось бы тут нет параллелизма, но если все это реализовать с помощью RaftLib, то оно будет выполняться параллельно, будет построен конвейер, блоки будут читаться в буфер в одном потоке, второй поток будет брать блоки по очереди, распаковывать и передавать на десериализацию во второй поток (можно буферизовать данные между потоками, опять же), далее данные будут фильрроваться в еще одном потоке и тд. Количество потоков и распределение задач по потокам будет определяться библиотекой, например, если filter выполняется очень быстро то он не будет выноситься в отдельный поток а будет выполняться в том же потоке что и deserialization step для балансировки нагрузки.
Можно сделать то же самое для merge join-а двух деревьев:
Тут scan каждого дерева (таблицы) может быть распараллелен через конвейерную обработку, плюс возможно выполнять параллельное сканирование двух таблиц, плюс конвейерная обработка (сканирование) -> (kway merge) -> (output).
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Существует много всего. В своем комментарии ты описал OpenMP (расширение для С++). OpenMP позволяет решать такие задачи (это называется data parallel — когда каждый поток работает со своей независимой памятью, а потом все объединяется), но помимо этого, он позволяет задействовать task parallelism (это когда вычисление может быть представлено как ациклический направленный граф задач, т.е. стартует первая задача, порождает несколько новых, те порождают еще ряд задач и тд., расчет факториала или параллельный quicksort это как раз оно).
Помимо этого, есть еще такое расширение языка как Cilk (https://www.cilkplus.org/). Это тоже task level parallelism. Еще MIT недавно представили Milk (этот призван исправлять data access patterns в параллельных приложениях).
В принципе, все это можно делать на уровне библиотек (кроме того что делает Milk). Существуют высокоуровневые тулкиты, вроде Intel TBB, которые позволяют описывать топологию вычислений и запускать их. Futures/promises это по сути просто удобный интерфейс для реализации task parallelism-а. Для task level подхода достаточно иметь хорошую реализацию task pool-а (work stealing например). Вообще, одна из серьезных проблем обоих подходов (data parallel и task parallel — балансировка нагрузки, наивный подохд — разделить заранее все между потоками, работает только в простых случаях).
Еще можно посмотреть в сторону dataflow языков программирования, например StreamIt (на MIT open courseware есть серия лекций по параллельному программированию, в которых про него рассказывают). Примерно того же самого пытаются добиться с помощью библиотек, пример — http://www.raftlib.io/
Принцип, лежащий в основе dataflow подхода похож на task level подход. У нас тут тоже есть ациклический направленный граф каких-нибудь задач, вот только топология не incidential а строится заранее. Пример: мы пишем скан для СУБД, (упрощенно) скан перебирает блоки Б+дерева хранящиеся на диске, каждый блок должен быть прочитан, распакован, данные должны быть десериализованы, потом идет фильтрация (т.к. у нас есть where clause в запрсое), далее оно должно быть преобразовано в соответствии с projection в немного другую форму.
Data parallel подход тут работать не будет, так как scan должен обрабатывать данные в определенном порядке.
Task parallel как-то очень сложно и криво выглядит для этого случая.
Dataflow подход: строим такую топологию
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] -> (output to cursor)Казалось бы тут нет параллелизма, но если все это реализовать с помощью RaftLib, то оно будет выполняться параллельно, будет построен конвейер, блоки будут читаться в буфер в одном потоке, второй поток будет брать блоки по очереди, распаковывать и передавать на десериализацию во второй поток (можно буферизовать данные между потоками, опять же), далее данные будут фильрроваться в еще одном потоке и тд. Количество потоков и распределение задач по потокам будет определяться библиотекой, например, если filter выполняется очень быстро то он не будет выноситься в отдельный поток а будет выполняться в том же потоке что и deserialization step для балансировки нагрузки.
Можно сделать то же самое для merge join-а двух деревьев:
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] \
(k-way merge) -> (output to db-cursor)
(input [read block]) -> [unpack] -> [deserialize] -> [filter] -> [apply projection] /Тут scan каждого дерева (таблицы) может быть распараллелен через конвейерную обработку, плюс возможно выполнять параллельное сканирование двух таблиц, плюс конвейерная обработка (сканирование) -> (kway merge) -> (output).