Локальні алгоритми та їх ефективна реалізація в багатопроцесорних обчислювальних системах

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

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

УДК 004.272.26:004.032.26:519.1

ЛОКАЛЬНІ АЛГОРИТМИ ТА ЇХ ЕФЕКТИВНА РЕАЛІЗАЦІЯ

В БАГАТОПРОЦЕСОРНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ

Спеціальність 01.05.03 - математичне та програмне забезпечення

обчислювальних машин і систем

АВТОРЕФЕРАТ

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

кандидата фізико-математичних наук

ГУЛАЄВА НАТАЛІЯ мИХАЙЛІВНА

Київ - 2005



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

Робота виконана на кафедрі математичної інформатики факультету кібернетики Київського національного університету імені Тараса Шевченка

Науковий керівник: кандидат фізико-математичних наук, доцент Глибовець Микола Миколайович, Київський національний університет імені Тараса Шевченка, доцент кафедри математичної інформатики

Офіційні опоненти: доктор фізико-математичних наук, старший науковий співробітник Буй Дмитро Борисович, Київський національний університет імені Тараса Шевченка, завідувач науково-дослідної лабораторії науково-дослідної частини

кандидат фізико-математичних наук, старший науковий співробітник Гороховський Семен Самуїлович, Національний університет “Києво-Могилянська академія”, доцент кафедри інформатики

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України, відділ автоматизації програмування, м. Київ

Захист дисертації відбудеться “23“ червня 2005 року о “14“ годині на засіданні спеціалізованої вченої ради Д 26.001.09 в Київському національному університеті імені Тараса Шевченка (03127, м. Київ, пр. Глушкова, 2, корп. 6, ф-т кібернетики, ауд. 40. Тел. 259-04-24. Факс 259-70-44. E-mail:rada1@unicyb.kiev.ua)

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

Автореферат розісланий “21“ травня 2005 року.

Вчений секретар

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

кандидат фізико-математичних наук, доцент В.П.Шевченко



АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Київський національний університет імені Тараса Шевченка, Київ, 2005.

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

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

Ключові слова: локальний алгоритм, теорія графів, штучна нейронна мережа, багатопроцесорна обчислювальна система, однорідне обчислювальне середовище.



Гулаева Н.М. Локальные алгоритмы и их эффективная реализация в многопроцессорных вычислительных системах. - Рукопись.

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

В работе рассмотрена модель локальных вычислений. Показано, что классы конечноавтоматных программ, сетей Петри и искусственных нейронных сетей эффективно транслируемы в класс локальных по А.В.Анисимову алгоритмов. Построены новые локальные алгоритмы решения практически важных дискретных задач.

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

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



Gulayeva N.M. Local Algorithms and Their Effective Implementation in the Multiprocessor Computing Systems. - Manuscript.

Thesis for a candidate's degree of physics and mathematics by speciality 01.05.03 - mathematical and software support of computing machines and systems. - Kyiv Taras Shevchenko National University, Kyiv, 2005.

This thesis is devoted to the model of local computations. New local algorithms to solve practically important discrete problems are proposed. Effective ways of local algorithms implementation in the multiprocessor computing systems are given.

It is shown that class of local algorithms proposed by Iu.I.Zhuravlev, class of local algorithms proposed by S.V.Iablonskii and A.Iu.Chernov, classes of local predicative and computational algorithms proposed by V.A.Ievstigne'ev are effectively translated to class of local algorithms proposed by A.V.Anisimov, hereinafter A-local algorithms.

It is shown that class of genetic algorithms implemented via diffusion model and class of artificial neural networks are effectively translated to class of A-local algorithms. As a consequence of the latter result it is claimed that class of Turing machines is effectively translated to class of A-local algorithms. Thus, A-local algorithms can be considered as a formal model to specify algorithmically computable functions.

It is shown that class of finite-state automaton programs is effectively translated to class of A-local algorithms. This was done aiming at elaboration of methods of finite-state automaton programs implementation in the multiprocessor computing systems, as far as finite-state automaton programming paradigm is considered today as one of the most advanced approaches to be used in real-time systems development. As an example of use of proposed technique, finite-state automaton approach to support IP-cameras in multi-user systems, like digital visual surveillance or videoconference systems are, is described.

A-local algorithms (nondeterministic and deterministic) to model classes of Petri Nets and extended (by disjunctive logic and switch) Petri Nets are constructed. To illustrate proposed approach to modelling problems solving, a parallel version of WML-page processing by WAP-gateway is worked up; an extended Petri Net is used as the modelling tool.

New local algorithms to solve several graph theory problems are constructed. In particular, a nondeterministic A-local algorithm for searching for the way with maximum throughput in the oriented graph is proposed; a number of its deterministic realizations, including parallel ones, are given. A-local algorithms for searching for the most failsafe way in the oriented graph and for searching for the critical path in the project management network model are described. Several A-local algorithms to build maximum parallel form of oriented graph are proposed. A-local algorithms of recognition of several classes of graphs are also considered.

It is claimed that theory of A-local algorithms is the theory of distributed computations on the network of processors. In support of this an approach to A-local algorithms implementation on the network of processors is proposed, where the topology of network of processors models the topology of graph of elements connections of given algorithm computing environment.

Several methods of embedding an arbitrary graph into regular graph of degree 4 are elaborated. Based on obtained results, different approaches to A-local algorithms implementation in the networks of processor elements, where the number of input/output ports per processor is equal to 4, are proposed. At that networks of rectangular mesh topology and configurable networks are considered. These approaches describe effective implementation ways of A-local algorithms in a wide number of multiprocessor computing systems; construction of such systems is based on von Neumann cellular automata. The possibility of A-local algorithms efficient implementation in the homogeneous computing environment (including pulsing grids) is proved.

It is shown that class of A-local algorithms is effectively translated to class of artificial neural networks. This determines effective ways of A-local algorithms implementation on neurocomputers. As a byproduct of result mentioned above a method to construct an artificial neural network that computes given partial recursive function (based on operator term of this fucntion) is obtained. The method construction is based on the theorem about primitive recursive function representation.

Key words: local algorithm, graph theory, artificial neural network, multiprocessor computing system, homogeneous computing environment, finite-state automaton programming, Petri Net, genetic algorithm.



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

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

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

Давно стало очевидним, що для отримання реальних переваг від використання багатопроцесорних ЕОМ необхідним є ретельне узгодження структури алгоритмів з архітектурою обчислювальної системи. Пошук ефективних алгоритмів розв'язання дискретних задач з використанням багатопроцесорних ЕОМ призвів до ідеї обмеження об'єму інформації, що оброблюється та запам'ятовується на кожному кроці роботи алгоритму. Алгоритми з вказаною властивістю були названі локальними. Класична теорія локальних алгоритмів була створена Ю.І.Журавльовим у 60-х роках ХХ ст. та розвивалась в роботах С.В.Яблонського, О.Ю.Чернова, В.А.Євстігнєєва, А.В.Анісімова, Г.Ф.Лосєва, І.Б.Гуревича, О.О.Щербіни, О.Є.Богданова, Ю.Ю.Фінкельштейна, І.Ш.Дідманідзе тощо. Виразимість задачі в класі локальних алгоритмів є важливою обчислювальною характеристикою, яка означає можливість її ефективної паралельної реалізації. Хоча сучасний рівень технічного розвитку й робить можливим практичне втілення різних методів паралельної організації обчислень, для локальних алгоритмів ще й досі не існує загальних методик їх реалізації в багатопроцесорних обчислювальних системах.

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

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

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

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

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

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

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

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

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

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

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

Наукова новизна одержаних результатів. У даній роботі отримано такі нові результати:

· Показано, що класи локальних алгоритмів Ю.І.Журавльова, локальних алгоритмів С.В.Яблонського та О.Ю.Чернова, локальних предикативних та обчислювальних алгоритмів В.А.Євстігнєєва ефективно транслюються в клас локальних алгоритмів А.В.Анісімова (в подальшому А-локальних алгоритмів).

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

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

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

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

Особистий внесок здобувача. Усі основні результати дисертації одержані автором одноосібно. У спільно виконаних роботах науковому керівникові Глибовцю М.М. належить постановка задач та участь в обговоренні результатів.

Апробація результатів дисертації. Результати дисертаційної роботи доповідались на Третій Всеукраїнській науково-практичній конференції студентів, аспірантів та молодих вчених “Крок у майбутнє” (Київ, 2003), П'ятій Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології” (Київ, 2003), П'ятій Міжнародній науково-технічній конференції “Штучний інтелект - 2004. Інтелектуальні та багатопроцесорні системи” (с. Кацивелі, Крим, 2004).

Публікації. Основні результати дисертації опубліковано в 9 роботах, список яких наведений у кінці автореферату; з них 6 - статті в наукових фахових виданнях, 3 - тези доповідей.

Структура та обсяг дисертації. Дана дисертаційна робота складається зі вступу, трьох розділів, висновків, списку використаних джерел із 230 найменувань та десяти додатків. Загальний обсяг дисертації - 210 сторінок, обсяг основного тексту - 138 сторінок.

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

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

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

Нехай задано алгоритми A₁ та A₂, та нехай In(A₁), In(A₂), Out(A₁), Out(A₂) - множини всіх допустимих значень наборів вхідних та вихідних даних відповідно. Алгоритми A₁ та A₂ називаються функціонально еквівалентними, якщо існують взаємно однозначні відображення fⁱⁿ:In(A₁)>In(A₂), f^out:Out(A₁)>Out(A₂), та з fⁱⁿ(in(A₁))=in(A₂) випливає, що обидва алгоритми або зациклюються, або зупиняються, причому f^out(out(A₁))=out(A₂); тут in(A₁)In(A₁), in(A₂)In(A₂), out(A₁)Out(A₁), out(A₂)Out(A₂).

Клас алгоритмів S₁ ефективно транслюється в клас алгоритмів S₂, якщо існує алгоритм, який перетворює будь-який алгоритм з S₁ у функціонально еквівалентний йому алгоритм з S₂.

У підрозділі 1.1 оглянуто основні наукові та прикладні праці, що стосуються тематики досліджень, а також простежено основні періоди історії розвитку теорії локальних алгоритмів. Детально розглянуто класи локальних алгоритмів, запропоновані Ю.І.Журавльовим, С.В.Яблонським та О.Ю.Черновим, В.А.Євстігнєєвим, А.В.Анісімовим. Показано, що класи локальних алгоритмів Ю.І.Журавльова, локальних алгоритмів С.В.Яблонського та О.Ю.Чернова, локальних предикативних та обчислювальних алгоритмів В.А.Євстігнєєва ефективно транслюються в клас локальних алгоритмів А.В.Анісімова (А-локальних алгоритмів). Тим самим обґрунтовується вибір класу А-локальних алгоритмів для подальших досліджень.

Нагадаємо, що запропонована А.В.Анісімовим формалізація задання локальних обчислень передбачає наявність множини D елементів обчислювального середовища, відображення ф:D>2^D, що визначає околи елементів dD, функції м:D>M, що задає інформаційне наповнення множини D, а також локальних операторів, що визначаються як одночасне обчислення всіх зіставлених елементам dD функцій f(Інф(ф(d))), та локальних предикатів, що визначаються як одночасна виконаність в будь-якому околі деякого локального предиката p(Інф(ф(d))); через Інф(d) позначається значення із M, що зберігається в dD. Локальні алгоритми будуються за допомогою певних (визначених конкретною алгоритмічною мовою) керуючих конструкцій з використанням локальних операторів та локальних умов як базисних операцій. Синтаксис алгоритмічної мови, якою записуються А-локальні алгоритми в даній роботі, описано за допомогою розширеної БНФ-граматики.

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

У підрозділі 1.3 дано приклад використання методів підрозділу 1.2 для розв'язання практичних задач. Зокрема, запропоновано скінченноавтоматний підхід до організації підтримки мережевих камер у багатоклієнтських системах, наприклад, у цифрових системах відеоспостереження та в системах організації відеоконференцій. В таких системах з метою запобігання перевантаженню процесора мережевої камери роботу з нею, як правило, організують через відео proxy-сервер, який відіграє роль єдиного під'єднаного до камери клієнта. У підрозділі побудовано скінченний автомат, що описує роботу відео proxy-сервера з мережевими камерами, які на кожен запит видають не більше одного зображення, причому параметри зображення (зокрема, його роздільна здатність) встановлюються глобально, отже, одночасне отримання зображень з різними значеннями одного параметру є неможливим. Кожен клієнт системи, якому потрібні відеодані, має переслати до відео proxy-сервера команду створення відеоканалу певної роздільної здатності, потік команд видачі нового зображення певної роздільної здатності та команду знищення відеоканалу певної роздільної здатності, якщо відеодані клієнтові більше не потрібні. Зазначимо, що побудований скінченний автомат має (6*k+1) станів, де k - кількість варіантів роздільної здатності, що підтримується мережевою камерою.

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

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

|D|=|T|+|P|

де T - множина переходів, P - множина позицій в мережі Петрі.

У підрозділі 1.5 наведено недетерміновані А-локальні алгоритми моделювання мереж Петрі, розширених операціями диз'юнктивної логіки та перемикачем. Мережу Петрі, розширену операціями диз'юнктивної логіки та перемикачем, використано при моделюванні процесу обробки WAP-шлюзом отриманої від WAP-сервера WML-сторінки. Побудова такої моделі дала змогу виявити можливі шляхи розпаралелювання роботи WAP-шлюзу.

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

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

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

S(a_j1,a_j2,…,a_jl)

де l - кількість з'єднань j-го нейрона, a_jk - величина активації, породженої k-м з'єднанням j-го нейрона. Величина a_jk визначається як дендритне перетворення

де - вектор вихідних сигналів нейронних елементів, що беруть участь в утворенні k-го з'єднання j-го нейрона, w_jk - величина ваги k-го з'єднання j-го нейрона.

Теорема 1.6. Клас штучних нейронних мереж ефективно транслюється в клас А-локальних алгоритмів.

Наслідок. Клас машин Тьюрінга ефективно транслюється в клас А-локальних алгоритмів.

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

Теорема 1.7. Клас генетичних алгоритмів на основі індивідів ефективно транслюється в клас А-локальних алгоритмів.

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

У другому розділі використано такі позначення: G=(V,E) - орієнтований граф, V - множина вершин, |V|=n, E - множина дуг, |E|=m, sV - джерело; r(v,w) - функція пропускних спроможностей, причому r(v,w)=0, якщо (v,w)E, та r(v,v)= для всіх вершин vV; R(v)={v}{wV:(w,v)E}{wV:(v,w)E} - базовий окіл вершини v; R⁺(v)={wR(v): (w,v)E}; R^-(v)={wR(v): (v,w)E}.

У підрозділі 2.1 запропоновано недетермінований А-локальний алгоритм розв'язання задачі знаходження в орієнтованому графі шляху з максимальною пропускною спроможністю. Зазначено, що з відомою величиною максимальної пропускної спроможності шлях від s до v легко відновлюється, та наведено відповідний алгоритм складності O(m).

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

, .

Зазначено, що змінивши початковий розподіл інформації по вершинах та поклавши

,

де p(w,v) - надійність дуги (w,v), наведений А-локальний алгоритм розв'язуватиме задачу знаходження найнадійнішого шляху в орієнтованому графі.

У підрозділі 2.2 запропоновано детерміновані реалізації недетермінованого А-локального алгоритму знаходження шляху з максимальною пропускною спроможністю. Серед них відзначимо паралельний А-локальний алгоритм складності O(nk), що використовує n процесорів та є зручним для реалізації в машинах архітектури типу SIMD; тут k - максимальний степінь заходу вершин графу G.

У підрозділі 2.3 запропоновано детерміновані реалізації недетермінованого А-локального алгоритму знаходження шляху з максимальною пропускною спроможністю для випадків, коли відомо, що граф G не містить контурів. В основі першого з наведених алгоритмів лежить пошук в ширину в графі G. Складність цього алгоритму O(nk), де k - максимальний степінь виходу вершин графу G.

Другий запропонований алгоритм працює з паралельною формою графу G. Його особливістю є поярусна оптимізація вершин, причому всі вершини одного ярусу оптимізуються паралельно. Цей алгоритм використовує l процесорів, а його складність оцінюється величиною O(hk), де l - ширина паралельної форми графу G, h - висота паралельної форми графу G, k - максимальний степінь заходу вершин графу G. Під паралельною формою безконтурного орієнтованого графу розуміється таке розбиття множини його вершин V на підмножини V₁,V₂,…,V_h, V_iV_j=,, що коли vV_i, uV_j та існує дуга (v,u), то i<j. Підмножини V₁,V₂,…,V_h називаються ярусами паралельної форми, число h - її висотою, число |V_i| називається шириною i-го ярусу, а максимальне з цих чисел - шириною паралельної форми графу. Максимальною паралельною формою називається паралельна форма мінімальної висоти.

У підрозділі 2.3 також описано А-локальні алгоритми розрахунку параметрів мережевої моделі проекту, зокрема, визначення ранніх/пізніх термінів настання подій та пошуку критичного шляху.

У підрозділі 2.4 наведено А-локальні алгоритми побудови максимальної паралельної форми орієнтованого графу. Серед них відзначимо алгоритм, який видає повідомлення про наявність контурів, якщо в графі є контури, або будує максимальну паралельну форму графу, якщо контурів немає. Цей алгоритм використовує n процесорів, його складність оцінюється величиною O(nk), де k - максимальний степінь заходу вершин графу G. Основна ідея алгоритму полягає в наступному.

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

, .

Після (n+1)-го кроку виконання тіла циклу у випадку наявності в графі контурів певна вершина з контуру обов'язково отримає номер n+1, а у випадку безконтурного графу для будь-якої вершини vV Інф(v) дорівнюватиме номеру ярусу максимальної паралельної форми, до якого цю вершину віднесено.

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

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

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

Означення 3.1. Графом зв'язків А-локального алгоритму називається граф, вершинами якого є елементи dD, та елемент d_iD з'єднується ребром з елементом d_jD тоді й лише тоді, коли d_jф(d_i), d_j?d_i.

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

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

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

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

Теорема 3.1. Будь-який А-локальний алгоритм, де D - скінченна множина, може бути ефективно реалізований в Р-Т-мережі з кількістю Т-елементів, що не перевищує

.

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



.

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

де h - висота дерева зв'язків А-локального алгоритму, |D|<2*3^h.

Як приклад Т-мереж розглянуто мережі трансп'ютерів; наведено приклади реалізації А-локальних алгоритмів у мережах трансп'ютерів, записані мовою Оккам.

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

Теорема 3.4. Для будь-якого А-локального алгоритму, де D - скінченна множина, існує p-алгоритм у вигляді ефективного p-кортежа, який може бути реалізований в однорідному обчислювальному середовищі.

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

У підрозділі 3.4 визначено способи реалізації А-локальних алгоритмів на нейрокомп'ютерах. Для цього доведено справедливість наступної теореми.

Теорема 3.5. Клас А-локальних алгоритмів ефективно транслюється в клас штучних нейронних мереж.

При доведенні вказаної теореми було запропоновано спосіб побудови штучної нейронної мережі, яка обчислює задану частково рекурсивну функцію. Для побудови такої мережі було використано теорему про представлення примітивної рекурсії та дано способи побудови нейронних мереж, що реалізують базові функції O(x)=0, S(x)=x+1, , функції +(x1,x2), Ч(x1,x2), (x1,x2), операції суперпозиції Sⁿ⁺¹ і мінімізації . Нейронна мережа, яка обчислює задану частково рекурсивну функцію, конструюється за операторним термом цієї функції.



ВИСНОВКИ

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

Основними результатами дисертації є наступні:

1. Показано, що в клас локальних алгоритмів А.В.Анісімова (А-локальних алгоритмів) ефективно транслюються:

· клас локальних алгоритмів Ю.І.Журавльова;

· клас локальних алгоритмів С.В.Яблонського та О.Ю.Чернова;

· класи локальних предикативних та обчислювальних алгоритмів В.А.Євстігнєєва;

· клас скінченноавтоматних програм;

· класи мереж Петрі та розширених (операціями диз'юнктивної логіки та перемикачем) мереж Петрі;

· клас генетичних алгоритмів на основі індивідів;

· клас штучних нейронних мереж;

· клас машин Тьюрінга.

2. Результати пункту 1 дозволили розв'язати такі практичні задачі:

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

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

3. Розроблено нові А-локальні алгоритми розв'язання таких задач на графах:

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

· знаходження найнадійнішого шляху в орієнтованому графі;

· знаходження критичного шляху в мережевій моделі проекту;

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

· розпізнавання деяких класів графів тощо.

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

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

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

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



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Глибовець М.М., Гулаєва Н.М. Локальний алгоритм розв'язання задачі знаходження шляху з максимальною пропускною спроможністю та його паралельні реалізації // УСиМ. - 2000. - №1. - С. 27-31.

Глибовець М.М., Гулаєва Н.М. Виконання локальних алгоритмів у однорідному обчислювальному середовищі // Вісник Київського університету. Сер.: фізико-математичні науки. - 2002. - №1. - С. 208-215.

Гулаєва Н.М. Про один підхід до організації роботи WAP-шлюзу в багатопроцесорних обчислювальних системах // Наукові записки НаУКМА. Сер.: комп'ютерні науки. - 2002. - Т. 19-20. - С. 25-28.

Гулаєва Н.М. Локальні алгоритми: зв'язок зі штучними нейронними мережами та генетичними алгоритмами // Наукові записки НаУКМА. Сер.: комп'ютерні науки. - 2003. - Т. 21. - С. 15-22.

Глибовец Н.Н., Гулаева Н.М. Связь между искусственными нейронными сетями и локальными алгоритмами // Искусственный интеллект. - 2004. - №4. - C. 545-548.

Глибовец Н.Н., Гулаева Н.М. Реализация локальных алгоритмов в транспьютерных сетях // УСиМ. - 2005. - №1. - С. 68-77.

Гулаєва Н.М. Представлення локальних алгоритмів у однорідному обчислювальному середовищі // Тез. доп. ІІІ Всеукр. науково-практичної конф. студентів, аспірантів та молодих вчених “Крок у майбутнє”. - Київ: Політехніка, 2003. - С. 53.

Глибовець М.М., Гулаєва Н.М. Використання мереж Петрі для моделювання роботи WAP-шлюзу в багатопроцесорних обчислювальних системах // Тез. доп. V Міжнар. науково-практичної конф. студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології”. - Київ: НТУУ КПІ, 2003. - С. 34-35.

Глибовец Н.Н., Гулаева Н.М. Связь между искусственными нейронными сетями и локальными алгоритмами // Матер. Междунар. научно-технической конф. “Искусственный интеллект. Интеллектуальные и многопроцессорные системы”. - Таганрог: ТРТУ, 2004. - Т. 1. - С. 402-403.

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

...