OberonCore
https://forum.oberoncore.ru/

Параллелизм
https://forum.oberoncore.ru/viewtopic.php?f=27&t=4557
Страница 1 из 2

Автор:  Rifat [ Четверг, 17 Октябрь, 2013 13:12 ]
Заголовок сообщения:  Параллелизм

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

Н. Вирт в статье "Хорошие идеи: взгляд из Зазеркалья" пишет: "Много лет спустя некоторые разработчики все чаще стали утверждать, что функциональные языки являются наилучшим средством для введения параллелизма - хотя было бы более уместно сказать "для облегчения работы компиляторов по определению возможностей распараллеливания программ". Вообще-то относительно несложно определить, какие части выражения могут вычисляться параллельно. Более важно то, что параллельно могут вычисляться параметры вызываемой функции, если запрещены побочные эффекты - которые не могут возникать в истинно функциональном языке. В то время, как это обстоятельство может быть истинным и, возможно, минимальным преимуществом функциональных языков, объектно-ориентированный подход предлагает более эффективный способ хорошего использования параллелизма, когда поведение каждого объекта представляется в виде отдельного процесса. ".

Меня заинтересовала фраза "объектно-ориентированный подход предлагает более эффективный способ хорошего использования параллелизма, когда поведение каждого объекта представляется в виде отдельного процесса" и у меня есть несколько вопросов:
1) реализован ли данный подход где-нибудь?
2) если да, то позволяет ли данный подход формально доказывать корректность программ?
3) если не позволяет, то есть ли другие методы параллелизма, которые можно реализовать и при этом формально доказывать корректность таких программ.

Автор:  Иван Кузьмицкий [ Четверг, 17 Октябрь, 2013 13:24 ]
Заголовок сообщения:  Re: Параллелизм

Если понимать процесс в общем, как "последовательность преобразований состояния" объекта (по выражению Н.Вирта), то наверняка можно найти массу реализаций. Например, агентные системы, которые мы можем моделировать в BlackBox с помощью межмодульной шины и отложенных действий.

Автор:  albobin [ Четверг, 17 Октябрь, 2013 13:59 ]
Заголовок сообщения:  Re: Параллелизм

Почитайте Легалова А.И. на softcraft.ru

Автор:  Пётр Кушнир [ Четверг, 17 Октябрь, 2013 14:23 ]
Заголовок сообщения:  Re: Параллелизм

Ресурс недоступен, видимо, речь об этом: Пифагор

Автор:  albobin [ Четверг, 17 Октябрь, 2013 14:34 ]
Заголовок сообщения:  Re: Параллелизм

Пётр Кушнир писал(а):
Ресурс недоступен,

Опять доступен, видимо были временные проблемы.

Автор:  Rifat [ Пятница, 18 Октябрь, 2013 10:24 ]
Заголовок сообщения:  Re: Параллелизм

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

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

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

Автор:  Пётр Кушнир [ Пятница, 18 Октябрь, 2013 10:55 ]
Заголовок сообщения:  Re: Параллелизм

Ну вы какие задачи решать будете?
Данные с формы в БД перекидывать?
Видео кодировать в реальном времени?
Вычислять числа Фибоначчи?

Автор:  Иван Кузьмицкий [ Пятница, 18 Октябрь, 2013 11:19 ]
Заголовок сообщения:  Re: Параллелизм

Rifat писал(а):
...но и чтобы можно было формально доказать коррекность такой программы.
Это очень интересное место. Работая с асинхронными взаимодействиями, которые по факту являются параллельными, можно заметить, что детерминированность асинхронных программ легко пропадает.

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

Автор:  Борис Рюмшин [ Пятница, 18 Октябрь, 2013 11:30 ]
Заголовок сообщения:  Re: Параллелизм

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

А относительно изначально асинхронных систем Иван прав. Там вообще правила игры другие.

Кажется мне, что где-то книжечка Котова была на эту тему...

Автор:  Борис Рюмшин [ Пятница, 18 Октябрь, 2013 11:37 ]
Заголовок сообщения:  Re: Параллелизм

Элементы параллельного программирования, 1983
Авторы: Вальковский В. А., Котов В. Е., Марчук А. Г., Миренков Н. Н.

Автор:  Rifat [ Пятница, 18 Октябрь, 2013 12:22 ]
Заголовок сообщения:  Re: Параллелизм

Пётр Кушнир писал(а):
Ну вы какие задачи решать будете?

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

Или, например, другой пример. Допустим, есть код:
BEGIN
Mod1.Method1;
Mod2.Method2;
END;
В данном случае последовательно вызываются два метода из разных модулей, при этом они независимы по параметрам и теоретически их можно выполнять параллельно.

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

Автор:  Kemet [ Суббота, 19 Октябрь, 2013 07:58 ]
Заголовок сообщения:  Re: Параллелизм

Rifat писал(а):
1) реализован ли данный подход где-нибудь?

Активный Оберон?

Автор:  Madzi [ Суббота, 19 Октябрь, 2013 14:41 ]
Заголовок сообщения:  Re: Параллелизм

Kemet писал(а):
Rifat писал(а):
1) реализован ли данный подход где-нибудь?

Активный Оберон?

Да.
+Composita

Только не понятно как это может позволить/не позволить доказать корректность программы ?

Автор:  Valery Solovey [ Суббота, 19 Октябрь, 2013 15:14 ]
Заголовок сообщения:  Re: Параллелизм

Rifat писал(а):
Насколько я знаю, в BlackBox реализована кооперативная многозадачность, то есть каждый отдельный момент времени выполняется только одна задача.
Вообще-то, вытесняющая многозадачность не гарантирует, что в любой момент времени будет выполняться больше одного потока.

Автор:  Илья Ермаков [ Суббота, 19 Октябрь, 2013 17:30 ]
Заголовок сообщения:  Re: Параллелизм

Если использовать взаимодействия на сообщениях изолированных процессов, то один из методов доказательства корректности - построение модели на какой-нибудь Promela и далее автоматизированный Model-Checking.

Автор:  Rifat [ Понедельник, 21 Октябрь, 2013 10:45 ]
Заголовок сообщения:  Re: Параллелизм

Madzi писал(а):
Kemet писал(а):
Rifat писал(а):
1) реализован ли данный подход где-нибудь?

Активный Оберон?

Да.
+Composita

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

Автор:  Madzi [ Понедельник, 21 Октябрь, 2013 12:01 ]
Заголовок сообщения:  Re: Параллелизм

Rifat писал(а):
Madzi писал(а):
Kemet писал(а):
Активный Оберон?

Да.
+Composita

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

В этих языках (Composita по сути расширение Active Oberon для моделирования) вытесняющая мультизадачность. Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого), но для каждого объекта выделено строго определённое время выполнения. Нагрузка равномерно распределяется на все процессоры (т.к. это было основным направлением при проектировании Активного Оберона). Т.е. чем больше процессоров, тем больше задач выполняется одновременно. Быстрее - не совсем корректный термин. Если в программе нет сильной зависимости одних частей от других - то да, быстрее. Если зависимости есть, то количество процессоров никак не повлияет на её исполнение.

Сборщик мусора работает в своей нити.

Для реал-тайм и хард-реал-тайм задач сборщик мусора использовать запрещено. Т.е. если объект имеет директиву
Код:
{realtime}
, то модуль не скомпилируется если у объекта есть выделение/удаление динамической памяти.

Параллельно в системе могут присутствовать не реал-тайм объекты, использующие сборку мусора.

Автор:  Kemet [ Понедельник, 21 Октябрь, 2013 12:37 ]
Заголовок сообщения:  Re: Параллелизм

Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

Конечно же каждая активность имеет аппаратную поддержку, если таковая есть в используемом процессоре, например для архитектуры i386/AMD64 каждая активность(нить) имеет собственный TSS, т.е происходит реальное аппаратное переключение контекста выполнения, иное было бы более чем странным.

Автор:  Madzi [ Понедельник, 21 Октябрь, 2013 13:16 ]
Заголовок сообщения:  Re: Параллелизм

Kemet писал(а):
Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

Конечно же каждая активность имеет аппаратную поддержку, если таковая есть в используемом процессоре, например для архитектуры i386/AMD64 каждая активность(нить) имеет собственный TSS, т.е происходит реальное аппаратное переключение контекста выполнения, иное было бы более чем странным.

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

Автор:  Kemet [ Понедельник, 21 Октябрь, 2013 13:57 ]
Заголовок сообщения:  Re: Параллелизм

Madzi писал(а):
Kemet писал(а):
Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

Конечно же каждая активность имеет аппаратную поддержку, если таковая есть в используемом процессоре, например для архитектуры i386/AMD64 каждая активность(нить) имеет собственный TSS, т.е происходит реальное аппаратное переключение контекста выполнения, иное было бы более чем странным.

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

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

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/