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

Аннотация

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