Найти

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

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

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

  6-20

  2025-10-01

  Аннотация ▼

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

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

  А.М. Альбертьян , И. И. Курочкин , Э.И. Ватутин

  142-153

  2021-10-05

  Аннотация ▼

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

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

  Е. А. Титенко , Э.И. Ватутин , М.А. Титенко , А. П. Локтионов , Э.В. Мельник

  2024-11-10

  Аннотация ▼

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

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

  А.О. Новиков , Э.И. Ватутин , С.И. Егоров , В.С. Титов

  2024-08-12

  Аннотация ▼

  Рассматривается математическая модель и базирующийся на ней алгоритм Даббагяна-Ву,
  предназначенный для построения нециклических пандиагональных латинских квадратов. Показано,
  что из-за высокой вычислительной сложности и факта существования других разновидностей
  пандиагональных квадратов, применение классических алгоритмов, таких как полный перебор и
  циклических сдвигов, недостаточно для построения полного перечня пандиагональных латинских
  квадратов. Этим подтверждается цель работы – исследование и экспериментальная апробация
  математических моделей и алгоритмов, предназначенных для задачи построения за приемлемое
  время. Здесь производится исследование алгоритма, представленного Даббагяном В. и Ву. Т, ко-
  торый предназначен для построения пандиагональных латинских квадратов простых порядков p,
  определяемых выражением p=6n+1. Можно сказать, что он является модификацией алгоритма
  циклического построения. То есть, позволяет получить из исходного циклического квадрата пан-
  диагональный нециклический. Преобразование выполняется путем циклических сдвигов в опреде-
  ленных ячейках в каждой строке исходного квадрата. Была разработана программная реализация
  алгоритма Даббагяна-Ву. Результат экспериментов подтвердил корректность предложенной
  Даббагяном В. и Ву. Т. методики построения. Таким образом, для порядка 13 удалось найти 72
  уникальных квадрата. К тому же, проведена попытка построения для порядка, не являющегося
  нечетным простым числом, например 25. В данном случае удалось получить 4 корректных пан-
  диагональных латинских квадрата. Путем дополнительных преобразований полученных наборов
  увеличить количество квадратов, так, для порядка 13 коллекция расширена до 1570, а для 25 – до
  210. Исследование позволило углубленно ознакомиться с алгоритмом Даббагяна-Ву и сделать вы-
  вод о его особенностях – к достоинствам относится его относительно низкая вычислительная
  сложность, а к недостаткам – полноценная корректность построений только для нечетных про-
  стых порядков. Полученные наборы квадратов в дальнейшем будут задействованы для получения
  их числовых характеристик при помощи распределенных вычислений.