Найти

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

• КОММУТАЦИОННАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ СРАВНЕНИЙ ЭЛЕМЕНТОВ ДЛЯ ПРОДУКЦИОННЫХ СИСТЕМ, УПРАВЛЯЕМЫХ ПОТОКОМ ДАННЫХ

  E.A. Титенко, E.В. Талдыкин

  2021-02-25

  Аннотация ▼

  В статье достигается цель - сокращение временных затрат на генерацию сочетаний
  элементов множества. Элементы множества формируются из образцов (левых частей) про-
  дукционных правил. Основная задача заключается в построении эффективных по времени схем
  (алгоритмов) параллельной генерации сочетаний элементов массива. Применительно к продук-
  ционным системам такие схемы необходимы для активации подмножества продукций, приме-
  нимых к символьным данным на текущем шаге. За основу взят и развит известный алгоритм
  параллельного пузырька. Схема коммутации «параллельный пузырек» состоит из двух чере-
  дующихся вариантов коммутации элементов в пары. Эти коммутации основаны на локальном
  объединении в пары элементов массива, имеющих смежные индексы. Такое локальное объеди-
  нение элементов в пары приводит к «малым» перемещениям элементов по длине массива и ре-
  гулярному характеру генерации пар. В каждой паре выполняется операция сравнения-обмена
  операндов. Для продукционных систем операция сравнения сводится к поиску пересечений об-
  разцов и формированию списка конфликтных слов. Сокращение времени генерации сочетаний
  основывается на построении вариантов коммутации с распределенным объединением элемен-
  тов в пары с шагом, равным 4. Разработанная схема коммутации содержит на нечетных ша-
  гах коммутации с локальным объединением элементов в пары. На четных шагах выполняется
  коммутация-ускоритель с распределенным объединением элементов в пары. Моделирование
  работы разработанной схемы коммутации осуществлялось на типовых задачах сортировки и
  полного перебора пар элементов. Установлено сокращение временных затрат по сравнению с
  четно-нечетной сортиовкой на 15-18%. В работе определена линейная зависимость времени
  сортировки с углом наклона меньше 1. Это позволяет использовать схему коммутации для
  продукционных систем большого размера. Локальные и распределенные связи в схеме коммута-
  ции сохраняют свойство регулярности. Эта особенность определяет аппаратную реализацию
  схемы в виде параллельного коммутатора с естественным масштабированием. Данная схема
  может использоваться в специализированном продукционном устройстве для декомпозиции
  продукционной системы на независимые подмножества продукций.