Найти

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

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

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

  2020-10-11

  Аннотация ▼

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

• ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ

  Д. В. Михайлов

  177-188

  2021-10-05

  Аннотация ▼

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

• ПРЕОБРАЗОВАНИЕ НЕКОТОРЫХ ВИДОВ ПОСЛЕДОВАТЕЛЬНЫХ ИНФОРМАЦИОННЫХ ГРАФОВ В ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНУЮ ФОРМУ

  Д. В. Михайлов

  2021-02-25

  Аннотация ▼

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