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