МЕТОДЫ  РАСПАРАЛЛЕЛИВАНИЯ  ИМИТАЦИИ  ОТЖИГА  ПРИ  ДЕЦЕНТРАЛИЗОВАННОМ  РЕШЕНИИ  ЗАДАЧИ  СОСТАВЛЕНИЯ  РАСПИСАНИЯ  С  ОПРЕДЕЛЕНИЕМ  МИНИМАЛЬНОГО  КОЛИЧЕСТВА  РЕСУРСОВ

Клименко  Анна  Борисовна

канд.  техн.  наук,  младший  научный  сотрудник,  научно-исследовательский  институт  многопроцессорных  вычислительных  систем  имени  академика  А.В.  Каляева  федерального  государственного  автономного  образовательного  учреждения  высшего  профессионального  образования  «Южный  федеральный  университет»,  РФ,  г.  Таганрог

E-mail: 

Клименко  Владислав  Валерьевич

канд.  техн.  наук,  научный  сотрудник,  научно-исследовательский  институт  многопроцессорных  вычислительных  систем  имени  академика  А.В.  Каляева  федерального  государственного  автономного  образовательного  учреждения  высшего  профессионального  образования  «Южный  федеральный  университет»,  РФ,  г.  Таганрог

Таранов  Антон  Юрьевич

младший  научный  сотрудник,  научно-исследовательский  институт  многопроцессорных  вычислительных  систем  имени  академика  А.В.  Каляева  федерального  государственного  автономного  образовательного  учреждения  высшего  профессионального  образования  «Южный  федеральный  университет»,  РФ,  г.  Таганрог

METHODS  OF  SIMULATED  ANNEALING  PARALLELIZING  FOR  THE  SCHEDULING  AND  RESOURCE  ALLOCATION  DECENTRALIZED  PROBLEM  SOLVING

Klimenko  Anna

Ph.D  in  Computer  science,  junior  research  fellow,  SFedU  Acad.  Kalyaev  Scientific  Research  Institute  of  Multiprocessor  Computer  Systems,  Russia,  Taganrog

Klimenko  Vladislav

Ph.D  in  Computer  science,  research  fellow,  SFedU  Acad.  Kalyaev  Scientific  Research  Institute  of  Multiprocessor  Computer  Systems,  Russia,  Taganrog

Taranov  Anton

junior  research  fellow,  SFedU  Acad.  Kalyaev  Scientific  Research  Institute  of  Multiprocessor  Computer  Systems,  Russia,  Taganrog

Работа  выполнена  при  поддержке  РФФИ,  грантов  14-08-00776,  13-08-01172

АННОТАЦИЯ

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

ABSTRACT

The  paper  contains  the  analytical  review  and  comparison  of  the  simulated  annealing  parallelizing  methods  applied  to  the  scheduling  and  resource  allocation  problem.  The  problem  formalization  is  presented,  well-known  methods  of  simulated  annealing  parallelizing  are  considered,  the  summary  of  the  one’s  prospects  in  the  decentralized  system  using  are  made. 

Ключевые  слова:  параллельные  вычисления;  информационно-управляющая  система;  реконфигурация;  восстановление;  имитация  отжига.

Keywords:  parallel  computing;  informational-control  system;  reconfiguration;  recovery;  simulated  annealing.

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

Одной  из  ключевых  задач  децентрализованного  управления  является  организация  восстановления  после  сбоя  [2],  то  есть  реконфигурация  ИУС,  которая  заключается  в  перераспределении  подзадач  основной  задачи  управления  (ЗУ)  по  работоспособным  ВУ.  Такое  перераспределение  является  по  сути  составлением  расписания  выполнения  подзадач  ЗУ  с  одновременным  формированием  необходимых  ресурсов  с  условием  выполнения  ЗУ  в  срок.

Следует  отметить,  что  в  случае  работы  системы  реального  времени  реконфигурация  подразумевает  еще  и  следующее:  не  только  подзадачи  должны  быть  распределены  по  ВУ  определенным  образом,  но  еще  и  сама  задача  реконфигурации  должна  быть  решена  таким  образом,  что:

T _ЗУ+T_РЕК=T_ДЕК,                                           (1)

где:  T_ЗУ  —  время  решения  подзадач  ЗУ  работоспособными  ВУ;

T _РЕК  —  время  реконфигурации  системы;

T _ДЕК  —  время,  за  которой  система  должна  восстановиться  после  сбоя.

Такая  постановка  вопроса  делает  нецелесообразным  использование  точных  методов  решения  типа  метода  «ветвей  и  границ»  даже  при  средней  размерности  входных  данных.  С  другой  стороны,  перспективным  кажется  использование  метаэвристик,  которые  позволяют  получить  приближенные  решения  за  приемлемое  время.  Учитывая,  что  ИУС  может  включать  более  одного  ВУ  (а  ИУС  комплексных  объектов,  как  правило,  построены  на  основе  многопроцессорных  комплексов),  применяемые  алгоритмы  могут  быть  распараллелены.

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

·     независимость  параллельных  ветвей  вычислительного  процесса  друг  от  друга;

·     степень  децентрализации;

·     перспективы  получения  решения  при  выходе  из  строя  одного  или  нескольких  ВУ. 

Формальная  постановка  задачи

В  качестве  примеров  формальной  постановки  задачи  составления  расписания  с  определением  минимального  количества  ресурсов  можно  привести  работы  А.  Барского  и  Костенко  [1,  3].  В  общем  виде  задача  может  быть  формализована  и  следующим  образом.  Даны:

1)  ациклический  граф,  описывающий  задачу  управления  и  разбитый  на  подзадачи,  которые  требуется  распределить  по  ВУ:

G =(H,X,W),                                       (2)

где:  H={j}={1,…,n}  —  вершины  графа,

X ={x_j}  —  трудоемкости  задач,

W -  множество  дуг,  определяющих  связи  между  задачами  по  информации,  каждая  из  которых  взвешена  значением  w_kl,  которое  определяет  объем  передаваемых  данных  между  k-ой  и  l-ой  задачами.

2)  В  общем  случае  неоднородное  множество  ВУ  M={m_i},i=1,…k, 

m_i=<i,  prod_i,  v_i,  s_i>   ,                                         (3)

где:  i  —  порядковый  номер  ВУ,

  —  производительность  ВУ, 

  —  стоимость  ВУ;

  —  скорость  передачи  результата  вычислений  (решения  задачи)  в  КС. 

3)  Максимально  допустимое  время  решения  задачи  T_plan.

4)  Также  обозначим  фактическое  время  решения  задачи,  описанной  информационным  графом  G  через  T_c. 

Таким  образом,  формально  задача  может  быть  представлена  в  следующем  виде:  среди  множества  вариантов  комплектаций  системы  ВУ  K={k₁,…k_q}  с  соответствующими  стоимостями  комплектации  S={s₁,…s_q}  с  исходными  данными,  перечисленными  в  п.п.  1—4  необходимо  найти    и  план  распределения  задач  по  ВУ  при  выполнении  условия:

;                                                      (4)

Параллельная  ИО

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

·     независимые  параллельные  запуски  с  синхронизацией  и  асинхронные;

·     распараллеливание,  базирующееся  на  декомпозиции  целевой  функции;

·     распараллеливание,  базирующееся  на  разбиении  пространства  решений  на  подобласти;

·     распараллеливание  внутри  температурной  итерации  с  параллельным  выполнением  марковских  цепей.

Рассмотрим  кратко  каждый  из  методов  распараллеливания  в  выделенных  аспектах.

Метод  независимых  параллельных  запусков  (Multiple  Independent  Runs,  MIP)  заключается  в  следующем:  на  множестве  ВУ  производится  запуск  алгоритмов  ИО,  возможно,  с  различными  точками  инициализации  вычислений,  с  выбором  наилучшего  решения  по  завершении.  Независимые  параллельные  запуски  с  синхронизацией  предполагают  периодический  обмен  текущими  решениями  между  ВУ  с  выбором  наилучшей  точки  для  продолжения  вычислений.  Вполне  очевидно,  что  метод  независимых  параллельных  запусков  может  быть  реализован  как  с  использованием  центрального  управляющего  элемента,  так  и  без;  в  случае  отсутствия  последнего  каждый  ВУ  должен  будет  перебрать  решения,  полученные  другими  ВУ  системы,  и  здесь  важную  роль  может  играть  топология  соединений  между  ВУ.  Аналогично  метод,  основанный  на  разбиении  пространства  решений  на  области,  довольно  просто  реализуем  децентрализованно,  однако  в  [3]  авторы  говорят  о  проблемах  отслеживания  получаемых  решений  и  их  отношения  к  той  или  иной  области  пространства  решений,  особенно  для  задачи  составления  расписаний.  Метод,  в  основу  которого  положена  декомпозиция  целевой  функции,  является  проблемно-ориентированным  и  подходит  для  целевых  функций  вида:

F(x₁,  x₂,  …  x_n)=F(x₁)+F(x₂)+…+F(x_n).                                (5)

Примером  задачи,  для  которой  применялся  такой  метод  распараллеливания,  является  задача  размещения  транзисторов  на  интегральной  схеме,  поскольку  если  в  качестве  ЦФ  рассматривать  количество  перекрывающихся  элементов,  то  оно  может  быть  посчитано  как  сумма  перекрывающихся  элементов  отдельных  участков  интегральной  схемы.  Однако,  при  постановке  задачи  реконфигурации,  как  правило,  в  качестве  ЦФ  выбираются  функции,  которые  затруднительно  представить  в  виде  (5):  это  либо  стоимость  системы  ВУ,  либо  суммарное  время  выполнения  ЗУ.

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

Анализ  методов  распараллеливания

Сведем  анализ  методов  распараллеливания  в  таблицу.

Таблица  1.

Результаты  сравнения  методов  распараллеливания  имитации  отжига

Выводы

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

Список  литературы:

1.Барский  А.Б.  Параллельные  процессы  в  вычислительных  системах:  планирование  и  организация.  М.:  Радио  и  связь,  1990. 

2.Каляев  И.А,  Мельник  Э.В.  Децентрализованные  системы  компьютерного  управления.  Ростов  н/Д:  Издательство  ЮНЦ  РАН,  2011.  —  196  с.

3.Костенко  В.А.  Проблемы  разработки  итерационных  алгоритмов  для  построения  расписаний  с  одновременным  нахождением  необходимого  количества  ресурсов  и  их  характеристик  //  Искусcтвенный  интеллект  (Донецк),  —  2002.  —  №  2,  —  С.  141—150.

4.Alba  E.,  Parallel  Methaheuristics.  A  new  class  of  algorithms.  Wiley-interscience,  New  Jersey,  2005. 

5.Azencott  R.,  Ed.,  Simulated  Annealing:  Parallelization  Techniques.  New  York:  John  Wiley  and  Sons.  1992.  —  P.  47—79.

6.Busetti  F.  Simulated  annealing  overview  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018  (дата  обращения:  20.02.2012).

7.Ingber  L.,  Simulated  annealing:  practice  versus  theory  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.104  (дата  обращения  20.03.2013).