Найти

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

• АППАРАТУРНО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ ДЛЯ БЫСТРОГО УМНОЖЕНИЯ КРОНЕКЕРОВА ПРОИЗВЕДЕНИЯ МАТРИЦ НА ВЕКТОР

  Е. И. Духнич, А. Г. Чефранов

  2021-02-25

  Аннотация ▼

  В статье на основе использования свойств произведения Кронекера (КП) матриц
  предлагается новый алгоритм для повышения эффективности выполнения операции ум-
  ножения КП на вектор. Указанная операция широко применяется при решении задач обра-
  ботки сигналов, изображений, криптографии и т.п., где выполняется формирование мат-
  риц большого размера с заданными свойствами с помощью КП матриц малого размера.
  При этом используются матрицы со следующими свойствами: ортогональные (унитар-
  ные), обращаемые, инволютивные. Умножение квадратной матрицы размера на
  вектор имеет вычислительную сложность O(n2). Поэтому при росте количества элемен-
  тарных матриц-сомножителей размер результирующей матрицы КП и сложность умно-
  жения ее на вектор растут экспоненциально. Это обстоятельство существенно повыша-
  ет время решения прикладных задач. Целью предлагаемой работы является построение
  алгоритма, ориентированного на аппаратную реализацию и ускоряющего процессы фор-
  мирования КП и умножения вектора на него. Предлагается совместить во времени эти
  процедуры. Таким образом матрица КП в явном виде фактически не рассчитывается. Вме-
  сто этого матрицы-сомножители КП итеративно умножаются на компоненты вектора
  за время O(nlog2n) и требуют линейной сложности памяти. Приведена схема вычислений с
  топологией гиперкуба для возможной аппаратной реализации предлагаемого алгоритма,
  которая легко поддается конвейеризации. В разделе 1 приведены определения и свойства
  КП, используемые при синтезе предлагаемого алгоритма. В разделе 2 рассмотрен иллюст-
  рирующий предлагаемый алгоритм пример с , на основе которого в разделе 3 пред-
  ложена аппаратурно-ориентированная структура его реализации для произвольного n.

• МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ

  А. В. Касаркин

  2021-02-25

  Аннотация ▼

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