автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Параллельные символьные процессоры с позиционной формой представления данных

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ф д

----------------------------------------------------у <\ г"ч / 1П

На правах рукописи УДК 631.3

Шуклина ЕЬгения Викторовна

ПАРАЛЛЕЛЬНЫЕ СИМВОЛЬНЫЕ ПРОЦЕССОРЫ С ПОЗИЦИОННОЙ ФОРМОЙ ПРЕДСТАВЛЕНИЯ ДАННЫХ

Специальность 05 13 05 "Элементы и устройства вычислительной техники и систем управления"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

КУРСК 2000

Работа выполнена в Курском государственном техническом университет!

Научные руководители:

доктор технических наук В.М. Довгаль

кандидат технических наук Ф.А. Старков.

Официальные оппоненты:

доктор технических наук О.И. Атакищев

кандидат технических наук В.И. Лопин.

Ведущая организация : СКБ "Авиаавтоматика" г. Курск.

Защита состоится 2 июня 2000 г. в 10е2 часов на заседании ди< сертационного совета Д064. 50. 02 при Курском государственном техш ческом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке университета.

Отзывы на автореферат в двух экземплярах, заверенные печать* просьба отсылать по адресу: 305040, г. Курск, ул. 50 лет Октября, 9 Курск, гос. техн. ун-т. ученому секретарю специализированного сове; Д064. 50. 02.

Автореферат разослан 28 апреля 2000 г.

Ученый секретарь диссертационногоодвета Д064.50,02 доктор технических наук / В.М. Довгаль

-з-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Информатизация общества относится к глобальным тенденциям его развития, что определяет потребность-в создает эффективных лингвистических, алгоритмических, программных и технических средств обработки информации. Особую значимость приобретает проблема создания средств обработки символьной информации, юс кольку она занимает до 90% объемов циркулирующей информации в ювременных системах обработки данных. Символьная информация имеет Зольшие обьемы и разнообразие (публикации, текстовые документы, затеи программ, архивные данные и т.д.). Следует отметить, что ежеминутно в мировой практике создается до 500 тысяч страниц одних только документов.

Символьная информация в виде текстов составляет основу как для формирования текстов задач, так и алгоритмов их решения. Высокая социальная значимость проблем обработки символьной информации (ОСИ) определила существование дорогостоящих государственных и межгосударственных научно-исследовательских программ, например, таких как SPI (США), ALVEY (Великобритания), TELETEXT, JESSI (страны Европейского союза) и др.

Доминирование символьной информации, быстрый рост ее обьемов и разнообразия требует адекватных алгоритмических, программных н технических средств обработки. Фундаментальным проблемам ОСИ посвятили свои работы отечественные и зарубежные авторы Р. Грисоулд, A.U. Колмогоров, Дж. Маккарти, A.A. Марков, Т. Мотоохо, Дж. Фон Нейман, Д.А. Поспелов, Э. Пост, В.Ф. Турчин, А. Тьюринг, Д. Уоррен, А. Черч, А. Шенгахе и многие другие известные ученые. В академических изданиях и специальной литературе имеются достаточные основания для решения проблемы по созданию высокоскоростных сис..:м ОСИ. Между тем, существующие системы ОСИ базируются на основе Taxiix методов и средств, которые не обеспечивают требуемой скорости решения прикладных задач, вследствие того, что во всех универсальных алгоритмических системах ОСИ отсутствуют инструментальные средствг. акселерации символьных вычислений, что создаст проблемную ентуашпо. Требуемая производительность систем ОСИ должна составлять сотни миллионов лс и-чсских вы водов в секунду (ЛИПС), а достигаемая на сегодняшний день производительность составляет единицы миллионов ЛИПС. Поэтому дальнейшее развитие алгоритмических, программных и технических средств ОСИ связывается специалистами с решением актуальной и перспективной задачи но разработке новых методов о^аботки и соответствующих им принципов структурно-функциональной организации устройств ОСИ.

Научный аспект решаемой задачи заключается в разработке фор) представления конструктивных обьектов, способов ОСИ, и обосновани их алгоритмической реализуемости, а также в разработке параллельны устройств ОСИ. Практический аспект решаемой задачи включает в себ структурно-функциональные схемы универсальных символьных парах лельных процессоров, работающих на основе алгоритмической проду» ционной парадигмы.

Основная часть диссертационной работы выполнялась в рамка госбюджетной НИР по распоряжению Госкомвуза №10-36-41, ИН/10-2С 03 от 16.03.92 г. с пролонгацией до 1999 г. при непосредственном участи автора.

Цель работы заключается в разработке форм представления конст руктнвных обьектов, акселеративных способов ОСИ и в синтезе стру1 турно-функциональных схем параллельных символьных процессоров, аг паратно поддерживающих продукционные алгоритмические схемы.

Основные задачи диссертационного исследования:

1.Разработка форм представления конструктивных обьектов.

2.Разработка способов и алгоритмов сопоставления и модификаци конструктивных обьектов в позиционных форматах представления.

3.Адаптация существующих методов модификации каноническо системы алгорифмов Маркова к разработанным формам представлени конструктивных обьектов.

4.Разра6отка системы операций исполнительного устройства.

5.Струк1урно-функциональный синтез параллельного символьног процессора и исследование его скоростных характеристик.

Методы исследования базируются на аппарате теории алгоритмо! математической логики, в том числе конструктивной, теории конечны автоматов и проектирования ЭЦВМ. Верификация корректности алгс ритмов функционирования разработанных устройств и эксперимента!!! ные исследования производительности устройств проводились с поме щью компьютерного моделирования.

Научная новизна работы заключается в решении научной задачи п созданию высокопроизводительных параллельных продукционных уст ройств ОСИ. В результате проведенных исследований получены следук щие основные научные результаты:

,1. Впервые разработан способ представления текстовых данных памяти ЭВМ (параллельное позиционное представление данных) и алгс ритмы операции символьного поиска и подстановки. Проведено доказ; тельство корректности алгоритмов поиска и подстановки.

2. На основе параллельного позиционного способа представлени данных разработан и формализовал параллельный позиционный аддити« ный способ представления данных, позволяющий организовать хранены данных в виде списка, что позволило сократить временные затраты на р<

энфигурацию слова при выполнении операции подстановки. Разрабста-ы и формализованы алгоритмы выполнения операции символьного по-ска и подстановки и проведено доказательство их корректности.

3. Методы модификации канонической систсТлы алгорифмов-А.А------------

1аркова адаптированы к предложенным параллельным способам пред-гавления данных. Уточнено определение алфавитной переменной в при-сняемом контексте и формализованы алгоритмы операции конкретиза-ии и подстановки алфавитной переменной.

Практическая ценность работы состоит в следующем.

1. На основе проведенных теоретических исследований разработана труктурно-функциональная ор анизация высокопроизводительных уни-ерсальных параллельных символьных устройств ОСИ со встроенными редствамн акселерации операций сопоставления и подсгановки, базн-ующихся на модифицированных алгорифмах А.А.Маркова.

2. Разработанные способы представления текстовых данных и аксе-ерации операций символьного поиска и подстановки могут быть исполь-оваиы для разработки систем ОСИ различной конфигурации и назначе-[ия и создают основу для постановки НИОКР.

Реализация результатов работы. Результаты диссертационной рабо-ы нашли применение при выполнении госбюджетных НИР Курского го-ударстпепного технического университета, практически реализованы и шедреиы в СКБ "Авиаавтоматика" (г. Курск) и учебном процессе Кур-:когч> государственного технического университета.

Апробация работы. Результаты работы докладывались и обсужда-шсь па III международной конференции "Оптико-электронные приборы и 'свойства в системах распознавания образов, обработки изображений и •нмпольной информации" (Курск, 1997), IV международной конферен-иш "Актуальные проблемы электронного приборостроения" (Новосибирск, 1998), IV международной конференции "Теория г техника переда-ш, приема и обработки информации" (Туапсе, 199S), I всероссийской на-г'чно-тсхннческоп конференции "Компьютерные технологии в науке, проектировании и производстве" (Нижний Новгород, 1999).

Основные положения, выносимые па защиту;

L Параллельный позиционный способ представления текстовых наниых и алгоритмы выполнения операций сим вольного сопоставление и подстановки над данными, представленными d такой форме.

2. Параллельный позиционный аддитивный способ представления текстовых данных и алгоритмы выполнения операций символьного сопоставления и подстановки над данными, представленными в такой форме.

3. Модификации канонической системы алгорифмов'A.A. Маркова, адаптированные к обработке данных, представленных в параллельном позиционном (аддитивном) формате. - „

4. Алгоритмы работы и структура продукционного устройства, ре лизующгго модифицированную алгоритмическую систему A.A. Марко! над данными, представленными в параллельной позиционной форме.

5. Алгоритмы работы и структура продукционного параллельно] устройства, реализующего модифицированную алгоритмическую систел/ A.A. Маркова над данными, представленными в списковой параллельнс позиционной аддитивной форме.

6. Результаты компьютерного моделирования работы разработа! ных устройств.

Публикации по работе. По материалам диссертации опубликовано печатных работ и 1 рукописная.

Структура и обьем работы. Диссертация состоит из введения, четь рех глав и заключения, изложенных на страницах машинописно! текста, содержит 61 рисунок, "54 таблицы, список литературы из ¥1 и именований и Ii приложений объемом в Î16 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении обоснована актуальность и перспективность тем! сформулированы цель и задача исследования, научная новизна, практич< екая ценность работы, основные положения, выносимые на защиту, и др.

В первой главе анализируется современное состояние средств ОС и раскрывается сущность предлагаемого подхода.

В обзорной части главы рассмотрены основные классы задач ОС (задачи текстообработки, экспертные системы, обработка естественны языков, системы распознавания речи и обработки визуальной информ; ции, управление базами данных, самообучающиеся системы и др.). Ан; лиз специфики рассмотренных задач позволил выделить основные черп присущие ОСИ в целом: большой обьем и сложная логическая структур обрабатываемых данных, для обработки которых характерны структу; ные преобразования, связанные с поиском, удалением, реконфигурацие фрагментов структур; нечеткость, неопределенность или ненадежное! данных; использование иерархии знаний метауровня (высокоуровневы символьные вычисления). Специфика организации и обработки символ! ных данных требует использования для описания алгоритмов решения з; дач ОСИ таких средств, как рекурсивные функции, правила подстановс и предикаты. Показано, что неэффективность реализации указанных м< тодов обработки на ЭВМ фон-Неймановской архитектуры вызвала поя! ление различных классов устройств ОСИ (машины для обработки си,\ вольной информации, символьные процессоры, подключенные к универ сальной ЭВМ, ЭВМ с расширенной системой команд, ориентированно на символьную обработку, реконфигурируемые процессоры на базе FPG, и DPGA).

Анализ вычислительных средств, ориентированных на обработку

ОСИ, позволил выделить два альтернативных подхода к решению задач ОСИ*, применение универсальных ЭВМ, имеющих специализированные программные средства" ОСИ, и применение специализированных^ аппаратных устройств ОСИ. Остальные подходы являются комбинациями первых двух. Рассмотрены преимущества и недостатки указанных подходов.

Сущность предлагаемого подхода к решению проблемной ситуации заключается в использовании в качестве методологической основы для построения устройств ОСИ универсальной системы продукций A.A. Маркова (СПМ). Рассмотрены ее преимущества н недостатки. Установлено, что недостатки, присущие канонической СПМ в метрическом аепекте, компенсируются методами модификации, включающими введение меток перехода, алфавитных конструктивов и др. Новизна предлагаемого подхода заключается в изменении конструктивного представления обрабатываемых данных, позволяющем акселерировать операции символьного сопоставления и подстановки, являющиеся базовыми операциями СПМ.

Во второй главе рассматривается понятийный аппарат конструктивной семиотики, приводится формальное определение канонической системы алгорифмов A.A. Маркова и правила ее функционирования, обосновывается введение "модификаций в каноническую систему алгорифмов и проводится их формализация, рассматриваются формы представления данных, алгоритмы их обработки и доказательства их корректности.

Во вводной части главы приводятся определения конструктивных объектов (символ, алфавит, слово) и отношений между обьектами (равенство слов, вхождения одного слова в другое), используемых в дальнейшем.

Рассмотрим кратко систему продукций Маркова. СПМ состоит из набора продукций вида:

0-»Р (1)

и

О-^Р, (2)

где О и Р - слова с некотором алфавите А, О - образец или левая часть формулы, Р - подстановка (модификатор) или правая часть формулы, "->" и "-У - метасимволы, не принадлежащие А, являющиеся разделителями между словами О и Р. Формула вида О—>Р является простой, 0->Р.- заключительной. Формула подстановки действует на слово S в алфавите А (срабатывает), если О входит в S. В этом случае результатом действия формулы на S является результат подстановки слова Р вместо первого вхождения О в S, СПМ задастся конечной системой продукций со следующими правилами передачи управления:

1) Первой включается в работу первая в списке продукция.

2) Всякий раз, когда срабатывает простая продукция, управлеш передается на первую в списке продукцию. При срабатывании заюиоч: тельной продукции алгорифм завершает работу.

3) Всякий раз, когда продукция не срабатывает, управление перед ется на следующую в списке продукцию. Если не срабатывает последи; в списке продукция, алгорифм завершает работу.

Для устранения недостатка нормальных алгорифмов в метрическс аспекте, выраженного в необходимости совершать отступы в пространс ве алгорифма для организации передачи управления между продукция*, (передача управления 1-й продукции после срабатывания любой из пр дукций), вводится модификация, позволяющая указать продукцию, кот рая следующей включится в работу в зависимости от того, сработала j текущая продукция. Каждая продукция снабжается обязательной мета продукции v и необязательной меткой перехода w

v:0-»P:w, (3)

и п. 2 правил передачи управления изменяется следующим образог 2) Всякий раз, когда срабатывает простая продукция, имеющая ме ку перехода, управление передается на продукцию, помеченную эт< меткой. Если метка перехода отсутствует, управление передается на сл дующую в списке продукцию. При срабатывании заключительной пр дукции алгорифм завершает работу.

Для устранения выполнения подстановки при срабатывании пр дукции вида:

v:0-»0:w (4)

вводится продукция специального вида, которую будем называ продукцией сопоставления, эквивалентная продукции (4)

v:0=:w (5)

Продукция (5) считается сработавшей, если вхождение О в S суш ствует. Входное слово при этом не изменяется, а управление передает на продукцию с меткой w.

С целью повышения выразительных возможностей и уменьшен: емкостной (а следовательно и временной) сложности продукционной си темы вводятся алфавитные переменные. Конструктив алфавитной пер мснной в том виде, в каком он был введен A.A. Марковым, не являет средством сокращения емкостной сложности алгорифма, а служит для с кращеннон записи алгорифма (подлежащего расшифровке перед выпо нением), и по ряду причин неприемлем для аппаратной реализации. I указанным соображениям в размеченную систему введены продукт специального вида, включающие алфавитные переменные, и им сопоста лены особые процедуры сопоставления и подстановки. Введено понят сопоставимости двух слов и расширено определите вхождения одно слова в другое для слов, включающих алфавитные переменные.

Алфавитные переменные предоставляют достаточно ограниченные )едства реализации задач ОСИ, если не определены средства задания тпазопа допустимых значений или отношений между алфавитными леченными. Для увеличения выразительных возможностей переменных, ¡едем операцию отношения между алфавитными переменными, которую /дсм называть условием формулы. Для этого сопоставим продукции би-арную операцию вида:

^•(Ь, . (6)

где 11) и с!а - алфавитные переменные или константы, • - знак опера-ии отношения из множества {>, >, <, =, Тогда продукцию, которой ^поставлено условие (6), буд»; считать сработавшей, если выполнено пределенное выше условие срабатывания, и условие (6) является истин-ым (перед проверкой условия на место алфавитных переменных под-гавляются их значения). •

Для продукционной системы с введенными указанным способом одификашшми построены синтаксические диаграммы.

С целью акселерации базовых операций продукционной системы -имволыюго сопоставления и подстановки - предлагается изменить кон-¡руктишюе представление данных. Параллельное позиционное пред-тавленне (ПП-представление) слона Б в алфавите Л представляет собой п исловых последовательностей (вектороз) Бц, где аеА, п - мощность ал-)авита А, и 8а - последовательность номеров позиций а в Б, упорядочения по возрастанию. Последовательность Ба будем называть ПП-юслсдовательностыо символа а слова 5. Так, для обрабатываемого слова алфавите А=-{а, Ь, с} вида:

Б=" ЬЬсаЬЬсаЬЬая" (7)

1234567891 1 1

ПП-представление будет иметь вид:

Б. = {3,7,10,11);

вь» {0,1,4,5,8,9}; (8)

5С = {2,6>

и обозначаться Бпп-

Рассмотрим алгоритм поиска образца О в слове Б ь алфавите А. Пе-)ед началом поиска слово и образец преобразуются в ПП-прсдставление. 1усть искомый образец начинается с символа ф алфавита А. Тогда Б, «._г-1сржн| номера позиции, с которых может начинаться вхождение образца 1 с ¡року. Нулем обозначай, элементы вектора Б,, как V), где } = [Л -юмер элемента пек-гора |5„| - количество элементов в векторе Ба. Ана-югичные обозначения пводятся для элементов множеств Оа и Ра- Обо-шлчнм за т номер элемента ПП-последовательносш Я, и пусть т=0. Значение и,,.,, будем и.тшать базой и обозначать символом В

Введем вектор Ь, состоящей из а элементов, и перед началом процедуры сопоставления присвоим нулевые значения его элементам.

1. Для всех аеА формируются векторы 0'а путем суммирования элементов Оа с значением базы

__0'«д = 0в4 + В, (10)

где 1 = 0,|Ов |-1.

2. Для всех аеА проводится последовательный просмотр элементов ва, начиная с з^ , до тех пор, пока не будет найден элемент, для которого выполняется

Ч^В. (11)

Номер позиции д, дол которого выполняется (11), будет новым значением Ьо.

3. Если для всех аеА выполняется условие

Чь.-ия(Ч«+в' (12>

где I = 0,| О. |-1, то присутствует вхождение образца О в позиции В слова 5. Если условие не выполняется и

(13)

то значение т увеличивается на 1 и процедура поиска повторяется с шага 1 алгоритма. Если (13) не выполняется, то процедура поиска завершается неуспешно.

Рассмотрим алгоритм подстановки на место вхождения образца О в слово в модификатора Р. Перед началом подстановки модификатор преобразуется в ПП-представление.

1. Введем понятия левого крыла ПП-представления. Левое крыло ПП-представления слова 8=ЬОЯ обозначается Ьпп и формируется из Бш путем удаления из Ба всех элементов, больших или равных В.

2. Правое крыло Бпп обозначается Игт и формируется из Бш путем удаления из Ба всех элементов, принадлежащих ПП-последовательностям Ц,иО'а.

3. Для формирования правого крыла ПП-представления результирующего слова И'ип, необходимо просуммировать элементы множеств 11а для всех аеА с значением |Р|-|0(:

__^в.1=га. гНР|-|0|, (14)

Где 1 = 0, |11, |-1.

4. Фрагмент подстановки Р'„ в составе ПП-представления результирующего слова формируется из Рпп путем суммирования элементов Ра для всех аеА с значением В:

____Р'«д-Рещ+В, (15)

где 1 = 0,| 5,1-1.

5. Результатом выполнения операции подстановки для данных в — ПП-представленин является слово Б'пгь образованное путем конкатенации последовательностей Ьа, Р'а и для всех аеА._____

Преимуществом ПП-представления является естественный паралле----------—

лизм, присущий этому типу данных и позволяющий распределить обработку ПП-последовательностей между отдельными исполнительными элементами. Тем не менее, сами ПП-последовательности имеют формат строки чисел и наследуют недостаток строкового представления данных, связанный с необходимостью полного просмотра правого крыла слова для его реконфигурации при подстановке (14). Предлагается модификация рассмотренного представления данных, позволяющая исключить операцию преобразования правого крыла слова при его реконфигурации.

Преобразуем ПП-представление слова Э следующим образом. Для всех аеА, сформируем §1а по следующим правилам:

Чо = 5в.о« (,б)

8в,| = »в,|-Ч1-1>пРи! = 1>15«1-1-

Будем называть представление символьных данных, сформированное по правигчм (16), параллельным позиционным аддитивным представлением данных (ППА-представлением), а последовательности !5а ППА-последовательностями. Для слова (7) ППА-представлегше имеет вид: '

£..»{3, 4,3, 1};

^={0,1,3,1,3,1}; (17)

= {2,4}.

Рассмотрим алгоритм поиска образца О в слове Б в алфавите А, представленных в ППА-формате.

Обозначим за ш номер элемента ППА-последовательности где

Ф - первый символ образца, и пусть т=0. Значение базы (9) вычисляется по формуле

В = О»)

Введем вектор Ь, состоящий из а элементов, и перед началом процедуры сопоставления присвоим нулевые значения его элементам.

1. Для всех аеА проводится последовательный просмотр элементов , начиная с з(цЬ<, до тех пор, пока не будет найден элемент , для которого выполняется ,

(19)

где Гн',^- номер позиции символа а в слове Б, который вычисляется по формуле

Значение ч будет новым значением Ьа. _

2. Для всех аеА сформируем векторы О^ по следующим правилам:

°М=г°«М>+в-гЧь.-ь (21)

= при 1 = 1,|0в |-1.

3. Если для всех аеА выполняется условие

+1 =51,1/ (22)

где 5 = 0,| Оа |-1, то присутствует вхождение образца О в позиции В слова Б и процедура поиска успешно завершается.

4. Если услоьие (22) не выполняется и

гас^!, (23)

то значение ш увеличивается на 1 и процедура поиска повторяется с шага 1 алгоритма. Если (23) не выполняется, то процедура поиска завершается неуспешно.

Рассмотрим алгоритм подстановки на место вхождения образца О в слово й модификатора Р, представленных в ППА-формате. ^

1. Формируется левое крыло ППА-представления слова ЬППА путем удаления из !5а элементов с индексами, большими или равными Ьц.

2. Формируются векторы 1»ц, образующие фрагмент подстановки в составе ППА-представления результирующего слова

Р^О =Ра,о + В- (24)

Га,¡= Ра,!, при г = 1,|Ра 1-1. (25)

3. Формируется правое крыло ППА-представления исходного слова К лил путем удаления из ¡8а элементов с индексами, большими, чем

Ь0+|Ря|-1. (26)

4. Формируется правое крыло ПП-представлемия результирующего слова Щт по формулам

П.0 = га>0 - +|РНО|; (27)

^ я Распри 1 = 1,|Йи 1-1. (28)

- 5. Результатом выполнения операции подстановки для данных в ППА-представлении является слово 5'пи, образованное путем конкатенации последовательное!ей Г,,, Р'„ и II '„ для всех аеА.

11дшьсн_глппе разработана структурно-фуикцноналыш орпжнза-иия архитектуры двух вариантов универсальных продукционных устройств ОСИ со встроенными средствами акселерации операций сопоставления и подстановки, ориентированных на обработку данных, представ-

лснных в ПП- и ППА-формате. Приведены структурные схемы, схемные решения блоков и алгоритмы функционирования, а также оценка аппа-— ратной сложности разработанных устройств.

Устройство РАК-ЯТИ для реализации продукционной системы над данными, представленными в ПП-формате, состоит из центральною бло- — -ка ЦБ и N локальных блоков обработки символа БОС(1) - БОС(М) (рис. 1).

Структурная схема устройства PAR-STR и PAR-LIST

Центральный блок предназначен для хранения исходных и результирующих данных и программы в строковом формате; хранения значений базы и коррекции; общего управления процессом преобразования форматов данных и процессом выполнения программы.

Блок обработки символа хранит ПП-представления обрабатываемого слова и программы для одного из символов алфавита (локальное ПП-прсдставление) и выполняет обработку локального ПП-представлепия слова в соответствии с программой.

ЦБ состоит из следующих основных узлов:

1. Блок памяти я регистров данных и программы служит для хранения, считывания и записи программы, исходных и результирующих данных в текстовом формате, а также преобразования Г1П-представле:шл данных в текстовый формат.

2. Блок адресации блоков обработки символа служит для адресации и передачи управляющих команд БОС.

3. Блок хранения базы служит для записи, считывания и хранения значения базы, а также определения состояния конца обрабатываемого слова при сопоставлении.

г

4. Блок памяти значений коррекции предназначен дня хранения однобайтовых значений коррекции (разность между длиной подстановки и длиной образца) для всех формул программы.

5. Блок памяти длин образца предназначен для хранения длин образцов для всех формул программы.

6. Блок проверки условия вхождения служит для проверки выхода вхождения за правую границу слова.

7. Блок хранения типа продукции служит для хранения кода типа продукции для всех формул программы.

8. Блок памяти меток продукции предназначен для хранения адресов перехода для воех формул программы.

9. Блок хранения и проверки услозий продукции служит для хранения условий продукции в сжатом виде, их дешифрации и проверки.

БОС состоит из следующих основных узлов:

1. Комбинационная схема дешифрации команд предназначена для дешифрации кода команды, поступающего из ЦБ.

2. Блок памяти и регистров программы предназначен для хранения локального ПП-представления программы (образцов и подстановок формул), адресов перехода по меткам в памяти программы, алфавитных переменных.

3. Блок памяти и регистров слова предназначен для хранения локального ПП-прсдставления обрабатываемого слова.

4. Арифметико-логический блок предназначен для выполнения операций компарации и суммирования в процессе выполнения поиска и подстановки.

Общая структура устройства PAR-LIST (рис. ]) для реализации продукционной системы надданными, представленными в ППА-формате, аналогична структуре устройства PAR-STR, так же как и функциональное назначение блоков ЦБ и БОС.

Принципиальное отличие устройства PAR-LIST заключается в организации одного из основных компонент БОС - блока памяти и регистров слова (БПнРС). Тогда как БПиРС устройства PAR-STR ориентирован на обработку последовательного массива данных, которым является ПП-прсдстаилсние символа, БПиРС устройства PAR-STR содержит средства поиска и реконфигурации списка чисел, которым является ППА-представлсиис символа, имеет более сложную структуру и включает в себя арифметические и логические функции, которые выполняет АЛБ в составе устройства PAR-STR.

Проведена оценка аппаратных затрат на реализацию устройств PAR-STR и PAR-LIST, составляющая в зависимости or количества N блоков обработки символа 28177 + 9703*N транзисторов для устройства PAR-STR л .28184 + 14930«N транзисторов для устройства PAR-LIST. Сопоставление аппаратных затрат разработанных устройств со сложностью

микропроцессора Celeron показало, что соотношение аппаратных затрат при обработке текста естественного языка для устройств Celeron, PAR-LIST II PAR-STR составило 1:0.25:0.16, а при обработке двуязычных текстов 1:0.41:0.27. ~-------------------------------

В четвертой главе приводятся результаты моделирования работы устройств и проводится сравнительный анализ производительности устройств по результатам тестирования программных эмуляторов разработанных устройств на бенчмарках.

Для проведения экспериментального анализа эффективности устройств PAR-STR и PAR-LIST на основе алгоритмов функционирования устройств разработаны эмулирующие программы.

В качестве эталонных устройств для проведения сравнительного анализа эффективности разработанных устройств исполь-ояалоеь последовательное устройство реализации марковских алгоритмов над списковыми данными SP2 и универсальный персональный компьютер на ба?е процессора Celeron с тактовой частотой 333 МГц. Сопоставление программных моделей указанных устройств производилось по параметру временных затрат (в тактах устройства) на выполнение тестовой задачи и по параметру производительности устройства при решении данной, задачи, выраженной в количестве элементарных операций задачи, выполняемых за машинный такт.

Сопоставление моделей устройств проводилось на следующем ил-боре тестовых задач ОСИ: символьный поиск, символьная подстановка, левая конкатенация, правая конкатенация, задача о ханойской башне. При исследовании параметров универсальной ЭВМ задачи символьного поиска, подстановки и конкатенации решались с использованием строкового (Celeron-STR) и спискового (Celeron-LIST) представления данных В качестве исходных данных для всех тестовых задач использовались фрагменты текста на естественном языке.

При проведении тестирования программных моделей были выявлены следующие аналитические зависимости для временных затрат устройств (в тактах) на решение тестовых задач.

1. Задача символьного поиска (частичные вхождения отсутствуют): Celeron-STR: t„«30+9*I+7*o; (29)

Celeron-LIST: tri*33+I3.3*I+14.5*o; (30)

SP2: t„=6+2*i+2*o; (31)

PAR-STR, PAR-LIST: t„=7+2*(i-l)+2*o, (32)

где 1 - длина левого крыла слова, о - длина образца, I и 6 - длина максимальной ПП-последовательности левого крыла слова и образца со- . ответственно. Под длиной максимальной ПП-послсдовательцости слова понимается максимальное количество одинаковых литер, встречающихся в данном слове.

2. Задача символьной подстановки:

{t„+22+19.9*p+11.5*r, при [Ко, t„+22+19.9*o+10.3*r+20.7*(p-o), при р>о, (33) t„+22+19.9*p, при р=о;

пет , ft„+10+I2.7*p, при pSo, .

Celeron-Li ST: W« jt|i+1o+i2.7*o+11.3*(p-o)) при p>o;

dad чти. ♦ _ftn+4+2*p +2*í,при p<o, П5.

PAR-STR. W-|tii+4+2,.+2A(._I))npHp^; (35)

PAR-LIST: W=tu+l+3*p; (36)

SP2: tn(U= t„+3*p, (37)

где t„ - время поиска вхождения (29 - 32), о - длина образца, р -длина подстановки, г - длина правого крыла слова, риг- длина максимальной ПП-последовательности подстановки и правого крыла слова соответственно.

3. Задача левой конкатенации:

Celeron-STR: t*135+4*k+5.5*s; (38)

Celeron-LIST: t*16+16*k; (39)

. SP2: t=7+3*k; (40)

PAR-STR: t=ll+2*k+2*s; (4i)

PAR-LIST: t=8+3*k, (42) где k - длина конкатенируемого образца, s - длина слова, к которому производятся конкатенация, к и s - длина максимальной ПП-гюследовательности образца и слова соответственно.

4. Задача правой конкатенации:

Celeron-STR: t«135+4*k+4*s; (43)

Celeron-LIST: t*24+8*k+ll*s; (44)

SP2: t=9+3*k+2*s; (45)

PAR-STR: t=I3+2*k+2*s; (46)

PAR-LIST: t=8+3*k+2*s. (47)

Анализ результатов тестирования позволил дать следующие качественные и количественные сценки сравнительной производительности устройств.

При решении задачи поиска затраты времени на обработку одного символа при варьировании длины образца от 0 до 100 символов и длины слова от 1 до 1000 символов составили для моделей PAR-STR и PAR-LIST 0.25-7, для SP2 2.01 - 8, для Celeron 7.3 - 39 тактов на символ.

При решении задачи подстановки (не включающей поиск) затраты времени на обработку одного символа при варьировании длины подстановки и длины правого крыла слова от 0 до 100 символов составили для

модели PAR-LIST 0.4 - 4, для PAR-STR 0.3 - 30, для SP2 3, для Celeron 11.4 - 21.3 тактов на символ.

При решении задачи левой конкатенации затраты времени на обработку одного символа при варьировании домны слова и длины конкатенируемого фрагмента от 0 до 100 символов составили для модели PAR-LFST 0.5 - 11, для PAR-STR 0.4 - 39, для SP2 3.1 - 10, для Celeron 16.2 - 32 тактов на символ.

При решении задачи правой конкатенации затраты времени на обработку одного символа при варьировании длины слова и длийы конкатенируемого фрагмента от 0 до 100 символов составили для модели PAR-LIST 0.5 - 37, для PAR-STR 0.4 - 41, для SP2 3.1 - 212, для Celeron 5 - 539 тактов на символ. .

При решении задачи о ханойской башне затраты времени на перемещение одного символа при различных начальных условиях (от 1 до 12 символов в стеке) составили для модели PAR-LIST от 46 до 26, для PAR-STR от 53 до 29, для SP2 от 210 до 90, для Celeron от 29 до 38 тактов на символ соответственно.

По результатам тестов построена обобщенная квалиметрическая диаграмма (рьс. 2). По интегральному критерию (площадь фигуры) модели PAR-LIST и PAR-STR на порядок и более опережают модели SP2 и Celeron, причем наибольший выигрыш отмечаемся на операциях поиска, подстановки и правой конкатенации.

Для проведения сопоставления моделей PAR-STR и PAR-LIST между собой построена квалиметрическая диаграмма (рис. 3), отражающая показатели времени, затрачиваемого на выполнение основных элементарных операций ОСИ. По данным диаграммы можно сделать следующие выводы. Затраты времени на выполнение операции поиска для обоих устройств одинаковы, а на выполнение правой конкатенации сопоставимы. Это связано с тем, что при выполнении этих операций, списковое представление слова, применяемое в PAR-LIST, не дает никаких преимуществ На операциях подстановки и левой конкатенации списковое представление слова имеет преимущество, что и отражено на диаграмме: затраты устройства PAR-LIST почти в 2 раза тшже при выполнении подстановки и более чем в 2.5 раза ниже при выполнении левой конкатенации, чем затраты устройства PAR-STR.

Учитывая оценку аппаратной сложности устройств, можно сделать вывод, что наиболее перспективным для применения в области ОСИ является устройство PAR-LIST. Вместе с тем, для приложений, ориентированных на символьный поиск, рациональнее использовать устройство PAR-STR, по производительности на задаче поиска не уступающее уст- .' ройству PAR-LIST, но имеющее существенно меньшую аппаратную сложность. Данное устройство целесообразно использовать в качестве т процессора-акселератора маш!?н баз данных.

Обобщенная квалиметрическая диафамма временных затрат устройств на выполнение элементарной операции при решении различных задач ОСИ

Обобщенная квапиметрическая диаграмма временных затрат устройств PAR-STR и PAR-LIST на выполнение элементарной операции при решении задач поиска, подстановки и конкатенации

Поиск

Рис.3.

В заключении обобщаются основные теоретические и практические результаты, полученные в диссертационной работе.

В приложениях содержатся листинги программных модулей, алгоритмы функционирования устройств и их описания-описания управляющих сигналов устройств и другие материалы, не вошедшие в основную часть.

ОСНОВНЫ Е РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе решена важная научно-техническая задача разработки и исследования высокопроизводительных параллельных продукционных устройств ОСИ. . - •

В рамках проведенных исследований в диссертационной работе получены следующие основные результаты:

1. Впервые разработаны параллельные формы представления символьных данных и алгоритмы их обработки, включающие операции символьного сопоставления и подстановки, а также преобразования данных из строковогг в параллельное представление и обратно. Доказана корректность разработанных алгоритмов, что позволяет организовать параллельные символьные вычисления.;

2. Обосновано введение модификации в каноническую систему алгорифмов Маркова и проведена адаптация существующих методов модификации к разработанным формам предстаЕиения конструктивных объектов, что обеспечивает высокую скорость обработки символьной информации.

3. Разработаны структурные и функциональные схемы и алгоритмы управления продукционных высокопроизводительных устройств, реализующих модифицированную алгоритмическую систему A.A. Маркова над данными, представленными в параллельной позиционной форме и параллельной позиционной аддитивной форме. Разработанные технические решения создают реальную основу для постанояки НИОКР.

4. Выполнено моделирование работы устройств и проведен сравнительный анализ производительности устройств, показавший преимущества разработанных методов акселерации операций сопоставления и подстановки при решении задач ОСИ. Показано, что разработанные символьные параллельные процессоры имеют скоростные преимущества на порядок и более по сравнению с процессором Celeron при решении типовых задач ОСИ.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Шуклина Е.В. Сравнительный анализ методов символьных подстановок: Препринт 34-97 / Курск, гос. техн. ун-т. Курск, 1997. 14 с.

2. Шуклина Е.В., Довгаль В.М. Сравнительный анализ методов сопоставления слов: Препринт 35-97/Курск. гос.техн. ун-т. Курск, 1997. 12с.

3. Белов В.Г'„ Шуклина Е.В. Метод реализации символьных подстановок. // Сборник материалов 3 международной конференции "Распозна-вание-97". Кур. гос. тех. ун-т, 1997. С. 215.

4. Белов В.Г., Шуклина Е.В. Метод представления и обработки символьных данных для ускорения операций сопоставления и подстановки. // Информационные технологии моделирования и управления. Межвузовский сборник научных трудов. Воронеж: ВГТУ, 1998. С. 136-141.

5. Шуклина Е.В. Об одном методе обработки символьных данных. // Груды IV международной конференции "Актуальные проблемы электронного приборостроения". Новосибирский гос. техн. ун-т. Новосибирск,

6. Шуклина Е.В. Применение устройства, базирующегося на универсальной системе алгорифмов Маркова, для криптографической обработки данных. //4-я Международная конференция "Теория и техника передачи, приема и обработки информации" ("Новые информационные технологии"); научные труды/ ХТУРЭ, Харьков, 1998. С. 507-508.

7. Шуклина Е.В. Устройство для реализации марковских алгорифмов над символьными данными, представленными в параллельной позиционной форме. Дел. в ВИНИТИ №33S1-B98 от 18.11.98.

8. Шуклина Е.В. Устройство символьной обработки данных. // Компьютерные технологии в науке, проектировании и производстве. Тезисы докладов I Всероссийской научно-технической конференции. Нижний Новгород: Нижегородский гос. тех. ун-т, 1999. С.ЗЗ.

1998.

Соискатель

Подписано к печати К. 04.2000 Формат 60x84 1/16 Печатных листов __/, 2.Т Тираж 100 экз. Заказ е'/

Курский государственный технический университет 305Ö40, г.Курск, ул. 50 лет Октября, 94.

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ТЕХНИЧЕСКИХ СРЕДСТВ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ.

1.1. Классификация и особенности задач ОСИ.

1.2. Обзор существующих аппаратных средств ОСИ.

1.3. Сущность и особенности предлагаемого подхода.

1.4. Выводы.

ГЛАВА 2. ПАРАЛЛЕЛЬНОЕ ПОЗИЦИОННОЕ ПРЕДСТАВЛЕНИЕ ДАННЫХ: МЕТОДЫ ОБРАБОТКИ И ПРИМЕНЕНИЕ В РАМКАХ АЛГОРИТМИЧЕСКОЙ СИСТЕМЫ МАРКОВА

2.1. Основные понятия конструктивной семиотики.

2.2. Алгоритмическая система Маркова

2.3. Модифицированная система продукций.

2.4. Параллельное позиционное представление данных и метод реализации операций поиска и подстановки

2.5. Параллельное позиционное аддитивное представление данных и метод реализации операций поиска и подстановки.

2.6. Выводы.

ГЛАВА 3. УСТРОЙСТВА ДЛЯ РЕАЛИЗАЦИИ ПРОДУКЦИОННОЙ СИСТЕМЫ НАД ДАННЫМИ, ПРЕДСТАВЛЕННЫМИ В ПП- И ППА-ФОРМАТЕ.

3.1. Устройство PAR-STR для реализации продукционной системы над данными, представленными в ПП-формате.

3.2. Устройство PAR-LIST для реализации продукционной системы над данными, представленными в ППА-формате.

3.3. Оценка аппаратной сложности разработанных устройств.

3.4. Выводы.

ГЛАВА 4. МОДЕЛИРОВАНИЕ РАБОТЫ УСТРОЙСТВ, РЕАЛИЗУЮЩИХ МОДИФИЦИРОВАННУЮ ПРОДУКЦИОННУЮ СИСТЕМУ МАРКОВА.

4.1. Программные модели устройств.

4.2. Оценка производительности устройств при решении задачи поиска вхождения.

4.3. Оценка производительности устройств при решении задачи символьной подстановки.

4.4. Оценка производительности устройств при решении задачи левой конкатенации.

4.5. Оценка производительности устройств при решении задачи правой конкатенации.

4.6. Оценка производительности устройств при решении задачи "Ханойская башня"

4.7. Комплексная оценка производительности устройств на различных тестовых задачах

4.8. Выводы.

Актуальность работы. Информатизация общества относится к глобальным тенденциям его развития, что определяет потребность в создании эффективных лингвистических, алгоритмических, программных и технических средств обработки информации. Особую значимость приобретает проблема создания средств обработки символьной информации, поскольку она занимает до 90% объемов циркулирующей информации в современных системах обработки данных [1]. Символьная информация имеет большие обьемы и разнообразие (публикации, текстовые документы, записи программ, архивные данные и т.д.). Следует отметить, что ежеминутно в мировой практике создается до 50 0 тысяч страниц одних только документов.

Символьная информация в виде текстов составляет основу как для формирования текстов задач, так и алгоритмов их решения. Высокая социальная значимость проблем обработки символьной информации (ОСИ) определила существование дорогостоящих государственных и межгосударственных научно-исследовательских программ, например, таких как SPI (США), ALVEY (Великобритания) , TELETEXT, JESSI (страны Европейского союза) и др [2].

Доминирование символьной информации, быстрый рост ее обьемов и разнообразия требует адекватных алгоритмических, программных и технических средств обработки. Фундаментальным проблемам ОСИ посвятили свои работы отечественные и зарубежные авторы Р. Грисоулд, А.Н. Колмогоров, Дж. Маккарти, A.A. Марков, Т. Мотооко, Дж. Фон Нейман, Д.А. Поспелов, Э.Пост, В.Ф. Турчин, А. Тьюринг, Д. Уоррен, А. Черч, А. Шенгахе и многие другие известные ученые. В академических изданиях и специальной литературе имеются достаточные основания для решения проблемы по созданию высокоскоростных систем ОСИ. Между тем, существующие системы ОСИ базируются на основе таких методов и средств, которые не обеспечивают требуемой скорости решения прикладных задач, вследствие того, что во всех универсальных алгоритмических системах ОСИ отсутствуют инструментальные средства акселерации символьных вычислений, что создает проблемную ситуацию. Требуемая производительность систем ОСИ должна составлять сотни миллионов логических выводов в секунду (ЛИПС), а достигаемая на сегодняшний день производительность составляет единицы миллионов ЛИПС. Поэтому дальнейшее развитие алгоритмических, программных и технических средств ОСИ связывается специалистами с решением актуальной и перспективной задачи по разработке новых методов обработки и соответствующих им принципов структурно-функциональной организации устройств ОСИ.

Научный аспект решаемой задачи заключается в разработке форм представления конструктивных обьектов, способов ОСИ, и обосновании их алгоритмической реализуемости, а также в разработке параллельных устройств ОСИ. Практический аспект решаемой задачи включает в себя структурно-функциональные схемы универсальных символьных параллельных процессоров, работающих на основе алгоритмической продукционной парадигмы.

Основная часть диссертационной работы выполнялась в рамках госбюджетной НИР по распоряжению Госкомвуза №10-3 6-41,

ИН/10-20-03 от 16.03.92 г. с пролонгацией до 1999 г. при непосредственном участии автора.

Цель работы заключается в разработке форм представления конструктивных объектов, акселеративных способов ОСИ и в синтезе структурно-функциональных схем параллельных символьных процессоров, аппаратно поддерживающих продукционные алгоритмические схемы.

Основные задачи диссертационного исследования:

1.Разработка форм представления конструктивных обьектов.

2.Разработка способов и алгоритмов сопоставления и модификации конструктивных обьектов в позиционных форматах представления .

3.Адаптация существующих методов модификации канонической системы алгорифмов Маркова к разработанным формам представления конструктивных обьектов.

4.Разработка системы операций исполнительного устройства .

5.Структурно-функциональный синтез параллельного символьного процессора и исследование его скоростных характеристик .

Методы исследования базируются на аппарате теории алгоритмов, математической логики, в том числе конструктивной, теории конечных автоматов и проектирования ЭЦВМ. Верификация корректности алгоритмов функционирования разработанных устройств и экспериментальные исследования производительности устройств проводились с помощью компьютерного моделирования.

Научная новизна работы заключается в решении научной задачи по созданию высокопроизводительных параллельных продукционных устройств ОСИ. В результате проведенных исследований получены следующие основные научные результаты:

1. Впервые разработан способ представления текстовых данных в памяти ЭВМ (параллельное позиционное представление данных) и алгоритмы операции символьного поиска и подстановки. Проведено доказательство корректности алгоритмов поиска и подстановки.

2. На основе параллельного позиционного способа представления данных разработан и формализован параллельный позиционный аддитивный способ представления данных, позволяющий организовать хранение данных в виде списка, что позволило сократить временные затраты на реконфигурацию слова при выполнении операции подстановки. Разработаны и формализованы алгоритмы выполнения операции символьного поиска и подстановки и проведено доказательство их корректности.

3. Методы модификации канонической системы алгорифмов A.A. Маркова адаптированы к предложенным параллельным способам представления данных. Уточнено определение алфавитной переменной в применяемом контексте и формализованы алгоритмы операции конкретизации и подстановки алфавитной переменной.

Практическая ценность работы состоит в следующем.

1. На основе проведенных теоретических исследований разработана структурно-функциональная организация высокопроизводительных универсальных параллельных символьных устройств ОСИ со встроенными средствами акселерации операций сопоставления и подстановки, базирующихся на модифицированных алгорифмах А.А.Маркова.

2. Разработанные способы представления текстовых данных и акселерации операций символьного поиска и подстановки могут быть использованы для разработки систем ОСИ различной конфигурации и назначения и создают основу для постановки НИОКР.

Реализация результатов работы. Результаты диссертационной работы нашли применение при выполнении госбюджетных НИР Курского государственного технического университета, практически реализованы и внедрены в СКВ "Авиаавтоматика" (г. Курск) и учебном процессе Курского государственного технического университета.

Апробация работы. Результаты работы докладывались и обсуждались на III международной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (Курск, 1997), IV международной конференции "Актуальные проблемы электронного приборостроения" (Новосибирск, 1998), IV международной конференции "Теория и техника передачи, приема и обработки информации" (Туапсе, 1998), I всероссийской научно-технической конференции "Компьютерные технологии в науке, проектировании и производстве" (Нижний Новгород, 1999) .

Основные положения, выносимые на защиту:

1. Параллельный позиционный способ представления текстовых данных и алгоритмы выполнения операций символьного сопоставления и подстановки над данными, представленными в такой форме.

2. Параллельный позиционный аддитивный способ представления текстовых данных и алгоритмы выполнения операций символьного сопоставления и подстановки над данными, представленными в такой форме.

3. Модификации канонической системы алгорифмов A.A. Маркова, адаптированные к обработке данных, представленных в параллельном позиционном (аддитивном) формате.

4. Алгоритмы работы и структура продукционного устройства, реализующего модифицированную алгоритмическую систему A.A. Маркова над данными, представленными в параллельной позиционной форме.

5. Алгоритмы работы и структура продукционного параллельного устройства, реализующего модифицированную алгоритмическую систему A.A. Маркова над данными, представленными в списковой параллельной позиционной аддитивной форме.

6. Результаты компьютерного моделирования работы разработанных устройств.

Публикации по работе. По материалам диссертации опубликовано 7 печатных работ и 1 рукописная.

Структура и обьем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 127 страницах основного текста, содержит 61 рисунок, 34 таблицы, список литературы из 72 наименований и 12 приложений обьемом в 117 страниц.

4.8. Выводы

1. Для сравнительной оценки эффективности предлагаемых устройств параллельной обработки символьных данных, реализующих модифицированную продукционную систему Маркова над данными, представленными в параллельной позиционной форме (PAR-STR) и параллельной позиционной аддитивной форме (PAR-LIST) в качестве эталонных моделей были выбраны устройство реализации марковских алгоритмов над списковыми данными (SP2) и универсальный персональный компьютер на базе процессора Celeron-ЗЗЗ.

2. Сопоставление программных моделей указанных устройств производилось по параметру временных затрат (в тактах устройства) на выполнение тестовой задачи и по параметру производительности устройства при решении данной задачи, выраженной в количестве элементарных операций задачи, выполняемых за машинный такт.

3. Сопоставление моделей устройств проводилось на следующем наборе тестовых задач: символьный поиск, символьная подстановка, левая конкатенация, правая конкатенация, задача о ханойской башне. В качестве исходных данных для всех тестовых задач использовались фрагменты текста на естественном языке. При проведении тестирования программных моделей устройств были выведены аналитические зависимости для временных затрат и производительности устройств.

4. По результатам тестирования были получены следующие качественные и количественные оценки сравнительной производительности устройств. При решении всех тестовых задач наилучшие показатели имела модель PAR-LIST. Модель PAR-STR по производительности уступала только модели PAR-LIST, за исключением операции подстановки и левой конкатенации, где на некоторых наборах входных данных модель SP2 имела лучшие показатели .

При решении задачи поиска затраты времени на обработку одного символа при варьировании длины образца от 0 до 100 символов и длины слова от 1 до 1000 символов составили для моделей PAR-STR и PAR-LIST 0.25-7, для SP2 2.01 - 8, для Celeron 7.3 - 39 тактов на символ.

При решении задачи подстановки (не включающей поиск) затраты времени на обработку одного символа при варьировании длины подстановки и длины правого крыла слова от 0 до 100 символов составили для модели PAR-LIST 0.4 - 4, для PAR-STR 0.3 - 30, для SP2 3, для Celeron 11.4 - 21.3 тактов на символ .

При решении задачи левой конкатенации затраты времени на обработку одного символа при варьировании длины слова и длины конкатенируемого фрагмента от 0 до 100 символов составили для модели PAR-LIST 0.5 - 11, для PAR-STR 0.4 - 39, для SP2 3.1 -10, для Celeron 16.2 - 32 тактов на символ.

При решении задачи правой конкатенации затраты времени на обработку одного символа при варьировании длины слова и длины конкатенируемого фрагмента от 0 до 100 символов составили для модели PAR-LIST 0.5 - 37, для PAR-STR 0.4 - 41, для SP2 3.1 - 212, для Celeron 5 - 539 тактов на символ.

При решении задачи о ханойской башне затраты времени на перемещение одного символа при различных начальных условиях (от 1 до 12 символов в стеке) составили для модели PAR-LIST от 46 до 26, для PAR-STR от 53 до 29, для SP2 от 210 до 90, для Celeron от 2 9 до 38 тактов на символ соответственно.

5. В связи с параллелизмом организации данных моделей PAR-LIST и PAR-STR на уровне символов, целесообразно использовать эти устройства для обработки символьных данных с большим обьемом алфавита, в частности, для обработки текстов естественного языка.

6. Учитывая оценку аппаратной сложности устройств, приведенную в п. 3.3, можно сделать вывод, что наиболее перспективным для применения в области обработки символьных данных является устройство PAR-LIST. Вместе с тем, для приложений, ориентированных в первую очередь на символьный поиск, рациональнее использовать устройство PAR-STR, по производительности на задаче поиска не уступающее устройству PAR-LIST, но имеющее существенно меньшую аппаратную сложность.

В диссертационной работе решена важная научно-техническая задача разработки и исследования высокопроизводительных параллельных продукционных устройств ОСИ.

В рамках проведенных исследований в диссертационной работе получены следующие основные результаты:

1. Впервые разработаны параллельные формы представления символьных данных и алгоритмы их обработки, включающие операции символьного сопоставления и подстановки, а также преобразования данных из строкового в параллельное представление и обратно. Доказана корректность разработанных алгоритмов, что позволяет организовать параллельные символьные вычисления.

2. Обосновано введение модификаций в каноническую систему алгорифмов Маркова и проведена адаптация существующих методов модификации к разработанным формам представления конструктивных объектов, что обеспечивает высокую скорость обработки символьной информации.

3. Разработаны структурные и функциональные схемы и алгоритмы управления продукционных высокопроизводительных устройств, реализующих модифицированную алгоритмическую систему A.A. Маркова над данными, представленными в параллельной позиционной форме и параллельной позиционной аддитивной форме. Разработанные технические решения создают реальную основу для постановки НИОКР.

166

4. Выполнено моделирование работы устройств и проведен сравнительный анализ производительности устройств, показавший преимущества разработанных методов акселерации операций сопоставления и подстановки при решении задач ОСИ. Показано, что разработанные символьные параллельные процессоры имеют скоростные преимущества на порядок и более по сравнению с процессором Celeron при решении типовых задач ОСИ.

1. Ba Б.У., Лоурай М.Б., Гоцзе Ли. ЭВМ для обработки символьной информации.//ТИИЭР. -1989.-т.77. №4. С.5-40.

2. Эйсымонт Л.К. Компьютеры для обработки символьной информации//Зарубежная радиоэлектроника.-1990.-№4. С.3-28.3.0tsu Nobuyuki. К новой парадигме в обработке информации //Joho Shori.-1993, -34, №12. С. 1423-1428.

3. Man-macine barriers begin to crumble/ Machlis Sheron, Editor Senior// Des. News., 1996.-51, №22. Pp.182-184, 186, 188.-Англ.

4. Kimbrell R. E. : "Searching For Text?. Send An N-Gram", Byte, vol.13, No. 5, May 1, 1998. Pp. 297-312, XP000576194 .

5. Федоров А. Средства разработки-99// Компьютер-ПРЕСС, №1, 1999, с. 24-28.

6. Макарова О. Коммерческие экспертные системы на научном семинаре //ComputerWeek-Москва.-1995.-№17.-С. 31,60 .

7. Экспертные системы еще живы /Tod Loofourrow // ComputerWeek-Москва.-1995.- №3 6.- С.21.

8. В.Э. Попов. Экспертные системы реального времени // Открытые системы.-1995.- №10.- С.66-71.

9. Симонов А. На смену Stylus приходят PROMT и WebTranSite// PC Week, №26, 1998. С. 34-35.

10. Левин К., Джинно М. Избавится ли машинный перевод от косноязычия? //PC Magazine/RE.-1994.- № 8.- С.183.

11. Искусственный интеллект: в 3 кн. Кн 1. Системы общения и экспертные системы: Справочник/ Под ред. Э.В. Попова.- М. : Радио и связь, 1990.-464 с.

12. Энн Ноулз, Ллойд Грей. Распознавание речи в процессе роста// PC Week, №30-31, 1998. С. 22.

13. Борисов Ю., Кашкаров В., Сорокин С. Нейросетевые методы обработки информации и средства их программно-аппаратной поддержки //Открытые системы.-19 97.- №4.- С.38-40.

14. Яфраков М.Ф., Корчагина Л.И. Особенности комплексного подхода к нейрокомпьютингу // Известия вузов. Приборостроение. 1997. Т 40. № 3.

15. Данкельбергер Д. Резервное копирование массивов данных// LAN, №11, 1998.

16. Асадуллаев С. Фирменные архитектуры хранилищ данных// PC Week, №№32-33, 1998. С. 17-19.

17. Д. Дэвитт, Д. Грей. Параллельные системы баз данных: будущее высокоэффективных баз данных. СУБД, вып. 2, 1995.

18. Лорьер Ж.-Л. Системы искусственного интеллекта.-М.: Мир.-1991.-568 с.

19. The Jellybean Machine // MIT Artificial Intelligence Laboratory/ http ://www.cva.Stanford.edu/j-machine/cva jmachine.html, July 7, 1998.

20. Noakes, Michael D. and Wallach, Deborah A. and Dally, William J. "The J-Machine Multicomputer: An Architectural Evaluation, Proceedings of the 20th International Symposium on Computer Architecture, 1993.

21. Britton Lee engin en France // 01 Informatique.-1989 . -№1062.-C.19.

22. Lee Dik L. Massive parallelizm on the hybrid text-retrievel mashine.//Inf. Process and Manag.-1995.-31, №6.

23. Krste Asanovic. SPACE: Symbolic Processing In Associative Computing Elements/ http://www.isci.berkley.edu, Jan 31,1996.

24. Мануэль Т. Процессор, сочетающий возможности числовых и символьных данных //Электроника.-1987.-т.60, № 8.

25. Hayashi Н., Haffory A., Akivmoto Н. Lisp mashine "ALPHA" //Fujitsu Scientific and Technical.-1984.- Vol.20, №2.

26. Lee K.H., Leung K.S.,Cheang S.M. A microprogrammable list processor for personal computers. "IEEE Micro", 1990, 4, №10, 50-61.

27. Lee K., Hickey T.M., Mak V.W., Herman G.E. VLSI accelerators for large base systems.//"IEEE Micro", 1991, 11, №6, 8-20.

28. Faudemay P., Mhiri M. An associative accelerator for large data bases.//"IEEE Micro", 1991, 11, №6, 22-34.

29. Пат. 5915248 США, МКИ G06F 017/30/Data searching apparatus /Kinoshita Tetsuya, Oyama Takamasa, Kikuchi Chuichi: Matsushita Electric Industrial Co., Ltd. (Япония) №797085/ заявл. 10.02.1997; опубл. 22.06.1999/ приор. 12.03.1996 №8054588, НКИ 707/001.

30. Пат. 5924090 США, МКИ G06F 017/30/Method and apparatus for searching a database of records /Krellenstein Marc F.:.

31. Northern Light Technology LLC (Кэмбридж, США) №846850; заявл. 1.05.1997; опубл. 13.07.1999; НКИ 707/005.

32. Пат. 5745745 США, МКИ G06F 017/30 /Text search method and apparatus for structured documents /Tada Katsumi ets: Hitachi, Ltd. (Япония) №495232; заявл. 27.06.1995; опубл. 28.04.98; приор. 29.06.1994 №147399 17.11.1994 №308201, НКИ 395/601.

33. Пат. 5963942 США, МКИ G06F 017/30/Pattern search apparatus and method /Igata Nobuyuki: Fujitsu Ltd. (Япония) №773295; заявл. 24.12.1996; опубл. 5.10.99; приор. 16.01.96 №8005236, НКИ 707/006.

34. Пат. 2067317 РФ, МКИ G06F 17/28. Устройство сортировки символов /Довгаль В.М. и др.- 1996, Бюл. N 27.

35. Пат. 2039375 РФ, МКИ 6 G 06 F 17/00, 17/20. Устройство для реализации продукций / Довгаль В.М. и др. (Россия). 504871/24; заявлено 22.06.92; опубл. 09.07.95, Бюл. N 19.

36. Wilson R. Системы команд процессоров пополняются мультимедийными инструкциями//КомпьютерУик.-1996.-№32.-С.34-35, 41.

37. Андрианов С.А. Центральный процессор: в центре проблем// Мир ПК, №2, 1999.

38. Денисов О., Назаров С., Процессоры и чипсеты для ПК// Компьютер Пресс, №3, 2 000.

39. Колеников С. Процессоры Хеоп обосновываются в серверах и рабочих станциях//Сотр^ег Weekly.-1998, №2 9.

40. Кузьминский М. Микроархитектура DEC Alpha 212 64// Открытые системы.-1998.-№1.-С.7-12.

41. Кузьминский M. Архитектурные особенности микропроцессоров РА-8000/8200/8500//Открытые системы.-1997.-№3.-С.6-9.

42. В.Шнитман. Архитектура процессоров UltraSPARC// Открытые системы, №2, 1996. С. 5-13.

43. Tom R. Halfhill. RISC Fights Back with the Mips R12000// BYTE Magazine, №1, 1998.

44. Виктор Шнитман. Семейство высокопроизводительных серверов RM600E// Открытые системы.-1998.-№2.-С.9-15.

45. Multiprocessor-Server// Thechnica (Suisse).-1997.-46, №1-2. -С.35.

46. Кузьминский M., Волков Д. Современные суперкомпьютеры: состояние и перспективы//Открытые системы.-1995.-№6.-С.3340.

47. Cray подтверждает свою репутацию самого мощного суперкомпьютера //PC Week.-1996.-№47.-С.27.

48. Кузьминский М. Современные архитектуры. Японский дракон . //Computerworld Россия.-1996.-№42.-С.17, 19.

49. Дубова H. Конфигурируемые процессоры: "Настройся на лучшее" //Computerworld Россия.-1997, №36.

50. D. A. Buell. A Splash 2 Tutorial. Technical Report SRC-TR-92-087, Supercomputing Research Center, Bowie, Maryland, December 1992.

51. P. Bertin, D. Roncin, and J. Vuillemin. Programmable Active Memories: A Performance Assessment. Prl report, DEC Paris Reserch Laboratory, 85, Av. Victor Hugo, 92563 Rueil-Malmaison Cedex, France, June 1992.

52. Клерк П. XILINX интегрирует технологии FPGA и Интернет// Chip News, №2(35), 1999, с. 13-14.

53. Марков А.А., Нагорный P.M. Теория алгорифмов,- М. : Наука, 1984.-432с.

54. Успенский В.А. Семенов А.А. Теория алгоритмов.- М. : Наука, 1987.- 218с.

55. Galler В. A., Perlis A.J. A view of programming languages. Reading: Addison Wesley, 1970. p. 82.

56. Довгаль B.M. Методы модификации формальных систем обработки символьной информации. Курск: Курск, гос. техн. ун-т, 1996, 115 с. (ISBN 5-7681-0010-5).

57. Леонов Е.И. Устройства для реализации модифицированных марковских алгортмов: дисю к.т.н.: 05.13.05/ Курск, гос. техн. ун-т Курск: КГТУ, 1996 - 341 с.

58. Кулик Б.А. Система поиска в произвольном тексте// Программирование. 1987. N1. С. 6-10.

59. Белов В.Г. Представление и обработка символьных данных в числовой символьно-параллельной форме: Препринт 36-97/ Курск, гос. тех. ун-т. Курск, 1997. 10 с.

60. Шуклина Е.В. Сравнительный анализ методов символьных подстановок: Препринт 34-97 / Курск, гос. техн. ун-т. Курск, 1997. 14 с.

61. Шуклина Е.В., Довгаль В.М. Сравнительный анализ методов сопоставления слов: Препринт 35-97 / Курск, гос. техн. унт. Курск, 1997. 12 с.

62. Белов В.Г., Шуклина Е.В. Метод реализации символьных подстановок. // Сборник материалов 3 международной конференции "Распознавание-97". Кур. гос. тех. ун-т, 1997. С. 215.

63. Шуклина Е.В. Об одном методе обработки символьных данных. // Труды IV международной конференции "Актуальные проблемы электронного приборостроения". Новосибирский гос. техн. ун-т. Новосибирск, 1998. С.53-54.

64. Шуклина Е.В. Устройство для реализации марковских алгорифмов над символьными данными, представленными в параллельной позиционной форме. Деп. в ВИНИТИ №3381-В98 от 18.11.98.

65. Шуклина Е.В. Устройство символьной обработки данных. // Компьютерные технологии в науке, проектировании и производстве. Тезисы докладов I Всероссийской научно-технической конференции. Нижний Новгород: Нижегородский гос. тех. ун-т., 1999, С.33.

66. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. М.: Мир, 1990.- 560 с.

67. Арсак Ж. Программирование игр и головоломок: Пер. с франц.-М.:Наука, 1990.-224 с.