Найти

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

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

  А.В. Болгак , Э.И. Ватутин , Д.А. Трокоз

  6-20

  2025-10-01

  Аннотация ▼

  Целью данной работы является оценка временных затрат на умножение квадратных бинарных матриц размером n × n устройства с конвейеризацией операции чтения данных из специализированной многопортовой памяти и ее сравнение с временными затратами прототипа. В данной работе использовались методы математической логики, теории множеств и графов, дискретных систем и устройств ЭВМ, теории проектирования конечных автоматов. В результате исследования было показано, что использование конвейеризации операции чтения данных из специализированной многопортовой памяти позволяет снизить временные затраты на обработку квадратных бинарных матриц размером n ≤ 2048 до 206,3 раза. Из полученных данных видно, что время загрузки и выгрузки исходных и результирующих данных для предложенного устройства существенно выше времени умножения матриц, ввиду чего частые загрузки и выгрузки матриц нецелесообразны. Например, при выполнении операции транзитивного замыкания бинарного отношения, представленного в виде бинарной матрицы, производится однократная загрузка исходной матрицы с последующей серией ее возведения в квадрат, что эффективно реализуется предложенным устройством. На основании полученных результатов можно сделать вывод, что предложенное устройство для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти обеспечивает существенный выигрыш во времени обработки и умножения квадратных бинарных матриц по сравнению с прототипом. Кроме того, результаты показали, что частые загрузки и выгрузки матриц нецелесообразны для предложенного устройства с конвейеризацией операции чтения из специализированной многопортовой памяти, так как затрачиваемое время на загрузку и выгрузку исходных и результирующих данных существенно превышает время на операцию умножения матриц

• РАСШИРЕННАЯ ПРОДУКЦИОННАЯ МАШИНА ВЫВОДА ДЛЯ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

  Е.A. Титенко , И.Е. Чернецкая , М.А. Титенко , Э. В. Мельник , Д. А. Трокоз

  2024-05-28

  Аннотация ▼

  Актуальность. В работе развивается теоретический подход организации параллельных
  вычислений на основе продукционной модели управления потоком данных. Продукционная пара-
  дигма параллельных вычислений имеет необходимые условия построения новых архитектур и ор-
  ганизации высокопроизводительных параллельных вычислений. Рассматриваются продукционные
  системы, управляющие наборами левых частей продукций (образцами). Цель – повышение эффек-
  тивности параллельного вывода решений за счет сокращения непродуктивных затрат времени на
  перебор возможных альтернатив в пространстве графа вывода. Метод решения основан на соз-
  дании расширенной машины символьного вывода для реализации параллельных вычислений. Маши-
  на символьного вывода – это абстрактная система, систематизирующая продукционный вывод
  как последовательность четырех вычислительно-поисковых этапов. Машина вывода задает об-
  щий вид однородной вычислительной системы. Главное отличие – декомпозиция базы продукцион-
  ных правил на отдельные подмножества на основе алгебры продукций и структуризации отноше-
  ний между продукциями. Вместо единой «плоской» структуры предлагается базу продукций де-
  композировать на части – ввести систему независимых подмножеств продукций. Параллельный
  вывод реализуется по отдельным подмножествам без потери общности, при этом перебор воз-
  можных альтернатив является сокращенным. Каждое подмножество продукций имеет специ-
  альное слово-маркер, по значению которого активизируется только одно подмножество продук-
  ций. Оно загружается в операционную часть однородной вычислительной системы для параллель-
  ного исполнения. Результаты. Показано, что количественные оценки сокращения времени вывода
  зависят от общего числа продукций, количества образуемых подмножеств и их размера. Модели-
  рование показало, что даже простейшая декомпозиция на два подмножества (одно подмножест-
  во состоит из 2-х продукций) дает временной выигрыш (1,07-1,52) раз, пропорциональный общему
  числу продукций. Выводы. Построенная расширенная машина символьного вывода является осно-
  вой для последующего создания архитектуры однородной вычислительной системы с комбинацией
  централизованного и локального управления, что позволяет вычислительным блокам однородной
  операционной части параллельно работать без избыточного обращения к обшей памяти.