Саід Садек Абдалла

УДК 621.3

ПСЕВДО SH-МОДЕЛЬ алгоритму ТА ЇЇ ВИКОРИСТАННЯ ДЛЯ

ПОКРАЩАННЯ ХАРАКТЕРИСТИК СКЛАДНОСТІ БЛОК-СХЕМ

ПРОГРАМ ТА ПРИСТРОЇВ АСОЦІАТИВНОЇ ПАМ’ЯТІ

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

Автореферат

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

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

Львів – 2007

Дисертацією є рукопис.

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

Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор

Черкаський Микола В’ячеславович,

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

професор кафедри “Електронні обчислювальні машини“.

Офіційні опоненти: доктор технічних наук, професор

Воробель Роман Антонович

Фізико-механічний інститут ім. Г.В. Карпенка

НАН України, м.Львів,

завідувач відділу автоматизованих методів і систем

перетворення інформації;

кандидат технічних наук, доцент

Яцків Василь Васильович

Тернопільський Національний економічний університет,

доцент кафедри “Спеціалізовані комп’ютерні системи”.

Провідна установа: Вінницький національний технічний університет,

кафедра лазерної та оптоелектронної техніки,

м.Вінниця.

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

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

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

Вчений секретар спеціалізованої вченої ради,

доктор технічних наук, професор Бунь Р.А.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Дослідження апаратно-програмних моделей комп’ютерного алгоритму – SH-моделей алгоритму (SH – Software/Hardware),

відносяться до області теорії і практики комп'ютерних систем, вузлів пам’яті і програм. Теорія алгоритмів та її складова - теорія складності, є основою комп’ютерних наук. Її роль у практиці розроблення схемотехнічних рішень і програм до сих пір обмежується лише розрахунками часової складності та об’ємом обладнання. Питання про інформаційний зміст комп’ютерних засобів - апаратних і програмних розглядаються частково. Найбільш відомі у цьому плані праці А.Колмогорова, В.Глушкова, Ю.Капітонової, О.Летичевського. У цих працях питання про інформаційний зміст комп’ютерних засобів досліджуються на моделях з абстрактним обчислювачем. Кількісні інформаційні оцінки комп'ютерних алгоритмів описані М.Черкаським. Запропонована ним SH-модель алгоритму дозволяє досліджувати технічні та інформаційні характеристики складності апаратно-програмних комп’ютерних засобів. Розширення набору характеристик складності створює умови для зменшення суб’єктивного фактору процесу проектування комп'ютерних засобів.

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

Розробка та дослідження такої моделі є актуальною задачею комп’ютерної теорії і практики.

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

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

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

· побудувати і дослідити псевдо SH-модель;

· провести дослідження характеристик складності псевдо SH-моделі;

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

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

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

Предмет дослідження – характеристики складності блок–схем програм сортування та вузлів асоціативної пам’яті.

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

Наукова новизна отриманих результатів. На основі проведених досліджень розв’язана наукова задача створення псевдо SH-моделі блок–схем програм та вузлів асоціативної пам’яті. При цьому отримано такі основні наукові результати, які виносяться на захист.

Вперше:

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

· показано взаємозалежність характеристик складності різних варіантів блок-схем програм сортування, яка дозволяє вибирати найбільш ефективний варіант залежно від конкретних умов використання;

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

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

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

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

· методи оцінки характеристик складності пристроїв асоціативної пам’яті з неоднорідними комірками.

Практичне значення отриманих результатів.

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

· Проаналізовано і проведено порівняння базових алгоритмів та блок-схем програм сортування за розширеним набором характеристик складності та показано шляхи мінімізації часової складності.

· Наведено способи мінімізації часової складності вузлів асоціативної пам’яті.

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

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

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідались та обговорювались на наступних міжнародних наукових конференціях та симпозіумах: Міжнародна конференція “Сучасні проблеми радіоелектроніки, телекомунікацій, комп’ютерної інженерії” (Львів-Славсько, 2004); Восьма міжнародна науково-технічна конференція “Досвід розробки та застосування САПР в мiкроелектронiцi” (Львів-Поляна, 2005); Третій ІЕЕЕ Симпозіум “Інтелектуальний збір даних і сучасні комп’ютерні системи: технологія і використання” (м. Софія, Болгарія, 2005), Друга міжнародна науково-технічна конференція “Сучасні комп’ютерні системи та мережі: розробка та використання” (Львів, 2005).

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

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, списку використаних джерел і додатків. Загальний об’єм роботи 132 сторінки. Основний зміст викладений на 107 сторінках. Робота містить 39 рисунків, 16 таблиць. Список використаних джерел з 67 найменувань. Додатки на 12 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі наведено загальну характеристику роботи, обґрунтовано її актуальність, показано зв’язок з науковими програмами, сформульовано мету

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

У першому розділі проведено аналіз сучасного стану теорії алгоритмів, її практичного використання. Для дослідження алгоритмів потрібні моделі - формальні алгоритмічні системи (ФАС). Ці системи дозволяють моделювати обчислювальні процеси. Вони мають точний математичний зміст. Відомі декілька ФАС, які складають основу теорії алгоритмів. До них відносяться рекурсивні функції Гьоделя, машина Тюрінга, машина Поста, нормальні алгоритми Маркова, система Колмогорова, моделі алгоритмів Глушкова, Капітонової, Летичевського і ряд інших. Ці ФАС мають різні математичні визначення і “конструктивне” оформлення, але клас розв’язувальних функцій за допомогою цих моделей співпадає з класом всіх обчислювальних функцій. Цей факт складає зміст основаної гіпотези теорії алгоритмів: формальні алгоритмічні системи еквівалентні.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

причому - множина вершин блок-схеми; - множина з’єднань;

- об’єм зовнішньої пам’яті, необхідний для розв’язання задачі.

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

Таблиця 1. Особливості трьох моделей алгоритмів

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

Характеристики складності псевдо SH-моделі. Характеристики складності псевдо SH-моделі комп’ютерних алгоритмів суттєво відрізняються за змістом і кількістю. Для псевдо SH-моделі їх є чотири: часова L, об’єктна A, структурна S, ємнісна M. Програмний продукт може бути представлений у декількох формах. Найбільш поширеними формами є блок-схема програми та програма на мові високого рівня. На користь блок-схеми свідчать:

· незалежність від мови програмування;

· краще сприйняття і розуміння графічних об’єктів у порівнянні з текстовою послідовністю команд;

· наявність видимої множини зв’язків між вершинами блок-схеми;

· можливість безпосереднього переходу від блок-схеми до математичних об’єктів – графів і матриць.

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

Об’єктна складність. Псевдо SH-модель не оцінюється апаратною складністю. Замість неї використовується “об’єктна складність”. Її одиницею є вершина блок-схеми програми. Кількість вершин деякого ієрархічного рівня псевдо SH-моделі є об’єктною складністю.

Структурна складність. Структурна складність псевдо SH-моделі є ступенем нерівномірності елементів матриці суміжності, побудованої на основі блок-схема програми:

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

- кількість вершин блок-схеми програми.

В матриці можуть існувати фрагменти, що повторюються. За визначенням вони не повинні враховуватися у підрахунку структурної складності. У такому випадку , де - кількість з’єднань -го неповторюваного фрагмента матриці суміжності схеми.

Отримання значення структурної складності проводиться в чотири етапи.

1. Блок-схема програми перетворюється в граф.

2. Граф стискується за рахунок скорочення кількості послідовно з’єднаних операційних вершин.

3. Отриманий граф кодується у вигляді матриці суміжності.

4. Розраховується значення нерівномірності матриці суміжності.

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

Рис.1. Блок-схема програми (a), граф (в), стиснений граф (д)

На рис. 1 а) наведено блок-схему абстрактної програми. Об’єктна складність дорівнює кількості вершин стиснутої блок-схеми програми. Для наведеного прикладу Х = 8.

Рис.2. Матриця суміжності

Основну увагу приділимо визначенню структурної складності – основному показнику інтелектуальних витрат в процесі розробки програм. Послідовність операцій розрахунку наступна. Спочатку блок-схему перетворюємо в граф (рис.1в), потім стискаємо його (рис.1д), далі будуємо матрицю суміжності (рис.2) і на її основі розраховуємо значення структурної складності.

Стиснення проводиться заміною в графі “в” декількох послідовно з’єднаних вершин, які не мають розгалужень. Так, наприклад, вершини К1, К2 замінюються вершиною Х1 “стиснутого” графу “д”. Зміну позначень між блок-схемою та графами наведено на рис.1 б) і г).

Структурна складність для цього прикладу дорівнює:

В результаті проведених досліджень псевдо SH-моделі встановлено:

· комп’ютерна програма є складовою алгоритму;

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

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

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

Третій розділ присвячено оцінці блок-схем програм сортування.

До комп’ютерних задач, важливих з точки зору дослідження складності алгоритмів, відноситься процедура сортування завдяки наступним ознакам:

· кількість алгоритмів сортування складає декілька десятків;

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

· фундаментальні дослідження процедур сортування проведені відомими фахівцями з теорії алгоритмів;

· процедури сортування займають одне з перших місць за частотою використання;

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

Рис.3. Блок-схема програми (а), граф (б), стиснений граф (в)

сортування простим включенням

В дисертації проведено аналіз восьми блок-схем програм. В авторефераті наведено дві з них зі складностями і . Дані про часову складність взяті з монографії Н. Вірта “Алгоритми та структури даних.”

Рис.4. Матриця суміжності

Алгоритм сортування простими включеннями. Це один з простих алгоритмів. Його опис, програма, аналіз кількості операцій порівняння та пересилок наведено в монографії Н.Вірта. Дисертантом створено блок-схему програми, її граф, стиснений граф (рис.3) та матрицю суміжності (рис.4).

Об’єктна складність за блок-схемою програми дорівнює 14.

Ємнісна складність приблизно дорівнює розміру входу .

Часова складність є сумою операцій порівняння L1 та пересилки L2. L1сер. = (N2 + N – 2)/4; L2сер.= (N2 -9N -10)/4. В обох випадках Lсер. = O(N2), де Lсер. – середне значення часової складності.

Структурна складність стисненого графу за матрицею суміжності дорівнює:

Швидке сортування (рекурсивний спосіб). На рис.5 зображено блок-схему програми, її граф, стиснений граф та матрицю суміжності.

Рис.5. Блок-схема програми (а), граф(б), стиснений граф (в), матриця суміжності(г) швидкого сортування

Об’єктна складність за блок-схемою програми дорівнює 22.

Ємнісна складність приблизно дорівнює розміру входу .

Часова складність складається з операцій порівняння L1 та пересилки L2

L1сер. = ; L2 сер.= . В обох випадках Lсер. = O().

Структурна складність стиснення графу за матрицею суміжності дорівнює:

.

В таблиці 2 наведено результати аналізу восьми програм сортування. l1 - кількість необхідних порівнянь, l2 - число пересилок елементів, La – асимптотична часова складність, A- об’єктна складність, S- структурна складність

Таблиця 2.Характеристики складності восьми блок-схем програм сортування

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

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

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

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

· взаємозалежність: зменшення часової складності досягається збільшенням її структурної та об’єктної складностей;

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

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

Розглянемо дві псевдо SH-моделі пристроїв асоціативної пам’яті: матрицю пошуку за компарандом і матрицю пошуку за максимумом. Перший пристрій широко використовується в кеш – пам’яті, другий розглянемо з точки зору можливості використання для реалізації процедури сортування.

При синтезі асоціативної матриці з умовою вибірки за компарандом є збіг змісту компаранда із змістом однієї чи декількох комірок матриці. Можливо побудувати декілька варіантів матриці, що задовольняють цій умові. Розглянемо особливості синтезу двох варіантів – з зосередженою та розподіленою схемою „І”. У першому варіанті сигнал обрання комірки формується збігом сигналів всіх елементів одної комірки єдиною (зосередженою) схемою “І”, у другому варіанті обрання комірки формується збігом сигналів всіх елементів розподіленою схемою “І”. Аналіз цих варіантів асоціативних матриць проведемо на трьох ієрархічних рівнях побудови: вузлів, комірок пам’яті і вентильних схем. Пристрої на кожному з цих рівнів представляються у вигляді псевдо SH-моделей алгоритму.

Асоціативні матриці звичайно оцінюють часовою та об’єктною складностями. Об’єктна складність вимірюється кількістю елементів схеми. Часова складність дорівнює кількості елементів схеми, що розташовані вздовж максимального шляху розповсюдження сигналу. Псевдо SH-модель додатково має структурну складність. Проведемо аналіз за цими трьома характеристиками складності. Покажемо, що вони взаємозалежні.

На рис.6 показано схеми і значення характеристик складності обох варіантів асоціативних матриць пошуку за компарандом на трьох ієрархічних рівнях.

Табл.3 містить характеристики складності обох варіантів пристроїв асоціативних матриць. З таблиці видно, що внесення неоднорідності у зв’язки між елементами матриць дозволяє зменшити часову складність в ~ рази ( – розрядність слів матриці)

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

Рис.6. Псевдо SH-моделі асоціативної пам’яті з пошуком за компарандом

Таблиця 3. Характеристики складності моделей

Якщо об’єктні складності відрізняються незначно, то за часовою складністю різниця велика, в на користь першого варіанту. Це досягнуто за рахунок зростання структурної складності.

На рівні елементів значення всіх характеристик кращі у першого варіанту. Це вплив мінімізації структурної складності матриці на рівні комірок () на побудову елемента матриці.

Перший варіант кращий за часовою складністю але він потребує трасування по шарах кристалу додаткових з’єднань, що небажано (велика втрата площі кристалу, зростання паразитної ємності).

На рис.7 показано схеми і значення характеристик складності двох варіантів асоціативних матриць пошуку максимуму також на трьох ієрархічних рівнях.

Таблиця 4. Характеристики моделей

В табл.. 4 наведено характеристики складності обох варіантів пристроїв асоціативних матриць пошуку максимуму. З таблиці видно, що внесення неоднорідності у зв’язки між елементами матриць розрядних зрізів дозволяє зменшити часову складність у ( –кількість комірок матриці). Всі решту характеристик складності мають близькі значення за винятком структурної складності елементів.

Рис.7. Псевдо SH-моделі асоціативної пам’яті з пошуком максимуму

В результаті проведеного дослідження пристроїв асоціативної пам’яті встановлено наступне:

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

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

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

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

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

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

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

2. Запропоновано та обґрунтовано метод аналізу блок-схем програм та пристроїв асоціативної пам’яті за трьома характеристиками складності: часовою, об’єктною та структурною, що дозволяє обирати оптимальні технічні рішення за часом і вартістю проектування.

3. Проведено дослідження блок-схем програм сортування, показана взаємозалежність їх характеристик складності: зростання структурної та об’єктної складності супроводжується зменшенням часової складності. Отримані взаємозалежності характеристик складності восьми найбільш поширених алгоритмів сортування дозволяють вибирати найкращий варіант для конкретного застосування.

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

5. Показано, що збільшення структурної складності комірок матриць асоціативної пам’яті пошуку за компарандом дозволяє зменшити часову складність у ~ рази ( – розрядність слів матриці).

6. Показано, що збільшення структурної складності розрядних зрізів матриць асоціативної пам’яті пошуку максимуму дозволяє зменшити часову складність у рази ( – кількість комірок матриці). Отримані взаємозалежності характеристик вузлів асоціативної пам’яті дозволяють вибрати найкращий варіант в процесі їх проектування.

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Черкаський М., Саід Садек Абдалла. Рівні складності моделей алгоритмів //Радіоелектроніка та телекомунікації. Вісник Національного університету “Львівська політехніка”. – Львів. 2004. – №508. – С.269-273.

2. Черкаський М., Саід Садек Абдалла. Псевдо SH-модель // Комп’ютерні системи проектування. Теорія і практика. Вісник Національного університету “Львівська політехніка”. – Львів, 2004. – №523. – С.145-150.

3. Саід Садек Абдалла. Характеристики складності алгоритмів знаходження найбільшого спільного дільника двох чисел // Комп’ютерні системи та мережі. Вісник Національного університету “Львівська політехніка”. – Львів, 2005. – №546. – С.131-135.

4. Черкаський М., Саід Садек Абдалла. Структурна складність асоціативної матриці пошуку за компарандом. // Комп’ютерні системи проектування. Теорія і практика. Вісник Національного університету “Львівська політехніка”. – Львів, 2005. – №548. – С.21-25.

5. Черкаський М., Саід Садек Абдалла. Складність блок-схем програм сортування // Комп’ютерні науки та інформаційні технології. Вісник Національного університету “Львівська політехніка”. – Львів, 2006. – №565. – С.224-231.

6. Cherkaskyy M., Said Sadek Abdallah. The levels of program complexity. // Modern Problems of Radio Engineering, Telecommunications and Computer Science. Proc. of the Intern. Conf. TCSET”2004. – Lviv – Slavsko, 2004. – Lviv: Publishing House of Lviv Polytechnic, 2004. – P.396-397.

7. Cherkaskyy M., Said Sadek Abdallah. Complexity of the program. // The Experience of Designing and Application of CAD Systems in Microelectronics. Proc. of the YIII Intern. Conf. CADSM-2005. – Lviv-Polyana-Lviv, 2005. – Publishing House of Lviv Polytechnic National University, 2005. – P. 461-464.

8. Cherkaskyy M.V., Said Sadek Abdallah. Associative matrix complexity levels. // The Third IEEE Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications – Sofia, Bulgaria, 2005. – P. 208-210.

9. Said Sadek Abdallah. Information content of euclidean algorithm. // Advanced Computer Systems and Networks: Design and Application. Proc. of the 2nd Intern. Conf. ACSN – 2005. – Lviv – Ukraine, 2005 –. Publishing House of National Lviv Polytechnic University, 2005. – P. 129-131.

АНОТАЦІЇ

Саід Садек Абдалла. Псевдо SH-модель алгоритму та її використання для покращання характеристик складності блок-схем програм та пристроїв асоціативної пам’яті – Рукопис.

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

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

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

Саид Садек Абдалла. Псевдо SH-модель алгоритма и ее использование для улучшения характеристик сложности блок-схем программ и узлов ассоциативной памяти. – Рукопись.

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

Работа посвящена синтезу и исследованию псевдо SH-модели и применению её для анализа программ и узлов ассоциативной памяти. Показано, что использование моделей абстрактных алгоритмов для этих целей в условиях бурного развития компьютерной техники имеет недостатки, поскольку они не учитывают информационные характеристики сложности, структурную и программную. Показаны преимущества аппаратно-программной SH-модели компьютерных алгоритмов. Псевдо SH-модель, созданная на этой основе, использована для анализа блок-схем программ сортировки и других процедур. Зафиксирована зависимость технической характеристики – временной сложности, от информационной - структурной сложности. Рассмотрено применение псевдо SH-модели для исследования узлов ассоциативной памяти на нескольких иерархических уровнях. Показаны способы улучшения технических и информационных характеристик сложности.

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

Said Sadek Abdallah. Pseudo SH-model algorithm and its use to improve the complexities characteristics of block diagram program and associative memory. - 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 Polytechnic National University, Lviv, 2007.

This Thesis is devoted to the synthesis and research of Pseudo SH-model algorithm and its use to improve the complexities characteristics of block diagram program and associative memory. It is shown that the use of models of abstract algorithms for these purposes in conditions of development of computer techniques is not effective, as they do not consider informational characteristics as structural and program complexity. The advantages of hardware-software SH-model of computer algorithms are shown.

Pseudo SH-model created on this principle is used for the analysis of block diagrams programs of sorting and other procedures. It fixes on the dependence of technical - Time complexity from informational characteristics - structural complexity. It considers the use of pseudo SH-models for research of units of associative memory at several hierarchical levels. Ways of optimization of technical and information characteristics of complexity are shown.

Keywords: abstract algorithm, computer algorithm, technical and informational characteristics of complexity, pseudo SH-model, the block diagram programs, associative memory.