Представлен способ поиска множества максимальных клик в графе. Данный способ основан на методе построения дополнительного графа-пирамиды, что позволяет легко распараллеливать вычисления. Вычислительная сложность представленного способа зависит линейно от количества максимальных клик в графе. При решении конкретных задач (распознавании изображений, например) данный способ позволяет ускорять получение решения. Это достигается за счет сокращения числа строящихся вершин и ребер путем использования при их построении дополнительных условий, которые учитывают специфику задачи.

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

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

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

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

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

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

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

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

Представлена библиотека функций для моделирования сложных динамических объектов на параллельных вычислительных системах. В качестве базовых алгоритмов библиотека использует параллельные блочные методы. Для организации обмена данными между параллельными процессорами использован стандарт MPI.

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

Удосконалено методи синтезу та реалізації швидких лінійних перетворень (ШЛП) на базі паралельних обчислювальних структур. Обгрунтовано обчислювальні структури реалізації ШЛП, частковими випадками яких є швидкі дискретні перетворення Фур'є, Хартлі, Хаара, Уолша - Адамара, Віленкіна - Крестенсона, косинусне та синусне дійсної послідовності. Синтезовано потокові процесори обчислення одно- та двовимірних ШЛП, орієнтовані на реалізацію на базі програмованих логічних інтегральних схем. Наведено результати моделювання синтезованих процесорів з використанням мови опису апаратних засобів VHDL. Розроблено швидкі нейронні мережі синтезу ШЛП. На задачах синтезу 32-точкових ШЛП досягнуто чотириразового скорочення часу навчання у порівнянні з одношаровою лінійною нейромережею. Розроблено систему обчислення ШЛП у складі потокового процесора та нейронної мережі синтезу перетворень. У даній системі використано практично значимі ШЛП та апаратно реалізовано нові типи перетворень шляхом запису відповідного набору коефіцієнтів до запам'ятовуючого пристрою процесора.

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

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

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

Досліджено алгоритм скорочення математичних моделей RLC-схем на базі Y-<$E DELTA> перетворення, який може використовуватися для зменшення розмірів математичних моделей МЕМС. Істотним недоліком базового алгоритму є велика кількість нових елементів, які створюються в схемі під час скорочення, що значно збільшує час скорочення та може повністю нівелювати результат внаслідок зростання похибки. Для усунення цього недоліку розроблено модифікацію евристичного кластерного алгоритму А. Санжованні - Вінсентеллі, що дозволяє перетворювати початкову структурну матрицю схеми до блочно-діагонального вигляду з обрамленням, що дозволяє розділення на n незалежних підсхем, які зв'язані між собою фіксованою кількістю вузлів. Розроблено паралельний алгоритм скорочення, під час виконання якого відбувається паралельне скорочення кожної підсхеми окремо базовим алгоритмом і "склейка" одержаних скорочених підсхем в одну з подальшим скороченням для одержання остаточного результату. Наведено числові результати оцінки ефективності по часу запропонованого алгоритму.

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

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

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

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