OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 01:43

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Параллелизм
СообщениеДобавлено: Четверг, 17 Октябрь, 2013 13:12 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Современные процессоры содержат все больше ядер. И чтобы полностью использовать ресуры компьютера необходимо какие-то действия делать параллельно. Но при этом программа становится сложнее. Становится сложнее тестировать и доказывать правильность программы. Для однопотоковой программы есть методы верификации (предусловия, инварианты, постусловия), которые можно использовать на практике и с их помощью доказывать корректность программ.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Четверг, 17 Октябрь, 2013 13:24 

Зарегистрирован: Четверг, 17 Ноябрь, 2005 11:51
Сообщения: 2935
Откуда: г. Ярославль
Если понимать процесс в общем, как "последовательность преобразований состояния" объекта (по выражению Н.Вирта), то наверняка можно найти массу реализаций. Например, агентные системы, которые мы можем моделировать в BlackBox с помощью межмодульной шины и отложенных действий.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Четверг, 17 Октябрь, 2013 13:59 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Почитайте Легалова А.И. на softcraft.ru


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Четверг, 17 Октябрь, 2013 14:23 

Зарегистрирован: Вторник, 29 Август, 2006 12:32
Сообщения: 2662
Откуда: Россия, Ярославль
Ресурс недоступен, видимо, речь об этом: Пифагор


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Четверг, 17 Октябрь, 2013 14:34 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Пётр Кушнир писал(а):
Ресурс недоступен,

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 10:24 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Иван Кузьмицкий писал(а):
Например, агентные системы, которые мы можем моделировать в BlackBox с помощью межмодульной шины и отложенных действий.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 10:55 

Зарегистрирован: Вторник, 29 Август, 2006 12:32
Сообщения: 2662
Откуда: Россия, Ярославль
Ну вы какие задачи решать будете?
Данные с формы в БД перекидывать?
Видео кодировать в реальном времени?
Вычислять числа Фибоначчи?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 11:19 

Зарегистрирован: Четверг, 17 Ноябрь, 2005 11:51
Сообщения: 2935
Откуда: г. Ярославль
Rifat писал(а):
...но и чтобы можно было формально доказать коррекность такой программы.
Это очень интересное место. Работая с асинхронными взаимодействиями, которые по факту являются параллельными, можно заметить, что детерминированность асинхронных программ легко пропадает.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 11:30 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4695
Откуда: Россия, Орёл
Всё зависит от постановки задачи. Универсального метода пока не существует и не факт, что он вообще появится. Если вы хотите выжать из системы именно вычислительную мощность (расчёты), то разбив задачу на параллельные (независимые) и использовав обмен сообщениями между ними, можно доказать формальную корректность каждой подзадачи, а так как они независимы, то и вся задача корректна.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 11:37 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4695
Откуда: Россия, Орёл
Элементы параллельного программирования, 1983
Авторы: Вальковский В. А., Котов В. Е., Марчук А. Г., Миренков Н. Н.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Пятница, 18 Октябрь, 2013 12:22 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Пётр Кушнир писал(а):
Ну вы какие задачи решать будете?

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Суббота, 19 Октябрь, 2013 07:58 

Зарегистрирован: Вторник, 26 Январь, 2010 09:31
Сообщения: 717
Откуда: Барнаул
Rifat писал(а):
1) реализован ли данный подход где-нибудь?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Суббота, 19 Октябрь, 2013 14:41 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Kemet писал(а):
Rifat писал(а):
1) реализован ли данный подход где-нибудь?

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

Да.
+Composita

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Суббота, 19 Октябрь, 2013 15:14 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Rifat писал(а):
Насколько я знаю, в BlackBox реализована кооперативная многозадачность, то есть каждый отдельный момент времени выполняется только одна задача.
Вообще-то, вытесняющая многозадачность не гарантирует, что в любой момент времени будет выполняться больше одного потока.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Суббота, 19 Октябрь, 2013 17:30 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Если использовать взаимодействия на сообщениях изолированных процессов, то один из методов доказательства корректности - построение модели на какой-нибудь Promela и далее автоматизированный Model-Checking.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Понедельник, 21 Октябрь, 2013 10:45 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Madzi писал(а):
Kemet писал(а):
Rifat писал(а):
1) реализован ли данный подход где-нибудь?

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

Да.
+Composita

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Понедельник, 21 Октябрь, 2013 12:01 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Rifat писал(а):
Madzi писал(а):
Kemet писал(а):
Активный Оберон?

Да.
+Composita

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Понедельник, 21 Октябрь, 2013 12:37 

Зарегистрирован: Вторник, 26 Январь, 2010 09:31
Сообщения: 717
Откуда: Барнаул
Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Понедельник, 21 Октябрь, 2013 13:16 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Kemet писал(а):
Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Параллелизм
СообщениеДобавлено: Понедельник, 21 Октябрь, 2013 13:57 

Зарегистрирован: Вторник, 26 Январь, 2010 09:31
Сообщения: 717
Откуда: Барнаул
Madzi писал(а):
Kemet писал(а):
Madzi писал(а):
Для каждого "активного" объекта создаётся своя нить выполнения (не на аппаратном уровне, так как переключение контекстов дорого)

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

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

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB