Структура та дослідження швидкодії систем обробки знань

Розробка нових, більш продуктивних, архітектур комп'ютерів для обробки знань залишається актуальною задачею. В роботі запропоновано структуру інтерпретатора баз знань та виконано емпіричне дослідження продуктивності системи обробки знань. У дослідженнях застосовано метод апроксимації. Отримані...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Кургаєв, О.П., Савченко, І.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем математичних машин і систем НАН України 2012
Schriftenreihe:	Математичні машини і системи
Schlagworte:	Нові інформаційні і телекомунікаційні технології
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/83756
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Структура та дослідження швидкодії систем обробки знань / А.Ф. Кургаев, И.В. Савченко // Мат. машини і системи. — 2012. — № 2. — С. 41-50. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-83756
record_format	dspace
spelling	irk-123456789-837562015-06-24T03:02:12Z Структура та дослідження швидкодії систем обробки знань Кургаєв, О.П. Савченко, І.В. Нові інформаційні і телекомунікаційні технології Розробка нових, більш продуктивних, архітектур комп'ютерів для обробки знань залишається актуальною задачею. В роботі запропоновано структуру інтерпретатора баз знань та виконано емпіричне дослідження продуктивності системи обробки знань. У дослідженнях застосовано метод апроксимації. Отримані результати свідчать про доцільність апаратної реалізації засобів інтерпретації баз знань. Запропонований інтерпретатор може бути використаний при побудові сучасних систем обробки знань. Разработка новых, более производительных, архитектур компьютеров для обработки знаний остается актуальной задачей. В работе предложена структура интерпретатора баз знаний и проведено эмпирическое исследование быстродействия системы обработки знаний. В исследованиях использован метод аппроксимации. Полученные результаты свидетельствуют о целесообразности аппаратной реализации средств интерпретации баз знаний. Предложенный интерпретатор может быть использован при построении современных систем обработки знаний. Nowadays developing of new and more productive computer architectures for knowledge processing is a vital task. The interpreter structure of intelligent databases is suggested. The empirical research of the system performance of knowledge processing is conducted. There was used an approximation method in the researches. The received results prove the feasibility of hardware implementation of intelligent databases. The proposed interpreter can be used in the construction of modern knowledge processing systems. 2012 Article Структура та дослідження швидкодії систем обробки знань / А.Ф. Кургаев, И.В. Савченко // Мат. машини і системи. — 2012. — № 2. — С. 41-50. — Бібліогр.: 11 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83756 004.27 uk Математичні машини і системи Інститут проблем математичних машин і систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Нові інформаційні і телекомунікаційні технології Нові інформаційні і телекомунікаційні технології
spellingShingle	Нові інформаційні і телекомунікаційні технології Нові інформаційні і телекомунікаційні технології Кургаєв, О.П. Савченко, І.В. Структура та дослідження швидкодії систем обробки знань Математичні машини і системи
description	Розробка нових, більш продуктивних, архітектур комп'ютерів для обробки знань залишається актуальною задачею. В роботі запропоновано структуру інтерпретатора баз знань та виконано емпіричне дослідження продуктивності системи обробки знань. У дослідженнях застосовано метод апроксимації. Отримані результати свідчать про доцільність апаратної реалізації засобів інтерпретації баз знань. Запропонований інтерпретатор може бути використаний при побудові сучасних систем обробки знань.
format	Article
author	Кургаєв, О.П. Савченко, І.В.
author_facet	Кургаєв, О.П. Савченко, І.В.
author_sort	Кургаєв, О.П.
title	Структура та дослідження швидкодії систем обробки знань
title_short	Структура та дослідження швидкодії систем обробки знань
title_full	Структура та дослідження швидкодії систем обробки знань
title_fullStr	Структура та дослідження швидкодії систем обробки знань
title_full_unstemmed	Структура та дослідження швидкодії систем обробки знань
title_sort	структура та дослідження швидкодії систем обробки знань
publisher	Інститут проблем математичних машин і систем НАН України
publishDate	2012
topic_facet	Нові інформаційні і телекомунікаційні технології
url	http://dspace.nbuv.gov.ua/handle/123456789/83756
citation_txt	Структура та дослідження швидкодії систем обробки знань / А.Ф. Кургаев, И.В. Савченко // Мат. машини і системи. — 2012. — № 2. — С. 41-50. — Бібліогр.: 11 назв. — укр.
series	Математичні машини і системи
work_keys_str_mv	AT kurgaêvop strukturatadoslídžennâšvidkodíísistemobrobkiznanʹ AT savčenkoív strukturatadoslídžennâšvidkodíísistemobrobkiznanʹ
first_indexed	2025-07-06T10:33:59Z
last_indexed	2025-07-06T10:33:59Z
_version_	1836893381779783680
fulltext	© Кургаєв О.П., Савченко І.В., 2012 41 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 НОВІ ІНФОРМАЦІЙНІ І ТЕЛЕКОМУНІКАЦІЙНІ ТЕХНОЛОГІЇ УДК 004.27 О.П. КУРГАЄВ, І.В. САВЧЕНКО СТРУКТУРА ТА ДОСЛІДЖЕННЯ ШВИДКОДІЇ СИСТЕМИ ОБРОБКИ ЗНАНЬ Анотація. Розробка нових, більш продуктивних, архітектур комп’ютерів для обробки знань зали- шається актуальною задачею. В роботі запропоновано структуру інтерпретатора баз знань та виконано емпіричне дослідження продуктивності системи обробки знань. У дослідженнях засто- совано метод апроксимації. Отримані результати свідчать про доцільність апаратної реалізації засобів інтерпретації баз знань. Запропонований інтерпретатор може бути використаний при побудові сучасних систем обробки знань. Ключові слова: система обробки знань, швидкодія, макетна плата, архітектура, процесор, набір команд. Аннотация. Разработка новых, более производительных, архитектур компьютеров для обработ- ки знаний остается актуальной задачей. В работе предложена структура интерпретатора баз знаний и проведено эмпирическое исследование быстродействия системы обработки знаний. В исследованиях использован метод аппроксимации. Полученные результаты свидетельствуют о целесообразности аппаратной реализации средств интерпретации баз знаний. Предложенный интерпретатор может быть использован при построении современных систем обработки зна- ний. Ключевые слова: система обработки знаний, быстродействие, макетная плата, архитектура, процессор, набор команд. Abstract. Nowadays developing of new and more productive computer architectures for knowledge processing is a vital task. The interpreter structure of intelligent databases is suggested. The empirical research of the system performance of knowledge processing is conducted. There was used an approxi- mation method in the researches. The received results prove the feasibility of hardware implementation of intelligent databases. The proposed interpreter can be used in the construction of modern knowledge processing systems. Keywords: knowledge processing system, performance, prototyping board, architecture, processor, com- mand set. 1. Вступ Системи обробки знань відіграють значну роль у житті людства і з кожним роком набува- ють все більшого розповсюдження. Дані системи застосовуються у таких прикладних об- ластях [1]: управління, контроль виробничих процесів, діагностика, виявлення несправнос- тей, робототехніка, обробка зображень, машинний зір, медичні системи, моніторинг та прогнозування на фінансовому й фондовому ринках та ін. Засобами систем обробки знань створюють прикладні системи, що відповідають найбільш суттєвим ознакам концепту ро- зумна діяльність [2–4]: розпізнавання, перетворення і розуміння образів (природномовних, зорових, тактильних тощо), вирішення задач у просторі станів, прийняття рішень, адапта- ція та навчання на основі накопиченого досвіду, цілеспрямована поведінка, самоорганіза- ція систем тощо. Об’єм та складність задач, які вирішують сучасні системи обробки знань, постійно зростають. Це змушує розробників апаратних засобів шукати шляхи створення більш шви- дких, надійних та одночасно економічних архітектур комп’ютерних систем. Принципови- ми в даному напрямі залишаються задачі [5, 6] підвищення продуктивності процесорів, 42 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 Рис. 1. Структура системи обробки знань швидкодії пам’яті, портів вводу-виводу. В роботі головну увагу зосереджено саме на зада- чі підвищення продуктивності роботи процесора. Для підтримки роботи систем обробки знань сьогодні застосовуються комп’ютери з такою архітектурою [5]: багатоядерні, мультитрейдові, суперскалярні та архітектури з ко- мандним словом великої довжини. На сьогодні підвищення продуктивності процесора до- сягається за рахунок розв’язання таких задач [5, 6]: зменшення розмірів логічних елементів та щільності їх розташування; підвищення розміру та швидкодії кеш-пам’яті; внесення змін в архітектуру та організацію процесора (використання різних форм паралелізму, кон- веєризації команд, введення додаткових наборів спеціалізованих пристроїв та команд про- цесора). Серед робіт, які глибоко досліджують проблему підвищення продуктивності про- цесора за рахунок розширення команд процесора, можна виділити роботу [7]. Прикладом використання такого підходу для підвищення продуктивності систем обробки знань є на- бір команд SSE4.2, який використовується у сучасних процесорах [8]: для ефективної об- робки строк у XML-файлах, синтаксичного розбору речення, створення міток, оцінки ре- гулярних виразів та пошуку вірусів. Стрімкий розвиток технологій проектування та розробки систем на кристалі зумо- вив виникнення робіт, які пропонують використання проблемно-орієнтованих архітектур для розв’язку задач у вузьких предметних областях. У [9] наведено широкий огляд апарат- них реалізацій систем обробки знань із використанням реконфігурованих засобів, генетич- них алгоритмів, нечіткої логіки, нейронних мереж та паралельних алгоритмів. Однак сема- нтичний розрив, недостатня гнучкість архітектури, неефективне використання пам’яті та апаратних витрат зумовлюють необхідність розробки нових наборів команд та архітектур співпроцесорів для ефективної підтримки роботи систем обробки знань [4]. Метою роботи є емпіричне дослідження швидкодії спеціалізованого інтерпретатора баз знань та порівняння експериментальних даних із даними, отриманими при викорис- танні відомих засобів інтерпретації на основі універсальної архітектури. 2. Структура системи обробки знань Для проведення емпіричних досліджень швидкодії було реалізовано систему обробки знань (рис. 1) на базі макетної плати M1AGL-DEV-KIT-SCS корпорації Actel. На базі крис- талу програмованої логі- чної інтегральної схеми (ПЛІС) M1AGL600 FPGA реалізовано систему об- робки знань, яка містить такі модулі: процесор CortexM1, контролер пам’яті, регістрову пам’ять, процесорну ши- ну AHB, периферійну шину APB, міст сполу- чення процесорної та пе- риферійної шини, апарат- ний інтерпретатор баз знань, UART-контролер, порти вводу-виводу, тай- мер, контролер перери- вань. До складу системи обробки знань також вхо- дить головний комп’ютер. ISSN 1028-9763. Математичні машини і системи, 2012, № 2 43 Рис. 2. Структура адресного простору системи обробки знань З метою розширення набору команд універсального процесора (Cortex M1) у систему об- робки знань інтегровано додатковий модуль – інтерпретатор баз знань зі спеціальним на- бором команд для ефективної підтримки роботи системи обробки знань. До складу функцій CortexM1 належать ініціалізація системи обробки знань; отри- мання завдання від головного комп’ютера; передача отриманого завдання до інтерпретато- ра баз знань; виконання термінальних програм на замовлення інтерпретатора баз знань; передача результатів виконання термінальних програм до інтерпретатора баз знань; зчиту- вання із регістрів інтерпретатора баз знань результатів опрацювання поставленого завдан- ня та передача отриманих результатів головному комп’ютеру. Флеш-пам’ять є енергонезалежною й призначена для постійного збереження таких даних системи обробки знань: пам’ять програм, база знань, словник термінів. Оскільки флеш-пам’ять достатньо повільна, однак енергонезалежна, то дані в ній зберігаються лише під час відсутності живлення системи. Під час ініціалізації системи всі дані переписуються у більш швидку – статичну пам’ять. Статична пам’ять у зв’язку з її високою швидкодією безперервно використовується у процесі роботи системи обробки знань і призначена для збереження таких даних: пам’ять програм, програмний стек Cortex-M1, база знань, словник термінів, вхідний масив, вихід- ний масив. Регістрова пам’ять використовується процесором CortexM1 для збереження локаль- них даних (змінних, масивів, констант), швидкість доступу до яких має бути максималь- ною. Інтерпретатор баз знань опрацьовує знання, представлені метамовою у формі взає- мопов’язаних визначень понять деякої предметної області [4]. Контролер переривань використовується для синхронізації процесів обміну коман- дами і даними між процесором CortexM1 та усіма функціональними модулями, розташо- ваними на процесорній та периферійній шинах системи. Контролер переривань також віді- грає суттєву роль у процесі обміну даними між головним комп’ютером і системою оброб- ки знань. UART-контролер виконує функцію пристрою сполучення або мосту між системою обробки знань і головним комп’ютером. Таймер та порти вводу-виводу використовуються спільно для візуа- льного відображення поточного стану системи обробки знань на світлодіод- ній панелі у вигляді рухомого рядка. Доступ процесора Cortex-M1 до ресурсів функціональних модулів (пам’ять, регістри), а також обмін командами й даними між ними, від- бувається через виділений для кож- ного із них окремий адресний прос- тір, структуру якого зображено на рис. 2. Слід зазначити, що статична пам’ять (рис. 2) включає пам’ять про- грам, яка містить програму, що керує й підтримує роботу системи обробки знань. Дана програма забезпечує ініціалізацію системи обробки знань; отримання завдання від головного комп’ютера; передачу отриманого завдання до апаратного інтерпретатора баз знань; виконання термінальних програм на замовлення інтерпретатора баз знань; пере- 44 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 Рис. 3. Структура інтерпретатора баз знань дачу результатів виконання термінальних програм до інтерпретатора баз знань; зчитування із регістрів інтерпретатора баз знань результатів опрацювання поставленого завдання та передачу отриманих результатів до головного комп’ютера. 3. Структура інтерпретатора баз знань Інтерпретатор баз знань опрацьовує знання, представлені метамовою у формі взаємо- пов’язаних визначень понять деякої предметної області. Кожне із понять визначається як альтернатива або послідовність деяких понять (серед яких може бути і поняття, що визна- чається), кожне із яких може бути ітерацією деякої структури визначень або задано визна- ченнями. Будь-яке просте поняття (найнижчого рівня складності) визначається у формі константи або процедури (термінальної програми) [4]. Інтерпретатор баз знань міс- тить такі основні компоненти (рис. 3): процесор баз знань, локальну та ста- тичну пам’ять. Процесор баз знань складається із пристрою управління, реалізованого у вигляді цифрового синхронного автомата Мура, та при- строю обробки даних із набором регі- стрів, в яких зберігається поточний стан інтерпретатора. Статична пам’ять, розміщена поза кристалом ПЛІС, містить такі пам’яті інтерпретатора баз знань: словник термінів, вхідний масив та вихідний масив. Процесор баз знань не має прямого доступу до даних статичної пам’яті, а отримує лише логічні результати їх опрацювання процесором Cortex-M1. Локальна пам’ять, яка розміщена на кристалі ПЛІС, містить такі пам’яті: бази знань, магазину та слі- ду. Словник термінів містить множину записів, кожний із яких складається із двох по- лів: «Ім’я поняття» та «Адреса структури визначення». Поле «Ім’я поняття» містить послі- довність алфавітно-цифрових символів і використовується для розіменування імені шука- ної структури у фізичну адресу її розміщення у базі знань. Фізична адреса даної структури міститься у полі «Адреса структури визначення». Вхідний та вихідний масиви у формі ASCII-коду містять відповідно: суб’єкт кате- горичного висловлювання, предикат якого потрібно довести, та суб’єкт, отриманий вна- слідок доведення. Пам’ять магазину містить поточний стан інтерпретації баз знань у формі множини записів фіксованої довжини. Кожен запис містить поля: координати вхідного та вихідного масивів, координати сліду, адресу поточного слова фрейму, кількість успішно виконаних ітерацій, режим інтерпретації. Пам’ять сліду містить масив записів фіксованої довжини, який відображає хід інте- рпретації понять у формі дерева виводу. Кожен запис може містити дані двох типів: фізич- ну адресу успішно інтерпретованої альтернативи або кількість успішно виконаних ітера- цій. Пам’ять бази знань містить інформаційну структуру знань, яка складається із мно- жини фреймів. Кожен фрейм бази знань містить голову та елементи, пов’язані одним від- ношенням: кон’юнкції, диз’юнкції або ітерації. Голова та будь-який з елементів займають декілька послідовно розташованих комірок пам’яті. Елементи одного масиву, пов’язані ві- дношенням диз’юнкції або кон’юнкції, розташовані у наступних сусідніх комірках пам’яті. Голова фрейму розташована першою в даній послідовності, при цьому розмір фрейму (чи- сло елементів в одному фреймі) може бути довільним. Фрейм ітерації складається із двох ISSN 1028-9763. Математичні машини і системи, 2012, № 2 45 компонент: голови та ітерованого елемента. Ітерований елемент представляється посилан- ням на деякий фрейм, який є головною компонентою опису даного елемента. Цим забезпе- чується зв’язність різних фреймів в єдину багаторазово вкладену структуру, що допускає рекурсивні конструкції. Складність опису (потужність множини, кількість масивів) може бути довільною і обмежується ресурсами конкретної реалізації. Ті поняття бази знань, які не мають опису через інші поняття, є термінальними і ви- значаються посиланням на термінальні програми, що в подальшому виконуються універ- сальним процесором (CortexM1). Термінальні програми реалізовано у вигляді скомпільо- ваного коду процедур та функцій. Формально базу знань KB можна визначити такою четвіркою [4]: >=< PSAAKB CONTR ,,, , (1) де TRA – множина термінальних програм, які визначено поза базою знань і які виконують- ся на універсальному процесорі; CONA – множина імен понять та текстових констант; S – поняття найвищого рівня складності, яке визначається базою знань; P – інформаційна структура поняття S. Детальний опис алгоритму інтерпретації наведено у [4]. Серед задач, які викону- ються у процесі інтерпретації знань, можна виділити задачі аналізу та породження предме- тних значень понять. Аналіз зводиться до доведення простого категоричного висловлення, предикат якого – поняття бази знань, а суб’єкт – дані із вхідного масиву. Логічний резуль- тат виконання задачі аналізу – істина або хибність. Задача породження є оберненою до за- дачі аналізу і зводиться до запису у вихідний масив значення суб’єкта, який отримано вна- слідок доведення останнього судження, предикат якого – відповідне поняття. Логічний ре- зультат виконання операції породження – завжди істина. Знання у базі знань задають статичну форму знань. Головний її компонент – інфор- маційна структура P , яка є системою правил виводу загального судження. Даний статич- ний компонент доповнюється динамічним компонентом (процедурою інтерпретації), яка розкриває зміст інформаційної структури та використовує її в процесі виводу судження. 4. Проведення емпіричного дослідження швидкодії системи обробки знань У процесі експериментального дослідження враховано такі фактори: 1) Як показник оцінки швидкодії слід обрати величину, що характеризує інтервал часу між початком запуску роботи інтерпретатора до моменту переходу його у стан очіку- вання нового завдання. 2) У процесі проведення емпіричного дослідження виконується порівняння ефекти- вності процесів інтерпретації на реалізованому апаратно інтерпретаторі баз знань (АІБЗ) та на реалізованому програмно інтерпретаторі баз знань (ПІБЗ). АІБЗ реалізовано на макетній платі M1AGL-DEV-KIT-SCS. ПІБЗ скомпільовано в середовищі Microsoft Visual Studio 2010 із застосуванням бібліотеки Boost/Spirit [10] та реалізовано у вигляді ПІБЗ2 та ПІБЗ4. ПІБЗ2 функціонує на базі персонального комп’ютера з такими характеристиками: опера- ційна система – MS Windows XP Professional 32-bit SP3; універсальний процесор – Intel Mobile Core 2 Duo T8100 2.10 ГГц; кількість процесорних ядер – 2; розмір оперативної пам’яті – 2 Гб. ПІБЗ4 функціонує на базі персонального комп’ютера з такими характерис- тиками: операційна система – Windows Server 2008 R2 Standard SP 1; універсальний проце- сор – Intel Xeon CPU E5504 2.00 ГГц; кількість процесорних ядер – 4; розмір оперативної пам’яті – 12 Гб. 3) Вимірювання часу виконання поставленого завдання у секундах не цілком корек- тне, оскільки центральні процесори АІБЗ та ПІБЗ виготовлені за різними технологіями і використовують різні тактові частоти (16 МГц – АІБЗ; 2.1 ГГц – ПІБЗ). Найбільш корект- 46 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 ний результат порівняння може бути отриманий лише при однакових тактових частотах обох процесорів. Для того, щоб позбутись впливу технологічних особливостей реалізації, доцільно порівнювати не абсолютний час виконання (в секундах), а число тактових імпу- льсів процесора, витрачених на виконання процесу інтерпретації. 4) Найбільш точна оцінка вимірювання тривалості виконання процесу інтерпретації для ПІБЗ досягається зчитуванням даних із процесорного регістра RDTSC – 64-розрядного лічильника тактів процесора. Цей метод вимірювання тривалості виконання деякої функції є найточнішим. Основною перевагою даного методу є те, що постійна зміна тактової час- тоти процесора (для економії енергоспоживання) не впливає на точність вимірювання. 5) При вимірюванні числа процесорних тактів ПІБЗ виникає ускладнення, пов’язане з тим, що сучасні обчислювальні системи є багатозадачними, тому весь процесорний час розподіляється між різними процесами. Це призводить до того, що може бути різною три- валість виконання одного й того ж завдання ПІБЗ на різних часових інтервалах. Щоб поз- бутись цього недоліку, тривалість виконання кожного процесу інтерпретації вимірюється декілька разів, із розподілом у часі. Для отримання оцінки середньої тривалості виконання завдання обчислюються середнє значення x та стандартне відхилення s відповідно за фо- рмулами (2) та (3): ∑ = = n i ix n x 1 1 , (2) ( )∑ = − − = n i ii xx n s 11 1 , (3) де ix – i -тий результат вимірювання, n – кількість проведених експериментів, x – серед- нє арифметичне результату вимірювання, s – стандартне відхилення. 6) Найбільш точна оцінка числа процесорних тактів АІБЗ визначається за рахунок введення у нього 32-розрядного лічильника тактів процесора. Даний підхід дозволяє ви- значити тривалість виконання поставленого завдання із точністю до одного процесорного такту. 7) З метою порівняння ефективності алгоритму інтерпретації АІБЗ та ПІБЗ необхід- но визначити закон (функцію апроксимації), який описує залежність тривалості виконання поставленого завдання від складності самого завдання. Для визначення функції апрокси- мації було використано інструментальний засіб Microsoft Office Excel, що входить до складу Microsoft Office. За допомогою даного інструментального засобу та на основі да- них, отриманих у результаті проведення експерименту, визначено функцію апроксимації за чотирма законами: лінійний, логарифмічний, степеневий та експоненціальний. Для ко- жної функції апроксимації визначена величина достовірності апроксимації 2R , що розра- ховується за формулами 4–6 [11]: SST SSE R −= 12 , (4) ( )∑ = −= n i i xxSSE 1 2 , (5) n x xSST n i in i i 2 1 1 2       −     = ∑ ∑ = = . (6) ISSN 1028-9763. Математичні машини і системи, 2012, № 2 47 y = 23,993x + 2183,5 R2 = 0,9974 y = 11,622x + 1204,3 R2 = 0,9868 y = 9x + 45 R2 = 1 0 500 1000 1500 2000 2500 3000 3500 5 10 15 20 25 30 35 40 Довжина вхідних даних, симв. К іл ьк іс ть т ак ті в п р о ц ес о р а ПІБЗ2 ПІБЗ4 АІБЗ ПІБЗ2 ПІБЗ4 АІБЗ Рис. 4. Дослідження швидкодії інтерпретації поняття «Regular» y = 172,32x + 4503,1 R2 = 0,9989 y = 89,584x + 2338,5 R2 = 0,9978 y = 72,807x + 258,91 R2 = 0,9953 0 2000 4000 6000 8000 10000 12000 14000 5 10 15 20 25 30 35 40 Довжина вхідних даних, симв. К іл ьк іс ть т ак ті в п р о ц ес о р а ПІБЗ2 ПІБЗ4 АІБЗ ПІБЗ2 ПІБЗ4 АІБЗ Рис. 5. Дослідження швидкодії інтерпретації поняття «Integer» Серед отриманих функцій апроксимації обираємо ту, яка має найбільшу величину достовірності апроксимації. 5. Результати емпіричного дослідження У процесі проведення експерименту було використано базу знань, що містить п’ять по- нять: Regular, Integer, RealValue, Identifier, Sentence. Базу знань було реалізовано у відпові- дності до вимог синтаксису інтерпретаторів та завантажено у ПІБЗ2, ПІБЗ4 та АІБЗ. У процесі проведення експерименту одну частину експериментальних даних було згенерова- но автоматично, іншу частину – отримано із літературних джерел. Усі отримані дані було по черзі проаналізовано на ПІБЗ2, ПІБЗ4, АІБЗ та записано у відповідні таблиці для аналі- зу. В результаті аналізу отриманих експериментальних даних встановлено, що алгоритміч- на складність алгоритму інтерпретації є лінійною. Найголовніші результати емпіричних досліджень зображено на рис. 4–8. На рис. 4 зображено результати дослідження швидкодії роботи ПІБЗ та АІБЗ при ін- терпретації поняття «Regular». Дані результати відображають залежність тривалості вико- нання інтерпретації поняття від довжини виразу, що інтерпретується. У результаті розра- хунків отримано функції апроксимацій для ПІБЗ2, ПІБЗ4 та АІБЗ, які відповідно дорівню- ють ( ) 5,2183993,23 += xxy ПІБЗ2 , ( ) 3,1204622,11 += xxy ПІБЗ4 та ( ) 459 += xxy АІБЗ . На осно- ві отриманих даних можна зробити висновок, що алгоритмічна складність задачі «Regular» є лінійною, тобто ( ) ( )nOny ПІБЗ2 = , ( ) ( )nOny ПІБЗ4 = , ( ) ( )nOny =АІБЗ . При цьому, у порівнянні з ( )xy ПІБЗ2 та ( )xy ПІБЗ4 , швидкість зростання функції ( )xyАІБЗ є най- меншою (9 < 11,622 < 23,993), що доводить ефективність реалізації АІБЗ. Середня трива- лість інтерпретації по- няття «Regular» на ПІЗ2, ПІЗ4 та АІБЗ від- повідно складає 2723,35; 1465,783 та 247,5 процесорних так- тів. Виходячи із цих даних, можна зробити висновок, що середній виграш в ефективності алгоритму роботи АІБЗ, у порівнянні із ПІБЗ2 та ПІБЗ4, при обробці поняття «Regular» відповідно складає 11,0 та 5, 92 рази. На рис. 5 зобра- жено результати дослі- дження швидкодії ро- боти ПІБЗ та АІБЗ при інтерпретації поняття 48 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 y = 203,53x + 7449,8 R2 = 0,9946 y = 90,45x + 4703 R 2 = 0,9716 y = 75,89x + 622,01 R 2 = 0,9935 0 2000 4000 6000 8000 10000 12000 2 4 6 8 10 12 14 16 18 Довжина вхідних даних, симв. К іл ьк іс ть т ак ті в п р о ц ес о р а ПІБЗ2 ПІБЗ4 АІБЗ ПІБЗ2 ПІБЗ4 АІБЗ Рис. 6. Дослідження швидкодії інтерпретації поняття «RealValue» y = 979,02x + 15631 R2 = 0,9976 y = 453,89x + 10220 R2 = 0,9939 y = 366,16x + 982,59 R2 = 0,999 0 10000 20000 30000 40000 50000 60000 5 10 15 20 25 30 35 40 Довжина вхідних даних, симв. К іл ьк іс т ь та к т ів п р о ц ес о р а ПІБЗ2 ПІБЗ4 АІБЗ ПІБЗ2 ПІБЗ4 АІБЗ Рис. 7. Дослідження швидкодії інтерпретації поняття «Identifier» «Integer». Дані результати відображають залежність тривалості виконання інтерпретації поняття від довжини виразу, що інтерпретується. У результаті розрахунків отримано фун- кції апроксимацій для ПІБЗ2, ПІБЗ4 та АІБЗ, які відповідно дорівнюють ( ) 1,450332,172 += xxy ПІБЗ2 , ( ) 5,2338584,89 += xxy ПІБЗ4 та ( ) 91,258807,72 += xxy АІБЗ . Із отриманих даних слідує, що алгоритмічна складність задачі «Integer» є лінійною, тобто ( ) ( )nOny ПІБЗ2 = , ( ) ( )nOny ПІБЗ4 = , ( ) ( )nOny АІБЗ = . При цьому, у порівнянні із ( )xy ПІБЗ2 та ( )xy ПІБЗ4 , швидкість зростан- ня функції ( )xy АІБЗ є най- меншою (72,807 < 89,584 < 172,32), що доводить ефек- тивність реалізації АІБЗ. Се- редня тривалість інтерпрета- ції поняття «Integer» на ПІЗ2, ПІЗ4 та АІБЗ відповід- но складає 8380,242; 4354,167 та 1897,075 проце- сорних тактів. Виходячи із цих даних, можна зробити висновок, що середній ви- граш в ефективності алгори- тму роботи АІБЗ, у порів- нянні із ПІБЗ2 та ПІБЗ4, при обробці поняття «Integer» відповідно складає 4,42 та 2,3 рази. На рис. 6 зображено результати дослідження швидкодії роботи ПІБЗ та АІБЗ при інтерпретації по- няття «RealValue». Дані ре- зультати відображають за- лежність тривалості вико- нання інтерпретації поняття від довжини виразу, що ін- терпретується. У результаті розрахунків отримано функції апроксимацій для ПІБЗ2, ПІБЗ4 та АІБЗ, які відповідно до- рівнюють ( ) 8,744953,203 += xxy ПІБЗ2 , ( ) 470345,90 += xxy ПІБЗ4 та ( ) 01,62289,75 += xxy АІБЗ . На основі отриманих даних можна зробити висновок, що алго- ритмічна складність задачі «RealValue» є лінійною, тобто ( ) ( )nOny ПІБЗ2 = , ( ) ( )nOny ПІБЗ4 = , ( ) ( )nOny АІБЗ = . При цьому, у порівнянні із ( )xy ПІБЗ2 та ( )xy ПІБЗ4 , швидкість зростання фун- кції ( )xy АІБЗ є найменшою (75,89 < 90,45 < 203,53), що доводить ефективність реалізації АІБЗ. Середня тривалість інтерпретації поняття «RealValue» на ПІЗ2, ПІЗ4 та АІЗ відпові- дно складає 9485,119; 5607,541 та 1380,911 процесорних тактів. Виходячи із цих даних, можна зробити висновок, що середній виграш в ефективності алгоритму роботи АІБЗ, у порівнянні із ПІБЗ2 та ПІБЗ4, при обробці поняття «RealValue» відповідно складає 6,87 та 4,06 рази. На рис. 7 зображено результати дослідження швидкодії роботи ПІБЗ та АІБЗ при ін- терпретації поняття «Identifier». Дані результати відображають залежність тривалості ви- ISSN 1028-9763. Математичні машини і системи, 2012, № 2 49 0 5000 10000 15000 20000 25000 30000 35000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Номер речення К іл ьк іс ть т ак т ів п р о ц е со р а ПІБЗ2 ПІБЗ4 АІБЗ Рис. 8. Дослідження швидкодії інтерпретації поняття «Sentence» конання інтерпретації поняття від довжини виразу, що інтерпретується. У результаті роз- рахунків отримано функції апроксимацій для ПІБЗ2, ПІБЗ4 та АІБЗ, які відповідно дорів- нюють ( ) 1563102,979 += xxy ПІБЗ2 , ( ) 1022089,453 += xxy ПІБЗ4 та ( ) 59,98216,366 += xxy АІБЗ . На основі отриманих даних можна зробити висновок, що алгоритмічна складність задачі «Identifier» є лінійною, тобто ( ) ( )nOny ПІБЗ2 = , ( ) ( )nOny ПІБЗ4 = , ( ) ( )nOny АІБЗ = . При цьому, у порівнянні із ( )xy ПІБЗ2 та ( )xy ПІБЗ4 , швидкість зростання функції ( )xyАІБЗ є найменшою (366,16 < 453,89 < 979,02), що доводить ефективність реалізації АІБЗ. Середня тривалість інтерпретації поняття «Identifier» на ПІЗ2, ПІЗ4 та АІЗ відповідно складає 37658,775; 20483,15 та 9221,15 процесорних тактів. Виходячи із цих даних, можна зробити висновок, що середній виграш в ефективності алгоритму роботи АІБЗ, у порівнянні із ПІБЗ2 та ПІБЗ4, при обробці поняття «Identifier» відповідно складає 4,08 та 2,22 рази. На рис. 8 зображено результати дослідження швидкодії роботи ПІБЗ та АІБЗ при ін- терпретації поняття «Sentence». Середня тривалість інтерпрета- ції поняття «Sentence» на ПІЗ2, ПІЗ4 та АІЗ відповідно складає 27510,556; 15284,556 та 2272,2 процесорних тактів. Виходячи із цих даних, можна зробити висновок, що середній виграш в ефективності алгоритму роботи АІБЗ, у порівнянні із ПІБЗ2 та ПІБЗ4, при обробці поняття «Sentence» відповідно складає 12,11 та 6,73 рази. 6. Висновки Результати емпіричних досліджень інтерпретації знань свідчать про те, що архітектура су- часних апаратних засобів не достатньо ефективна для підтримки обробки знань. Це пов’язано із наявністю семантичного розриву між поняттями відношень та їх об’єктів у мовах (моделях) представлення знань та поняттями операцій і даних, що визначаються ар- хітектурою сучасного комп’ютера. Для підвищення продуктивності роботи сучасних систем обробки знань доцільна розробка нових архітектур апаратних засобів, більш адекватних архітектурам систем обро- бки знань. Зокрема, це стосується розробки спеціалізованих апаратних засобів, які можуть розширювати набір команд універсального процесора. Перспективність даного напряму обумовлюють сучасні технології виготовлення систем на кристалі, які дозволяють швидко та за невисоку вартість реалізувати нові архітектури й поєднати їх із існуючими система- ми. На основі отриманих емпіричних даних встановлено, що апаратні засоби інтерпре- тації знань забезпечують суттєвий виграш порівняно із програмними інтерпретаторами знань, які функціонують на базі процесорів універсальної архітектури. Середній виграш у швидкодії становить від 2,22 до 12,11 разів. СПИСОК ЛІТЕРАТУРИ 1. Knowledge-Based Intelligent Information and Engineering Systems (KES). Aim and Scope: портал [Електронний ресурс]. – Режим доступу: http://www.kesinternational.org/aim.php. 50 ISSN 1028-9763. Математичні машини і системи, 2012, № 2 2. Luger G.F. Artificial Intelligence. Structures and Strategies for Complex Problem Solving / Luger G.F.; Fifth ed. – Harlow: Copyright © Pearson Education Limited, 2005. – 903 p. 3. Рассел С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг; пер. с англ. – [2-е изд.]. – М.: Издательский дом «Вильямс», 2006. – 1408 с. 4. Кургаев А.Ф. Проблемная ориентация архитектуры компьютерных систем / Кургаев А.Ф. – Ки- ев: Сталь, 2008. – 540 с. 5. Stallings W. Computer Organization and Architecture. Designing for performance / Stallings W.; Eight ed. – New Jersey: Copyright © by Pearson Education, Inc., 2010. – 763 p. 6. Hennessy J.L. Computer Architecture. A Quantitative Approach / J.L. Hennessy, D.A. Patterson; Fourth ed. – San Francisco: Copyright © by Elsevier, Inc., 2007. – 704 р. 7. Galuzzi C. The Instruction-Set Extension Problem: A Survey / C. Galuzzi, K. Bertels // Proc. of the 4th International Workshop, (London, UK, March 26–28 2008). – London, UK, 2008. – P. 209 – 220. 8. Intel 64 and IA-32 Architectures. Software Developer’s Manual. Vol. 1: Basic Architecture [Електрон- ний ресурс]. – Режим доступу: http://www.intel.com. 9. Teodorescu H.N. Hardware Implementation of Intelligent systems / Teodorescu H.N., Jain L.C., Kandel A. – Heidelberg: Copyright © Physica-Verlag, 2010. – 282 p. 10. Boost Spirit About [Електронний ресурс]. – Режим доступу: http://boost-spirit.com/home/about-2. 11. Добавление, изменение и удаление линии тренда на диаграмме [Электронный ресурс]. – Режим доступа: http://office.microsoft.com/ru-ru/excel-help/HP010342158.aspxhttp://iproc.ru/programming/ windows-timers. Стаття надійшла до редакції 02.02.2012

Структура та дослідження швидкодії систем обробки знань

Institution

Ähnliche Einträge