Найти

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

• ПРЕОБРАЗОВАНИЕ ПРОСТЕЙШИХ СОРТИРУЮЩИХ СЕТЕЙ К НЕЧЕТНО-ЧЕТНОЙ СЕТИ БАТЧЕРА

  И.И. Левин , К. Н. Алексеев , А.А. Гуленок

  2024-10-08

  Аннотация ▼

  Все алгоритмы сортировки являются информационно-эквивалентными, поэтому выбор наи-
  более эффективного алгоритма обычно зависит от скорости его работы и от количества ис-
  пользуемой памяти. При параллельной, аппаратной реализации на эффективность алгоритмов
  сортировки также влияют: степень утилизации аппаратных ресурсов; латентность результи-
  рующей вычислительной структуры; количество и разрядность сортируемых элементов. Задача
  сортировки или упорядочивания данных не формализована в виде математических преобразова-
  ний, поэтому каждый из известных алгоритмов ее решения принято рассматривать как атомар-
  ную, независимую единицу. Переход от одного алгоритма решения задачи к другому возможен при
  описании задачи в виде информационного графа, вершины которого отражают элементарные
  выполняемые операции, а дуги – информационные зависимости между ними. Имея набор элемен-
  тарных преобразований, можно влиять на функциональную регулярность связей информационного
  графа, латентность вычислительной структуры, коэффициент параллелизма и т.д. К преимуще-
  ствам работы с информационным графом задачи также можно отнести сравнительную про-
  стоту используемого понятийного аппарата. Информационный граф задачи сортировки «пузырь-
  ком» представляет собой простейшую сортирующую сеть, построенную по принципу объедине-
  ния ступеней «голова-хвост». В данной работе показана и обоснована функциональная избыточ-
  ность подобных сортирующих сетей; приведены способы оптимизации числа операций и измене-
  ния порядка их следования. Основным результатом работы является методика преобразования
  сортирующих сетей в нечетно-четную сеть слияния Батчера. Разработана программа, автома-
  тически выполняющая преобразование сортирующих сетей и позволяющая подстраивать тополо-
  гию информационного графа под наиболее эффективный вид в зависимости от результирующей
  степени параллелизма вычислительной структуры. Обобщая полученные результаты, можно
  отметить, что автоматизированное приведение известных алгоритмов к «быстрым» может
  обеспечить получение оптимальной параллельно-конвейерной программы при заданных ограниче-
  ниях, что позволит значительно ускорить процесс их разработки.

• КОМПЛЕКС СРЕДСТВ ТРАНСЛЯЦИИ ПРОГРАММ НА ЯЗЫКЕ C В ПРОГРАММЫ НА ЯЗЫКЕ ПОТОКА ДАННЫХ COLAMO

  А. И. Дордопуло, A.A. Гуленок, А.В. Бовкун, И.И. Левин, В. А. Гудков, С.А. Дудко

  2021-02-25

  Аннотация ▼

  Рассматриваются программные средства трансляции последовательных программ
  на языке C в масштабируемые параллельно-конвейерные программы на языке программи-
  рования реконфигурируемых вычислительных систем COLAMO. В отличие от существую-
  щих средств высокоуровневого синтеза, результатом трансляции является не IP-ядро
  фрагмента задачи, а комплексное решение задачи для многокристальных реконфигурируе-
  мых вычислительных систем с автоматической синхронизацией информационных и управ-
  ляющих сигналов. Рассмотрены основные этапы трансляции последовательной программы
  на языке C: преобразование в информационный граф, анализ информационных зависимо-
  стей и выделение функциональных подграфов, преобразование в масштабируемую ресурсо-
  независимую параллельно-конвейерную форму и масштабирование программы на языке
  COLAMO для заданной многокристальной реконфигурируемой вычислительной системы.
  Масштабирование программы осуществляется с помощью методов редукции производи-
  тельности абсолютно-параллельной формы задачи – информационного графа, который
  адаптируется под архитектуру реконфигурируемой вычислительной системы. Разрабо-
  тан ряд правил, позволяющих существенно сократить число шагов преобразований при
  масштабировании задачи и обеспечить плотный поток обработки данных в функциональ-
  ных подграфах задачи. Созданный комплекс средств трансляции программ на языке C в
  конфигурационные файлы ПЛИС позволяет существенно сократить время синтеза вычис-
  лительной структуры задачи для многокристальных РВС и обеспечить сокращение общего
  времени решения задачи.