H-модель алгоритму і універсальна SH-модель обчислювача та їх використання для дослідження комп’ютерних засобів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Національний університет Львівська політехніка

УДК 621.3

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

H-модель алгоритму і універсальна SH-модель обчислювача та їх використання для дослідження комп'ютерних засобів

Хуссейн Халіл Мурад

Львів - 2007

Дисертація є рукописом

Робота виконана в Національному університеті “Львівська політехніка” Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Черкаський Микола В'ячеславович, Національний університет “Львівська політехніка”, професор кафедри “Електронні обчислювальні машини“.

Офіційні опоненти: доктор технічних наук, професор Николайчук Ярослав Миколайович, Тернопільський національний економічний університет, завідувач кафедри “Спеціалізовані комп'ютерні системи”; кандидат технічних наук, доцент Савенко Олег Станіславович, Хмельницький національний університет, декан факультету “Комп'ютерні системи та програмування”.

Провідна установа: Вінницький національний технічний університет, кафедра лазерної та оптоелектронної техніки, м. Вінниця.

Захист відбудеться “13” квітня 2007 р. о “14” год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С.Бандери, 12).

З дисертацією можна ознайомитися у бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська,1).

Автореферат розісланий “12” березня 2007 р.

Вчений секретар спеціалізованої вченої ради, доктор технічних наук, професор Бунь Р.А.

Загальна характеристика роботи

Актуальність теми. Виконані дослідження відносяться до області теорії і практики комп'ютерних алгоритмів. До останніх часів теорія абстрактних алгоритмів і архітектура комп'ютерних систем розвивалися майже паралельно. Основна причина такого становища полягає в тому, що класичні алгоритми, теорія яких була в основному створена до 80-х років минулого століття, базувалися на використанні абстрактних моделей алгоритму, які не враховують технічні засоби обчислень. Прикладами цих моделей є машина Тюрінга, нормальні алгоритми Маркова, машина Колмогорова та інші. Багато в цьому напрямку зробили також М.Вигодський, Н.Вірт, Д.Кнут, Е.Пост, В.Глушков, В.Успенський, А.Семенов, Н.Криницький А.Ахо, Дж.Хопкрофт, Дж.Ульман, а також сучасні автори М.Глибовець, Д.Макконел, Р.Седжвік, Р.Стівенс, Т.Кормен, Ч.Лейзерзон, Р.Рівест, Д.Ульман, Д.Хопкрофт, К.Штайн.

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

Використання SH-моделі алгоритму (SH - Software/Hardware), яка оперує збільшеним набором характеристик складності, змінює ситуацію. Формулювання аксіом для комп'ютерних обчислень суттєво розширює область застосування теорії алгоритмів, особливо її складової - метричної теорії. Безпосередня декларація апаратних засобів у визначенні моделі алгоритму дозволяє в процесі синтезу, аналізу і оптимізації апаратно-програмних засобів користуватися додатково апаратною, програмною та структурною характеристиками складності. В метричній теорії абстрактних алгоритмів такі характеристики відсутні. Представляє інтерес також модель алгоритму, реалізованого тільки апаратними засобами - H-модель алгоритму.

Важливе значення в теорії алгоритмів належить універсальному обчислювачу. Існує доведення теореми про можливість побудови універсальної машини Тюрінга, яка дозволяє розв'язувати будь-яку обчислювальну задачу. По суті вона є набором програм машин Тюрінга, закодованих і записаних на одну стрічку разом з конфігурацією даних. Вона “громіздка”, практично не може бути використана для будь-яких реальних обчислень.

Разом з тим, потреба в моделях подібного типу, але здатних досліджувати сучасні комп'ютери, досить висока. Цей напрямок знайшов розвиток в роботах Ю.Капітонової, О.Летичевського, Г.Луцького, М.Черкаського.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до наукового напрямку кафедри “Електронні обчислювальні машини“ Національного університету “Львівська політехніка” “Питання теорії, проектування та реалізації комп'ютерних систем та мереж, а також математичних засобів, приладів і пристроїв, вимірювальних, інформаційних та керуючих систем”, а саме “Розробка питань теорії складності комп'ютерних засобів”. Результати дисертаційної роботи застосовані при проектуванні спеціалізованого обчислювача за темою г/д 6934/02.

Мета і задачі дослідження. Метою дисертаційної роботи є створення моделі апаратного алгоритму та моделі апаратно-програмного універсального обчислювача на основі апаратно-програмної моделі (SH-моделі).

Для досягнення мети в роботі необхідно розв'язати наступні задачі:

провести дослідження сучасного стану теорії складності абстрактних і комп'ютерних алгоритмів;

провести дослідження властивості “масовість” алгоритму, що виконується апаратними і апаратно-програмними засобами;

розробити структуру H-моделі алгоритму;

дослідити взаємозалежність характеристик складності H-моделі алгоритму;

розробити структуру універсальної SH-моделі обчислювача;

дослідити взаємозалежність характеристик складності універсальної SH-моделі обчислювача;

розробити спосіб оптимізації характеристик складності універсальної SH-моделі процесора.

Об'єкт дослідження - H-модель алгоритму та універсальна SH-модель обчислювача.

Предмет дослідження - властивості та характеристики складності апаратно-програмних комп'ютерних засобів.

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

Наукова новизна отриманих результатів. На основі проведених досліджень розв'язано наукову задачу створення нових апаратно-програмних моделей алгоритму та універсального обчислювача. При цьому отримано такі основні наукові результати, які виносяться на захист:

Вперше:

запропоновано та обґрунтовано H-модель алгоритму, що має властивість реконфігурації напрямів передачі даних в моделі без зміни апаратної і структурної складності і забезпечує оптимізацію характеристик складності перетворення, передачі і зберігання даних;

досліджено універсальну SH-модель обчислювача, яка передбачає розв'язування класу всіх обчислюваних функцій із поліноміальною часовою складністю і дозволяє проводити оптимізацію технічних та інформаційних характеристик складності обчислень.

Набули подальшого розвитку:

зближення теорії складності апаратно-програмних засобів і архітектурних способів оптимізації комп'ютерних побудов;

методологія оцінки характеристик складності апаратно-програмних засобів на всіх ієрархічних рівнях представлення комп'ютерних засобів;

розширення спроможності використання теорії складності в процесі розробки операційних пристроїв, процесорів і систем.

Практичне значення отриманих результатів. На основі розроблені способи оптимізації характеристик складності операційних пристроїв та процесорів. Результати досліджень впроваджено в навчальний процес кафедри “Електронні обчислювальні машини” національного університету “Львівська політехніка” в лекційному курсі “Дослідження та проектування комп'ютерних систем та мереж” та застосовані при проектуванні спеціалізованого обчислювача для апаратури обробки сигналів.

Особистий внесок здобувача. Всі основні результати досліджень, які представлені до захисту, одержані автором особисто. У працях, опублікованих у співавторстві, автору дисертації належать: [1, 3, 9] - уточнення поняття функції, що виконується елементарним перетворювачем, дослідження принципів оптимізації універсальної SH-моделі обчислювача; [2] - порівняння складності двох схем пристроїв управління; [5, 8] - дослідження взаємозалежності характеристик складності трьох моделей пристроїв множення; [6] - доведення можливості використання SH-моделі для аналізу систем масового обслуговування; [7] - формулювання вимог до характеристик складності процесорів. В одноосібній статті [4] запропоновано модель апаратно реалізованих комп'ютерних засобів (H-модель), дано розширене поняття властивості масовості комп'ютерних алгоритмів.

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідались та обговорювались на наступних наукових міжнародних конференціях та симпозіумах: Міжнародна конференція “Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії” (Львів - Славсько, 24-28 лютого, 2004), 8-а Міжнародна науково-технічна конференція “Досвід розробки та застосування САПР в мiкроелектронiцi” (,Львів-Поляна, 23-26 лютого, 2005), Третій ІЕЕЕ Симпозіум “Інтелектуальний збір даних і сучасні комп'ютерні системи: технологія і використання” (м. Софія, Болгарія, 5-7 вересня, 2005), 2-а Міжнародна науково-технічній конференція “Сучасні комп'ютерні системи та мережі: розробка та використання” (Львів, 21-23 вересня, 2005), Міжнародна конференція “Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії” (Львів - Славсько, 28 лютого-4 березня, 2006).

Публікації. За результатами виконаних досліджень опубліковано 9 друкованих праць, з них 5 статей у фахових наукових виданнях, які входять до переліку, затвердженого ВАК України, 4 праці - в матеріалах міжнародних науково-технічних конференцій.

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, списку використаних джерел і трьох додатків. Загальний об'єм роботи 119 сторінок. Основний зміст викладений на 106 сторінках. Робота містить 44 рисунки та 8 таблиць. Список використаних джерел складається з 67 найменувань. Додатки на 2-х сторінках.

Основний зміст роботи

У вступі наведено загальну характеристику роботи, обґрунтовано її актуальність, показано зв'язок з науковими програмами, сформульовано мету та задачі дослідження, окреслено наукову новизну і практичне значення отриманих результатів. Наведено дані про впровадження та апробацію результатів роботи.

У першому розділі проведений аналіз сучасного стану теорії алгоритмів, її практичного використання. Алгоритм - це фундаментальне поняття математики, його не можна математично точно визначити за допомогою інших фундаментальних понять. Його інтуїтивне тлумачення наступне: “Алгоритм - це точний припис, який задає обчислювальний процес, що починається з деякого початкового даного і спрямований на одержання результату, який повністю відповідає цим початковим даним”. Це формулювання не є математичним об'єктом. Воно не може бути основою для дослідження математичних і комп'ютерних проблем. Тому дослідження алгоритмів проводять за допомогою моделей, надаючи їм точного математичного змісту. Прикладом моделі алгоритму є машина Тюрінга.

Машина Тюрінга є формальною алгоритмічною системою (ФАС) з абстрактним обчислювачем. Абстрактний обчислювач не враховує технічні засоби виконання обчислювальних операцій. Ця особливість не дозволяє повністю перенести результати досліджень математичних моделей на практику досліджень апаратно-програмних комп'ютерних засобів. Для опису властивостей параметрів та характеристик алгоритму оберемо абстрактну модель алгоритму - машину Тюрінга.

Машина Тюрінга - це шістка

,

де - кінцева множина символів зовнішнього алфавіту;

- кінцева множина символів внутрішнього алфавіту ;

- початковий і кінцевий стани, ;

- позначення порожньої комірки стрічки, ;

множини не перетинаються і не містять літер ;

- така програма, яка не може мати двох різних п'ятірок , у яких би співпадали два перші символи:

причому зсувати головку вліво, вправо, залишити на місці.

Машина Тюрінга відповідає інтуїтивному тлумаченню алгоритму. Вона має всі вісім параметрів алгоритму. Особливості роботи машини Тюрінга не суперечать властивостям алгоритму. Кроки машини Тюрінга дискретні, детерміновані і умовно елементарні, правило безпосереднього перероблення має властивість масовості. Використання машини Тюрінга дозволило сформулювати перелік характеристик складності алгоритмів і тим самим започаткувати метричну теорію складності. Фіксованість кроку машини Тюрінга дозволяє порівнювати різні алгоритми.

У формальному математичному визначенні машини Тюрінга відсутні дані про елементи її конструкції. Уявний образ цієї машини (головка читання, стрічка, засоби керування) використовується лише для пояснення принципу її роботи. Крок машини Тюрінга теж є математичною абстракцією, його не можна ототожнити з якимось елементарним процесом, що відбувається у матеріальному середовищі. Крок машини Тюрінга визначається зміною її станів без пояснень того, як це відбувається. Тому термін “елементарність кроку” точно не визначається.

Таким чином, недоліками машини Тюрінга з точки зору використання її для дослідження комп'ютерних засобів є:

· відсутність апаратної складності серед характеристик моделі;

· математична нестрогість визначення елементарності кроку алгоритму.

В процесі розробки комп'ютерних засобів потрібна модель, яка вільна від цих недоліків.

В другому розділі розглянута апаратно-програмна модель формальної алгоритмічної системи (ФАС) та на її основі словесне тлумачення алгоритму. Модель передбачає у своєму складі наявність засобів перетворення даних. Для комп'ютерного алгоритму перетворення даних здійснюється апаратно-програмними засобами. Для комп'ютерних алгоритмів справедливі наступні аксіоми:

Аксіома I Алгоритми можуть бути реалізовані апаратними засобами.

Аксіома II Алгоритми можуть бути реалізовані апаратно-програмними засобами.

Аксіома III Алгоритми не можуть бути реалізовані тільки програмними засобами.

Звідси випливає формальне визначення комп'ютерного алгоритму, що дозволяє створити таку модель алгоритму, яка враховує апаратні засоби в явній формі. Прикладом такої моделі є SH-модель алгоритму, запропонована професором М.Черкаським.

Визначення: SH-модель - це сімка

де кінцева множина символів зовнішнього алфавіту;

- кінцева множина станів SH-моделі;

- початковий і кінцевий стани, ;

- конфігурація апаратних засобів моделі:

- множина елементарних перетворювачів:;

- множина з'єднань: ;

- програма;

- пам'ять.

Поняття “елементарний перетворювач” має принципово важливе значення. Воно дозволяє уникнути нестрогості визначення властивості “елементарність”, розширити список властивостей і характеристик комп'ютерного алгоритму. Елементарний і-й перетворювач є одиницею апаратної складності: алгоритм SH-модель обчислювач процесор

.

Елементарний перетворювач перетворює деяку сукупність початкових даних в сукупність вихідних даних :

.

Часова складність перетворювача прийнята рівною одиниці :

.

Елементарний перетворювач представляється у вигляді “чорної скриньки”. Звідси випливає, що поняття “SH-модель” і “елементарний перетворювач” мають ієрархічний зміст.

Таким чином, для SH-моделі справедлива властивість ієрархічності.

Відзначимо, що абстрактні моделі обчислювачів такої властивості не мають.

Використання елементарних перетворювачів в складі моделі алгоритму робить необхідним врахування конфігурації зв'язків між ними.

SH-модель, крім відомих властивостей - дискретність, елементарність, детермінованість, масовість, має також властивість “ієрархічність”. Властивість “ієрархічність” означає, що кожний елементарний перетворювач може бути представлений SH-моделлю нижчого ієрархічного рівня, або бути елементарним перетворювачем вищого ієрархічного рівня.

Параметри SH-моделі ті самі, що й в моделях абстрактних алгоритмів.

В процесах синтезу, аналізу і оптимізації SH-моделей пропонується використовувати п'ять характеристик складності: апаратну, часову, ємнісну програмну і структурну.

Апаратна складність - кількість елементарних перетворювачів і елементів оперативної пам'яті деякого ієрархічного рівня апаратних засобів SH-моделі:

де - множина елементів схеми.

Часова складність SH-моделі визначається кількістю елементарних перетворювачів, розташованих вздовж максимального критичного шляху розповсюдження сигналу:

.

Ємнісна складність - кількість комірок пам'яті, необхідних для реалізації алгоритму.

Апаратна, часова та ємнісна складності відносяться до технічних характеристик. Крім технічних, SH-модель має інформаційні характеристики - програмну і структурну складності.

Програмна складність визначається логарифмічною мірою ступеня нерегулярності розташування сигналів керування часової діаграми SH-моделі:

, (1)

де ;

- кількість входів керування;

- кількість дискретів часу (часової діаграми);

- кількість сигналів керування -го фрагмента часової діаграми для обраного рівня ієрархії побудови апаратних засобів;

- кількість фрагментів часової діаграми, конфігурації яких не повторюються.

Структурна складність алгоритмічного пристрою - це ступінь нерегулярності матриці суміжності:

, (2)

де E - кількість елементів трикутної матриці суміжності системи;

n - кількість вершин графу.

Використовуючи класичне формулювання алгоритму, наведене у першому розділі, “алгоритм - це припис...”, та надаючи слову припис комп'ютерного змісту, одержимо наступне тлумачення: “Комп'ютерний алгоритм - це фіксована для розв'язання деякого класу задач конфігурація апаратно-програмних засобів, що задає обчислювальний процес, який починається з деякої системи початкових даних (потенційно нескінченної) і скерований на отримання результату, повністю визначеного цими початковими даними”.

Проілюструємо розрахунки характеристик складності на прикладі перемножувача на багаторозрядному суматорі, схема якого наведена на рис.1. Принцип роботи перемножувача пояснюється його функціональною схемою (рис.1, а) та часовою діаграмою (рис.1, б). Додатково зауважимо, що регістри RG2 і RG3 є регістрами зсуву, сигнали управління: C1, C2, C3 є сигналами запису даних в регістри, а C3, C5 є сигналами зсуву даних в регістрах в бік старших розрядів. Для послідовніcтної схеми часова складність визначається підрахунком кількості дискретів часу реалізації алгоритму. За часовою діаграмою вона дорівнює:

,

де l - одиниця складності часової діаграми;

n - кількість розрядів множника.

Програмна складність визначається за формулою (1), у нашому прикладі P=5log₂5/5*4 = 10.

Основою для підрахунків апаратної та структурної складності є граф схеми пристрою. За кількістю вершин апаратна складність у нашому прикладі дорівнює: А= 4. Структурна складність визначається за допомогою матриці суміжності (рис.1 г)) за формулою (2): .

Отже, SH-модель у порівнянні з моделями абстрактних алгоритмів дає суттєво більше можливостей дослідження комп'ютерних засобів:

· SH-модель, крім технічних характеристик, має дві інформаційні;

· ключову роль в SH-моделях має поняття “елементарний перетворювач”.

SH-модель не охоплює моделі алгоритмів, які реалізуються тільки апаратними засобами, та модель універсального обчислювача.

В третьому розділі сформульовано визначення і проведено дослідження апаратного алгоритму - H-моделі. Розглянуто тлумачення властивості “масовість” та його розширення в теорії складності апаратно-програмних засобів. Структура правила безпосереднього перероблення абстрактного алгоритму має дві частини - виконавчу частину та програму (рис.2). Перший блок - це уявні засоби перероблення даних. Другий блок - це програма. “Масовість” для абстрактного алгоритму означає можливість за одним алгоритмом розв'язувати множину задач одного класу, які відрізняються тільки наборами вхідних даних. Клас задач може бути змінений тільки заміною програми.

Структура правила безпосереднього перероблення SH-моделі показана на рис.3 a). Вона подібна до структури моделі абстрактного алгоритму (рис.2). Проте існують варіанти структури, які не містять програмного блоку. Назвемо їх H-моделями. Правило безпосереднього перероблення H-моделі алгоритму реалізовано апаратним способом без використання програми. Для моделей абстрактних алгоритмів такого варіанту структури не існує.

Структура H-моделі має два варіанти. Його прикладами є моделі комбінаційних пристроїв - суматори, дешифратори, матричні перемножувачі та інші. В дисертації проведений аналіз складності двох схем матричних перемножувачів.

Це комбінаційна схема, її програмна складність P=0, апаратна - А=nІ. Конфігурація зв'язків між комірками однорідна, тому структурна складність матриці S=0. Часова складність L = 3n - 2. Схема комірки наведена на рис.4 б.

Матричний перемножувач з діагональним переносом показаний на рис.5а. Тут також програмна складність P=0, апаратна - А=nІ, але пристрій побудований із використанням трьох різнотипних комірок, які показані на рис.3 b, c, d. Конфігурація зв'язків між комірками неоднорідна. Це викликає зміни структурної та часової складності. У даному випадку S=5, L = 2n - 2.

Результати аналізу характеристик складності трьох розглянутих схем перемножувачів наведені в табл.1 Першим фактором зменшення часової складності є суттєве збільшення апаратної складності: „дешева” апаратна складність в обмін на „дорогу” часову складність. Другим фактором є зменшення надлишковості шляхів розповсюдження сигналів шляхом виключення горизонтальних зв'язків в матриці з діагональним переносом, крім останнього рядка. Така побудова схеми збільшує її структурну складність: відносно “недорога” структурна складність в обмін на „дорогу” часову складність.

Таблиця 1. Порівняння трьох перемножувачів за характеристиками складності

№	Перемножувач	L	A	P	S
1	Перемножувач на багаторозрядному суматорі	n(2n+1)	6n	10,57	6.32
2	Матричний перемножувач з горизонтальним переносом	3n-2	n2	0	0
3	Матричний перемножувач з діагональним переносом	2n-2	n2	0	10

Прикладом реконфігурованої H-моделі є модель комбінаційної схеми арифметико-логічного пристрою процесора.

В четвертому розділі досліджено універсальну SH-модель (USH-модель). Прототипом USH-моделі є універсальна машина Тюрінга (UMT), яка дозволяє реалізувати потенційно необмежену множину обчислювальних алгоритмів. Формально доведено теорему про існування UMT. В роботі описано метод структурного доведення існування UMT. Метод полягає у поетапній побудові однострічкової UMT з набору ізольованих машин Тюрінга. Для практичного застосування UMT не придатна, але теоретичні дослідження UMТ, які проведені фон Нейманом, дозволили сформулювати фундаментальні принципи побудови комп'ютерів: виконання обчислень за програмою, збережуваної програми, умовного переходу, двійкового кодування, ієрархії пам'яті.

Подібно до універсальної машини Тюрінга, USH-модель дозволяє реалізувати потенційно необмежену множину обчислювальних алгоритмів. Базою для синтезу USH-моделі обчислювача також є набір SH-моделей алгоритмів обчислювальних операцій. Всі SH-моделі набору об'єднуються в одну. При переході від реалізації одного алгоритму до іншого змінюється правило безпосереднього перероблення: змінюється внутрішня структура елементарних перетворювачів, переналаштовується конфігурація напрямків передачі даних між ними, забезпечується обмін даними. Всі ці зміни можуть відбуватися на початку і в процесі перетворення даних за одним алгоритмом. Всі ці операції проводяться за допомогою пристрою керування, який є невід'ємною частиною універсальної SH-моделі. Пристрій керування, подібно до UMT, зберігає мікропрограми, або має засоби генерування мікропрограм за кількістю, рівною кількості комп'ютерних алгоритмів.

Отже, універсальна SH-модель визначається об'єднанням двох SH-моделей:

,

де - функціональна SH-модель;

- SH-модель пристрою керування.

Функціональна SH-модель призначена для реалізації обчислювального процесу перетворення, передавання і зберігання даних та адрес. SH-модель пристрою керування організовує цей процес: генерує або зчитує мікропрограми (з пам'яті програми) для виконання операцій. Обидві SH-моделі об'єднуються двома потоками сигналів: від пристрою керування - потік мікрокоманд, а від функціональної частини - потік сигналів про необхідність зміни порядку виконання обчислювального процесу. На вхід SH(f) подаються вхідні дані та зовнішні команди. Останні дешифруються у SH(c) та подаються для керування обчислювальним процесом в SH(f).

Практично важливою задачею проектування USH-моделі обчислювача є оптимізація її характеристик складності.

Часова та програмна характеристики складності USH-моделі обчислювача безпосередньо зв'язані з продуктивністю обчислень комп'ютерних засобів та з продуктивністю проектування цих засобів. Часова складність в основному визначає продуктивність обчислювача, програмна складність в основному визначає час (трудомісткість) проектування.

Основними способами зменшення часової складності SH(f) моделі є: розділення трактів обробки даних, команд, адрес на підтракти; конвеєрність; паралелізм; апаратне виконання операцій; скорочення критичних шляхів розповсюдження сигналів; мінімізація пересилок; використання КЕШ пам'яті даних і команд.

Основними способами зменшення програмної складності USH моделі обчислювача є: розділення трактів обробки даних, команд, адрес на підтракти; апаратне виконання операцій; мінімізація пересилок; зменшення типів команд; зменшення форматів команд; зменшення форматів даних. Всі характеристики складності зв'язані між собою - зміна однієї обов'язково викликає зміну іншої або декількох інших. Найбільшу вартісну вагу мають часова і програмна складність. Значно меншу мають структурна, і особливо апаратна та ємнісна складності.

Оптимізацію характеристик складності виконуємо за допомогою мінімаксного методу. Суть його полягає у наступному:

· зі всього набору характеристики складності виділяються дві - часова і програмна;

· вибираються ті способи мінімізації часової складності, які збігаються із способами мінімізації програмної складності; мінімізація часової та програмної складності досягається за рахунок зростання апаратної, ємнісної та структурної характеристик складності;

· якщо є декілька способів мінімізації часової складності, які по відношенню до програмної складності є нейтральними, то вибирається спосіб, який веде до мінімального збільшення структурної складності;

· зростання апаратної і ємнісної характеристик складності, викликане зменшенням часової складності, обмежується лише розміром кристала.

Вимоги до керуючої SH(c) моделі не співпадають з вимогами до функціональної SH(f) моделі. Пристрій керування повинен мати малу часову й апаратну складність. Основними способами зменшення часової та апаратної складності SH(с) моделі є: апаратний синтез команд, зменшення типів команд, власно команд, форматів команд, форматів даних. Виконання цих умов реалізовано в процесорах з RISC архітектурою. Інший приклад - останні моделі процесорів INTEL. В них тракт обробки розділений на два підтракти. Перший закінчується транслятором CISC команд в RISC. У другому (RISC ядро) проводиться обробка даних.

Таким чином, універсальна SH-модель алгоритму складається з двох SH-моделей - функціональної частини і пристрою керування. Вимоги до SH-моделі функціональної частини не співпадають з вимогами до SH-моделі пристрою керування. Якщо для першої головним є мінімізація часової та програмної складності, то для другої - мінімізація апаратної та частково часової. В роботі зроблений аналіз характеристик складності двох способів побудови пристроїв керування: з мікропрограмним та апаратним способами керування.

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

Основні результати роботи та висновки

У дисертації сформульовано і вирішено наукову задачу побудови апаратної моделі алгоритму і універсального обчислювача на основі SH-моделі і розроблено методи синтезу, аналізу і оптимізації цих моделей за характеристиками складності.

При цьому отримані такі результати.

На основі проведеного дослідження складності обчислювальних операцій показано, що використання для цих цілей моделей абстрактних алгоритмів недостатньо, оскільки вони не враховують технічні засоби їх реалізації. Запропоновано і обґрунтовано новий підхід до визначення та дослідження властивостей і характеристик складності комп'ютерних алгоритмів на основі поняття “елементарний перетворювач”, який дозволяє надати властивості “елементарність” точний математичний зміст, визначити характеристику “апаратна складність”, визначити нову властивість алгоритму - “ієрархічність”. Запропоновано H-модель алгоритму, що передбачає реалізацію обчислень лише апаратними засобами, яка дозволяє вирішувати задачі деякої обмеженої множини класів без зміни апаратної і структурної складностей моделі. Проведено дослідження універсальної SH-моделі обчислювача, показано ефективність її застосування на прикладах оцінки характеристик складності сучасних процесорів. Сформульовано вимоги до характеристик складності двох SH-моделей процесора - функціональної і керуючої, які дозволяють оптимізувати величини зайнятих ними площ на кристалі та значення часової і програмної складностей. Сформульовано вимоги і розроблено способи мінімаксної оптимізації характеристик складності процесорів на основі критеріїв максимальної продуктивності обчислень і мінімальних витрат часу на проектування комп'ютерних засобів.

Список праць за темою дисертації

1. Черкаський М., Мурад Хусейн Халіл. Комп'ютерні алгоритмічні системи // Радіоелектроніка та телекомунікації. Вісник Національного університету “Львівська політехніка”. - Львів, 2004. - № 508. - С.274-280.

2. Черкаський М.В, Мурад Хусcейн Халіл. Складність пристрою керування. //Комп'ютерна інженерія та інформаційні технології Вісник Національного університету “Львівська політехніка”. - Львів, 2004. - № 521. - С. 3-7.

3. Черкаський М.В, Мурад Хуссейн Халіл. Універсальна SH-модель // Комп'ютерні системи та мережі: Вісник Національного університету “Львівська політехніка”. - Львів, 2004. - № 523. - С.150-154.

4. Мурад Хуcсейн Халіл. Розширення поняття масовості комп'ютерних алгоритмів // Комп'ютерні системи та мережі: Вісник Національного університету “Львівська політехніка”. - Львів, 2005. - № 546. - С. 101-105.

5. Черкаський М.В, Мурад Хуссейн Халіл. Аналіз складності пристроїв множення // Комп'ютерні системи проектування. Теорія і практика: Вісник Національного університету “Львівська політехніка” - Львів , 2005. - № 548. - С.15-21.

6. Cherkaskyy M., Mourad Houssein Khalil. System - Algorithm // Modern Problems of Radio Engineering, Telecommunications and Computer Science. Proc. of the Intern. Conf. TCSET”2004. February 24-28, 2004, Lviv - Slavsko. - Lviv: Publishing House of Lviv Polytechnic, 2004. - P. 394-395.

7. Cherkaskyy M., Mourad Houssein Khalil. Model of the Processor // The Experience of Designing and Application of CAD Systems in Microelectronics. Proc. of the YIII Intern. Conf. CADSM 2005. 23-26 February, 2005, Lviv-Polyana. - Lviv, Publishing House of Lviv Polytechnic National University, 2005. - Р. 189-191.

8. Cherkaskyy M.V., Mourad Houssein Khalil. Multiplicative devices SH-model // The Third IEEE Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications. 5-7 September, 2005, Sofia, Bulgaria. - 2005. - P. 162-166.

9. Cherkaskyy M., Mourad Houssein Khalil H-Model of the Algorithm // Modern Problems of Radio Engineering, Telecommunications and Computer Science. Proc. of the Intern. Conf. TCSET”2006. February 28 - March 4, 2006, Lviv - Slavsko. - Lviv, Publishing House of Lviv Polytechnic, 2006. - P.44-45.

Анотація

Хуссейн Халіл Мурад. H-модель алгоритму і універсальна SH-модель обчислювача та їх використання для дослідження комп'ютерних засобів. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - Обчислювальні машини, системи та мережі. - Національний університет “Львівська політехніка”, Львів, 2007.

Дисертація присвячена питанням аналізу сучасних методів дослідження складності алгоритмів та комп'ютерних обчислювачів. Показано, що використання моделей абстрактних алгоритмів в умовах бурхливого розвитку комп'ютерної техніки неефективне, оскільки вони не враховують технічних складових, таких як апаратна складність. Доведена необхідність об'єднання здобутків теорії абстрактних алгоритмів та архітектури комп'ютерів, розвитку на цій основі теорії комп'ютерних алгоритмів з використанням SH-моделі. Поняття “елементарний перетворювач” є ключовим у дослідженні властивостей й характеристик комп'ютерних алгоритмів. Воно надає властивості “елементарність” точного математичного змісту, дозволяє розширити тлумачення властивості “масовість”, визначити характеристику “апаратна складність”, ввести додаткову інформаційну характеристику “структурна складність”. На цій основі запропоновано дві нові H-моделі алгоритмів з апаратною реалізацією. Вперше запропонована універсальну SH-модель обчислювача, яка дозволяє ефективно проводити синтез, аналіз та оптимізацію процесорів з використанням технічних та інформаційних характеристик складності. Розроблені способи мінімаксної оптимізації процесорів. Наведені приклади дослідження SH- й H-моделей.

Ключові слова: абстрактний алгоритм, комп'ютерний алгоритм, технічні й інформаційні характеристики складності, універсальна машина Тюрінга, SH-модель, H-модель.

Аннотация

Хуссейн Халил Мурад. H-модель алгоритма и универсальная SH-модель вычислителя и их использование для исследования компьютерных средств. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук за специальностью 05.13.13 - Вычислительные машины, системы и сети. - Национальный университет “Львовская политехника”, Львов, 2007.

Диссертация посвящена вопросам анализа сложности алгоритмов и компьютерных вычислителей. Показано, что использование моделей абстрактных алгоритмов в условиях бурного развития компьютерной техники неэффективно, поскольку они не учитывают технических составляющих, таких как аппаратная сложность. Показана необходимость объединения достижений теории абстрактных алгоритмов и архитектуры компьютеров и развития новой теории компьютерных алгоритмов с использованием SH-модели. Понятие “элементарный преобразователь” является ключевым в исследовании свойств и характеристик компьютерного алгоритма. Оно позволяет придать свойству алгоритма “элементарность” точный математический смысл, расширить толкование свойства “массовость”, определить характеристику “аппаратная сложность”, ввести информационную характеристику “структурная сложность”. На этой основе предложена новая аппаратно реализуемая модель алгоритма (H-модель). Исследованы ее свойства. В отличие от моделей абстрактных алгоритмов H-модель не имеет программных средств. Алгоритм преобразования данных реализуется только аппаратными средствами. При этом свойство массовости трактуется двояко. Если правило непосредственной переработки H-модели остается постоянным при переходе от одной задачи к другой, то свойство массовости трактуется в традиционном смысле. Второй вариант расширенного толкования этого свойства связан с возможностью менять правило непосредственной переработки без изменения аппаратной сложности H-модели. Переход от одного алгоритма к другому возможен изменением направлений передачи данных в H-модели, но без изменения ее структуры.

Проведено сравнение SH- и H-моделей алгоритма, реализующих операцию умножения. Показано, что временная сложность H-модели в n-раз лучше, чем у SH-модели.

Проведено сравнение двух H-моделей перемножителей. Установлено, что уменьшение временной сложности достигается увеличением структурной сложности H-модели.

В диссертации исследована универсальная SH-модель (USH-модель). Прототипом USH-модели является универсальная машина Тьюринга. Как и универсальная машина Тюринга, USH-модель позволяет реализовать потенциально неограниченное множество вычислительных алгоритмов. Базой для синтеза USH-модели вычислителя также является набор SH-моделей алгоритмов вычислительных операций. Все SH-модели набора объединяются в одну. При переходе от реализации одного алгоритма к другому изменяется правило непосредственной переработки: изменяется внутренняя структура элементарных преобразователей, перенастраивается конфигурация направлений передачи данных между ними, обеспечивается обмен данными. Все эти изменения могут происходить в начале и в процессе преобразования данных по одному алгоритму. Все операции производятся при помощи устройства управления, которое является неотъемлемой частью универсальной SH-модели. Устройство управления, как и универсальная машина Тьюринга, хранит микропрограммы, или имеет средства генерирования микропрограмм в количестве, равным количеству компьютерных алгоритмов.

Важной задачей проектирования USH-модели вычислителя является оптимизация ее характеристик сложности.

Временная и программная характеристики сложности USH-модели вычислителя непосредственно связаны с производительностью вычислений компьютерных средств и с производительностью проектирования этих средств. Временная сложность в основном определяет производительность вычислителя, программная сложность в основном определяет время (трудоемкость) проектирования.

Требования к SH-модели функциональной части не совпадают с требованиями к SH-модели устройства управления. Если для первой главным является минимизация временной и программной сложности, то для второй - минимизация аппаратной и частично временной. В работе сделан анализ характеристик сложности двух способов построения устройств управления, а именно: с микропрограммным и аппаратным способами управления.

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

Ключевые слова: абстрактный алгоритм, компьютерный алгоритм, технические и информационные характеристики сложности, универсальная машина Тьюринга, H-модель, SH-модель, универсальная SH-модель.

Annotation

Houssein Khalil Mourad. H-Model of algorithm and universal SH- model of computer and their use in the research of computer devices - The manuscript.

Thesis to the competition of the scientific degree of Candidate in Technical Sciences in specialty 05.13.13 - Computers, System and Networks. - Lviv Рolytechnic National University, Lviv, 2007.

Thesis is devoted to questions of the complexity analysis of algorithms and computer calculators. It is shown, that the use of abstract algorithms models during the currently rapid development of computer technology and sciences: it is inefficient, since they do not consider technical components, such as apparatus complexity.

It is shown a need for union of all achievements of the abstract algorithms theory, computers architecture and development of the new theory of computer algorithms with the use of SH- model. T

he concept “elementary converter” is the key to study the properties and characteristics of computer algorithm. It makes it possible to give to the property of algorithm “elementariness” precise mathematical sense, expands concept of property “mass character”.

Important significance in the computer algorithms theory a collection of complexity characteristics of SH-model. This collection includes technical and informational characteristics.

The technical includes: time, apparatus and capacitive complexities, the informational includes: program and structural. Two new models of algorithm realizable by apparatus are proposed on this basis. The methods of constructing the effective apparatus algorithms are indicated.

For the first time it is proposed the universal SH-model of calculator, consisting of two SH-models. Universal SH-model makes it possible to effectively carry out synthesis, analysis and optimization of processors taking into account difference in the requirements for the characteristics of the complexity of its major parts. Min-max method is used for the optimization of processors.

The examples to study the H-model and the universal SH-model are given.

Keywords: abstract algorithm, computer algorithm, technical and informational characteristics of complexity, universal Turing machine, H-model, SH-model, universal SH-model.

Размещено на Allbest.ru