Найти

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

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

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

  2021-02-25

  Аннотация ▼

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