УДК 519.68

 

Л.С. ВЕЛЕНТ1, С.И. КИРКОРОВ2

 

1Научно-производственное предприятие «МедиаСкан» , г. Минск, Республика Беларусь

2Высший государственный колледж связи, г. Минск, Республика Беларусь

 

композиции параллельных алгоритмов ЯЗЫКА ADA для средств связи

 

Введение

 

Есть множество задач, которые по различным причинам должны быть решены быстро. Поэтому во многом делается упор на компьютеры с несколькими ядрами, в частности – в средствах связи обработки речевой и видео информации. Параллельные вычисления (параллельная обработка) – это использование нескольких или многих вычислительных устройств для одновременного выполнения разных частей одной программы (одного проекта) [1]. Основная цель параллельных вычислений – это уменьшение времени решения задачи. Единственным универсальным языком программирования имеющем международный стандарт и поддерживающим параллельные алгоритмы строго стандартными средствами является Ada. Выбор языка Ada – оптимальный подход для приложений критичных к безопасности и выполнения требований информационной безопасности [2,3].

В данной работе рассмотрен следующий подход к композиции параллельных алгоритмов и улучшению локальности алгоритмов: каждое гнездо циклов (каждый алгоритм) отображается на параллельный компьютер сам по себе. Получены достаточные условия на эти отображения, которые обеспечивают хорошую локальность «стыковочных» данных. Исследована локальность данных, определяемых в одном, а используемых в другом гнезде циклов.

 

1. Тайлинг

Одним из основных способов уменьшения накладных расходов на использование иерархической памяти является тайлинг [4,5]. При тайлинге операции алгоритма разбиваются на тайлы, т.е. на множества операций, выполняемых атомарно, как одна единица вычислений.

Обобщенный тайлинг является допустимым, если для любой такой зависимости выполняются следующие условия:

,            (1.2.3)

                                     (1.2.4)

При отсутствии указанных зависимостей тайлинг допустим [5].

 

2. Улучшение локальности композиции параллельных алгоритмов

 

Локальность – это вычислительное свойство алгоритма, отражающее степень использования памяти с быстрым доступом. рассматривается композиция параллельных алгоритмов. Подход для нее следующий: каждый алгоритм (каждое гнездо циклов) отображается на параллельный компьютер сам по себе. Наша задача – получить условия на эти отображения, обеспечивающие хорошую локальность «стыковочных» данных

Пусть у нас имеется зависимость , , , которую описывает функция зависимостей вида:

.     (2.3.1)

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

Для каждого ,  зафиксируем один из параметров циклов . Обозначим  – вектор размера , у которого координата с номером  равна . Обозначим через  и  строки матриц с номером ; если , то примем , , .

Поставим в соответствие тайлам  функции вида

.                       (2.3.2)

Нам необходимо определить последовательности зернистых вычислений (т.е. разбитых на тайлы). К одной последовательности отнесём операции тайлов с одинаковыми значениями функции (2.3.2). Данные функции  можно использовать для распределения операций алгоритма между процессорами: организуется вычислительные процесс для выполнения на процессоре с номером  операций тайлов . Задача выбора функций  – задача распределения операций между процессорами – должна быть согласована с задачей распределения массивов данных между процессорами. От степени согласованности распределения операций и массивов данных зависит локальность параллельных реализаций алгоритмов, одного из важнейших вычислительных свойств алгоритмов.

Для операторов  и  функцию (2.3.2) можно записать следующим образом:

.                     (2.3.3)

.                     (2.3.4)

Т е о р е м а 2.3.1. Пусть элемент массива  определяется на вхождении  и используется на вхождении  в правой части оператора . Определение и использование данных происходят в одном вычислительном процессе, если выполняются следующие условия:

,                                    (2.3.5)

,                                                 (2.3.6)

. (2.3.7)

Можно сформулировать следствие из теоремы 2.3.1 [6].

С л е д с т в и е 2.3.1. Пусть элемент массива  определяется на вхождении  и используется на вхождении  в правой части оператора . Если , то определение и использование данных происходят в одном вычислительном процессе, если выполняются следующие условия:

,                     (2.3.11)

,                                  (2.3.12)

.              (2.3.13)

Таким образом, в данном случае мы получили условия для любого .

Выводы

 

Таким образом, в теореме 2.3.1. [6] сформулированы достаточные условия, при выполнении которых мы получаем, что вычисленные данные попадают именно в тот процесс, в котором эти данные нужны, т.е. определение данных и использование данных происходит в одном вычислительном процессе. Подтверждение, что теорема работает ‑ решение, полученное геометрическим путём совпадает с решений, полученным теоретическим путём [6]. Полученные результаты могут использоваться при автоматизации распараллеливания алгоритмов на языке Ada.

 

Литература

 

1.     Лиходед, Н.А. Методы распараллеливания гнезд циклов: Курс лекций / Н.А. Лиходед. – Мн.: БГУ. 2007. – 100 с..

2.     Ada 95 Language Reference Manual ANSI/ISO 8652.1995-std: [Electronicresource]. – http://www.adapower.com/rm95/index.html.

3.     Киркоров С. И., Киркорова Л. С. (Велент Л.С.) Параллельные алгоритмы математических моделей: исследование локальности и применение языка Ada. Ж-л: ВІСНИК Харківського національного університету імені В.Н. Каразіна, №863 Серія: Математичне моделювання. Інформаційні технології. Автоматизовані системи управління, Випуск 12, стр. 129-142, Харків, 2009..

4.     Лиходед, Н.А. Характеристика локальности параллельных реализаций многомерных циклов / Н.А. Лиходед // Доклады НАН Беларуси. 2010 – Т54. №1 – С.26-32.

5.     Лиходед, Н.А. Обобщенный тайлинг / Н.А. Лиходед // Доклады НАН Беларуси. 2011.

6.     Киркорова Л.С.(Велент Л.С.) Улучшение локальности композиции параллельных алгоритмов: Магистерская диссертация, Институт подготовки научных кадров НАН Беларуси, 2011.