автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства параллельно-рекурсивного программирования для транспортных комплексов

Київський національний університет імені Тараса Шевченка

ргв ол

На правах рукопису

ГРИЦЕНКО Дмитро Володимирович

МЕТОДИ І ЗАСОБИ ПАРАЛЕЛЬНО-РЕКУРСИВНОГО ПРОГРАМУВАННЯ ДЛЯ ТРАНСП’ЮТЕРНИХ КОМПЛЕКСІВ

0£. /?. //

~01:6ік63~— математичне та програмне забезпечення обчислювальних машин та систем

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

Київ — 1996

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

Роботу виконано в Інституті кібернетики імені В. М. Глуш-кова НАН України.

Науковий керівник: доктор фізико-математичних наук,

професор Анісімов Анатолій Васильович.

Офіційні опоненти: член-кореспондент НАН України,

доктор фіз.-мат. наук :

Ющенко Катерина Логвинівна,

кандидат фіз.-мат. наук Нікітченко Микола Степанович.

Провідна установа: Національний- технічний університет • України «Київський політехнічний

інститут».

Захист відбудеться «--------»---------------— 199 р. о ----------

год. на засіданні спеціалізованої вченої ради Д 01.01.23 при Київському національному університеті ім. Тараса Шевченка за адресою:

252127 Київ 127, проспект Академіка Глушкова, 2, корп. 6, факультет кібернетики, ауд. 40.

(Тел. (044) 266 12 58, факс 266 12 48, '

E-mail: vpsh а icchq.univ.kiev.ua).

З дисертацією можна ознайомитись у науковій бібліотеці Київського університету ім. Тараса Шевченка (Київ, вул. Во-лодимирська, 58).

Автореферат розісланий «------» —:----------------- 199 р.

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

В. П. Шевченко

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

Актуальність тем». На сучасному етапі висока продуктивність обчислювальних машин досягається новими, архітектурними рішеннями, удосконаленням їх елементно: бази, розробкою високоефективного системного програмного забезпечення, методів і алгоритмів обробки інформації. При цьому приоріггетним напрямком у цій галузі с створення паралельних ЕОМ, методів та засобів паралельних обчислень. .

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

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

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

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

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

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

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

Поставлена мета досягається розв язком таких завдань:

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

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

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

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

■ реалізація розширення мови програмування Сі новими конструкціями, які надають відповідні засоби програмного інтерфейсу для розробників;

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

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

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

Наукова новизна роботи. Наукова новизна роботи полягає у всесторонньому теоретичному дослідженні можливостей ПАРУС (ПАРУС-Параллельные Асинхронные Рекурсивно Управляемые Пространства) технології програмування, в створенні нового .конкретного розширення мови Сі для трансп’ютерних комплексів, що дістаь назву ПАРУС-Сі, за допомогою набору засобів опису динамічного і рекурсивного паралелізму. Це розширення суттєво збільшує можливості опису класів алгоритмів, що піддаються розпаралелюванню на трансп’ютерних комплексах, забезпечує створення масштабоваких, архітектурно незалежних програм, збільшує швидкість розробки паралельного програмного забезпечення для трансп’ютерних комплексів. Для демонстрації можливостей запропонованої технології розроблений та математично обгрунтований новий паралельно-рекурсивний алгоритм обчислення модулярної експоненти для надвеликих натуральних чисел, якій використовується як одна із складових частин систем захисту інформації з загальними ключами. '

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

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

Аппобпція результатів поботи. Результати роботи доповідалися та обговорювалися на 3-й міжнародній конференції з паралельних компьютерних технологій “РАСТ-95”, м.Санкт-Петербург, вересень 1995 р., на семінарах у відділі Інтелектуалізації інформаційних технологій Інституту кібернетики ім.

В.М.Глушкова НАН України та кафедри математичної информатики Київського

. і

національного Університету ім.Т.Г.ИІевченка.

робота виконувалась у рамках програм з держбюджетної' та і о; пдоговірної тематики, що велись на кафедрі Математичної інформатики Київського національного університету ім.Т.Г.Шевченка та віддилу № 465 Інтелектуалізації інформаційній технологій Інституту кібернетики ім.В.М.Ппушкова НАН України: ":

тема №2 ВИ-КУ-10-УО, розділ 08.03, програма 08; .

тема №4 “Макроме”, розділ 09.06, програма 09;

що виконувались відповідно до рішення Кабінету Міністрів України від 26 червня 1995 р. №452-007; •

тема ИП 465.03 “Розробка принципів створення систем інтелектуалізації інформаційних та робототехнічних комплексів";

тема ПСНТ КН 465.02 Шифр проекту 05.02.03./011-95 “Системи штучного інтелекту базовані на асоціативно-пошукових алгоритмах”, комплексного проекту 05.02.03/001К-95.

Публікації. По темі дисертації опубликовано 4 друковані роботи.

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

Загальний обсяг роботи - 112 сторінок, у тому числі 10 малюнків. Бібліографія - 72 найменувань.

Зміст роботи.

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

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

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

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

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

Аналізується метод макроконвейерно'і обробхи та сімейство мов МАЯК, як один іп можливих підходів до паралельного програмування для архітектур МКМД. .

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

Наводяться деякі результати досліджень, які спрямовані на розширення діапазону алгоритмів, що розпаралелюються на трансп’ютерних комплексах, та е засобами високого рівня для створення паралельних програм, таких, що скорочують час розробки програмного забезпечення. Серед них - комплекс розпаралелювачня Сі-программ для трансп’ютерних систем, розширення мови Сі Сінапс/З, система С)иіскр!ау.

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

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

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

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

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

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

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

У них були реалізовані деякі засоби вищого різня, ніж ті, кс^рі представляє мова Оккам. Ці засоби дещо вирішують проблему динамічного паралелізму, хоча існування в них деякігх обмежень значно звужує клас алгоритмів, що розв’язуються за допомогою цих методів. Система ПАРУС-Сі, що розроблюється, є новим засобом високого рівня для створення паралельного програмного забезпечення для трансп’ютерних комплексів. Воно базується на поняттях керуючого простору і інформаційному каналі. Засади ПАРУС-технології з'явились раніше, ніж перший опис мови Оккам.

Друга глава присвячена питанням створення системи динамічного паралельно-рекурсивного програмування для траисп’ют^рних комплексів, зокрема, мови програмування ПАРУС-Сі.

Роїділ 2.1 описує основні положення теорії асинхронних керуючих просторів у паралельних обчисленнях, яка с в основі ПАРУС-технології ирограммування для трансп’ютерних комплексів. ПАРУС-технологія

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

Система програмування ПАРУС надає програмні засоби, що забезпечують побудову і модифікацію КП, збереження та передачу інформації шляхом КП, навантаження КП алгоритмічними модулями. Завдяки керуючим просторам, 11 М'УС-технологія забезпечує підтримку:

В структурного паралельного програмування на основі як статичного, так і динамічного паралелізйи,

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

взаємодії не тільки синхронізацію, але й видозміну керування (на основі засобів . • . базової мови);

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

И розробки систем віртуальних ПАРУС-машин, які забезпечують можливість паралельної обробки інформації на різних рівнях деталізації;

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

У розділі 2.2 вводяться оператори ПАРУС-ядра для мови Сі, що .реалізують створення, зьищення, керування, передачу інформації та синхронізацію паралельних процесів у керуючому просгорі алгоритмів.

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

Керуючою точкою в Г1АРУС-СІ служить паралельний процес, який внчтусться на одному із вузлів комплексу, що базується на описаній

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

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

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

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

Функції обміну інформацією служать для пересилання повідом-лень різної структури і синхронізації між керуючими точками. У параметрах цих функцій звичайно вказується дескриптор точки, на яку спрямоване повідомлення, номер каналу і саме повідомлення. При цьому розробнику не обов’язково враховувати архітектурні особливості трансп’ютерної системи. Всі проблеми, пов’язані з маршрутизацією повідомлення по трансп’ютерній мережі бере на себе ядро ПАРУС. Ці функції реалізують прийом та передачу наборів даних різних типів рядків (зепсір, 2еір), цілочисельних змінних {хетір і, кеірі), змінних з плаваючою комою (хеіісір/, %еГр/), а також функції, що реалізують прийом та передачу масивів цілочисельних змінних і змінних з плаваючою комою (зеїиір іа, %е!р іа, зелф і/, getp і/)

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

У розділі 2.3 описується внутрішня структура і принципи організації системи программування ПАРУС-Сі. Розглядаються переваги кільцевої топології для релізації систем розподілення обчислень.

Система паралельного програмування, що реалізується на багатопроцесорному комплексі, повинна забезпечувати:

В використання існуючого програмного та математичного забезпечення, базових алгоритмічних моз; .

а паралельну і розподілену обробку інформації;

О ефективне завантаження і реконфігурацію системи;

И стійкість до збоїв і відмов устаткування И обробку інформації у реальному масштабі часу.

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

Для реалізації ПАРУС-системи для трансп’ютерного кільця був обраний варіант організації кільця з маркерним доступом. Основний алгоритм, який описує роботу вузлів кільцевої мережі з передачею маркера, має такий вигляд, повторювати

повторювати

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

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

. отримати (без передачі) пакет даних ; інакше

відіслати вільний маркер; кінець якщо доки система працює

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

Заголовок Хвіст [ Дані.

|нв КП ПІ П2 ПЗІП4 П5 Пб| ... „

32 біота 32 бита 1 N байт

Н2 - помер вузла

КП - код повідомлення

Ш...П6 - параметри повідомлення '

Дані - вміст повідомлення (якщо є).

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

Глава 3 присвячена аспектам практичного використання мови ПАРУС-Сі для реалізації конкретних алгоритмів паралельних обчислень.

У розділі ЗЛ досліджуються можливі підходи у використанні системи ПАРУС-Сі для побудови складних керуючій просторів паралельних процесів.

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

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

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

Зокрема, кодування за методом RSA забезпечується обчисленням односторонньою функцією RSA з потаємним ходом у = хе(тпойп), де х — додатне ціле, шо не перевищує п = pq, р і q - великі нерівні числа, такі, що ф(«)=(р-1)(^-1), е додатне ціле, що не перевищує ф(п), для якого ПОД (е,ф(н))=1. Іншими словами х -повідомлення, що шифрується, а у -зашифроване повідомлення. Відкритим ключем є числа п и е.

Для дешифрування використовується обернена функція, що має вигляд: х = yd (modn), де d - єдине ціле, менше за п, і задовольняє умови <1е = і (mod <!>(»)). Показник d, необхідний для дешифрування знаходимо за допомогою алгоритму Евклида, який обчислює НОД(е,ф(п)) . <р(я), в спою чергу, можна знайти, знаючи прості р і q, n=pq. При зикористанні в ключах надвеликих натуральних чисел знаходження потрібних простих множників з метою злому захисту є практично неможливим.

Схема логарифмічного обміну також базується на модулярному піднесенні до ступеня натуральних чисел великої розмірності. 0r>ve, реалізація паралельного виконання алгоритму модулярного експоненціювання має велике значення для побудови високонадійних і високопродуктивних систем захисту інформації. ■

Паралельний алгоритм обчислення модулярної експоненти базується на використанні деяких властивостей лінійних форм Фібоначчі максимального рангу, зокрема на і.осудові лінійного дерева Фібоначчі для показника ступеня. Тобто для обчислення виразу х" mod 2 показник повинен бути представлений у вигляді лінійної форми Фібоначчі максимального рангу і. у = а/-,' , + Ь!-\. Числа

а і b в свою чергу також можуть розкладатися в лінейні форми Фібоначчі максимального рангу. Таким чином отримаємо лінейне дерево Фібоначчі. Глибина дерева Фібоначчі дорювнює O(loglog у) (Теорема 1).

Таким чином, вираз ху mod z перетворюється на вираз

V •

(xF,'vy *{хг,У' modz.Числа xF'-‘ і xF‘ можуть обчислюватися паралельно.

Рекурсивно повторюючи розклад у лінійну форму Фібоначчі коефіцієнтів а

і Ь, ми зведемо обчислення ху modz до операцій розпаду у лінійну форму і рекурсивного піднесення до ступеня чисел Фібоначчі. Загальний час паралельного алгоритму потребує 0(T!oglog у) паралельних операцій. Де Т -час, потрібний до піднесення до ступеня, яке є числом Фібоначчі (Теорема 2).

Операція піднесення до ступеня типу Х^‘, де Fk - це к-е число Фібоначчі, потребує к операцій множення.

У розділі 3.3 наводяться описи структури ПАРУС-програми, яка реалізує паралельний алгоритм обчислення •модулярної експоненти для натуральних чисел великої розмірності.

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

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

Х^‘ = XF» * Х^‘~'. Рекурсивна функція загалом має такий вигляд: xnt Exponenta(X,Y,Z) //XYmodZ { ' if(Y=0) return (1); ■ if (Y=l) return (X);

/‘Розкласти показник у лінійну форму Фібоначчі*/

Y= A*F^x+B*Ft

RI =Exponenta( X^‘', A, Z);

Rl=Exponenta(.V^', A, Z);

геШт(Ц]*І12 той 2);

}

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

1. Якщо Ь>а, то враховуючи, що Рк, підвищуємо ранг

розкладу: а/г4_1 + ЬРк = (6 - + аЕм.

2. (Підготовка в і і до перетворення 1). Якщо Ь <а, то подавши

як (а- + (6 + л'Рк_х)Гк знаходимо якесь і, що відповідає

. а а-Ь „ „ . ,

умові — < ^ <--------. Якщо 5 знайдено, то перевизначимо а і о :

ру Рм

а = а- .іРк ,Ь = Ь+- . Якщо ні, то розклад максимального рангу досягнуто.

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

Програма тестувалася на трансп’ютерному комплексі, який складається з процесорів Т800 і Т425 із загальною продуктивністю 270 МІР5 і 12 МЛЬОРБ. Хост-машиною с персональний комп’ютер на базі процесору ІМеІ РеШіиш.

У висновку наводяться основні результати виконаної роботи.

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

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

И Досліджена модель паралельних асинхронних процесів, що задаються за допомогою керуючи! просторів. Ця модель є основою для реалізації - новий технології паралельно-рекурсивного програмування на трансп’ютерному комплексі.

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

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

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

Список публікацій.

За темою дисертації опубліковані такі роботи:

1. Анісімова О.А., Гриценко Д.В. Використання трансп’ютерних мереж в задачах візуалізації складних динамічних систем ітеративного типу.//Вісннк київського університету.-№2 -1993

2. Анісімова О. А., Гриценко Д.В. Порівнення ПАРУС та трансп’ютерної технології програмування.//Там же.-№ 1 .-1994

3. Гриценко Д.В. Основы параллельного программирования на языке

ПАРУС-Си.-Киев, 1995.-31 с.-(Препр. / НАН Украины. Ик-т кибернетики км. В.М.Глушкова; 95-22). . .

4. Гриценко Д.В. Параллельно-рекурсивный алгоритм вычисления модульной зкспонентьіУ/Доповіді національної академії наук України. №3 , 1996.

Гриценко Д. В. Методы и средства параллельно-рекурсивного программирования для транспьютерных комплексов. Рукопись. Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 — математическое и программное обеспечение вычислительных машин и систем. Киевский национальный университет им. Тараса Шевченко. Киев, 1996.

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

A model of parallel computations, which is based on the theory of controlling spaces is elaborated in this thesis. A new concurrent extension of the programming language С is suggested. This gives effective tools for creating transputer software. A new parallel algorithm for modular exponentiation for large integers is suggested and studied in detalis. This algorithm is implemented by means of developed programming technology.

Ключові слова: паралельні обчислення, трансп’ютери, паралельне програмування, керуючі простори, мова програмування Сі, модулярне піднесення до ступеня.

Підписано до друку 08.04.96. Формат 60X84/16. Папір для розмнож, апар. Офс. друк. Ум. друк. арк. 0,93. Ум. фарбо-відб. 1,05. Обл.-вид. арк. 1,0. Зам. 221. Тираж 100 прим.

Редакційно-видавничий відділ з поліграфічною дільницею Інституту кібернетики імені В. М. Глушкова НАН України 252022 Київ 22, проспект Академіка Глушкова, 40