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

Аннотация

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