Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Рис.2. Запам’ятовуюче середовище МАЕОМ
транспортування матриць. Відповідно до цього принципу матриці в машині передаються паралельно всіма елементами, але послідовно - розряд за розрядом їхнього позиційного представлення. Під час цієї передачі "сходовий зріз" квадрата регістрів (рис.3) відповідає одному і тому ж двійковому розряду представлення елементів матриці. Для запропонованої машинної технології розроблені оригінальні алгоритми обробки інформації, що ліквідують "уповільнення" обчислювального процесу за рахунок послідовної передачі інформації. Ці алгоритми досліджуються в розділі 3.
У розділі, що розглядається, наведені особливості процесорного поля МА ЕОМ. Увага приділяється апаратурній підтримці числової алгебри матриць. Зокрема, проведені дослідження апаратурної реалізації операції множення матриць. Для цього використовується модель "куба" множення матриць, що представлена на рис.4. На бічні грані цього куба, (відповідно до стрілок), подаються вихідні машинні матриці А і В. На перетині каналів передачі цих матриць (всередині куба), розташованих перпендикулярно зазначеним граням, містяться пристрої множення, кількість яких дорівнює m. Ті перетини (пристрої множення), що проектуються в одну крапку грані С, об’єднуються суматором m добутків (скалярний добуток векторів). Сукупність таких сум на верхній грані і є матриця-добуток.
Окрім процесора, що реалізує операції числової алгебри матриць, у процесорному полі передбачаються також реалізація операції над нечисловими матрицями (алгебри булєвих матриць).
У даному розділі досліджуються машинні операції МА ЕОМ. Серед них: операції числових алгебр (алгебр дійсних і комплексних чисел, кватерніонів); операції з поліномами, рядами Фур'є, числовими матрицями, матрицями Буля, функціями, векторами алгебри евклідова простору. У машинному наборі, як машинні операції, виступають також великі процедури сучасних машин, такі як розв’язок системи лінійних алгебраїчних рівнянь (два способи) і розкладання функції в ряд Фур'є.
Відповідно до концепції мовного забезпечення МА ЕОМ розглядаються чотири рівня внутрішньої мови машини. Самий нижній рівень реалізує операції числової і булєвої алгебр матриць. Ці операції є основою мови мікропрограмування. Наступний (другий) рівень використовує, як операції, команди мікропрограмної мови, а також машинні операції, представлені мікропрограмами. Асемблером МА ЕОМ є символьний запис машинної мови другого рівня. Набір його операцій розширений за рахунок введення операцій алгебр, "еквівалентних" матричним (відповідно до теореми Келі). До них належать операції над дійсними і комплексними числами, кватерніонами, поліномами, рядами Фур'є, булєвими матрицями. Четвертий рівень внутрішньої мови машини призначений для вирішення задач системного програмного забезпечення. Як основа його використовується вищезазначений асемблер.
У розглянутій технології обробки інформації як машинна
використовується мова високого рівня. Для її підтримки в машині слугує
принцип, відповідно до якого реалізація машинних
Рис. 3. Варіанти розміщення матриці в квадраті регістрів:
а – звичайний спосіб,
б – спосіб “руху матриці під кутом”.
Рис. 4. Модель куба множення матриць
операцій (команд) здійснюється виключно апаратурними засобами, без використання мікропрограмування.
Підвищення продуктивності ЕОМ завжди супроводжується необхідністю вирішення проблеми забезпечення її вихідними даними. Ця ж проблема особливо актуальна для МА ЕОМ, оскільки її продуктивність перевищує продуктивність і функціональні можливості сучасних супер-ЕОМ. У даному розділі пропонується принцип забезпечення даними, коли кожен тип алгебраїчних даних має свій канал зв'язку. Інформація в каналах зв'язку структурується тільки відповідно до розмірів її матричного представлення в операндах - машинних матрицях. Кожен канал з'єднаний тільки з приписаної йому пам'яттю запам'ятовуючого середовища. Такий специфічний (автономний) для кожного типу даних (алгебраїчних даних) підхід не накладає особливих обмежень на підготовку інформації для введення її в машину. Іншими словами, підготовка даних не залежить від характеру майбутньої обробки, і може бути виконана поза машиною будь-якими відомими методами і засобами.
У цьому ж розділі дисертації пропонується концепція схеми структурної організації машини. Ця концепція відбиває основну ідею якісного стрибка в розвитку ОТ, що може бути реалізований завдяки застосуванню нової машинної технології обробки інформації, коли як машинні операнди виступають не числа (дані), а їх складні структури даних, а командами - відповідно процедури (макрооперації) сучасних машин. У блок-схемі відображені всі особливості основних принципів, запропонованих у даному розділі дисертації (рис.5) .
У третьому розділі досліджуються технологічні й алгоритмічні основи створення МА ЕОМ з використанням напівпровідникової мікроелектроніки. Сформульовано основний принцип, згідно з яким будується елементна база машини. Відповідно до цього принципу технічна реалізація запропонованої машинної технології обробки інформації, як машини нового покоління, повинна розроблятися на основі спеціального функціонально-повного набору елементів-мікросхем (НВІС). Кожен елемент цього набору для своєї роботи не повинний вимагати підтримки з боку програмних засобів.
Докладно розглядаються елементи набору, що складається з трьох мікросхем. Запропоновано оригінальне вирішення структурної організації мікросхем скалярного добутку векторів, скалярної обробки матриць і мікросхеми пам'яті. Ці напрацювання втілені в конкретних функціональних схемах, що захищені авторськими посвідченнями.
Для мікросхеми скалярного добутку векторів, що працюють у двох режимах (фіксованої коми і коми, що плаває), запропоновано принцип множення дійсних чисел, заснований на використанні способу множення, чисельний приклад якого ілюструється на рис.6.
Рис. 5. Узагальнена структурна схема МА ЕОМ: КПМ - куб перемножування матриць; БЛОМ - блок логічної
обробки матриць
1 0 1 1 0 1 1 1 0 1 0 1 1
0 1 1 0 1 0 1 0 1 1
0 0 0 0 0 0 0 0
0 1 1 0 1 1
0 0 1 1
0 0
--------------------------------------------------
0 0 1 1 0 0 0 0 0 1 0 0 1
Рис. 6. Таблиця цифр множення чисел
У ньому представлений добуток двох двійкових співмножників А = 1011011 і В=1101011, що використовує об'єднання роботи двох відомих способів множення чисел. Один з них заснований на тому, що співмножник А представляється множником, а В - множеним. Другий спосіб, навпаки, В - множник, А - множене. Реалізація першого і другого способів (самостійно) зводяться до додавання таблиці двійкових цифр (паралелограм цифр) множеного в залежності від значення відповідних цифр множника. Одночасне використання цих двох способів призводить до трансформації такої ("паралелограмної") таблиці цифр у вигляді "трикутної" таблиці (рис.6). У лівій половині цієї таблиці, від її середини, використовується перший спосіб, а в правій - другий.
Запропонований спосіб дуже технологічний, і може бути реалізований при послідовному введенні двійкових співмножників у мікросхему. Це дозволяє істотно скоротити кількість контактних площадок мікросхеми скалярного добутку векторів. Застосування розглянутого способу множення чисел відкриває реальні можливості створення ЕОМ на основі запропонованої нової технології машинної обробки інформації.
Для мікросхеми скалярної обробки матриць розроблений новий принцип сортування чисел. Відповідно до цього принципу сортування виконується розпаралелено, коли числа із масиву, що сортується, порівнюються не між собою, а незалежно один від одного із загальною для них константою. Таке вирішення процедури сортування дозволяє в МА ЕОМ створити умови для ефективного її розпаралелювання і перетворення в машинну команду.
Як третій елемент набору пропонується спеціальна мікросхема пам'яті з застосуванням "часового" способу адресації комірок. Це дозволило ефективніше використовувати площу кристала.
Зазначено, що функціональні схеми запропонованого набору мікросхем задовольняють вимогам, що визначаються рівнем сучасної мікроелектронної технології. Вони однорідні, вимагають невелику (технологічну) кількість прилеглих зв'язків, контактних площадок, рівнів металізації. Варіант функціональної схеми скалярного добутку векторів наведений на рис.7. Ця схема складається з трьох типів комірок Yi,j. У кожному типі комірки
d0. 7. ( 2)
однакові. Основну площу кристала покривають комірки з індексами, що не перевищують відповідно величини m і n. Приклад логічного машинного моделювання однієї із таких схем наведено у додатку А.
У четвертому розділі "Методи алгоритмічної та апаратурної підтримки машинних операцій" досліджуються алгоритми і схеми, що виконують машинні операції з використанням мікропрограмної мови МА ЕОМ. Для реалізації операції множення "великих" матриць, розміри яких перевищують порядок машинної матриці, пропонується, з метою спрощення, зберігати співмножники-матриці і їхній добуток відповідно до спеціального принципу, коли в запам'ятовуючому середовищі для матриць, що беруть участь у множенні, пропонується спеціальна область, яка визначається двома двійковими розрядами кодів їхніх адрес. Запропонована апаратурна підтримка дозволяє істотно скоротити непродуктивні витрати, пов’язані зі зчитуванням та записом вихідних і проміжних матричних даних під час реалізації операції множення, формуванням транспонованої матриці.
Розглядаються способи алгоритмічної підтримки адитивних операцій "великих" матриць, суми парних добутків матриць, а також дискретного перетворення Фур'є. Пропонується алгоритмічна підтримка машинної технології по реалізації (у вигляді машинних команд) таких процедур сучасних ЕОМ, як чисельне диференціювання й інтегрування функцій Це означає, що зазначені процедури сучасних ЕОМ повинні виконуватись розпаралелено і тільки апаратурними засобами. Аналіз диференціювання в сучасній обчислювальній математиці показав, що вихідна ідея похідної, яка сьогодні використовується, закладена ще засновниками диференціального числення. Вона призводить до виключно послідовних алгоритмів. Для запропонованої технології потрібен був трохи інший підхід до розуміння і реалізації цієї важливої операції обчислювальної математики. У розділі, який розглядається, для диференціювання запропонований принцип, відповідно до якого математична модель похідної знаходиться в апараті сімейства функцій i(x+), де є змінна аргументу x та приймає довільне значення з області визначення функції. Власне кажучи, розглянуте сімейство являє собою множину функцій, що збігаються з (x), але тільки зрушених щодо осі зміни змінної x на величину , яку будемо називати фазою, а сімейство функцій - фазовим. Тоді похідною в дисертації розглядається наступна межа:
,
яка збігається з похідною, визначеною класичним способом. Використовуючи цю модель похідної, пропонується виконувати алгоритм чисельного диференціювання відповідно до виразу
= A’Q,
де Q = , A' = (А –Е), і - вектори коефіцієнтів інтерполяційних багаточленів відповідно функції, що диференціюється, та її похідної , А - матриця-константа, що характеризує сітку інтерполяції.
У четвертому розділі досліджується алгоритмічна підтримка наступних машинних операцій: обернення елементів діагональної матриці, розв’язування системи лінійних алгебраїчних рівнянь порядку машинної матриці, обернення функції, обернення машинної матриці.
У п'ятому розділі досліджується матричне зображення даних у МА ЕОМ за допомогою математичного апарату регулярних матричних представлень. Основу цього апарату складає наступна теорема.
Теорема. Нехай А - алгебра з одиницею рангу n над полем К; тоді існує мономорфізм р :T Mn(K), алгебри A у повну алгебру матриць Mn(K).
Мономорфізм р алгебри А в алгебру матриць Mn(K) називається регулярним матричним представленням алгебри А. Цю теорему в літературі називають теоремою Келі.
Регулярним матричним представленням алгебри поліномів є алгебра матриць Жордана, які п'ятого порядку мають вигляд
.
Верхній рядок цієї матриці збігається з вектором коефіцієнтів полінома.
Із формулювання теореми Келі не випливає алгоритм регулярного матричного представлення конкретної алгебри. Вона тільки стверджує про його існування. Тому не для всіх алгебр, що застосовуються в обчислювальній математиці, розвинутий достатньою мірою апарат регулярних матричних представлень. У п’ятому розділі пропонується оригінальне матричне представлення алгебри рядів Фур'є. Прикладом одного з варіантів матричного зображення п'ятого порядку ряду розглянутої алгебри є матриця
.
У дисертації введений принцип матрично-алгебраїчної технології. Він використовує математичний апарат регулярних матричних представлень для завдання інформації в структурних компонентах обчислювальної машини.
У шостому розділі дисертації розглядаються особливості розв’язування задач на МА ЕОМ. Показано, що сучасне програмне забезпечення може бути використане як складова частина програмного забезпечення матрично-алгебраїчної ЕОМ. Розглянуто технологію обчислювального процесу машини в алгебрі поліномів на прикладі розв’язування системи лінійних алгебраїчних рівнянь, що описуються функціональною матрицею. Запропоновано технологію обчислювального процесу, організованого в операціях алгебри рядів Фур'є. Уперше пропонується спосіб перетворення Фур'є в операціях алгебри рядів Фур'є. Показано, що прискорення обчислень (згідно з цим способом) порівняно з відомими алгоритмами БПФ, досягається в m раз, де m - кількість коефіцієнтів рядів Фур'є, в алгебрі яких реалізується обчислювальний процес.
У цьому розділі розглядаються особливі режими розв’язування обчислювальних задач на МА ЕОМ, у яких за рахунок зміни тільки програми обчислень можна досягати: або пікової продуктивності, або підвищеної точності обчислень, або значно підняти надійність роботи машини. В останньому випадку вірогідність правильного результату можна забезпечити не за рахунок подвійних або потрійних обчислень, які широко використовуються в обчислювальній практиці, а за рахунок т кратного обчислення більш важливого для користувача, наприклад, самого старшого коефіцієнта поліноміального представлення інформації. При цьому самий молодший коефіцієнт обчислюється усього лише один раз. Іншими словами, із застосуванням матрично-адгебраїчної технології обробки інформації з'явилася можливість цілеспрямовано підходити до вирішення надійності та вірогідності проведених обчислень.
У розглянутому розділі досліджується використання операцій алгебри булєвих матриць для розв’язування практичних задач. Запропоновано варіант застосування зазначеної алгебри в матрично-алгебраїчній технології для розв’язку логічної задачі - визначення булєвої функції у вузлах інтервалу, на якому вона задана.
ВИСНОВКИ
У дисертаційній роботі поставлена і вирішена фундаментальна проблема сучасного розвитку ОТ. Її зміст полягає в усуненні протиріччя між рівнем інтеграції в мікроелектронній апаратурі (величезне зосередження обчислювальних схем на кристалі) і технологією обчислювального процесу (обробка в дрібних одиницях інформації - числах). Вирішення проблеми зводиться до заміни машинної арифметики ( основа обчислювальної
технології сучасних ЕОМ) машинною алгеброю. Зазначена алгебра дозволяє реалізувати процеси збереження, передачі й обробки інформації в
укрупнених одиницях, адекватних рівню інтеграції елементів ОТ у
мікросхемі.
Для вирішення фундаментальної проблеми в дисертації запропонована оригінальна універсальна алгоритмічна матрично-алгебраїчна система. На її базі розроблена нова технологія машинної обробки інформації, а також запропоновані загальна концепція й основні принципи організації та функціонування ЕОМ нового покоління.
Принципи, алгоритмічна й апаратурна підтримка нової технології, що захищаються в дисертації:
. Пропозиція, згідно з якою машинною мовою ЕОМ має бути мова високого рівня, у якій процедури сучасних ЕОМ використовуються як машинні команди, а машинними операндами (мінімальними одиницями інформації, з яким працює ЕОМ) запропоновані складні структури даних сучасних машин.
. Підвищення технологічності обчислювального процесу виконується за рахунок
- організації оригінальної архітектури і структури ЕОМ, що підтримує роботу двох контурів: матричного (алгебраїчного) і числового (керуючого);
- застосування єдиних апаратурних і комунікаційних напрацювань для алгебраїчної (матричної) і скалярної (числової) обробки інформації;
- структурування пам'яті машини і засобів зв'язку із середовищем користувача за типами даних, що належать різним машинним алгебрам;
- зведення обчислення добутку матриць високого порядку до рівня машинної операції.
. Ефективне використання переваги мікроелектроніки як основи елементної бази, на якій реалізується технологія, здійснюється шляхом
- організації адресації пам'яті комбінацією двох способів - "просторового" і "часового";
- застосування мінімального функціонально повного набору елементів-мікросхем, необхідного і достатнього для реалізації ЕОМ, що працює в алгебрі матриць;
- застосування способу множення дійсних чисел (складова операція множення матриць), яке дозволяє створювати пристрої, що не уступають по швидкодії існуючим аналогам, але одночасно на 1,5 порядку вимагають меншої кількості необхідних контактів у мікросхемах.
. Забезпечення високого рівня продуктивності ЕОМ досягається за рахунок
- розпаралелювання на рівні реалізації машинних операцій (використовується математичний апарат інтерполяції і розпаралелювання робочих даних обчислювального процесу до його початку (апріорі));
- транспортування машинної матриці (операнда машинної технології) паралельно всіма її елементами, але послідовно розряд за розрядом позиційного представлення;
- застосування суто апаратурного (не мікропрограмного) способу підтримки мови надвисокого рівня (самого нижнього рівня машинної мови), технічно реалізуючи алгебру матриць (структурна реалізація мови надвисокого рівня);
- використання нової організації розпаралелювання сортування, у якій порівняння виконується не між числами, взятими із вихідного масиву, а з однієї (загальної для всієї матриці чисел) константою;
- представлення даних в оптимальному вигляді для нової технології на основі математичного апарату регулярних матричних представлень.
Застосування нової машинної технології і запропоновані принципи її реалізації дозволили на сучасному етапі розвитку вирішити ряд принципово важливих проблем, що з’явились при створенні ЕОМ понадвисокої продуктивності і сьогодні набули самостійного значення. До них належать такі проблеми:
- організації зв'язку і керування обчислювальними засобами;
- розпаралелювання обчислювального процесу на рівні процедур сучасних машин;
- використання надвеликої інтеграції мікроелектронної технології для створення схем обробки ОТ;
- використання надвеликої інтеграції мікроелектронної технології для створення схем пам'яті.
Крім того, на сучасному етапі знята актуальність інших не менш важливих проблем
- узгодження частоти обробки інформації в мікросхемі і поза нею;
- контактних площадок мікросхеми;
- створення САПР мікросхем надвеликої інтеграції;
- відбраковування (верифікація) готових мікросхем надвеликої інтеграції.
Розроблена і запропонована теоретична база по створенню нової технології дозволяє
- досягти еквівалентної швидкодії в 1Тфлопс для однопроцесорного варіанта матрично-алгебраїчної машини (варіант SISD) при тактовій частоті елементів, що не перевищує 300 МГц;
- ліквідувати диспропорцію між витратами на апаратуру і програмними засобами (понад 90% вартості витрат сучасної обчислювальної системи складають витрати на програмне забезпечення).
Запропоноване вирішення фундаментальної проблеми дозволяє створити ЕОМ нового типу, для якої
- програмне забезпечення містить у собі як складову частину весь програмний продукт сучасних засобів ОТ, чим вирішується задача спадковості програмного забезпечення;
- мова користувача (зовнішня) є функціональною (не процедурною), що дозволяє відгородити ЕОМ від небажаного втручання (проблема хакерів, програмних вірусів).
Отримані результати фундаментальних досліджень мають велике
прикладне значення, оскільки сучасний розвиток мікроелектроніки дозволяє без особливих кадрових і фінансових ускладнень створити протягом двох - трьох років дослідний зразок однопроцесорної ЕОМ з використанням запропонованої матрично-алгебраїчної технології обробки інформації. Еквівалентна швидкодія такої машини сягає понад 1Тфлопс. Апаратурні витрати і надійність її належать до класу середніх машин.
Матеріал дисертації оригінальний і аналогів не має.
Основні положення дисертації викладені в таких працях:
Вишинський В.А. Електронні обчислювальні машини на основі алгебр з регулярним матричним представленням. –Рукопис.
Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.13 –обчислювальні машини, системи та мережі. –Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2004.
У дисертації вирішується фундаментальна проблема сучасного розвитку ОТ шляхом формування нових знань в області Computer science. Для цього запропонована оригінальна матрично-алгебраїчна універсальна алгоритмічна система, на якій побудована нова машинна технологія обробки інформації - машинна алгебра. Запропонована машинна математика для ЕОМ нового покоління. У такій однопроцесорній ЕОМ є можливість досягти порогу продуктивності, який оцінюється в 1Тфлопс. Програмне забезпечення нової машини має наступність стосовно програмного багажу сучасних ЕОМ.
Складність і вартість програмного забезпечення запропонованої ЕОМ істотно спрощується. Його частка на сучасному етапі розвитку значно менше витрат на апаратуру.
Ключові слова: матрично-алгебраїчна ЕОМ, регулярне матричне представлення, машинна обробка інформації, машинна алгебра.
Вышинский В.А. Электронные вычислительные машины на основе алгебр с регулярным матричным представлением. –Рукопись.
Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.13 –вычислительные машины, системы и сети. –Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2004.
В диссертационной работе исследуются проблемы современного развития ВТ. Формулируется фундаментальная проблема, разрешение которой позволяет решить четыре из восьми исследуемых в диссертации проблем, а для остальных четырех снять их актуальность. Разрешение предложенной фундаментальной проблемы позволяет ликвидировать основное противоречие в современном развитии средств ВТ, а для этого потребовалось формирование новых знаний в Computer science. В качестве таких знаний в диссертации предлагается оригинальная матрично-алгебраическая универсальная алгоритмическая система, на базе которой создана новая машинная технология обработки информации. Для предлагаемой технологии изложена концепция и основные принципы ее организации и функционирования.
Для создания эффективного метода выработки знаний, направленных на решение указанной фундаментальной проблемы, в диссертации используется оригинальная модель развития ВТ по поколениям. Впервые формулируются восемь признаков отличия (n+1)–го поколения ВМ от n–го, семь из которых - оригинальные. Согласно этим признакам в новой технологии машинной обработки информации в качестве машинных команд используются процедуры современных ЭВМ, а вместо машинных операндов соответственно их сложные структуры данных.
Для аппаратурной и алгоритмической поддержки основных принципов в диссертации предложены
- новый алгоритм умножения действительных чисел;
- оригинальный алгоритм сортировки чисел;
- новая математическая модель производной функции;
- новая организация данных в памяти ЭВМ;
- новый способ транспортировки данных в коммуникациях машины;
- нетрадиционное применение интерполирования функций для решения проблемы распараллеливания процедур современных ЭВМ;
- новый подход в применении микроэлементной базы для развития ВТ;
- использование математического аппарата регулярных матричных представлений для технологического задания данных.
Предложенная машинная технология обработки информации позволяет создать ЭВМ нового поколения, которая в однопроцессорном варианте позволяет
- достигнуть эквивалентного быстродействия в 1Тфлоп;
- создать программное обеспечение, доля которого в системе ЭВМ меньше доли аппаратурных затрат.
Программное обеспечение ЭВМ совместимо с имеющимся современным программным обеспечением. При этом новая машинная технология предполагает использование проблемно-ориентированного пользовательского языка, приближенного к естественному, который исключает несанкционированное вмешательство в программные и аппаратурные средства ЭВМ.
Ключевые слова: матрично-алгебраическая ЭВМ, регулярное матричное представление, машинная обработка информации, машинная алгебра.
Vishinsky Vitaly Andreevich. Computers on the basis of algebras with regular matrix representation . –The manuscript.
The dissertation on defence of a scientific degree of the doctor of engineering sciences on speciality 05.13.13 - computers, systems and networks. - V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2004.
In a thesis the fundamental problem of modern development computer engineering is solved by framing new knowledge in area Computer science. For this purpose the original matrix-algebraic universal algorithmic system is offered on which the new machine technology of a data processing - machine algebra is created.
In a thesis machine mathematics for the computer of a new generation is offered. In such uniprocessor computer there is a possibility to overcome a threshold of productivity up to 1ТFLOPS. The software of the new computer is acceptable for program language of modern computers.
The complexity and cost of the software of the offered computer is essentially lower. The expenditures to software of new computer are lower than its hardware.
Key words: the matrix-algebraic computer, regular matrix representation, machine processing of the information, machine algebra.