Q:авто и полуавто?
Каковы ближайшие перспективы автоматических и полуавтоматических средств распараллеливания? ;)
| |
Re: Q:авто и полуавто?
Каковы ближайшие перспективы автоматических и полуавтоматических средств распараллеливания? ;)
Тут надо сразу определять область обсуждения - речь идёт о средствах, которые должны давать 100% производительности, или 50% будет достаточно, или вообще хоть что-то хоть когда-то? для каких языков? для каких типов задач? какая часть работа может оставаться на программисте, а какая должна автоматизироваться ? и т.д.
Средств, которые дают 100% производительность, для всех языков и для всех задач, нет, не предвидится в ближайшем будущем и в более отдалённом тоже.
Средства, которые дают хоть какой-то прирост производительности хоть когда-то (иногда замедление), уже есть. Сейчас в основном для функциональных языков идёт такая работа. Для Haskell недавно видел статью по автоматическому распараллеливанию.
Для очень частных случаев, типа обработки массивов, когда работа над каждым элементом независима, автоматическое распараллеливание было достаточно давно. В то время в основном для FORTRAN.
В своё время на RSDN была большая баталия на этот счёт:
http://www.rsdn.ru/forum/philosophy/2917762.aspx
А вот например там же статья по автоматическому распараллеливанию специального языка программирования FPTL:
http://files.rsdn.ru/14680/FPTL%20language.html
А по поводу полу-автоматических, Cilk++ чем не полу-автоматическое распараллеливание.
Хотя вот этот язык FPTL это фактически тот же Cilk++ в плане автоматического распараллеливания, т.к. значительная доля работы всё равно лежит на программисте, она (часть работы) просто достаточно завуалирована.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Q:авто и полуавто?
А OpenMP - это не полуавтоматическое распараллеливание? По-моему оно...
| |
Re: Q:авто и полуавто?
Ok! Спасибо за интересные ссылки. И OpenMP - это полуавтоматическое. И поиск в Гугле много на эту тему дает. А вот кто что думает насчет перспектив? В идеале, ИМХО, есть исходный код программы, написанный только для основного потока, и есть инструмент, который сам разбивает на потоки, может спрашивая человека, может предлагая разные варианты... Насколько достижим такой идеал? Т.е. решаема ли эта задача в принципе? Насколько быстро могут появиться такие инструменты не для узкого круга специальных задач? Что мешает?
Конечно, принципиально другое алгоритмическое решение ни один инструмент предложить не сможет, пока AI не разовьется до такого уровня :) Так что, видимо, стоит говорить о решениях в рамках заданного человеком алгоритма. И конечно, долго еще (наверное всегда) на человеке будет лежать необходимость отлаживать и тестировать создаваемую программу. В 80-е годы были оптимизирующие компиляторы, которые ошибались один раз из двух, и практически любой фрагмент кода, переписанный на ассемблере вручную практически любым программистом, работал быстрее, чем сгенерированный таким компилятором. Сейчас, чтобы оптимизировать лучше обычного компилятора, надо затратить, как правило, слишком много усилий. Возможно ли, что с оптимизацией генерации параллельного кода (из непараллельного) произойдет через несколько лет то же, что произошло с оптимизацией непараллельного?
| |
Re: Q:авто и полуавто?
Ok! Спасибо за интересные ссылки. И OpenMP - это полуавтоматическое. И поиск в Гугле много на эту тему дает. А вот кто что думает насчет перспектив? В идеале, ИМХО, есть исходный код программы, написанный только для основного потока, и есть инструмент, который сам разбивает на потоки, может спрашивая человека, может предлагая разные варианты... Насколько достижим такой идеал? Т.е. решаема ли эта задача в принципе? Насколько быстро могут появиться такие инструменты не для узкого круга специальных задач? Что мешает?
Я думаю тогда же, когда появятся инструменты, которые автоматически пишут однопоточный код для любой задачи. То есть - никогда. Ну по-крайней мере не на нашем веку.
Конечно, принципиально другое алгоритмическое решение ни один инструмент предложить не сможет, пока AI не разовьется до такого уровня :) Так что, видимо, стоит говорить о решениях в рамках заданного человеком алгоритма. И конечно, долго еще (наверное всегда) на человеке будет лежать необходимость отлаживать и тестировать создаваемую программу.
А кто сказал, что в рамках заданного алгоритма вообще возможно распараллеливание? Для многих задач как раз так и есть. Например, самые эффективные однопоточные алгоритмы сортировки вообще не распараллеливаются.
Любое значение термина распараллеливание, которое я могу представить, подразумевает достижение ускорения при параллельной работе. Соотв. любое распараллеливание, будь то ручное или автоматическое, просто требует изменения алгоритма работы.
Ну а если под автоматическим распараллеливанием для произвольных задач подразумевается, что оно будет работать на самом деле не для всех задач, будет давать не линейное масштабирование, будет требовать ручной проверки и отладки, то опять же, пожалуйста, - компиляторы функциональных языков могут это делать сегодня, afair для Haskell было что-то подобное. Хотя ИМХО это нельзя назвать "автоматическим распараллеливанием произвольных задач".
В 80-е годы были оптимизирующие компиляторы, которые ошибались один раз из двух, и практически любой фрагмент кода, переписанный на ассемблере вручную практически любым программистом, работал быстрее, чем сгенерированный таким компилятором. Сейчас, чтобы оптимизировать лучше обычного компилятора, надо затратить, как правило, слишком много усилий. Возможно ли, что с оптимизацией генерации параллельного кода (из непараллельного) произойдет через несколько лет то же, что произошло с оптимизацией непараллельного?
Оптимизация трансляции программы принципиально отличается, т.к. она работает локально для очень ограниченных кусков кода. А те оптимизации однопоточных программ, которые делаются глобально (LTCG/IPO), не ушли далеко от сегодняшних средств "автоматического" распараллеливания.
Автоматическое *локальное* распараллеливание тоже уже есть - распараллеливание простых циклов в Fortran и C/C++.
Распараллеливание же на глобальном уровне на порядки сложнее, просто потому что оно на глобальном уровне, соотв. должно оперировать большими моделями. Плюс сюда добавляются сложности вызванные многопоточным исполнением - анализ даже небольших фрагментов многопоточного кода нерешаемая задача, т.к. NP-сложная.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Q:авто и полуавто?
Re: А вот кто что думает насчет перспектив? В идеале, ИМХО, есть исходный код программы, написанный только для основного потока, и есть инструмент, который сам разбивает на потоки, может спрашивая человека, может предлагая разные варианты... Насколько достижим такой идеал? Т.е. решаема ли эта задача в принципе? Насколько быстро могут появиться такие инструменты не для узкого круга специальных задач? Что мешает?
Да уже мало что. Можно делать, например, так.
1) В автомате. Для любого алгоритма можно найти эквивалентный конечный автомат. Обычно действия, выполняемые им на переходах, представляют множество элементарных/атомарных действий. Поэтому делаем анализ действий. Если они не связаны по данным, то атомарные действия разбрасываем по потокам. Все.
2) В диалоге. Строим, как в выше автомат. Далее делаем его декомпозицию на множество параллельных автоматов. На этом этапе уместен диалог, когда предлагаются варианты, а человек выбирает или сам делает такую декомпозицию. Далее по потокам, как уже описано выше.
Все это хорошо, но кроме увеличения скорости мы здесь не порождаем ничего нового. Новый даже параллельный алгоритм это всего лишь эквивалент исходного последовательного. Так мы можем, думаю, ускорить тот же алгоритм быстрой сортировки Хоара, но он таковым и останется по сути.
Более перспективно – создавать новые параллельные алгоритмы с нуля. Например, можно создать новый параллельный алгоритм, который будет в разы быстрее даже распараллеленного быстрого алгоритма. Но здесь придется все делать самому. Правда инструментарий может подсказывать насколько корректен вновь создаваемый алгоритм. Так, строя обратным способом из «человеческого» параллельного последовательный алгоритм, мы можем на нем легко найти те же противоречивые действия (когда параллельными действиями изменяется одновременно общая переменная).
Re: Например, самые эффективные однопоточные алгоритмы сортировки вообще не распараллеливаются.
В той или иной степени распараллеливается, не скажу все, но почти любой алгоритм.
И я полностью согласен с тем, что «Я думаю тогда же, когда появятся инструменты, которые автоматически пишут однопоточный код для любой задачи. То есть - никогда. Ну, по крайней мере, не на нашем веку» :)
| |
Re: Q:авто и полуавто?
Распараллеливание же на глобальном уровне на порядки сложнее, просто потому что оно на глобальном уровне, соотв. должно оперировать большими моделями. Плюс сюда добавляются сложности вызванные многопоточным исполнением - анализ даже небольших фрагментов многопоточного кода нерешаемая задача, т.к. NP-сложная.
NP-сложная задача не является нерешаемой, просто время ее решения растет по экспоненте от входа. Но экспоненты бывают весьма приемлемыми для практики. Многие NP алгоритмы постоянно применяются в работающих программах - там, где не найдено лучших или там, где доказано, что лучших быть не может ;)
Иногда так же возможны аппроксимация, эвристики, стохастические подходы... Распараллеливание тоже ускоряет.
| |
Re: Q:авто и полуавто?
Все это хорошо, но кроме увеличения скорости мы здесь не порождаем ничего нового. Новый даже параллельный алгоритм это всего лишь эквивалент исходного последовательного.
[...]
Более перспективно – создавать новые параллельные алгоритмы с нуля.
Согласен; а чтобы с нуля автоматически - тут дело за AI и это будет не скоро, если будет.
| |
Re: Q:авто и полуавто?
Согласен; а чтобы с нуля автоматически - тут дело за AI и это будет не скоро, если будет.
Не нужно строить иллюзий насчет AI :) Пока еще создавать с нуля алгоритмы - прерогатива интеллекта естественного. Можно верить, что уж коли есть интеллект естественный, то нет принципиальных препятствий на пути создания интеллекта искусственного. Но пока естественный интеллект будет считать многопоточность моделью параллельных вычислений, перспективы создания интеллекта искусственного отодвигаются на более поздний срок :)
Лично я знаю другое – параллельное композиция из известных алгоритмов компонент формирует новый алгоритм. А последний можно изменять, изменяя связи между компонентами и алгоритмы компонентов. При этом задача анализа параллельного алгоритма сводится часто к анализу последовательного алгоритма, эквивалентного параллельному.
И еще раз подчеркну, что распараллеливание ЛЮБОГО последовательного алгоритма – задача, фактически решенная уже давно (см. теорию синтеза цифровых устройств).
| |
Re: Q:авто и полуавто?
И еще раз подчеркну, что распараллеливание ЛЮБОГО последовательного алгоритма – задача, фактически решенная уже давно (см. теорию синтеза цифровых устройств).
Вот только ребята из Интела почему то не пользуются этим фактическим решением при реализации своих программных продуктов. Вы их надоумьте.
-----------------
Legendary intelligence officer Drozdov was nicknamed «Fabergé» owing to his unique capability to work with information, to get information, and to convert it into the most precious treasures. | |
Re: Q:авто и полуавто?
Вот только ребята из Интела почему то не пользуются этим фактическим решением при реализации своих программных продуктов. Вы их надоумьте.
Видимо их устраивает то, что есть? ;)
| | |
