Представлены результаты совместной работы Ясского Университета (Румыния) и Института Работы и Техники (Гельзенкирхен, Германия) по разработке простых параллельных алгоритмов для проблем выпуклых оболочек, которые могут быть использованы в графически-ориентированных обучающих веб-приложениях.

Рассмотрено программное средство - PNtool, предназначенное для синтеза и анализа параллельных и критических во времени систем, которые описываются с помощью формализма сетей Петри (СП). PNtool предназначен для поддержки четырех диалогов СП: обобщенные СП (generalized PN), временно-базисные СП (Time-basic PN), эвалюационные СП (evaluative PN) и раскрашенные СП (Coloured PN). PNtool позволяет конструирование и симуляцию системы с применением любого из упомянутых диалектов СП, а также проделать анализ системы с целью одержания ее инвариантов и решения проблемы достижимости для системы представленной обобщенной СП. Спецификация систем на языке обобщенных или эвалюационных СП может быть представлена и сохраняться в формате PNML. PNtool реализован на языке JAVA как одна из частей программной среды mFDTE (multi FDT Environment). Среда mFDTE предназначена для синтеза и анализа параллельных (concurrent) дискретных систем, включая и временно-критические системы. Программная среда mFDTE создана в университете авторов статьи. В ней интегрированы три формальных метода, которые обладают взаимно комплементарными свойствами: СП, процессные алгебры и метод В AMN. Описаны интерфейсы, связывающие PNtool с остальными частями среды mFDTE.

Індекс рубрикатора НБУВ: З970.21-018

Рубрики:

Паралельні обчислювальні системи (ПОС)

Шифр НБУВ: Ж43601 Пошук видання у каталогах НБУВ 
Повний текст  Наукова періодика України 

Provided with the brief overview of the algorithms that solve Quantifier Elimination Problem and detailed description of the Bashu, Pollack and Roy algorithm. Suggested the method for multithread realization of Basu, Pollack and Roy algorithm. Provided complexity estimation of the parallelized algorithm.

Надано паралельні алгоритми ID прямого та зворотного одновимірного косінус-перетворення зі зменшеною кількістю необхідних операцій множення. Це надає можливості розпаралелювання обчислень DCT/IDCT.

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

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

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

Исследована реальная производительность процессорного элемента в зависимости от различных способов расположения данных в кэш-памяти на примере умножения двух матриц (рассмотрены алгоритмы Фокса, Кеннона и wbgemm).

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

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

Запропоновано маштабовану паралельну реалізацію алгоритму побудови діаграми Вороного на площині. Описано процес розробки алгоритму та програмування з використанням бібліотеки Intel Threading Building Blocks (TBB). Проведено дослідження продуктивності та наведено результати експериментів.

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

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

Рассмотрены вопросы адаптации параллельных программ, использующих библиотеку PVM, для запуска на кластере НТУУ "КПИ" через планировщик PBS. Разработана модификация способа баланса загрузки, учитывающая архитектуру вычислительных узлов кластера. Даны рекомендации по организации блока анализа конфигурации PVM для параллельных программ.

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

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

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

Исследована задача повышения производительности приложений для параллельных ЭВМ путем многопоточной реализации вычислений. Для классических вычислительных задач построены и программно реализованы последовательный и параллельный алгоритмы, выполнен их сравнительный анализ и тестирование на различных архитектурах ЭВМ.