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

Рассмотрено программное средство - 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 Пошук видання у каталогах НБУВ 
Повний текст  Наукова періодика України 

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

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.

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

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

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

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

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

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

Для двоичного структурного алфавита определены значения и количество вспомогательных сигналов, которые необходимы для реализации частотных логических функций И, ИЛИ, И-НЕ, ИЛИ-НЕ, сложение по модулю 2, которые зависят от n переменных. Показано, что значения вспомогательных сигналов определяются как разница между значениями полного промежуточного результата и частотно-логической функции.

Запропоновано нові методи та засоби високопродуктивних паралельних обчислень із використанням відеографічних прискорювачів компанії AMD/ATI та NVidia на базі платформи МИША та мов програмування МИША М10 і МАЯ.

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

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

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

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

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

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

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