Найти

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

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

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

  2020-10-11

  Аннотация ▼

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