Найти

Результаты поиска

• ПРЕДСТАВЛЕНИЕ ГРАФОВ С АССОЦИАТИВНЫМИ ОПЕРАЦИЯМИ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ SET@L

  И.И. Левин , И. В. Писаренко, Д.В. Михайлов , А. И. Дордопуло

  2020-10-11

  Аннотация ▼

  Как правило, информационный граф с ассоциативными операциями реализуется в
  виде последовательной («голова/хвост») или параллельной («разбиение пополам») топ о-
  логии, причем обе структуры содержат одинаковое число операционных вершин. Реду к-
  ционные преобразования графов с представленными топологиями при недостатке в ы-
  числительного ресурса не обеспечивают создание эффективной ресурсонезависимой пр о-
  граммы: вариант «разбиение пополам» характеризуется нерегулярной межитерацион-
  ной коммутацией, а структура «голова/хвост» – увеличенной скважностью данных при
  редукции. В данной статье предлагается преобразовать топологию графа с ассоци а-
  тивными операциями в один из комбинированных вариантов с последовательными и па-
  раллельными фрагментами вычислений, синтезированный в соответствии с заданным
  вычислительным ресурсом. Это позволяет повысить удельную производительность в ы-
  числений при редукции. Модифицированная топология включает изоморфные подграфы с
  топологией «разбиение пополам», содержащие максимальное число аппаратно реализу е-
  мых операционных вершин, а обработка промежуточных данных осуществляется по
  принципу «голова/хвост». Вычислительная структура для рассмотренной топологии
  имеет минимальную латентность и состоит из одного базового подграфа и одной вер-
  шины, в которую редуцируется блок обработки промежуточных данных с топологией
  «голова/хвост». Разработан алгоритм, позволяющий в зависимости от доступного а п-
  паратного ресурса перейти от базового последовательного варианта реализации к раз-
  личным комбинированным топологиям вплоть до предельного случая топологии «разби е-
  ние пополам». Поскольку традиционные методы параллельного программирования могут
  описать множество топологий только в виде набора отдельных подпрограмм, для соз-
  дания ресурсонезависимого описания графов с ассоциативными операциями предлагае т-
  ся использовать язык архитектурно-независимого программирования Set@l. Принципы
  построения топологий «голова/хвост» и «разбиение пополам» описаны в виде признаковметода обработки множеств на языке Set@l, а ресурсонезависимая программа оперирует
  этими типами и типами параллелизма для модификации топологии графа и последующей
  редукции производительности в соответствующих аспектах программы.

• ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗБИЕНИЯ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ

  Б.К. Лебедев, О. Б. Лебедев, Е. О. Лебедева

  2020-07-20

  Аннотация ▼

  Работа алгоритма разбиения базируется на использовании коллективной эволюцион-
  ной памяти, под которой подразумевается информация, отражающая историю поиска
  решения и хранится независимо от индивидуумов. Алгоритм, связанный с эволюционной
  памятью, стремится к запоминанию и многократному использованию способов достиже-
  ния лучших результатов. Коллективная эволюционная память алгоритма разбиения со-
  стоит из некоторого количества статистических индикаторов, отображающих для ка-
  ждого выполненного варианта число θ его вхождений в состав лучших решений на выпол-
  ненных генерациях алгоритма и число, δ определяющее насколько полезна реализованная
  альтернатива при формировании результатов на прошлых генерациях алгоритма. Коллек-
  тив не имеет централизованного управления, и в связи с этим используется непрямой об-
  мен информацией. Непрямой обмен состоит в выполнении неких действий, в различное
  время, при которых происходит изменение некоторых частей эволюционной памяти одним
  агентом. В дальнейшем происходит использование этой измененной информации другими
  агентами, в этих частях. Вначале на каждой итерации конструктивным алгоритмом
  формируется nk решений Qk,. Каждое решение Qk является отображением Fk=V→X, пред-
  ставляется в виде двудольного подграфа Dk и формируется путем последовательного на-
  значения элементов в узлы. Формирование каждого решения Qk выполняется множеством
  агентов A, посредством вероятностного выбора каждым агентом ai узла vj. Процесс на-
  значения элемента в узел включает две стадии. На первой стадии выбирается агент ai, а
  на второй стадии − узел vj. При этом должно выполняться ограничение: каждому агенту
  множества A соответствует один единственный узел множества V. Рассчитывается
  оценка ξk решения Qk и оценка полезности δk множества альтернатив, реализованных
  агентами в решении Qk. На втором этапе агенты увеличивают в интегральной россыпи
  альтернатив R* интегральную полезность множества альтернатив на величину δk..
  На третьем этапе осуществляется снижение оценок полезности δk интегральной россыпи
  альтернатив на величину μ. В работе используется циклический метод формирования ре-
  шений. В этом случае наращивание оценок интегральной полезности δk множества пози-
  ций P выполняется после полного формирования множества решений Q на итерации l.
  Экспериментальные исследования проводились на основе сформированных тестовых при-
  меров с полученным ранее оптимальным решением. Полученные результаты сравнивались
  с результатами полученными другими известными алгоритмами разбиения схем на части.
  Для сравнения был сформирован набор стандартных бенчмарок. Проанализировав получен-
  ные результаты, можно сделать вывод, что предложенный метод позволяет получать на
  4–5 % решения качественнее, чем его аналоги.