BC/NW 2009, №1 (14): 2.1

ФОРМАЛИЗАЦИЯ ЗАДАЧИ ОПТИМАЛЬНОЙ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В СИСТЕМАХ ОБРАБОТКИ СИГНАЛЬНОЙ ИНФОРМАЦИИ РЕАЛЬНОГО ВРЕМЕНИ

Иванов А.В., Овчинников В.А.

(Московский энергетический институт (технический университет), Москва, Россия)

          1. Введение

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

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

          При этом, даже первичная оценка алгоритмов обработки информации, применяемых, например, в оптико-электронных приборах астроориентации космических аппаратов по звездам [1], позволяет сделать вывод о возможности наличия в этих алгоритмах значительной степени параллелизма. Об этом свидетельствует хотя бы тот факт, что на различных этапах обработки информации, среди которых можно выделить:

–   поиск источников излучения и определение их координат;

–   селекция источников излучения по мощности, скорости и угловым расстояниям между ними;

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

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

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

–   минимизацию времени решения возложенных на вычислительную систему задач;

–   повышение эффективности использования (загруженности) аппаратных ресурсов вычислительной системы.

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

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

 

          2. Существующие методы решения и их недостатки

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

–        какова должна быть структура используемой вычислительной системы;

–        каким образом должны использоваться отдельные элементы вычислительной системы (процессоры, память, коммуникационная среда) в процессе обработки информации.

          Ответом на первый вопрос является формальное описание структуры вычислительной системы (количество процессоров, емкость и организация памяти, тип коммуникационной среды и т.д.). Для ответа на второй вопрос требуется построить расписание выполнения задач обработки информации на вычислительной системе заданной структуры.

К настоящему времени разработан целый ряд методов решения этой задачи, cреди которых [2-8]:

–        «жадные» алгоритмы и сети Хопфилда для решения задачи построения расписаний;

–        методы слияния для минимизации аппаратных ресурсов вычислительной системы;

–        алгоритмы случайного поиска;

–        генетические и эволюционные алгоритмы, настраиваемые на любой конкретный вариант постановки задачи.

К основным недостаткам существующих методов оптимизации параллельных вычислений можно отнести:

–        отсутствие этапа формального анализа параллельной структуры алгоритма, для реализации которого проектируется вычислительная система — вместо этого предлагается применять различные эвристики или (как при использовании методов слияния) попарный перебор операций алгоритма;

–        необходимость  на каждом шаге поиска оптимальной структуры вычислительной системы решать задачу построения по возможности оптимального расписания организации вычислительного процесса (являющуюся, в общем случае, NP-полной задачей);

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

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

 

3. Формальная постановка задачи

Так как задача синтеза структуры вычислительной системы, на решение которой направлен разрабатываемый метод, является задачей оптимизации, то прежде всего необходимо определить критерии оптимальности (fi) и выбрать ограничения (gi), которым должны удовлетворять получаемые решения.

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

          Сначала рассмотрим какие ограничения могут быть наложены при проектировании структуры ВС. Одним из них служит время Tmax выполнения прикладной программы Н:

 

                                                                      (1)

 

где t —  время выполнения прикладной программы H на ВС выбранной на очередном j-ом шаге поиска структуры HWj.

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

Критерием оптимальности f, в соответствии с приведенной формулировкой задачи, служит минимизация аппаратных затрат на построение ВС.

          Один из возможных способов постановки и решения задачи синтеза архитектуры вычислительной системы под определенное приложение представлен в работе [2]. В ней предлагается рассматривать задачу как смешанную многопараметрическую и многокритериальную экстремальную задачу с ограничениями в следующей постановке:

 

                                        (2)

 

Где:

–   HP и HW — модели расписания выполнения программы и структуры ВС соответственно;

–   j — оператор интерпретации, задающий взаимодействие между компонентами моделей HP и HW;

–   fi — критерии оценки качества решения;

–   gi — ограничения на допустимые решения;

–   I1, I3, I5 — множества динамических критериев и ограничений;

–   I2, I4, I6 — множества статических критериев и ограничений;

–   (HP', HW') — пространство решений.

В настоящей работе ВС рассматриваются как совокупность аппаратных средств, в отличие от работы [2], где предлагается вводить в рассмотрение еще и системное программное обеспечение,необходимое для функционирования аппаратных средств.

При такой постановке задачи оценки значений динамических критериев и ограничений (например, время выполнения прикладной программы H) для любого варианта решения (HPj,HWj) могут быть получены лишь после выполнения оператора интерпретации j, тогда как оценки значений статических критериев и ограничений (например, величину аппаратных затрат на построение ВС) можно вычислить непосредственно по моделям HP и HW без применения оператора j.

Так как для выполнения оператора интерпретации (а следовательно, и вычисления оценок значений динамических критериев и ограничений) необходимо знание модели расписания выполнения программы HPj на выбранной архитектуре HWj, то на каждом шаге поиска оптимального с точки зрения архитектуры ВС решения задачи (2) требуется дополнительно решать задачу построения по возможности оптимального расписания организации вычислительного процесса. При этом возникают ряд сложностей, связанных с тем что, задача построения оптимального расписания организации вычислительного процесса относится к классу NP-полных задач комбинаторной оптимизации, что приводит к практической невозможности ее точного решения для реальных алгоритмов обработки сигнальной информации за приемлемое время, а выбор эвристического метода решения задачи построения расписания не является тривиальной задачей и в общем случае зависит от того как устроен граф алгоритма решения задачи, под которую проектируется архитектура ВС, а также от вида критериев fi [2-8].

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

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

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

Тогда задача (2) сводится к следующей:

 

                                                (3)

 

где H — модель поведения прикладной программы (например, граф алгоритма), HW — модель структуры ВС.

          Несложно видеть, что в (3) остались лишь статические критерии и ограничения, а пространство решений сузилось до HW', что должно упростить решение задачи (3) по сравнению с (2).

Для выполнения критерия оптимальности f необходимо осуществить минимизацию аппаратных затрат ВС. Очевидно, что термин «аппаратные затраты» нуждается в уточнении. В работе [2] и ряде других публикаций предлагается ограничить термин «аппаратные затраты» лишь количеством процессоров ВС. Это, безусловно, упрощает процесс поиска оптимального решения, но предполагает, в частности, наличие полносвязной структуры коммуникационной среды, что не всегда является достижимым при практическом построении ВС.

Введение в рассмотрение других элементов ВС (памяти, коммуникационной среды) требует, с одной стороны, некоторого способа формального описания структуры ВС, а с другой — введения весовых коэффициентов, определяющих относительную значимость вклада элементов каждого типа в общие аппаратные затраты. Формальное описание структуры ВС может быть выполнено на основе классификации Д. Скилликорна [9] с введением следующих соглашений:

–   понятия «процессор команд» (IP) и «процессор данных» (DP) заменим обобщенным понятием «процессор» (P);

–   понятия «память команд» (IM) и «память данных» (DP) заменим обобщенным понятием «память» (M).

Тогда структуру вычислительной системы можно описать следующим набором характеристик:

–   количество процессоров (NP);

–   количество модулей памяти с возможностью независимого одновременного доступа со стороны процессоров (NM);

–   тип переключателя (коммуникационной среды) между процессорами;

–   тип переключателя между процессорами и модулями памяти.

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

–   C1 — коэффициент, определяющий влияние количества процессоров (NP) на общие аппаратные затраты;

–   C2 — коэффициент, определяющий влияние количества модулей памяти (NM) на общие аппаратные затраты;

–   C3 — коэффициент, определяющий влияние типа переключателя между процессорами на общие аппаратные затраты;

–   C4 — коэффициент, определяющий влияние типа переключателя между процессорами и модулями памяти на общие аппаратные затраты.

Очевидно, что при таком наборе характеристик, различным структурам вычислительных систем могут соответствовать одинаковые аппаратные затраты. Дополнительным критерием для выбора структуры ВС в таком случае может служить оценка времени выполнения прикладной программы H на ВС структуры HW. Эту оценку времени можно либо рассчитывать лишь при нахождении нескольких оптимальных с точки зрения аппаратных затрат структур, либо, как предлагается в работе [5], включить в общий критерий оптимальности. Последний вариант является предпочтительным, так как с одной стороны не приводит к необходимости каких-либо дополнительных вычислений (так как оценку времени в любом случае требуется вычислять для проверки ограничения (1)), а с другой — позволяет (введя дополнительный весовой коэффициент C5) учесть относительную значимость времени решения задачи и аппаратных затрат в каждой конкретной системе обработки сигнальной информации.

Из всего вышесказанного следует, что задачу оптимизации (3) можно сформулировать в следующем виде:

 

                     (4)

 

Здесь N — множество натуральных чисел, CP — тип переключателя между процессорами, CM — тип переключателя между процессорами и модулями памяти.

Очевидно, что вычисление функции f из (4) при известных аргументах не представляет сложностей, а основная задача заключается в нахождении оценки времени t на каждой итерации поиска, а также в определении «направления движения» для следующей итерации.

При этом для эффективного поиска решения задачи (4) (в частности, вычисления времени t) необходимо выбрать метод описания модели прикладной программы H, удовлетворяющий следующим требованиям:

–   наличие формального языка явного описания параллельных алгоритмов на уровне отдельных операций;

–   возможность введения в формальное описание параллельного алгоритма сведений о времени выполнения отдельных операций на одном процессоре ВС;

–   возможность введения в формальное описание параллельного алгоритма сведений о времени, затрачиваемом на пересылку результатов выполнения каждой операции через коммуникационную среду ВС;

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

–   возможность получения оценки времени выполнения алгоритма для вычислительных систем различной структуры без непосредственного выполнения прикладной программы на реальной ВС;

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

          Учитывая перечисленные требования, наиболее целесообразным представляется применение графовых моделей для описания модели прикладной программы H; такой выбор обусловлен следующими причинами:

–   уровень описания параллельного алгоритма является варьируемым параметром, сопоставив каждой операции алгоритма отдельную вершину графа можно добиться требуемого уровня детализации;

–   введение в описание параллельного алгоритма сведений о времени выполнения отдельных операций на одном процессоре ВС сводится к взвешиванию каждой вершины графа алгоритма целым числом;

–   введение в описание параллельного алгоритма сведений о времени, затрачиваемом на пересылку результатов выполнения каждой операции через коммуникационную среду ВС сводится к взвешиванию каждой дуги графа алгоритма целым числом;

–   представление параллельного алгоритма в виде объединения графов зависимостей четырех типов (out-in, in-out, in-in, out-out), его описание с помощью набора покрывающих функций и применение математического аппарата разверток [9] дает потенциальную возможность разработки метода получения оценки времени выполнения алгоритма на вычислительной системе заданной структуры непосредственно по записи алгоритма, без построения расписания вычислительного процесса и без выполнения прикладной программы на реальной ВС.

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

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

 

ЛИТЕРАТУРА

1.  Абакумов В.М. Изделие 329К. Алгоритм работы изделия 329К. – М.: ОАО НПП «Геофизика-Космос», 2008.

2.  Костенко В.А. Задачи синтеза архитектур: формализация, особенности и возможности различных методов для их решения. – Программные системы и инструменты. Тематический сборник. 2000, №1 – М.: МАКС Пресс, с. 31-41.

3.  Винокуров А.В., Костенко В.А. Использование сетей Хопфилда для построения расписаний. - М.: Изд-во МГУ, 2001.

4.  Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов. - М.: Изд-во МГУ, 2000.

5.  Костенко В.А., Трекин А.Г. Влияние способа задания целевой функции на качество работы генетического алгоритма. - М.: Изд-во МГУ, 2000.

6.  Костенко В.А., Трекин А.Г. Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС. - М.: Изд-во МГУ, 2000.

7.  Костенко В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС. - Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения».­ М.: Изд-во МГУ, 2000.

8.  Вавинов С.В., Костенко В.А. Параметризованный жадный алгоритм построения статических расписаний. - М.: Изд-во МГУ, 2003.

9.  Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2004.