Теорія "фібоначчієвих" моделей даних, методів обчислень і операційних пристроїв високої продуктивності та надійності

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

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

Теорія "фібоначчієвих" моделей даних, методів обчислень і операційних пристроїв високої продуктивності та надійності

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

обчислювальний цифровий пристрій

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

Значний внесок у розвиток теорії сучасної обчислювальної техніки зробили наукові школи В. М. Глушкова, Г. Є. Пухова, К. Г. Самофалова, О. В. Палагіна, З. Л. Рабіновича, С. О. Майорова, В. Б. Смолова, А. Д. Закревського, А. В. Каляєва, І. В. Прангішвілі, Е. В. Євреінова, І. Я. Акушського та ін.

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

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

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

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

Один із нетрадиційних підходів до представлення даних базується на використанні р-чисел Фібоначчі і чисел "золотої" р-пропорції. Прикладами практичної реалізації цього підходу є систолічний комп`ютер зі структурою поліморфної матриці, що заснована на числовому граті Фібоначчі (Ізраїль), оптичний суперкомп`ютер на основі "надгратів Фібоначчі" (США) і технічний аналіз із використанням Fibonacci-обчислень (програмна реалізація відома рядом версій програмних пакетів, остання з яких FibNodes 5.0, і апаратна реалізація в процесорі ADSP-2189M фірми Analog Devices).

Дослідження, що спрямовані на створення "фібоначчієвих" спеціалізованих процесорів, проводилися багатьма вітчизняними та закордонними авторами. Аналіз результатів цих досліджень показує, що в межах кожного напрямку дослідження проводилися із використанням свого певного апарату розв`язання поставлених задач. І як наслідок, виникає неузгодженість моделей даних і алгоритмів виконання арифметичних операцій, запропонованих одними авторами, з методами обчислень, що запропоновані іншими авторами. Відсутні також моделі і методи, що комплексно поєднують мету підвищення продуктивності з метою підвищення надійності обчислювальних пристроїв. Тобто існує недостатній математичний взаємозв`язок використовуваних моделей, що істотно ускладнює комплексні дослідження з декількох напрямків і проектування "фібоначчієвих" операційних пристроїв високої продуктивності та надійності для спеціалізованих процесорів, що орієнтовані на задачі обчислювальної математики. Крім того, відсутні імітаційні моделі, які дозволяють перевіряти правильність функціонування та визначати характеристики пристроїв на етапі їх проектування.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалася згідно з такими постановами і програмами.

1. Постанова ЦК КПРС і РМ СРСР від 16.01.85 р. Розділ програми ”Розробка інформаційних, арифметичних, логічних і схемотехнічних основ високонадійної обчислювальної техніки з використанням кодів Фібоначчі” (автор безпосередній учасник і заступник наукового керівника теми).

2. Постанова Президії Академії наук України від 14. 06. 89 р. Розділ програми “Коди і комп'ютери Фібоначчі. Новий підхід до побудови вимірювальних, обчислювальних і керуючих систем нових поколінь” (автор безпосередній учасник і науковий керівник розділу теми).

3. Наказ Мінвузу УРСР № 78 від 21.03. 91 р. Тема 55-Д-8 "Розвиток теорії чисел Фібоначчі і створення нових інформаційних, арифметичних і схемотехнічних основ самоконтролюючих і відмовостійких високонадійних обчислювальних, вимірювальних, інформаційно-реєструючих систем, систем передавання та відображення інформації" № 0193U002770 (автор безпосередній учасник і науковий керівник розділу теми).

4. Тема 52-Д-158 "Розробка нових інформаційних і алгоритмічних основ перспективних ЕОМ, орієнтованих на розв'язання задач обчислювальної математики" № 0196U007366 (автор безпосередній учасник і науковий керівник теми).

5. Тема 5801 "Розробка теорії високонадійних проблемно-орієнтованих інформаційно-обчислювальних систем" № 0101U004673 (автор безпосередній учасник і відповідальний виконавець теми).

Мета і задачі дослідження. Метою дослідження є підвищення продуктивності та надійності операційних пристроїв для спеціалізованих процесорів, орієнтованих на розв`язання задач обчислювального характеру, принципи побудови яких базуються на "фібоначчієвих" моделях даних і методах обчислень.

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

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

- розробити "фібоначчієві" моделі даних;

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

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

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

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

- розробити інженерні рекомендації щодо схемотехнічного проектування “фібоначчієвих” операційних пристроїв на основі НВІС.

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

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

Методи досліджень. Для створення основ теорії моделей математичних об'єктів використовуються положення теорії лінійних просторів і теорії множин. Розробка "фібоначчієвих" моделей даних і методів обчислень над кодованими математичними об`єктами базується на теорії кодування, теорії чисел, комбінаториці, матричному, диференційному й інтегральному численнях. Схемотехнічні основи "фібоначчієвих" операційних пристроїв створюються з використанням теорії скінченних автоматів і теорії надійності.

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

До захисту виносяться такі основні наукові результати:

- вперше створено теоретичні основи систем позиційного кодування математичних об'єктів, які є методологічним базисом, що забезпечує можливість кодувати математичні об'єкти із урахуванням певних вимог і теоретично обґрунтовувати методи виконання операцій над кодами цих об`єктів;

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

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

- вперше запропоновано методи виконання алгебричних операцій над р-кодами Фібоначчі математичних об'єктів, що забезпечують меншу складність обчислень (від 2 до 8 раз) у порівнянні з відомими методами;

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

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

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

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

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

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

- розроблені інженерні рекомендації щодо схемотехнічного проектування “фібоначчієвих” операційних пристроїв підвищеної продуктивності та надійності на основі НВІС.

З метою практичного підтвердження результатів теоретичних досліджень та напрацювання основних технічних рішень для перспективних розробок були виготовлені та пройшли випробування:

- “фібоначчієвий” арифметико-логічний пристрій із самоконтролем для оброблення паралельних кодів (дослідна партія ВІС К1801ВП1-124);

- “фібоначчієвий” алгебричний суматор для оброблення послідовних кодів, починаючи зі старших розрядів (дослідна партія ВІС на основі БМК 1515ХМ1);

- “фібоначчієвий” пристрій для множення послідовних кодів, починаючи зі старших розрядів (дослідна партія ВІС на основі БМК 1515ХМ1);

- керуючий Фібоначчі-процесор із самоконтролем;

- Фібоначчі-процесор для цифрової обробки сигналів.

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

Особистий внесок здобувача. Усі наукові результати дисертації здобувач одержав самостійно. У наукових працях, що опубліковані у співавторстві, йому належать: [13,14,19,21] - ідеї методів представлення цілих і дійсних чисел; [15,22-27] - методи виконання арифметичних операцій над р-кодами дійсних і цілих чисел, структури пристроїв; [16-18,20] - ідеї методів знаходження та виправлення помилок із допомогою різних форм р-кодів Фібоначчі; [22] - ідея методу контролю цифрових автоматів "причина-наслідок".

Апробація pезультатів дисертації. Основні положення дисертації і результати досліджень доповідалися й обговорювалися на:

- всесоюзних школах із технічної діагностики (Вінниця, 1980, 1986);

- 6-й всесоюзній школі-семінарі з обчислювальних мереж (Вінниця, 1981);

- всесоюзному семінарі “Оптимізація складних систем” (Вінниця, 1983);

- всесоюзних конференціях "Методи та мікроелектронні засоби цифрового перетворення й обробки сигналів" (Рига, 1983, 1986);

- всесоюзній науково-технічній конференції "Вимірювальні інформаційні системи" ВІС-85 (Вінниця, 1985);

- всесоюзній нараді "Конвеєрні обчислювальні системи" (Київ, 1985);

- науково-технічній конференції військового інженерного інституту ім. А.Ф. Можайського (Ленінград, 1985);

- 2-й всесоюзній конференції з актуальних проблем інформатики й обчислювальної техніки (Єреван, 1987);

- республіканській конференції "Автоматизація контролю обчислювальних пристроїв і систем" (Вінниця, 1988);

- міжнародній науково-технічній конференції, "Приладобудування -97" (Вінниця - Симеіз, 1997);

- VI - науково-технічній конференції "Вимірювальна та обчислювальна техніка в технологічних процесах" (Хмельницкий, 1999);

- міжнародній науково-технічній конференції "Фотоніка-ОДС 2000" (Вінниця, 2000)

- щорічних науково-технічних конференціях пpофесоpсько-викладацького складу Вінницького державного технічного університету (Вінниця, 1981-2003).

Публікації. Результати дисертації опубліковано у 72 працях, у тому числі 1 монографія, 22 статті, 36 авторських свідоцтв, 12 патентів США, Великобританії, Франції, ФРН, Японії, Канади та Польщі, 1 препринт.

Структура та обсяг роботи. Дисертація складається зі вступу, шести розділів, висновків, списку використаних літературних джерел у кількості 375 найменувань, 6 додатків. Повний обсяг роботи 372 сторінки, 72 рисунки, 24 таблиці та 29 сторінок додатків.

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

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

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

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

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

Одним із перспективних у цьому напрямку є підхід, що базується на використанні властивостей чисел Фібоначчі і золотої пропорції. Однак існуючий теоретичний апарат, алгоритми та структури не дозволяють проводити на достатньо високому рівні проектування та дослідження "фібоначчієвих" спеціалізованих операційних пристроїв високої продуктивності та надійності.

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

Другий розділ присвячено розробці основ теорії моделей математичних об'єктів (МО). Ключове питання побудови узагальнених моделей математичних об`єктів, що утворюють певні типи даних, це вибір основного (математичного) формалізму. Пропонується підхід, в основу якого покладено поняття багатовимірного векторного простору. Основна ідея просторового підходу до побудови моделей полягає у тому, що математичні об'єкти розглядаються як вектори певного простору. В межах цього підходу можливо будувати не тільки моделі самих об'єктів, але й моделі обчислень, реалізація яких забезпечує певні вимоги конкретних застосувань.

Вводяться у розгляд поняття адитивного, мультиплікативного, адитивно-мультиплікативного і мультиплікативно-адитивного просторів. Кожен із цих просторів визначається над кільцем V і є множиною упорядкованих сукупностей МО, що називаються векторами. Наводяться умови, які задовольняє відповідна множина.

Базис простору може бути канонічним або надмірним.

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

Якщо u - деякий адитивний простір над кільцем V і v,u₁,u₂, …,u_nu_j, то будь-який вектор v представляється у вигляді:

v=k₁ u₁ + k₂ u₂ + …+ k_n u_n,

де k₁, k₂, …, k_n - координати.

У мультиплікативному просторі E над кільцем V і з базисом e₁,e₂, …,e_n будь-який вектор E представляється у вигляді:

В адитивно-мультиплікативному просторі W над кільцем V вектор wW представляється у вигляді:

де {w_j} - дуальний базис ;

{ k_i } і - координати.

У мультиплікативно-адитивному просторі над кільцем V вектор представляється у вигляді:

де {_i} - дуальний базис;

{k_ij} і {q_j}- координати.

Дуальні базиси можуть бути адитивно або мультиплікативно канонічними (надмірними).

Фінітний простір можна визначити над одним скінченним кільцем V, загальним для усіх векторів базису, а також над множиною {V_i} підкілець, де кожне підкільце V_i відповідає одному або декільком векторам базису. Як кільце V, так і кожне з підкілець мають максимальний елемент k_max і k_imax, відповідно.

Якщо u - фінітний простір над множиною скінченних підкілець {V_i} , то його можна розбити на l підпросторів u_j таким чином, щоб u=u_j. Причому u_j u_h=0 для j h. Кожен із підпросторів u_j має усі властивості фінітного простору u над множиною скінченних підкілець {V_i} , а також свій базис. Останнє означає, що вектори, які належать до різних підпросторів, розкладаються за різними базисами. З точки зору фінітного простору u це означає, що для представлення векторів використовується змінний базис. В даному випадку кожен вектор має основні координати {k_i} у базисі {u_i} і одну додаткову координату, що вказує номер підпростору u_j, до якого належить цей вектор. Тобто упорядкований набір підпросторів {u_j} можна розглядати як своєрідний базис простору u.

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

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

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

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

S = [M, K, A, W, f, f ^-1]

де M - скінченна множина МО з однією визначальною властивістю;

K - скінченна множина кодів;

А - автоматний алфавіт;

W = {w_i} - базис автоматного простору;

f : M K - функція кодування;

f ^-1: K M- функція декодування.

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

В роботі досліджуються адитивні системи позиційного кодування з базисами у вигляді послідовностей, що задовольняють однорідному лінійному різницевому рівнянню го порядку:

w_l+p+1 + c_pw_l+p + …+ c₀w_l = 0, (1)

де c_p … c₀ - цілі числа, l= 0, 1, ... .

Множина МО однієї визначальної властивості, якими оперує людина, є простором певної розмірності. Наприклад, множина цілих чисел - це 1-вимірний простір, множина комплексних чисел - 2-вимірний простір, а множина поліномів степеня (r -1) - r-вимірний простір.

Координатами МО є дійсні числа, але на практиці вони апроксимуються раціональними числами, які, у свою чергу, можна замінити цілими числами. Тому МО з координатами, які є дійсними числами, можуть бути представлені як МО з цілочисельними координатами.

Теорема 1. Нехай базисна послідовність задовольняє рекурентному співвідношенню

,

нехай e_l - l-й елемент базису (p+1)-вимірного нескінченного простору та w_l=e_l для 0 l p і нехай a_j{0, 1, -1}, тоді будь-який математичний об'єкт (р+1)-вимірного нескінченного простору, який має цілочисельні координати, представляється у вигляді:

. (2)

Теорема 2. Нехай w_j, w_j+1,…, w_j+p - елементи змінного базису, , тоді будь-який математичний об'єкт -вимірного нескінченого простору представляється у вигляді

.

Таким чином, розглядаючи набори певних МО як постійний або змінний базиси адитивного простору можна забезпечити представлення МО різних властивостей.

У третьому розділі розробляються "фібоначчієві" моделі даних із використанням запропонованого у розд. 2 просторового підходу щодо побудови моделей математичних об`єктів.

Такі МО, як цілі, комплексні і гіперкомплексні числа, тривимірні вектори, -матриці і поліноми третього степеня запропоновано представляти у вигляді (2) з використанням базисів , елементи яких обчислюються за формулами:

w_l+p+1 =w_l+p + w_l, l= 0, 1,… (3)

w_l = w_l+p+1 - w_l+p, l=- 1, -2, … (4)

починаючи з елементів:

w₀ = w₁ =…= w_{p - 1} = 0; w_p = 1 - для цілих чисел;

- для комплексних чисел;

w₀ = 1 , w₁ = i , w₂ = j ,w₃ = k - для кватерніонів;

w₀ =1, w₁ =i, w₂ = j, w₃ = k, w₄= e, w₅= ie, w₆= je, w₇= ke - для октав;

w₀ = i, w₁ = j, w₂ = k - для тривимірних векторів;

- для 2x2-матриць;

w₀=1, w₁= x, w₂= x², w₃= x³ - для поліномів третього степеня.

Описаним представленням МО з використанням постійного базису відповідає така модель:

,

де K_p - множина розширених р-кодів Фібоначчі;

A={-1;0;1}- автоматний алфавіт;

- унарне відношення "відповідати позиційному представленню";

P(a) - унарне відношення "відповідати набору з властивістю …".

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

Характерною особливістю р-кодів, що випливає з надмірності їх базисів, є наявність множини кодів (класу еквівалентності), яка відповідає кожному МО. Виходячи з цього, автор пропонує класифікацію форм р-кодів, що наведена на рис. 1. Дослідження форм р-кодів показали, що вони мають певні властивості, які дозволяють розв'язувати задачі, що виникають під час проектування високонадійних Ф-процесорів. При цьому є можливість вибору певної форми коду залежно від характеру найімовірніших помилок. У тих випадках, коли рівень перешкод незначний і не потрібно знаходити або виправляти помилки, пропонується зменшувати надлишковість р-кодів, використовуючи для цього скорочені форми.

Аналіз побудованих "фібоначчієвих" моделей даних показує, що елементом основної множини, незалежно від типу даних, є один р-код Фібоначчі у разі постійного базису і набір із р+2 р-кодів, коли використовується змінний базис. Але моделі відрізняє предикат, що вказує на тип даних. Виходячи з цього, автоматне представлення даних повинно мати спеціальний покажчик типу даних (тег).

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

Форми представлення даних з фіксованою комою утворені постійними базисами, а форми з плаваючою комою й індексні - змінними базисами.

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

У четвертому розділі розглядаються методи обчислень над кодованими математичними об'єктами.

Операції підсумовування і віднімання p-кодів реалізуються на основі елементарних операцій, що називаються базовими мікроопераціями, і до яких належать р видів мікрооперацій згортки та розгортки, мікрооперації переміщення та поглинання.

Ідея підсумовування кодів А і В полягає у переміщенні усіх одиниць із коду А в код В. Для цього послідовно виконуються мікрооперації переміщення, згортки і розгортки.

Мінімальна кількість кроків підсумовування n-розрядних кодів дорівнює 1, а максимальна - .

Для прискорення процесу підсумовування пропонується сумістити у часі виконання усіх мікрооперацій. Але при цьому необхідно враховувати додаткові умови, щоб заборонити виконання одночасно двох мікрооперацій над одним розрядом.

Для віднімання р-кодів автор пропонує метод, ідея якого полягає у поглинанні додатних одиниць від'ємними в однойменних розрядах кодів зменшуваного і від'ємника. Для того щоб один із р-кодів поглинув другий, необхідно виконати їх перетворення шляхом розгортки. Процес віднімання закінчується, коли один із кодів стає нульовим. Як знак результату віднімання береться знак ненульового коду.

Мінімальна кількість кроків віднімання дорівнює 1, а максимальна - (2n+p+1)/(p+1).

Для прискорення процесу віднімання пропонується сумістити у часі виконання поглинань і розгорток. Максимальна кількість кроків алгоритму прискореного віднімання - (n+1)/(p+1).

Для отримання добутку чисел, що представлені у постійному базисі, необхідно виконати два множення і одне підсумовування. Перше множення зводиться до виконання n циклів: П_і=П_і-1+а_іВ_і, В_і=(В_і-1), для початкових умов П₀=0, В₀=В. Тут для формування часткових добутків використовується зсув р-коду В вліво на один розряд, що випливає з властивості послідовності ^*_Р. Результат другого множення отримується m-кратним виконанням циклу: П_і=П_і+1+а_іВ_і, В_і= ^-1 (В_і-1), для початкових умов П₀=0, В₀=В. Тут означає зсув р-коду вправо на один розряд.

Якщо для представлення А і В використовується алфавіт {0;1;-1}, то у процесі множення виконуються підсумовування, коли а_і=1 і віднімання у разі а_і=-1 .

Для множення (n+m+1)-розрядних р-кодів треба m+n кроків формування часткових добутків і m+n+1 кроків нагромаджування часткових добутків.

Ділення чисел, що представлені у постійному базисі ^*_Р , виконується у такий спосіб. Зобразивши результат ділення А на В у вигляді , можемо записати: . Звідси випливає, що цифри c_nc_n-1... c₁ можуть бути отримані шляхом послідовного розкладання числа А і остач r_i за формулою r_i-1= _р(j_i)B + r_i , де r₀=A і 0 r_i < _р(j_i - p)B.

Представляючи _р(l) в базисі ^*_Р і виконуючи додавання з урахуванням значень , дістанемо остаточний результат, тобто р-код частки в базисі ^*_Р . Для реалізації цього алгоритму треба n-1 зсувів і віднімань і в найгіршому випадку додавань.

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

Запропоновано алгоритми виконання арифметичних операцій над числами, що представлені у змінному базисі _Р . Ці алгоритми необхідні для організації обчислень над цілими числами, що лежать у широкому діапазоні. Отримані порівняльні оцінки складності запропонованих алгоритмів і відомих алгоритмів арифметики багатократної точності (АБТ) показують, що алгоритм додавання q-представлень складніше за алгоритм додавання АБТ, а алгоритми множення і ділення q-представлень значно простіше. Так для р=1, n=16 і m=8 алгоритм додавання q-зображень складніше в 53 рази, а алгоритми множення і ділення q-представлень простіше більш ніж у 10⁵ і 10⁴ разів.

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

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

Додавання (віднімання) двох векторів, комплексних і гіперкомплексних чисел, 2x2-матриць і поліномів третього степеня полягає у додаванні (відніманні) відповідних їм р-кодів.

Інші обчислення над даними математичними об'єктами описуються узагальненою формулою:

,

з якої випливає, що процес обчислень зводиться до додавання w^*_l, яким керують цифри c_l. Якщо c_l=1, то додається w^*_l до суми, яка раніше нагромаджена, а якщо c_l=0, то додається код нуля. Цей процес є аналогічним множенню двох р-кодів Фібоначчі цілих чисел. Тут значення w^*_l обчислюються за формулами (3) і (4), починаючи з певних початкових значень, а c_l - цифри відповідного операнда.

Для комплексних чисел описані правила виконання операції множення двох комплексних чисел z₁ і z₂, обчислення комплексно-спряженого числа z*=x - yi і квадрата модуля комплексного числа z²= x²+y² .

Для тривимірних векторів описані обчислення добутку вектора на скаляр , а також скалярного і векторного добутків двох векторів a₁ і a₂.

Наведено правила обчислення добутку двох кватерніонів h₁ і h₂, а також кватерніона h*=a-bi-cj-dk, спряженого з кватерніоном h*=a+bi+cj+dk і добутку двох октав O₁ і O₂.

Для 2x2-матриць наводяться правила множення матриці D на скаляр , транспонування матриці D, множення матриць D₁ і D₂, кронекерового множення матриць D₁ D₂, обчислення приєднаної матриці D⁺, det D і оберненої матриці D^-1= (1/det D)D⁺.

Для функцій, які на всьому відрізку [a,b] замінюються поліномами степеня r вигляду:

,

де ,

розглядаються додавання, віднімання та множення поліномів G₁(x) і G₂(x), множення числа на поліном G(x), обчислення похідної G'(x) і невизначеного інтеграла полінома і обчислення чисельного значення G(x) для x=N.

Оцінки складності обчислень для наведених методів показують, що ці методи вимагають від 2 до 8 раз меншу кількість операцій додавання (віднімання) і множення, ніж у відомих випадках.

У п'ятому розділі розглядаються питання побудови операційних пристроїв високої надійності, швидкодії та продуктивності, які реалізують методи та алгоритми обчислень, що описані в pозд. 4.

Сформульовано такі основні принципи побудови “фібоначчієвих” операційних пристроїв високої надійності та продуктивності:

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

- реалізація усіх обчислювальних операцій на основі базових мікрооперацій;

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

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

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

- використання послідовних і паралельних p-кодів для представлення даних.

Для розв`язання задачі апаратного контролю різних "фібоначчієвих" цифрових пристроїв запропоновано єдину модель апаратного контролю, яка інваріантна типу цифрового пристрою і його структурі. Застосування цієї моделі на початкових етапах синтезу цифрових пристроїв дозволяє найповніше врахувати особливості функціонування цифрового пристрою і, завдяки цьому, зменшити надмірність, що вводиться.

Контроль “фібоначчієвих” цифрових автоматів запропоновано здійснювати за методом “причина-наслідок”. Суть цього методу така.

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

Мікрооперації згортки й розгортки є взаємо-зворотними, тому зворотне перетворення не спеціальна контролююча операція, а основна. Наприклад, виконання згортки над комбінацією 011 (“причина”) породжує кодову комбінацію 100 (“наслідок”), яка є необхідною умовою для виконання розгортки, тобто після правильного виконання згортки обов'язково виникає умова можливості розгортки.

Узагальнена модель "фібоначчієвого" цифрового автомата з контролем (рис. 3) забезпечує єдиний підхід до побудови різних цифрових вузлів. Будь-який з вузлів міститиме інформаційний і контрольний регістри, а відміна буде полягати у побудові логічних схем “причина” і “наслідок”. Місце помилок, що знаходяться, указується з точністю до p+2 розрядів, що дає можливість ввести оцінку важливості помилок і не зупиняти процес обчислень, якщо помилка неістотна.

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

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

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

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

Аналіз алгоритмів обробки МО показує, що однією з основних операцій є формування послідовності Фібоначчі для певних початкових елементів у кожному конкретному випадку. Тому значна увага приділяється побудові пристроїв, що називаються генераторами узагальнених послідовностей Фібоначчі (ГУПФ). Рекурсивний характер обчислень принципово не дозволяє організувати одночасне обчислення декількох коли обробляються паралельні коди. Однак це обмеження знімається коли здійснюється обробка послідовних кодів, починаючи зі старших розрядів. Запропоновано структурні схеми систолічних генераторів, які можуть формувати одночасно послідовні коди (n+4p+4)/(2p+2) елементів w_i (2p+2)n/(n+4p+4) узагальнених послідовностей Фібоначчі.

Розглянуто побудову пристроїв для множення чисел, що представлені у різних базисах. До складу цих пристроїв входять ГУПФ, регістри і нагромаджувальний суматор. Для найпростішого пристрою мінімальний час множення дорівнює T^min=2(t_дод+t_зап), а максимальний - T^max=2n(t_дод+t_зап), де - час додавання; t_зап - час запису коду. Пристроєм прискореного множення операція виконується вдвічі швидше.

Однак є галузі застосування обчислювальної техніки, де треба мати не високу швидкодію, а високу продуктивність, яка досягається не стільки зменшенням часу виконання операції, скільки збільшенням кількості операцій, що виконуються одночасно. Тому запропоновано структурну схему систолічного пристрою для множення, який має систолічний ГУПФ⁺, n+1 суматорів ПСМ0,..., ПСМn послідовних кодів, регістр послідовного наближення РгА і n+1 логічних елементів І.

Множення однієї паpи опеpандів у такому пристрої продовжується (2p+3)n+4p+4 тактів, але кожні (n+4p+4) тактів видається код добутку, що еквівалентно 2t_дод паpалельних кодів. Тобто пpодуктивність систолічного пристрою для множення в (n-1)/2 pазів більше, ніж продуктивність пристрою для прискореного множення на основі ГУПФ⁺ паралельних кодів. Це досягається за рахунок збільшення апаpатних витpат в 2р²+2p+2 pазів.

Розглянуто також різні варіанти побудови пристроїв для ділення.

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

Спільність методів обчислень над р-кодами різних МО приводить до однієї структури алгебричного пристрою, що наведено на рис. 4. Розглянуто алгоритми роботи алгебричного пристрою для різних обчислень над р-кодами МО і побудову БФПЕ.

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

Розглядаються схеми резервування перепризначенням і заміщенням однотипних зв'язаних і однотипних не зв'язаних між собою структурних елементів, що самоконтролюються. Аналіз отриманих оцінок складність апаратури та ймовірності функціонально безвідмовної роботи структур показує, що ці оцінки відрізняються незначно, але резервування перепризначенням забезпечує більшу регулярність, ніж резервування заміщенням, що є важливою перевагою для реалізації структур у вигляді НВІС.

У шостому розділі розглядаються питання організації та проектування високонадійних математичних Фібоначчі-процесорів (Ф-процесорів) на основі операційних пристроїв, що розроблені в розд.5.

Математичний Ф-процесор - це цифровий пристрій, що входить до складу обчислювальної системи і виконує базові операції над кодованими МО.

Спочатку сформульовано такі принципи побудови Ф-процесорів:

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

- використання тега для зазначення типу даних;

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

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

- оперативний наскрізний контроль процесів зберігання, оброблення й передавання інформації;

- використання функціонального та кодового контролю модулів;

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

А потім розглядаються особливості їх реалізації.

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

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

- модуля системних операцій (МСО), що здійснює зв'язок із командним процесором і реалізує процеси DI і DO;

- модуля перетворення кодів (МПК), що реалізує процеси TI і TO;

- модуля обробки (МОбр), що здійснює виконання заявок (обчислення над кодованими математичними об'єктами);

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

- модуля керування (МК), що координує роботу решти модулів.

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

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

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

Можливі три варіанти набору S:

- усі - спеціалізовані елементи;

- одна частина - спеціалізовані елементи, а друга - універсальні;

- усі - універсальні елементи.

Причому до набору S можуть входити по декілька елементів типу .

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

Крім того, варіанти відрізняються потенційною відмовостійкістю. Відмова спеціалізованого структурного елемента, якщо він один, призводить до необоротної деградації структури. У разі відмови універсального структурного елемента функція може бути реалізована на іншому елементі. Для підвищення відмовостійкості структури третій варіант вимагає найменших витрат резервної апаратури.

Аналіз “фібоначчієвих” арифметичних і алгебричних пристроїв, показує, що як у другому варіанті набору S можуть бути вибрані: блоки множення (БМ) і ділення цілих чисел (БДЦЧ), генератори узагальненої послідовності Фібоначчі (ГУПФ⁺, ГУПФ^-, ГУПФ), блок формування початкових елементів, нагромаджувальний суматор, суматор-віднімач, регістри зсуву, послідовного наближення і зберігання коду. Тут БМ і БДЦЧ є спеціалізованими структурними елементами. У третьому варіанті набору S можуть бути вилучені ГУПФ⁺, ГУПФ^-, ГУПФ.

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

Розглянуто особливості побудови модуля керування у вигляді автоматів із програмованою й жорсткою логікою.

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

Показано, що контроль як даних, так і адрес у модулі оперативної пам'яті забезпечується за рахунок представлення даних у М- і ЧР-формах. При цьому є можливість забезпечення правильного функціонування пристрою пам'яті, побудованого на мікросхемах, що мають 4 або 8 розрядів даних, доти поки не трапиться відмова більше, ніж m/4 або m/8 мікросхем (m - розрядність даних).

Оскільки Ф-процесор може мати зв'язок із різноманітними пристроями (процесори, АЦП, ЦАП, канали зв'язку, пам'ять, клавіатура і т.п.), які функціонують як у звичайних двійкових кодах, так і в p-кодах Фібоначчі різних видів, то розроблено перетворювачі двійкового коду в p-коди МО і зворотне, що забезпечують обмін інформацією між двійковими і "фібоначчієвими" пристроями і мають різні характеристики швидкодії, продуктивності й апаратурних витрат. Показано, що швидкодія перетворювачів кодів досягається за рахунок збільшення ємності ПЗП кодових еквівалентів і в граничному випадку перетворювач кодів будується тільки на основі ПЗП. Однак така реалізація для великих розрядностей кодів практично неприйнятна.

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

Розроблено алгоритми імітаційного моделювання і сімейство імітаційних моделей, кожна з яких відображає різний рівень деталізації "фібоначчієвих" операційних пристроїв

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

...