Розділ 3. Розробка набору спеціальних команд та проектування АІБЗ на основі поведінкової моделі .................................................................................... 67
Розділ 4. Реалізація та експериментальне дослідження швидкодії опрацювання метамовних об’єктівна базі макетного зразка СОЗ .................................. 91
4.1. Структура та принцип роботи СОЗ..................................................... 91
4.2. Варіанти структурної реалізації АІБЗ.................................................. 99
4.2.1. Структура та принцип роботи конвеєрного АІБЗ1 із спільною локальною пам’яттю та спрощеним набором команд................................................... 99
4.2.2. Структура та принцип роботи АІБЗ2 із спільною локальною пам’яттю 101
4.2.3. Структура та принцип роботи АІБЗ3 із розподіленою локальною пам’яттю....................................................................................................................... 103
4.3. Структура пам’яті АІБЗ........................................................................ 108
4.4. Результати синтезу, розміщення та трасування СОЗ.......................... 111
Список використаних джерел ..................................................................... 126
Додаток А. Набір регістрів периферійних модулів СОЗ........................... 145
Додаток Б. Алгоритм роботи АІБЗ на рівні базових операцій.................. 149
Додаток В. Приклад побудови бази знань.................................................. 164
Додаток Г. Результати синтезу АІБЗ3......................................................... 173
Додаток Д. Дослідження швидкодії ПІБЗ та АІБЗ3.................................... 182
Додаток Е. Акти впровадження результатів дисертації............................. 201
АІБЗ
Апаратний інтерпретатор баз знань
АЛП
Арифметико-логічний пристрій
БЗ
База знань
ГОД
Граф операцій та даних
ГПП
Граф переходів між процесами
КС
Комп’ютерна система
МЛВ
Машина логічного виводу
ПБЗ
Процесор баз знань
ПІБЗ
Програмний інтерпретатор баз знань
ПЛІС
Програмована логічна інтегральна схема
РП
Робоча пам’ять
СОЗ
Система обробки знань
Актуальність теми. Системи обробки знань відіграють значну роль у житті людства та з кожним роком набувають все більшого поширення у таких прикладних галузях, як [1]: бізнес, виробництво, медицина, військова справа, інжиніринг, комп’ютерні системи, сільське господарство, космонавтика, освіта, транспорт, електроніка тощо. СОЗ традиційно використовуються для рішення структурно складних задач, які формулюють як задачі символьних перетворень, до числа яких відносять: діагностику й прийняття рішень, інтерпретацію даних, розпізнавання образів (зображень, мови), проектування, планування, моніторинг, керування, навчання, доказ теорем, ігри, трансляцію, природномовний переклад тощо.
Сучасний етап розвитку СОЗ пов’язаний із розробкою теорій, методів та засобів підвищення продуктивності та ефективності використання СОЗ. Серед актуальних проблем побудови СОЗ можна виділити [1-6]: представлення знань, виявлення знань, аналіз даних, машинне навчання, добування знань, методологію розробки СОЗ, управління знаннями, комп’ютерна лінгвістика, архітектура КС обробки знань та ін.
Сьогодні для реалізації СОЗ переважно використовують універсальні комп’ютери, головним недоліком яких є семантичний розрив між поняттями операцій та їх об’єктів у мові високого рівня та поняттями операцій і їх об’єктів, що визначаються архітектурою комп’ютера [5,6]. Наслідком цього є низька продуктивність сучасних СОЗ. Зокрема, сучасний інструмент CLІPS, призначений для створення експертних систем, може незадовільно працювати в реальному часі, коли потрібен час реакції, менший за 0,1 с [7].Витрати ж часу на рішення реальних задач експертизи складають від одиниць та десятків секунд [8].
Необхідність підвищення продуктивності СОЗ обумовлена: 1) наявністю високих вимог до продуктивності з боку систем реального часу (підтримка прийняття рішень на фондових біржах, діагностування серцево-судинних захворювань та ін.); 2) зростанням об’ємів знань про дійсність; 3) еволюцією знань про методи рішення наукових чи освітніх проблем, висуванням нових, більш складних вимог до функціональних можливостей СОЗ.
Перші спроби розв’язання проблем семантичного розриву та ряду інших проблем були зроблені ще у 60-70-х роках. Їхня суть зводилась до розробки проблемно-орієнтованих КС із «нефоннейманівською архітектурою», придатною для безпосереднього виконання програм, написаних на спеціальній мові високого рівня або на проміжній мові [6]. Розгляд таких КС висвітлено в [6, 9-12].
Широко відомі роботи Глушкова В.М., Скуріхіна В.І., Палагіна О.В., Морозова А.О, Малиновського Б.М., Боюна В.П., Кліменка В.П., Яковлева Ю.С., Амамія М., Танака Ю., Teodorescu H.N., Jain L.C., Kandel A., що використовують різні методи і засоби вдосконалення ефективності архітектур проблемно-орієнтованих КС.
По багатьох причинах, які наведено у [13], ідея широкомасштабної заміни програмних засобів апаратними виявилася невиправданою. А розвиток комп’ютерної індустрії пішов іншим шляхом, розвиваючи програмні засоби із застосуванням більш простих, але стандартних (універсальних) апаратних засобів. Хоча вдалі комерційні та промислові проблемно-орієнтовані комп’ютери існують і сьогодні, їхня висока вартість, несумісність із традиційними КС заважають їхньому розповсюдженню на ринку [14].
Сьогодні апаратні засоби підтримки СОЗ використовують такі архітектури універсальних процесорів: багатоядерні, мультитрейдові, суперскалярні та архітектури із командним словом великої довжини [15]. Одним із сучасних напрямків проблемної орієнтації архітектур КС є розширення набору команд процесора спеціальними командами[16, 17]. Серед головних недоліків відомих наборів команд та особливостей організації пам’яті існуючих КС можна виділити: 1) необхідність виконання великої кількості операцій при символьних обчисленнях; 2) відсутність ефективного представлення у пам’яті і обробки інформаційно складних структур, зокрема, вкладених, ітераційних та рекурсивних.
Загальніпідходи до проектування цифрових систем широко висвітлено в [18-27]. Найбільші складності проектування цифрових систем мають місце на початковому етапі, пов’язаному із розробкою специфікації системи [28]. Існуючі підходи проектування цифрових систем на основі поведінкової моделі потребують вдосконалення, зокрема, відносно розв’язку задачі визначення функціонально-модульної структури СОЗ [29-34].
Загальні підходи до проектування спеціалізованих процесорів висвітлено у [35-37]. Серед інших робіт можна виділити: проектування операційної частини процесора [38-40], пристрою керування [41-42], організація структури пам’яті [43-44]. Однак проектування апаратного інтерпретатора баз знань (АІБЗ) має певну специфіку відносно рішення задач синтезу спеціалізованих процесорів, зокрема щодо розв’язку задач [45]: декомпозиції пристрою керування, організації пам’яті, розділення даних в оперативній пам’яті.
Отже, актуальною є науково-технічна задача дослідження і розробки структурної моделі та реалізації проблемно-орієнтованого апаратного інтерпретатора баз знань із набором спеціальних команд з метою підвищення продуктивність апаратного інтерпретатора баз знань.
Зв’язок роботи з науковими програмами, планами, темами.Робота виконувалась у відділі мікропроцесорної техніки Інституту кібернетики імені В.М. Глушкова НАН України згідно наукових тем, в яких дисертант був виконавцем:
«Розробка теоретичних засад онтологокерованих комп’ютерних систем з реконфігуровною архітектурою» (№ держреєстрації 0107U003616, виконана за постановою Бюро відділення інформатики НАН України, Протокол № 6 від 17.01.2007 р., 2007–2011);
«Розробити та провести дослідження формальних моделей та архітектури онтолого-керованих інформаційних систем обробки знань» (№ держреєстрації 0109U001606, виконується за постановою Бюро відділення інформатики НАН України, Протокол № 4 від 7.05. 2008 р., 2009–2013).
«Розробити теоретичні засади, методи та інформаційні технології побудови комп‘ютерних засобів та систем на основі інтегрованого використання методів обробки знань, редукційного паралелізму та реконфігурування» (№ держреєстрації 0112U002255, виконується за постановою Бюро відділення інформатики НАН України, Протокол № 2 від 10.11.2011 р., 2012–2016).
Мета і задачі дослідження. Метою дослідження є підвищення продуктивності апаратного інтерпретатора баз знань за рахунок синтезу і реалізації набору спеціальних команд.
Для досягнення поставленої мети в роботі необхідно вирішити такі задачі:
– аналіз архітектур КС, орієнтованих на ефективну апаратну підтримку обробки знань та оцінка основних напрямів їх подальшого розвитку;
– визначення функціонально-модульної структури СОЗ;
– формування набору спеціальних команд, структур пристрою керування та пам’яті АІБЗ;
– розробка структури та реалізація АІБЗ на основі поведінкової моделі;
– оцінка швидкодії обробки знань на базі АІБЗ порівняно із швидкодією існуючих систем на базі комп’ютерів універсальної архітектури.
Об’єктом дослідження в дисертаційній роботі є процеси проектування проблемно-орієнтованих комп’ютерних систем та їх функціональних модулів.
Предметом дослідження в дисертаційній роботі є методи проектування архітектури, структури, реалізації та засоби експериментального дослідження АІБЗ.
Методи дослідження. Для досягнення мети роботи використано низку загальнонаукових та специфічних методів дослідження: загальні методи проектування обчислювальних систем – для вибору структури СОЗ, структури АІБЗ; методи мінімізації – для вибору мінімальної кількості процесів системи, для вибору мінімальних апаратних витрат на реалізацію модулів системи, для збільшення швидкодії модулів системи; методи теорії цифрових автоматів – для побудови керуючої частини АІБЗ; методи математичного аналізу – для розробки засобів обробки даних; методи алгоритмізації та програмування на мові С, С++ та VHDL – для реалізації алгоритмів і структур та оцінки ефективності запропонованої системи на базі проблемно-орієнтованої архітектури.
Наукова новизна результатів дисертаційної роботи. Основними результатами, які визначають наукову новизну та виносяться на захист, є:
– удосконалено процес проектування структурної моделі системи обробки знань, який на відміну від відомих відрізняється розв’язком задачі синтезу функціонально-модульної структури СОЗ на підставі мінімізації числа процесів системи та обсягу даних міжмодульної взаємодії;
– удосконалено процес проектування апаратного інтерпретатора баз знань на основі поведінкової моделі, який на відміну від відомих відрізняється розв’язком задач:
• формування набору спеціальних команд згідно до нового алгоритму пошуку у графі операцій та даних множини підграфів, апаратна реалізація кожного з яких спеціальною командою забезпечує підвищення продуктивності АІБЗ,
• декомпозиції пристрою керування на ведучий та ведені, кожен з яких об’єднує стани із найбільшою вірогідністю переходів між ними,
•структурування пам’яті відповідно до вірогідності доступу до даних;
– вперше отримано якісні аналітичні залежності для емпіричної оцінки швидкодії СОЗ: вимірюванням числа тактів тривалості рішення тестових задач;обрахуванням середньостатистичних оцінок; апроксимацією експериментальних даних та обрахуванням відносних показників.
Практичне значення отриманих результатів.
1. На базі множини VHDL файлів розроблено поведінкову модель прототипу АІБЗ. Це дозволяє проектувати різні реалізації подібних пристроїв із необхідними обсягами пам’яті бази знань у межах наявних ресурсів.
2. Для обміну даними між СОЗ та головним комп’ютером написано драйвер у вигляді набору С-файлів, який може бути використаний для різних реалізацій СОЗ.
3. Прототип АІБЗ реалізовано у вигляді IP-блока, інтерфейс якого забезпечує сумісність пристрою із шиною AMBA та надає можливість його інтеграції в інші системи.
4. На платі корпорації Actel M1AGL-DEV-KIT-SCS реалізовано прототип СОЗ, який дозволяє оцінити його швидкодію та порівняти із швидкодією систем на основі універсальної архітектури.
Достовірність отриманих результатів підтверджується моделюванням роботи запропонованої реалізації СОЗ за допомогою інструментального засобу ModelSim, що міститься у середовищі САПР. За допомогою використання макетної плати корпорації Actel M1AGL-DEV-KIT-SCS проведено ряд експериментальних досліджень над прототипом СОЗ. Проведені дослідження свідчать про те, що виграш у швидкодії роботи СОЗ на базі проблемно-орієнтованої архітектури, порівняно із швидкодією СОЗ на базі універсальної архітектури, у середньому становить від 2,22 до 12,11 разів.
Особистий внесок здобувача. Всі основні положення та результати роботи отримані автором особисто. У працях, виконаних у співавторстві, здобувачу належать такі результати: [46] – теоретичний аналіз та експериментальне оцінювання швидкодії методів для ефективного пошуку даних у словнику термінів інтерпретатора баз знань; [47] – розробка алгоритму проектування керуючої частини спеціалізованого пристрою в системі автоматизованого проектування; [28] – розробка алгоритму проектування специфікації вбудованої системи на основі поведінкової моделі; [48] – аналіз основних задач розробки спеціалізованого процесора; [45] – розробка алгоритму проектування спеціалізованого процесора в системі автоматизованого проектування; [49] – розробка структури СОЗ, емпірична оцінка швидкодії АІБЗ та порівняння із даними швидкодії щодо відомих засобів інтерпретації на основі універсальної архітектури; [50] – систематизація й аналіз архітектур засобів підтримки СОЗ.
Апробація результатів дослідження. Результати досліджень за темою дисертації доповідались та обговорювались на: міжнародній науково-технічній конференції «Гарантоздатні системи, сервіси та технології (DESSERT–2010)» (Кіровоград, Україна 2010); міжнародній науково-технічній конференції «Електроніка і нанотехнології (ELANO-2011)» (Київ, Україна 2011); міжнародній науковій конференції імені Т.А. Таран «Інтелектуальний аналіз інформації (ИАИ-2011, ИАИ-2012)» (Київ, Україна 2011, 2012).
Публікації. Основні результати дисертації опубліковано в десяти наукових працях, серед яких 6 – у фахових наукових виданнях України, перелік яких затверджений ДАК України, 4 – матеріали доповідей на міжнародних наукових та науково-технічних конференціях.
Структура та об’єм роботи. Робота складається із вступу, чотирьох розділів, висновків, додатків та списку використаних джерел. Повний обсяг роботи – 203 сторінки, із них основний текст – 125 сторінок, у тому числі: 88 рисунків, з яких 31 у додатках, 27 таблиць, список з використаних джерел – 20 сторінок, що містить 193 найменування, 6 додатків на 59 сторінках.
Головним результатом дисертаційної роботи є розв’язання науково-технічної задачі підвищення продуктивності апаратного інтерпретатора баз знань за рахунок синтезу і реалізації набору спеціальних команд. Для досягнення цього результату в роботі запропоновано розв’язок задач проектування, які дозволяють підвищити продуктивність у середньому від 2 до 12 разів порівняно із існуючими системами.
Нові наукові та практичні результати отримано використанням низки загальнонаукових, фахових методів дослідження та сучасних інформаційних технологій алгоритмізації, програмування мовами С, С++, VHDL та проектування в середовищі системи автоматизованого проектування.
Основні результати дисертаційної роботи:
1. За рахунок розв’язку задачі вибору мінімального числа процесів системи та розробки міжмодульного інтерфейсу відповідно до мінімуму обміну даними між модулями системи, удосконалено процес проектування структурної моделі системи обробки знань. Мінімальне число процесів системи дозволяє прискорити процес розробки системи за рахунок зменшення загальної кількості апаратних та програмних реалізацій процесів, швидкодію яких потрібно порівнювати. Розробка міжмодульного інтерфейсу дозволяє підвищити швидкодію системи за рахунок зменшення загального часу на обмін даними між модулями системи.
2. За рахунок синтезу набору спеціальних команд із поведінкової моделі АІБЗ для представлення і інтерпретації інформаційно-складних структур, зокрема, ітераційних, рекурсивних та вкладених, роботи із пам’ятями магазину та сліду, удосконалено архітектуру апаратного інтерпретатора баз знань, що дозволило підвищити його швидкодію у середньому від 2 до 12 разів порівняно із відомими програмними реалізаціями.
3. Декомпозиція пристрою керування на ведучий та ведені, кожен з яких об’єднує стани із найбільшою вірогідністю переходів між ними, дозволяє за рахунок усунення станів, що повторюються, побудувати еквівалентний розподілений пристрій керування із мінімальною кількістю його станів.
4. Структурування пам’яті відповідно до вірогідності доступу до даних дозволяє підвищити швидкодію апаратного інтерпретатора баз знань за рахунок зменшення числа його звернень до відносно повільної зовнішньої пам’яті.
5. Отримані аналітичні залежності для емпіричної оцінки швидкодії СОЗ забезпечують високу точність оцінки тривалості рішення задач на програмному інтерпретаторі баз знань за рахунок того, що: вимірювання числа тактів тривалості рішення тестових задач не залежить від впливу технологічних відмінностей (зокрема, різниці тактових частот) реалізації досліджуваних об’єктів;обрахування середньостатистичних оцінок позбавляє від похибки вимірюванняна різних часових інтервалах, пов’язаної із багатозадачністю сучасних систем; апроксимація експериментальних даних та обрахування відносних показників позбавляє від впливу фонових процесів операційної системи.
6. В результаті проведених досліджень розроблено:
– множину VHDL файлів поведінкового опису апаратного інтерпретатора баз знань, що дозволяє проектувати різні реалізації подібних пристроїв із необхідними розмірами пам’яті бази знань у межах наявних ресурсів;
– драйвер у вигляді набору С-файлів, що може бути використаний для інтеграції апаратного інтерпретатора баз знань до складу різних систем обробки знань;
– діючий прототип апаратного інтерпретатора баз знань, реалізованого у вигляді IP-блока, інтерфейс якого забезпечує можливість інтеграції пристрою із іншими системами;
– прототип системи обробки знань на базі плати корпорації Actel M1AGL-DEV-KIT-SCS, який дозволив оцінити її швидкодію та порівняти із швидкодією систем на основі універсальної архітектури.
3.Рассел С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2006. – 1408 с.
В.Н. Разработка интеллектуальных информационных систем с использованием CLIPS: методические указания к практическим и лабораторным работам / В.Н. Дякин. – Тамбов : Изд-во Тамб. гос. техн. ун-та, 2007. – 32 с.
Яковлев – Винница: УНІВЕРСУМ – Вінниця, 2005. – 680 с.
19.Слипченко Н.И. Проблемно-ориентированные вычислительные средства высокой производительности: методология построения, базовые архитектуры, применения / Н.И. Слипченко, О.Г. Руденко, О.М. Сотников и др. – Харьков: ЧНУЗЭ, 2012. – 512 с.
/ P.R.Panda, N.D.Dutt, A.Nicolau// ACM Transactions on Design Automation of Electronic Systems. – 2000. – Vol. 5, №. 3. – P. 682–704.
/ A.Macii// Low-Power Processors and Systems on Chips Edited by Christian Piguet CRC Press 2006. – P. 9-1 – 9-12.
ев А.Ф. О проектировании специализированного процессора в системе автоматизированного проектирования / А.Ф. Кургаев, И.В. Савченко // Управляющие системы и машины. – 2012. – № 1. – С.39–44.
I міжнародної наукової конференції імені Т.А. Таран ИАИ-2011, Київ 17-20 травня 2011р. – С.241-248.
В.М. Теория автоматов и вопросы проектирования структур цифровых машин / В.М.Глушков // Кибернетика. – 1965. – №1. – С. 3–11.
В.М. Вычислительные машины с развитыми системами интерпретации / В.М.Глушков, А.А.Барабанов, Л.А.Калиниченко, и др. – Киев: Наук. Думка. – 1970. – 260 С.
64.Джексон П. Введение в экспертные системы / П.Джексон // М.: Издательский дом «Вильямс», 2001. – 450 с.
65.Джарратано Д. Экспертные системы: принципы разработки и программирование / Д.Джарратано, Г.Райли // 4-е издание.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2007. – 1152 с.
L. An Efficient interpreter for the LAMBDA-calculus / L. Aiello, G. Prini // Computer and Synts. Scien. – 1981. – Vol. 23, №3. – P.383–424.
Stanley T.J. A performance analysis of automatically managed top of stack buffers / T.J. Stanley, R.G. Weding // SIGPLAN Notices. – 1987. – Vol. 22, № 10. – P. 272–281.
New York, 1981. – P. 64–71.
– P. 193–206.
A.R. WISQ: A Restartable Architecture Using Quenes / A.R. Pleszkin et al. // Comp. Archit. News. – 1987. – Vol. 15, №2. – P. 290–299.
N. Representation of Binary Trees on Associative Memories / N. Minsky // Inform. Proc. Letters. – 1973. – Vol. 2. – P. 1–5.
Tokyo, Jap., ICOT. – 1984.
T. A relationaldatabase machine «Delta» / T. Kakatu, N. Miyazaki, S. Shibayama, at al. // ICOT Technical Memorandum TM-0008 (May). Tokyo:Institute for New Generation Computer Technology. – 1983. – 456 p.
С.В. Машины для инженерных расчетов (МИР) / С.В.Погребинский // Кибернетика. – 1982. – С. 55–60.
100.Эйсымонт Л.К. О возможности параллельных схем реализации одного языка для описания задач переработки текстовой информации / Л.К. Эйсымонт // УСиМ, 1977. – № 2. – С. 56–64.
101.Задыхайло И.Б. Исследование процессов параллельного выполнения компилирующих программ некоторого типа / И.Б. Задыхайло и др. //. М: Препринт. – 1980.
102.Эйсымонт Л.К. Выбор и оценка базового языка символьного процессора / Л.К. Эйсымонт, Л.Н. Платонова // Совещание по системам и методам аналитических вычислений на ЭВМ и их применению в теоретической физике. – Дубна, 1983. – С 19–23.
103.Головков С.Л. О некоторых новых средствах языка рекурсивных функций / С.Л. Головков, Н.А. Наумов, В.К. Смирнов // М.: Препринт – 1982.
Amsterdam, New York, Oxford, Tokyo, North-Holland. – 1986. – P. 301–320.
– № 99. — С. 1-21.
– 224 с.
. 5097407 США, МКИ G06F 9/16. Artifical intelligence processor. Опубл. 17.03.1992. – 9 с.
Розділ 3. Розробка набору спеціальних команд та проектування АІБЗ на основі поведінкової моделі .................................................................................... 67
Розділ 4. Реалізація та експериментальне дослідження швидкодії опрацювання метамовних об’єктівна базі макетного зразка СОЗ .................................. 91
4.1. Структура та принцип роботи СОЗ..................................................... 91
4.2. Варіанти структурної реалізації АІБЗ.................................................. 99
4.2.1. Структура та принцип роботи конвеєрного АІБЗ1 із спільною локальною пам’яттю та спрощеним набором команд................................................... 99
4.2.2. Структура та принцип роботи АІБЗ2 із спільною локальною пам’яттю 101
4.2.3. Структура та принцип роботи АІБЗ3 із розподіленою локальною пам’яттю....................................................................................................................... 103
4.3. Структура пам’яті АІБЗ........................................................................ 108
4.4. Результати синтезу, розміщення та трасування СОЗ.......................... 111
Список використаних джерел ..................................................................... 126
Додаток А. Набір регістрів периферійних модулів СОЗ........................... 145
Додаток Б. Алгоритм роботи АІБЗ на рівні базових операцій.................. 149
Додаток В. Приклад побудови бази знань.................................................. 164
Додаток Г. Результати синтезу АІБЗ3......................................................... 173
Додаток Д. Дослідження швидкодії ПІБЗ та АІБЗ3.................................... 182
Додаток Е. Акти впровадження результатів дисертації............................. 201
АІБЗ
Апаратний інтерпретатор баз знань
АЛП
Арифметико-логічний пристрій
БЗ
База знань
ГОД
Граф операцій та даних
ГПП
Граф переходів між процесами
КС
Комп’ютерна система
МЛВ
Машина логічного виводу
ПБЗ
Процесор баз знань
ПІБЗ
Програмний інтерпретатор баз знань
ПЛІС
Програмована логічна інтегральна схема
РП
Робоча пам’ять
СОЗ
Система обробки знань
Актуальність теми. Системи обробки знань відіграють значну роль у житті людства та з кожним роком набувають все більшого поширення у таких прикладних галузях, як [1]: бізнес, виробництво, медицина, військова справа, інжиніринг, комп’ютерні системи, сільське господарство, космонавтика, освіта, транспорт, електроніка тощо. СОЗ традиційно використовуються для рішення структурно складних задач, які формулюють як задачі символьних перетворень, до числа яких відносять: діагностику й прийняття рішень, інтерпретацію даних, розпізнавання образів (зображень, мови), проектування, планування, моніторинг, керування, навчання, доказ теорем, ігри, трансляцію, природномовний переклад тощо.
Сучасний етап розвитку СОЗ пов’язаний із розробкою теорій, методів та засобів підвищення продуктивності та ефективності використання СОЗ. Серед актуальних проблем побудови СОЗ можна виділити [1-6]: представлення знань, виявлення знань, аналіз даних, машинне навчання, добування знань, методологію розробки СОЗ, управління знаннями, комп’ютерна лінгвістика, архітектура КС обробки знань та ін.
Сьогодні для реалізації СОЗ переважно використовують універсальні комп’ютери, головним недоліком яких є семантичний розрив між поняттями операцій та їх об’єктів у мові високого рівня та поняттями операцій і їх об’єктів, що визначаються архітектурою комп’ютера [5,6]. Наслідком цього є низька продуктивність сучасних СОЗ. Зокрема, сучасний інструмент CLІPS, призначений для створення експертних систем, може незадовільно працювати в реальному часі, коли потрібен час реакції, менший за 0,1 с [7].Витрати ж часу на рішення реальних задач експертизи складають від одиниць та десятків секунд [8].
Необхідність підвищення продуктивності СОЗ обумовлена: 1) наявністю високих вимог до продуктивності з боку систем реального часу (підтримка прийняття рішень на фондових біржах, діагностування серцево-судинних захворювань та ін.); 2) зростанням об’ємів знань про дійсність; 3) еволюцією знань про методи рішення наукових чи освітніх проблем, висуванням нових, більш складних вимог до функціональних можливостей СОЗ.
Перші спроби розв’язання проблем семантичного розриву та ряду інших проблем були зроблені ще у 60-70-х роках. Їхня суть зводилась до розробки проблемно-орієнтованих КС із «нефоннейманівською архітектурою», придатною для безпосереднього виконання програм, написаних на спеціальній мові високого рівня або на проміжній мові [6]. Розгляд таких КС висвітлено в [6, 9-12].
Широко відомі роботи Глушкова В.М., Скуріхіна В.І., Палагіна О.В., Морозова А.О, Малиновського Б.М., Боюна В.П., Кліменка В.П., Яковлева Ю.С., Амамія М., Танака Ю., Teodorescu H.N., Jain L.C., Kandel A., що використовують різні методи і засоби вдосконалення ефективності архітектур проблемно-орієнтованих КС.
По багатьох причинах, які наведено у [13], ідея широкомасштабної заміни програмних засобів апаратними виявилася невиправданою. А розвиток комп’ютерної індустрії пішов іншим шляхом, розвиваючи програмні засоби із застосуванням більш простих, але стандартних (універсальних) апаратних засобів. Хоча вдалі комерційні та промислові проблемно-орієнтовані комп’ютери існують і сьогодні, їхня висока вартість, несумісність із традиційними КС заважають їхньому розповсюдженню на ринку [14].
Сьогодні апаратні засоби підтримки СОЗ використовують такі архітектури універсальних процесорів: багатоядерні, мультитрейдові, суперскалярні та архітектури із командним словом великої довжини [15]. Одним із сучасних напрямків проблемної орієнтації архітектур КС є розширення набору команд процесора спеціальними командами[16, 17]. Серед головних недоліків відомих наборів команд та особливостей організації пам’яті існуючих КС можна виділити: 1) необхідність виконання великої кількості операцій при символьних обчисленнях; 2) відсутність ефективного представлення у пам’яті і обробки інформаційно складних структур, зокрема, вкладених, ітераційних та рекурсивних.
Загальніпідходи до проектування цифрових систем широко висвітлено в [18-27]. Найбільші складності проектування цифрових систем мають місце на початковому етапі, пов’язаному із розробкою специфікації системи [28]. Існуючі підходи проектування цифрових систем на основі поведінкової моделі потребують вдосконалення, зокрема, відносно розв’язку задачі визначення функціонально-модульної структури СОЗ [29-34].
Загальні підходи до проектування спеціалізованих процесорів висвітлено у [35-37]. Серед інших робіт можна виділити: проектування операційної частини процесора [38-40], пристрою керування [41-42], організація структури пам’яті [43-44]. Однак проектування апаратного інтерпретатора баз знань (АІБЗ) має певну специфіку відносно рішення задач синтезу спеціалізованих процесорів, зокрема щодо розв’язку задач [45]: декомпозиції пристрою керування, організації пам’яті, розділення даних в оперативній пам’яті.
Отже, актуальною є науково-технічна задача дослідження і розробки структурної моделі та реалізації проблемно-орієнтованого апаратного інтерпретатора баз знань із набором спеціальних команд з метою підвищення продуктивність апаратного інтерпретатора баз знань.
Зв’язок роботи з науковими програмами, планами, темами.Робота виконувалась у відділі мікропроцесорної техніки Інституту кібернетики імені В.М. Глушкова НАН України згідно наукових тем, в яких дисертант був виконавцем:
«Розробка теоретичних засад онтологокерованих комп’ютерних систем з реконфігуровною архітектурою» (№ держреєстрації 0107U003616, виконана за постановою Бюро відділення інформатики НАН України, Протокол № 6 від 17.01.2007 р., 2007–2011);
«Розробити та провести дослідження формальних моделей та архітектури онтолого-керованих інформаційних систем обробки знань» (№ держреєстрації 0109U001606, виконується за постановою Бюро відділення інформатики НАН України, Протокол № 4 від 7.05. 2008 р., 2009–2013).
«Розробити теоретичні засади, методи та інформаційні технології побудови комп‘ютерних засобів та систем на основі інтегрованого використання методів обробки знань, редукційного паралелізму та реконфігурування» (№ держреєстрації 0112U002255, виконується за постановою Бюро відділення інформатики НАН України, Протокол № 2 від 10.11.2011 р., 2012–2016).
Мета і задачі дослідження. Метою дослідження є підвищення продуктивності апаратного інтерпретатора баз знань за рахунок синтезу і реалізації набору спеціальних команд.
Для досягнення поставленої мети в роботі необхідно вирішити такі задачі:
– аналіз архітектур КС, орієнтованих на ефективну апаратну підтримку обробки знань та оцінка основних напрямів їх подальшого розвитку;
– визначення функціонально-модульної структури СОЗ;
– формування набору спеціальних команд, структур пристрою керування та пам’яті АІБЗ;
– розробка структури та реалізація АІБЗ на основі поведінкової моделі;
– оцінка швидкодії обробки знань на базі АІБЗ порівняно із швидкодією існуючих систем на базі комп’ютерів універсальної архітектури.
Об’єктом дослідження в дисертаційній роботі є процеси проектування проблемно-орієнтованих комп’ютерних систем та їх функціональних модулів.
Предметом дослідження в дисертаційній роботі є методи проектування архітектури, структури, реалізації та засоби експериментального дослідження АІБЗ.
Методи дослідження. Для досягнення мети роботи використано низку загальнонаукових та специфічних методів дослідження: загальні методи проектування обчислювальних систем – для вибору структури СОЗ, структури АІБЗ; методи мінімізації – для вибору мінімальної кількості процесів системи, для вибору мінімальних апаратних витрат на реалізацію модулів системи, для збільшення швидкодії модулів системи; методи теорії цифрових автоматів – для побудови керуючої частини АІБЗ; методи математичного аналізу – для розробки засобів обробки даних; методи алгоритмізації та програмування на мові С, С++ та VHDL – для реалізації алгоритмів і структур та оцінки ефективності запропонованої системи на базі проблемно-орієнтованої архітектури.
Наукова новизна результатів дисертаційної роботи. Основними результатами, які визначають наукову новизну та виносяться на захист, є:
– удосконалено процес проектування структурної моделі системи обробки знань, який на відміну від відомих відрізняється розв’язком задачі синтезу функціонально-модульної структури СОЗ на підставі мінімізації числа процесів системи та обсягу даних міжмодульної взаємодії;
– удосконалено процес проектування апаратного інтерпретатора баз знань на основі поведінкової моделі, який на відміну від відомих відрізняється розв’язком задач:
• формування набору спеціальних команд згідно до нового алгоритму пошуку у графі операцій та даних множини підграфів, апаратна реалізація кожного з яких спеціальною командою забезпечує підвищення продуктивності АІБЗ,
• декомпозиції пристрою керування на ведучий та ведені, кожен з яких об’єднує стани із найбільшою вірогідністю переходів між ними,
•структурування пам’яті відповідно до вірогідності доступу до даних;
– вперше отримано якісні аналітичні залежності для емпіричної оцінки швидкодії СОЗ: вимірюванням числа тактів тривалості рішення тестових задач;обрахуванням середньостатистичних оцінок; апроксимацією експериментальних даних та обрахуванням відносних показників.
Практичне значення отриманих результатів.
1. На базі множини VHDL файлів розроблено поведінкову модель прототипу АІБЗ. Це дозволяє проектувати різні реалізації подібних пристроїв із необхідними обсягами пам’яті бази знань у межах наявних ресурсів.
2. Для обміну даними між СОЗ та головним комп’ютером написано драйвер у вигляді набору С-файлів, який може бути використаний для різних реалізацій СОЗ.
3. Прототип АІБЗ реалізовано у вигляді IP-блока, інтерфейс якого забезпечує сумісність пристрою із шиною AMBA та надає можливість його інтеграції в інші системи.
4. На платі корпорації Actel M1AGL-DEV-KIT-SCS реалізовано прототип СОЗ, який дозволяє оцінити його швидкодію та порівняти із швидкодією систем на основі універсальної архітектури.
Достовірність отриманих результатів підтверджується моделюванням роботи запропонованої реалізації СОЗ за допомогою інструментального засобу ModelSim, що міститься у середовищі САПР. За допомогою використання макетної плати корпорації Actel M1AGL-DEV-KIT-SCS проведено ряд експериментальних досліджень над прототипом СОЗ. Проведені дослідження свідчать про те, що виграш у швидкодії роботи СОЗ на базі проблемно-орієнтованої архітектури, порівняно із швидкодією СОЗ на базі універсальної архітектури, у середньому становить від 2,22 до 12,11 разів.
Особистий внесок здобувача. Всі основні положення та результати роботи отримані автором особисто. У працях, виконаних у співавторстві, здобувачу належать такі результати: [46] – теоретичний аналіз та експериментальне оцінювання швидкодії методів для ефективного пошуку даних у словнику термінів інтерпретатора баз знань; [47] – розробка алгоритму проектування керуючої частини спеціалізованого пристрою в системі автоматизованого проектування; [28] – розробка алгоритму проектування специфікації вбудованої системи на основі поведінкової моделі; [48] – аналіз основних задач розробки спеціалізованого процесора; [45] – розробка алгоритму проектування спеціалізованого процесора в системі автоматизованого проектування; [49] – розробка структури СОЗ, емпірична оцінка швидкодії АІБЗ та порівняння із даними швидкодії щодо відомих засобів інтерпретації на основі універсальної архітектури; [50] – систематизація й аналіз архітектур засобів підтримки СОЗ.
Апробація результатів дослідження. Результати досліджень за темою дисертації доповідались та обговорювались на: міжнародній науково-технічній конференції «Гарантоздатні системи, сервіси та технології (DESSERT–2010)» (Кіровоград, Україна 2010); міжнародній науково-технічній конференції «Електроніка і нанотехнології (ELANO-2011)» (Київ, Україна 2011); міжнародній науковій конференції імені Т.А. Таран «Інтелектуальний аналіз інформації (ИАИ-2011, ИАИ-2012)» (Київ, Україна 2011, 2012).
Публікації. Основні результати дисертації опубліковано в десяти наукових працях, серед яких 6 – у фахових наукових виданнях України, перелік яких затверджений ДАК України, 4 – матеріали доповідей на міжнародних наукових та науково-технічних конференціях.
Структура та об’єм роботи. Робота складається із вступу, чотирьох розділів, висновків, додатків та списку використаних джерел. Повний обсяг роботи – 203 сторінки, із них основний текст – 125 сторінок, у тому числі: 88 рисунків, з яких 31 у додатках, 27 таблиць, список з використаних джерел – 20 сторінок, що містить 193 найменування, 6 додатків на 59 сторінках.
Список литературы:
Головним результатом дисертаційної роботи є розв’язання науково-технічної задачі підвищення продуктивності апаратного інтерпретатора баз знань за рахунок синтезу і реалізації набору спеціальних команд. Для досягнення цього результату в роботі запропоновано розв’язок задач проектування, які дозволяють підвищити продуктивність у середньому від 2 до 12 разів порівняно із існуючими системами.
Нові наукові та практичні результати отримано використанням низки загальнонаукових, фахових методів дослідження та сучасних інформаційних технологій алгоритмізації, програмування мовами С, С++, VHDL та проектування в середовищі системи автоматизованого проектування.
Основні результати дисертаційної роботи:
1. За рахунок розв’язку задачі вибору мінімального числа процесів системи та розробки міжмодульного інтерфейсу відповідно до мінімуму обміну даними між модулями системи, удосконалено процес проектування структурної моделі системи обробки знань. Мінімальне число процесів системи дозволяє прискорити процес розробки системи за рахунок зменшення загальної кількості апаратних та програмних реалізацій процесів, швидкодію яких потрібно порівнювати. Розробка міжмодульного інтерфейсу дозволяє підвищити швидкодію системи за рахунок зменшення загального часу на обмін даними між модулями системи.
2. За рахунок синтезу набору спеціальних команд із поведінкової моделі АІБЗ для представлення і інтерпретації інформаційно-складних структур, зокрема, ітераційних, рекурсивних та вкладених, роботи із пам’ятями магазину та сліду, удосконалено архітектуру апаратного інтерпретатора баз знань, що дозволило підвищити його швидкодію у середньому від 2 до 12 разів порівняно із відомими програмними реалізаціями.
3. Декомпозиція пристрою керування на ведучий та ведені, кожен з яких об’єднує стани із найбільшою вірогідністю переходів між ними, дозволяє за рахунок усунення станів, що повторюються, побудувати еквівалентний розподілений пристрій керування із мінімальною кількістю його станів.
4. Структурування пам’яті відповідно до вірогідності доступу до даних дозволяє підвищити швидкодію апаратного інтерпретатора баз знань за рахунок зменшення числа його звернень до відносно повільної зовнішньої пам’яті.
5. Отримані аналітичні залежності для емпіричної оцінки швидкодії СОЗ забезпечують високу точність оцінки тривалості рішення задач на програмному інтерпретаторі баз знань за рахунок того, що: вимірювання числа тактів тривалості рішення тестових задач не залежить від впливу технологічних відмінностей (зокрема, різниці тактових частот) реалізації досліджуваних об’єктів;обрахування середньостатистичних оцінок позбавляє від похибки вимірюванняна різних часових інтервалах, пов’язаної із багатозадачністю сучасних систем; апроксимація експериментальних даних та обрахування відносних показників позбавляє від впливу фонових процесів операційної системи.
6. В результаті проведених досліджень розроблено:
– множину VHDL файлів поведінкового опису апаратного інтерпретатора баз знань, що дозволяє проектувати різні реалізації подібних пристроїв із необхідними розмірами пам’яті бази знань у межах наявних ресурсів;
– драйвер у вигляді набору С-файлів, що може бути використаний для інтеграції апаратного інтерпретатора баз знань до складу різних систем обробки знань;
– діючий прототип апаратного інтерпретатора баз знань, реалізованого у вигляді IP-блока, інтерфейс якого забезпечує можливість інтеграції пристрою із іншими системами;
– прототип системи обробки знань на базі плати корпорації Actel M1AGL-DEV-KIT-SCS, який дозволив оцінити її швидкодію та порівняти із швидкодією систем на основі універсальної архітектури.
3.Рассел С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2006. – 1408 с.
В.Н. Разработка интеллектуальных информационных систем с использованием CLIPS: методические указания к практическим и лабораторным работам / В.Н. Дякин. – Тамбов : Изд-во Тамб. гос. техн. ун-та, 2007. – 32 с.
Яковлев – Винница: УНІВЕРСУМ – Вінниця, 2005. – 680 с.
19.Слипченко Н.И. Проблемно-ориентированные вычислительные средства высокой производительности: методология построения, базовые архитектуры, применения / Н.И. Слипченко, О.Г. Руденко, О.М. Сотников и др. – Харьков: ЧНУЗЭ, 2012. – 512 с.
/ P.R.Panda, N.D.Dutt, A.Nicolau// ACM Transactions on Design Automation of Electronic Systems. – 2000. – Vol. 5, №. 3. – P. 682–704.
/ A.Macii// Low-Power Processors and Systems on Chips Edited by Christian Piguet CRC Press 2006. – P. 9-1 – 9-12.
ев А.Ф. О проектировании специализированного процессора в системе автоматизированного проектирования / А.Ф. Кургаев, И.В. Савченко // Управляющие системы и машины. – 2012. – № 1. – С.39–44.
I міжнародної наукової конференції імені Т.А. Таран ИАИ-2011, Київ 17-20 травня 2011р. – С.241-248.
В.М. Теория автоматов и вопросы проектирования структур цифровых машин / В.М.Глушков // Кибернетика. – 1965. – №1. – С. 3–11.
В.М. Вычислительные машины с развитыми системами интерпретации / В.М.Глушков, А.А.Барабанов, Л.А.Калиниченко, и др. – Киев: Наук. Думка. – 1970. – 260 С.
64.Джексон П. Введение в экспертные системы / П.Джексон // М.: Издательский дом «Вильямс», 2001. – 450 с.
65.Джарратано Д. Экспертные системы: принципы разработки и программирование / Д.Джарратано, Г.Райли // 4-е издание.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2007. – 1152 с.
L. An Efficient interpreter for the LAMBDA-calculus / L. Aiello, G. Prini // Computer and Synts. Scien. – 1981. – Vol. 23, №3. – P.383–424.
Stanley T.J. A performance analysis of automatically managed top of stack buffers / T.J. Stanley, R.G. Weding // SIGPLAN Notices. – 1987. – Vol. 22, № 10. – P. 272–281.
New York, 1981. – P. 64–71.
– P. 193–206.
A.R. WISQ: A Restartable Architecture Using Quenes / A.R. Pleszkin et al. // Comp. Archit. News. – 1987. – Vol. 15, №2. – P. 290–299.
N. Representation of Binary Trees on Associative Memories / N. Minsky // Inform. Proc. Letters. – 1973. – Vol. 2. – P. 1–5.
Tokyo, Jap., ICOT. – 1984.
T. A relationaldatabase machine «Delta» / T. Kakatu, N. Miyazaki, S. Shibayama, at al. // ICOT Technical Memorandum TM-0008 (May). Tokyo:Institute for New Generation Computer Technology. – 1983. – 456 p.
С.В. Машины для инженерных расчетов (МИР) / С.В.Погребинский // Кибернетика. – 1982. – С. 55–60.
100.Эйсымонт Л.К. О возможности параллельных схем реализации одного языка для описания задач переработки текстовой информации / Л.К. Эйсымонт // УСиМ, 1977. – № 2. – С. 56–64.
101.Задыхайло И.Б. Исследование процессов параллельного выполнения компилирующих программ некоторого типа / И.Б. Задыхайло и др. //. М: Препринт. – 1980.
102.Эйсымонт Л.К. Выбор и оценка базового языка символьного процессора / Л.К. Эйсымонт, Л.Н. Платонова // Совещание по системам и методам аналитических вычислений на ЭВМ и их применению в теоретической физике. – Дубна, 1983. – С 19–23.
103.Головков С.Л. О некоторых новых средствах языка рекурсивных функций / С.Л. Головков, Н.А. Наумов, В.К. Смирнов // М.: Препринт – 1982.
Amsterdam, New York, Oxford, Tokyo, North-Holland. – 1986. – P. 301–320.
– № 99. — С. 1-21.
– 224 с.
. 5097407 США, МКИ G06F 9/16. Artifical intelligence processor. Опубл. 17.03.1992. – 9 с.
