1.2 Постановка задачи
На основе анализа существующих методик управления распределёнными вычислениями и аналогов были сформулированы следующие цели и требования дипломного проекта. Основная цель – разработать программное средство, позволяющее программисту использовать распределённые вычисления в любых его приложениях. Для этих вычислений может использоваться группа компьютеров, объединённых либо локальной сетью, либо сетью Интернет – в зависимости от способа размещения сервера. При этом запуск любой задачи на параллельное выполнение должен быть максимально простым, сравнимым с вызовом метода. Схема применения разрабатываемого ПС предполагает автоматическое, скрытое от пользователя разбиение задачи на подзадачи, распределение нагрузки и сбор результатов. Такой подход позволит без усилий привлекать большие вычислительные мощности даже для мелких, но трудоёмких задач.
Программное средство должно быть применимым для распараллеливания алгоритмов как с параллелизмом данных, так и с параллелизмом задач. Для выполнения этого требования ПС должно иметь следующие сценарии работы:
1) Параллельная обработка массива данных. В качестве исходных данных ПС должно принимать сам массив, функцию для его обработки и – опционально – функцию для свёртки результатов работы. Обработка элементов и свёртка должны происходить параллельно. Этот сценарий будет востребован при выполнении приложений с параллелизмом данных.
2) Параллельная обработка разнородных задач. Исходными данными для такого сценария служит набор функций, каждая из которых будет выполняться параллельно. Этот сценарий необходим для алгоритмов с параллелизмом задач.
Все сценарии использования ПС должны предполагать возможность асинхронных вызовов.
ПС должно удовлетворять следующим требованиям:
1) Минимальные затраты на передачу данных. Необходимо максимально снизить объём передаваемых по сети данных, так как эти затраты могут компенсировать все преимущества одновременной обработки данных.
2) Рациональное распределение нагрузки. Необходимо так решить эту задачу, чтобы каждый из компьютеров системы простаивал минимальное время. Нужно также иметь в виду фактор неопределённости, так как иногда заранее неизвестно, сколько времени потребуется на обработку каждой подзадачи.
3) Обработка ошибок. Нужно корректно реагировать на исключительные ситуации, происходящие при решении задачи, а также на различные сетевые сбои. В случае сетевых сбоев система, если это возможно, должна продолжить корректную работу.
2 МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ПОЛОЖЕННЫЕ В ОСНОВУ РАЗРАБАТЫВАЕМОГО ПРОЕКТА, И ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ
2.1 Теоретическое моделирование параллельных вычислений
При разработке ПО для параллельных или распределённых вычислительных систем возникает ряд важных вопросов: в какой степени это ПО позволяет ускорить решение задачи с помощью распараллеливания, насколько оптимально используются компьютеры кластера, какова эффективность применяемых для параллельной обработки программного и аппаратного обеспечения. В данном разделе приведены модели и расчёты, призванные дать оценку теоретически возможному эффекту от использования разрабатываемого ПС для параллельной обработки. В следующих разделах теоретические расчёты будут проверены на практике.
Для описания некоторого абстрактного алгоритма, выполняемого на параллельной системе, и существующих в нём информационных зависимостей часто используется модель в виде графа «операции – операнды» [17] [18]. Для упрощения модели можно принять, что время выполнения любых операций является одинаковым и равняется 1 (в тех или иных единицах измерения). Кроме того, в первом приближении можно предположить, что передача данных между вычислительными устройствами выполняется мгновенно, что может быть справедливо, например, при наличии общей разделяемой памяти. Теоретическая оценка затрат на передачу данных по сети для распределённой системы будет приведена ниже.
Модель «операции – операнды» рассматривает множество операций алгоритма и информационные зависимости между ними в виде ациклического ориентированного графа
(2.1)
где V = {1,...,|V|} – множество вершин графа, представляющих операции алгоритма,
R – множество дуг графа. При этом дуга r = (i, j) принадлежит графу, если операция j использует результат выполнения операции i [17].
На рисунке 2.1 приведён пример графа операций и операндов для алгоритма нахождения выражения
(2.2)
Для выполнения одного и того же алгоритма могут быть построены различные схемы вычислений и различные модели, которые обладают различными возможностями для распараллеливания.
В рассматриваемой вычислительной модели алгоритма вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода. Обозначим через V множество вершин графа без вершин ввода, а через d(G) — диаметр (длину максимального пути) графа.
Рисунок 2.1 Модель алгоритма в виде графа «операции – операнды»
Операции алгоритма, между которыми нет пути в графе вычислений, могут быть выполнены параллельно. Например, в рассмотренном примере параллельно можно вычислить все операции умножения. Для организации параллельного вычисления конкретного алгоритма можно составить расписание, представляющее собой множество
(2.3)
в котором для каждой операции указывается номер используемого для выполнения операции процессора Pi и время начала выполнения операции ti. Здесь p – количество одновременно работающих процессоров в параллельной системе [17].
Граф G, представляющий собой вычислительную схему алгоритма, в совокупности с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G, Hp), исполняемого с использованием p процессоров.
Время выполнения параллельного алгоритма определяется максимальным значением времени, применяемым в расписании
. (2.4)
Если используется расписание, обеспечивающее наиболее быстрое выполнение данного алгоритма при данном количестве процессов, то на выполнение алгоритма будет затрачено минимальное время
Минимальное возможное время выполнения алгоритма на p процессорах независимо от используемых расписания и вычислительной схемы:
Если не принимать во внимание ограничение на количество процессоров, получим оценку наименьшего времени выполнения алгоритма
Оценка T∞ характеризует время исполнения алгоритма при наличии неограниченного количества процессоров. Гипотетическую систему с бесконечным количеством параллельно работающих компьютеров называют паракомпьютер. Концепция паракомпьютера часто применяется при теоретическом анализе параллельных и распределённых вычислений.
Для оценки параллельного выполнения алгоритма по сравнению с последовательным исполнением важным является понятие времени выполнения алгоритма при использовании одного процессора:
где – количество вершин вычислительной схемы без вершин ввода.
Если не принимать во внимание все возможные вычислительные схемы для алгоритма и ограничиться наиболее эффективной схемой из всех возможных, получим оценку
характеризующую минимальные затраты времени на выполнение алгоритма на одном процессоре. Оперируя этой величиной, можно оценить ускорение решения задачи при использловании параллельных вычислений.
Для приведённых здесь оценок времени выполнения алгоритма параллельной вычислительной системой справедливы следующие теоретические положения, доказательства которых приведены в [18].
Теорема 1. Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма [17], т.е.
Теорема 2. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.
Теорема 3. Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма
Теорема 4. Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T∞, можно достичь при количестве процессоров порядка , а именно,
При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров, т.е.
Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:
1) При выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (см. теорему 1);
2) Для параллельного выполнения целесообразное количество процессоров определяется величиной (см. теорему 4);
3) Время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 3 и 4.
Рассмотренные оценки позволяют показатели эффективности работы параллельного алгоритма – ускорение и собственно эффективность.
Ускорение (speedup), т.е. относительный выигрыш во времени выполнения параллельного алгоритма для p процессоров по сравнению с последовательным вариантом вычислений, определяется величиной:
где n – абстрактный показатель вычислительной сложности решаемой задачи, например, количество входных данных задачи [17].
Эффективность (efficiency) использования при параллельном вычислении задачи – средняя долю времени выполнения алгоритма, в течение которой процессоры реально задействованы для решения задачи [17]. Численно эффективность равно отношению ускорения к количеству процессоров в системе:
Из этих формул следует, что наилучшее значение ускорения , а для эффективности . Однако на практике в некоторых случаях данные соотношения могу нарушаться. При определенных обстоятельствах ускорение Ep может оказаться больше количества используемых процессоров p. В таких случаях говорят о наличии сверхлинейного ускорения. Причиной такого явления могут быть неравные условия выполнения параллельной и последовательной программ (например, при выполнении алгоритма на одной машине может оказаться недостаточно оперативной памяти), а также нелинейная зависимость времени выполнения задачи от количества входных данных.
Ускорение и эффективность как показатели качества параллельных вычислений часто являются противоречивыми. Так, повышение ускорения часто достигается за счёт экстенсивных мер, т.е. увеличения количества процессоров в системе, что снижает эффективность их использования. Поэтому при решении реальных задач обычно приходится выбирать некий компромиссный вариант с учетом желаемых показателей ускорения и эффективности. При этом может оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров:
Эта оценка позволяет ввести понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.
Знание максимально достижимых показателей ускорения и эффективности необходимо для оценки качества параллельных вычислений на практике, но получение идеальных величин и может быть обеспечено не для всех вычислительно трудоемких задач. Оценить максимально достижимое ускорение помогают законы Амдала и Густавсона – Барсиса.
Закон Амдала (Amdahl) [19] позволяет учесть влияние доли последовательных вычислений, которые не могут быть распараллелены, на максимально достижимое ускорение при параллельном выполнении алгоритма. Он формулируется следующим образом. Пусть f – доля последовательных вычислений в применяемом алгоритме обработки данных, тогда ускорение процесса вычислений при использовании p процессоров ограничивается величиной
Так, например, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных. Графики, иллюстрирующие ограничение закона Амдала при различной доле параллельных вычислений, приведены на рисунке 2.2:
Рисунок 2.2 Иллюстрация закона Амдала
При этом важно, что доля последовательных расчётов f в общем случае не является постоянной величиной и часто зависит от параметра n, определяющего вычислительную сложность решаемой задачи. Для большого ряда задач f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет увеличения вычислительной сложности решаемой задачи. В таком случае ускорение Sp=Sp(n) является возрастающей функцией от параметра n. Это явление носит название эффект Амдала [17]. Учесть эту зависимость ускорения от сложности задачи позволяет закон Густавсона-Барсиса.
Закон Густавсона-Барсиса также позволяет оценить максимально достижимое ускорение и выражается формулой
где g – доля последовательных расчетов в выполняемых параллельных вычислениях, определяемая как
где – время последовательной части выполняемых вычислений,
– время параллельной части выполняемых вычислений, т.е.
Данная закономерность может показать, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач, потому что ускорение Sp в этом законе является функцией от n. В связи с этим оценку ускорения, получаемую в соответствии с законом Густавсона-Барсиса, еще называют ускорением масштабирования (scaled speedup) [17].
При параллельном выполнении алгоритма – даже если не принимать во внимание потери на передачу данных – неизбежно возникают накладные расходы, связанные с организацией взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации и т.п. Величину накладных расходов можно выразить как разницу в суммарном процессорном времени, потраченном при параллельной и последовательной обработке:
Ускорение и эффективность можно выразить через накладные расходы как
Из этих формул видно, что, если сложность задачи постоянна (T1=const), то при увеличении количества процессоров эффективность будет убывать за счёт роста накладных расходов. Можно улучшить ситуацию, если при росте числа процессоров соответственно повышать сложность решаемых задач, потому что, как правило, при увеличении сложности (например, увеличении объёма входных данных) накладные расходы T0 увеличиваются медленнее, чем объем вычислений T1. Необходимое соотношение темпов роста сложности расчетов и числа используемых процессоров задаёт понятие изоэффективности.
Пусть E=const – желаемый уровень эффективности выполняемых вычислений. Из (2.23) и (2.25) можно получить
или
Выражение (2.27) задаёт зависимость между сложностью решаемой задачи и числом процессоров, которую необходимо поддерживать для обеспечения постоянного уровня эффективности при масштабировании (увеличении количества процессоров). Эту зависимость называют функция изоэффективности [17]. Если это соотношение выполняется, то такой параллельный алгоритм называют масштабируемым (scalable) [17].
|
