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

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

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

Рубрики:

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

Шифр НБУВ: Ж72727 Пошук видання у каталогах НБУВ 

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

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

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

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

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

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

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

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

  Скачати повний текст

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

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

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

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

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

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

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

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