Расчет эффективности параллельных вычислений

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Введение в параллельную обработку данных

1.1 Основы параллельных вычислений

1.2 Характеристика средств программирования параллельных вычислительных систем

1.3 Архитектура параллельных вычислительных систем

Глава 2. Оценивание ускорения параллельных вычислений

2.1 Методика оценивания предельного ускорения параллельных вычислений

2.2 Алгоритм статистических испытаний методики оценивания предельного ускорения

2.3 Характеристика среды Visual Fox Pro для разработки программного комплекса

2.4 Сравнение с аналогами

2.5 Руководство пользователя по эксплуатации программного комплекса

2.6 Анализ полученных данных

Глава 3. Организация рабочего места пользователя

Глава 4. Экономико-организационный раздел

Заключение

Перечень сокращений, символов и специальных терминов с их определением

Список источников информации

Введение

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

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

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

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

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

Глава 1. Введение в параллельную обработку данных

1.1 Основы планирования параллельных вычислений

Идея параллельной обработки данных как мощного резерва увеличения производительности вычислительных аппаратов была высказана Чарльзом Бэббиджем примерно за сто лет до появления первого электронного компьютера. Однако уровень развития технологий середины 19-го века не позволил ему реализовать эту идею. С появлением первых электронных компьютеров эти идеи неоднократно становились отправной точкой при разработке самых передовых и производительных вычислительных систем. Без преувеличения можно сказать, что вся история развития высокопроизводительных вычислительных систем - это история реализации идей параллельной обработки на том или ином этапе развития компьютерных технологий, естественно, в сочетании с увеличением частоты работы электронных схем. Принципиально важными решениями в повышении производительности вычислительных систем были: введение конвейерной организации выполнения команд; включение в систему команд векторных операций, позволяющих одной командой обрабатывать целые массивы данных; распределение вычислений на множество процессоров. Сочетание этих 3-х механизмов в архитектуре суперкомпьютера Earth Simulator, состоящего из 5120 векторно-конвейерных процессоров, и позволило ему достичь рекордной производительности, которая в 20000 раз превышает производительность современных персональных компьютеров.

Очевидно, что такие системы чрезвычайно дороги и изготавливаются в единичных экземплярах. Ну, а что же производится сегодня в промышленных масштабах? Широкое разнообразие производимых в мире компьютеров с большой степенью условности можно разделить на четыре класса:

Персональные компьютеры (Personal Computer - PC);

Рабочие станции (WorkStation - WS);

Суперкомпьютеры (Supercomputer - SC);

Кластерные системы.

Условность разделения связана в первую очередь с быстрым прогрессом в развитии микроэлектронных технологий. Производительность компьютеров в каждом из классов удваивается в последние годы примерно за 18 месяцев (закон Мура). В связи с этим, суперкомпьютеры начала 90-х годов зачастую уступают в производительности современным рабочим станциям, а персональные компьютеры начинают успешно конкурировать по производительности с рабочими станциями. Тем не менее, попытаемся каким-то образом классифицировать их.

Персональные компьютеры. Как правило, в этом случае подразумеваются однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем (Microsoft Windows и др.). Используются в основном как персональные рабочие места.

Рабочие станции. Это чаще всего компьютеры с RISC процессорами с многопользовательскими операционными системами, относящимися к семейству ОС UNIX. Содержат от одного до четырех процессоров. Поддерживают удаленный доступ. Могут обслуживать вычислительные потребности небольшой группы пользователей.

Суперкомпьютеры. Отличительной особенностью суперкомпьютеров является то, что это, как правило, большие и, соответственно, чрезвычайно дорогие многопроцессорные системы. В большинстве случаев в суперкомпьютерах используются те же серийно выпускаемые процессоры, что и в рабочих станциях. Поэтому зачастую различие между ними не столько качественное, сколько количественное. Например, можно говорить о 4-х процессорной рабочей станции фирмы SUN и о 64-х процессорном суперкомпьютере фирмы SUN. Скорее всего, в том и другом случае будут использоваться одни и те же микропроцессоры.

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

Таким образом, многопроцессорные системы, которые ранее ассоциировались в основном с суперкомпьютерами, в настоящее время прочно утвердились во всем диапазоне производимых вычислительных систем, начиная от персональных компьютеров и заканчивая суперкомпьютерами на базе векторно-конвейерных процессоров. Это обстоятельство, с одной стороны, увеличивает доступность суперкомпьютерных технологий, а, с другой, повышает актуальность их освоения, поскольку для всех типов многопроцессорных систем требуется использование специальных технологий программирования для того, чтобы программа могла в полной мере использовать ресурсы высокопроизводительной вычислительной системы. Обычно это достигается разделением программы с помощью того или иного механизма на параллельные ветви, каждая из которых выполняется на отдельном процессоре [11].

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

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

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

1. Все ресурсы отдаются для выполнения одной программы, и тогда мы вправе ожидать n-кратного ускорения работы программы по сравнению с однопроцессорной системой;

2. Одновременно выполняется n обычных однопроцессорных программ, при этом пользователь вправе рассчитывать, что на скорость выполнения его программы не будут оказывать влияния другие программы. [2].

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

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

Задачи параллельной обработки информации объединяются в три большие группы:

1) задачи построения операционных моделей ПП;

2) задачи расчета операционных характеристик ПВП;

3) задачи планирования ПВП.

Задачи построения операционных моделей параллельных программ решаются применением матричной и графовой форм моделей ПП. Матричное представление ПП заключается в построении матриц связности (смежности) планируемых задач. Каждый элемент матрицы учитывает информационную связь между соответствующими задачами.

Примером матрицы смежности может служить квадратная матрица Н(n x n), где n - общее число задач, элемент h(i, j) которой определяется выражением:

Матричная модель ПП удобна для использования в ЭВМ.

Графовая форма модели ПП основывается на представлении ПП в виде ориентированного взвешенного графа. В качестве моделей ПП используются обычно ориентированные графы с конечным числом вершин и дуг, с которыми сопоставляются соответствующие параметры. Рассмотрим ориентированный ациклический взвешенный граф G(X,U,T), в котором непустое множество Х={x1, х2, ..., хn} задает множество вершин (n - общее количество вершин в графе), представляющих некоторые непересекающиеся программные элементы, реализация которых в ПВС и составляет ПВП.

Множество U определяет совокупность дуг между вершинами графа, с которыми будем ассоциировать связи между соответствующими программными элементами ПП. Дуга (i,j) от вершины i к вершине j (будем полагать, что i<j) задает отношение предшествования между вершинами i и j (другая форма записи i->j), заключающееся в том, что выполнение программного элемента j может быть начато только после завершения программного элемента i.

Если множество U пустое, то говорят, что между задачами множества Х нет отношений предшествования, т.е. они являются независимыми. Этот частный случай является довольно распространенным. Множество Т={t1,t2,...,tn} задает вектор весов вершин графа, соответствующих времени выполнения каждой задачи. Так как для неоднородной вычислительной системы время выполнения задачи на разных ВМ различно в виду различной их производительности, то каждой вершине i можно приписать m значений времени выполнения задачи (m - число ВМ в системе).

Тогда множество Т будет представлять собой квадратную матрицу nxm (n - число задач, m - число ВМ). Элемент tij такой матрицы представляет собой время решения задачи i на ВМ j. Критическим путем графа называют путь, имеющий максимальную сумму весов вершин, через которые он проходит. Критический путь соответствует максимальному времени от начала выполнения первой задачи до окончания выполнения последней.

Ярусно-параллельной формой графа называют такое его представление, при котором на каждом i-ом ярусе находятся задачи, имеющие непосредственных предшественников на ярусе i-1, а преемников (потомков) на ярусе i+1. Задачи, лежащие на одном ярусе между собой независимы.

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

1) множеством PN номеров ВМ;

2) множеством ТN номеров распределяемых задач;

3) множеством ТS моментов времени начала выполнения задач;

4) множеством ТF моментов времени завершения выполнения задач.

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

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

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

При решении задачи планирования ПВП следует учитывать эффективность применения параллельных программ. В идеале решение задачи на P ВМ должно выполняться в P раз быстрее, чем на одном ВМ. На самом деле такое ускорение практически никогда не достигается. Причина этого хорошо иллюстрируется законом Амдала:

(1)

где S - ускорение работы программы на P ВМ, а f - доля непараллельного кода в программе.

Эта формула справедлива и при программировании в модели общей памяти, и в модели передачи сообщений. Несколько разный смысл вкладывается в понятие доля непараллельного кода. Для SMP систем (модель общей памяти) эту долю образуют те операторы, которые выполняет только главная нить программы. Для MPP систем (механизм передачи сообщений) непараллельная часть кода образуется за счет операторов, выполнение которых дублируется всеми процессорами. Оценить эту величину из анализа текста программы практически невозможно. Такую оценку могут дать только реальные просчеты на различном числе процессоров. Из формулы (1) следует, что P-кратное ускорение может быть достигнуто, только когда доля непараллельного кода равна 0. Очевидно, что добиться этого практически невозможно. Очень наглядно действие закона Амдала демонстрирует таблица. 1.

Таблица 1 Ускорение работы программы в зависимости от доли непараллельного кода

Число ВМ	Доля последовательных вычислений %
	50	25	10	5	2
	Ускорение работы программы
2	1.33	1.60	1.82	1.90	1.96
4	1.60	2.28	3.07	3.48	3.77
8	1.78	2.91	4.71	5.93	7.02
16	1.88	3.36	6.40	9.14	12.31
32	1.94	3.66	7.80	12.55	19.75
512	1.99	3.97	9.83	19.28	45.63
2048	2.00	3.99	9.96	19.82	48.83

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

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

1.2 Характеристика средств программирования параллельных вычислительных систем

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

К системам с общей памятью относятся компьютеры с SMP архитектурой, различные разновидности NUMA систем и мультипроцессорные векторно-конвейерные компьютеры. Для этих компьютеров характерными являются: единая оперативная память, единая операционная система, единая подсистема ввода-вывода и множество процессоров. Единая операционная система, управляющая работой всего компьютера, функционирует в виде множества процессов. Каждая пользовательская программа также запускается как отдельный процесс. Операционная система сама определенным образом распределяет процессы по процессорам. В принципе, для распараллеливания программ можно использовать механизм порождения процессов. Однако этот механизм не очень удобен, поскольку каждый процесс функционирует в своем адресном пространстве, и основное достоинство этих систем - общая память - не может быть использован простым и естественным образом. Для распараллеливания программ используется механизм порождения нитей (threads) - легковесных процессов, для которых не создается отдельного адресного пространства, но которые на многопроцессорных системах также распределяются по процессорам. В языке программирования C возможно прямое использование этого механизма для распараллеливания программ посредством вызова соответствующих системных функций, а в компиляторах с языка fortran этот механизм используется либо для автоматического распараллеливания, либо в режиме задания распараллеливающих директив компилятору (такой подход поддерживают и компиляторы с языка С).

Все производители симметричных мультипроцессорных систем в той или иной мере поддерживают стандарт POSIX Pthread и включают в программное обеспечение распараллеливающие компиляторы для популярных языков программирования или предоставляют набор директив компилятору для распараллеливания программ. В частности, многие поставщики компьютеров SMP архитектуры (Sun, HP, SGI) в своих компиляторах предоставляют специальные директивы для распараллеливания циклов. Однако эти наборы директив, во-первых, весьма ограничены и, во-вторых, несовместимы между собой. В результате этого разработчикам приходится распараллеливать прикладные программы отдельно для каждой платформы [2].

В последние годы все более популярной становится система программирования OpenMP, являющаяся во многом обобщением и расширением этих наборов директив. Интерфейс OpenMP задуман как стандарт для программирования в модели общей памяти. В OpenMP входят спецификации набора директив компилятору, процедур и переменных среды. Разработчик не создает новую параллельную программу, а просто добавляет в текст последовательной программы OpenMP-директивы. При этом система программирования OpenMP предоставляет разработчику большие возможности по контролю над поведением параллельного приложения. Вся программа разбивается на последовательные и параллельные области. Все последовательные области выполняет главная нить, порождаемая при запуске программы, а при входе в параллельную область главная нить порождает дополнительные нити. Предполагается, что OpenMP-программа без какой-либо модификации должна работать как на многопроцессорных системах, так и на однопроцессорных. В последнем случае директивы OpenMP просто игнорируются. Следует отметить, что наличие общей памяти не препятствует использованию технологий программирования, разработанных для систем с распределенной памятью. Многие производители SMP систем предоставляют также такие технологии программирования, как MPI и PVM. В этом случае в качестве коммуникационной среды выступает разделяемая память [3].

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

Стремление добиться максимальной производительности заставляет разработчиков при реализации механизма передачи сообщений учитывать особенности архитектуры многопроцессорной системы. Это способствует написанию более эффективных, но ориентированных на конкретный компьютер программ. Вместе с тем независимыми разработчиками программного обеспечения было предложено множество реализаций механизма передачи сообщений, независимых от конкретной платформы. Наиболее известными из них являются EXPRESS компании Parasoft и коммуникационная библиотека PVM (Parallel Virtual Machine), разработанная в Oak Ridge National Laboratory.

В 1994 г. был принят стандарт механизма передачи сообщений MPI (Message Passing Interface). Основная цель, которую ставили перед собой разработчики MPI - это обеспечение полной независимости приложений, написанных с использованием MPI, от архитектуры многопроцессорной системы, без какой-либо существенной потери производительности. По замыслу авторов это должно было стать мощным стимулом для разработки прикладного программного обеспечения и стандартизованных библиотек подпрограмм для многопроцессорных систем с распределенной памятью. В настоящее время этот стандарт поддерживается практически всеми производителями многопроцессорных систем. Реализации MPI успешно работают не только на классических MPP системах, но также на SMP системах и на сетях рабочих станций (в том числе и неоднородных).

MPI - это библиотека функций, обеспечивающая взаимодействие параллельных процессов с помощью механизма передачи сообщений. Поддерживаются интерфейсы для языков C, C++ и FORTRAN. Библиотека включает в себя множество функций передачи сообщений типа точка-точка, развитый набор функций для выполнения коллективных операций и управления процессами параллельного приложения. Основное отличие MPI от предшественников в том, что явно вводятся понятия групп процессов, с которыми можно оперировать как с конечными множествами, а также областей связи и коммуникаторов, описывающих эти области связи. Это предоставляет программисту очень гибкие средства для написания эффективных параллельных программ. В настоящее время MPI является основной технологией программирования для многопроцессорных систем с распределенной памятью. Несмотря на значительные успехи в развитии технологии программирования с использованием механизма передачи сообщений, трудоемкость программирования с использованием этой технологии все-таки слишком велика.

Альтернативный подход предоставляет парадигма параллельной обработки данных, которая реализована в языке высокого уровня HPF. От программиста требуется только задать распределение данных по процессорам, а компилятор автоматически генерирует вызовы функций синхронизации и передачи сообщений (неудачное расположение данных может вызвать существенное увеличение накладных расходов). Для распараллеливания циклов используются либо специальные конструкции языка, либо директивы компилятору, задаваемые в виде псевдокомментариев. Язык HPF реализует идею инкрементального распараллеливания и модель общей памяти на системах с распределенной памятью. Эти два обстоятельства и определяют простоту программирования и соответственно привлекательность этой технологии. Одна и та же программа, без какой-либо модификации, должна эффективно работать как на однопроцессорных системах, так и на многопроцессорных вычислительных системах [8].

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

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

1.3 Архитектура параллельных вычислительных систем

Эффективное функционирование информационно-вычислительных комплексов (ИВК) зависит от многих факторов и прежде всего от:

типа и характеристик ЭВМ, входящих в ИВК;

организации вычислительного процесса в ИВК;

программного обеспечения ИВК;

квалификации обслуживающего персонала и др.

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

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

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

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

В настоящее время развитие параллельных вычислительных систем идет по четырем основным направлениям:

1) векторно-конвейерные суперкомпьютеры;

2) SMP системы, MPP системы

3) кластерные системы.

Рассмотрим основные особенности перечисленных архитектур.

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

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

1. Cистема выполняет повторяющуюся операцию;

2. Эта операция может быть разделена на независимые части, степень перекрытия которых невелика;

3. Трудоемкость подопераций примерно одинакова [2].

Длина одновременно обрабатываемых векторов в современных векторных компьютерах составляет, как правило, 128 или 256 элементов. Векторные процессоры имеют сложную структуру и по сути содержат множество арифметических устройств. Основное назначение векторных операций состоит в распараллеливании выполнения операторов цикла, в которых в основном и сосредоточена большая часть вычислительной работы. Как правило, это выполняется автоматически компиляторами при изготовлении ими исполнимого кода программы. Поэтому векторно-конвейерные компьютеры (PVP) не требуют какой-то специальной технологии программирования, что и явилось решающим фактором в их успехе на компьютерном рынке. Как правило, несколько векторно-конвейерных процессоров (2-16) работают в режиме с общей памятью, образуя вычислительный узел, а несколько таких узлов объединяются с помощью коммутаторов. Уровень развития микроэлектронных технологий не позволяет в настоящее время производить однокристальные векторные процессоры, поэтому эти системы довольно громоздки и чрезвычайно дороги [10].

Характерной чертой симметричных многопроцессорных систем (Symmetric Multi-Processing - SMP) является то, что все процессоры имеют прямой и равноправный доступ к любой точке общей памяти. Первые SMP системы состояли из нескольких однородных процессоров и массива общей памяти, к которой процессоры подключались через общую системную шину. Однако очень скоро обнаружилось, что такая архитектура непригодна для создания сколь либо масштабных систем. Первая возникшая проблема - большое число конфликтов при обращении к общей шине. Остроту этой проблемы удалось частично снять разделением памяти на блоки, подключение к которым с помощью коммутаторов позволило распараллелить обращения от различных процессоров. Однако и в таком подходе неприемлемо большими казались накладные расходы для систем более чем с 32-мя процессорами.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1 Архитектура симметричных мультипроцессорных систем

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

С большим или меньшим успехом эти проблемы решаются в рамках общепринятой в настоящее время архитектуры ccNUMA (cache coherent Non Uniform Memory Access). В этой архитектуре память физически распределена, но логически общедоступна. Это, с одной стороны, позволяет работать с единым адресным пространством, а, с другой, увеличивает масштабируемость систем. Когерентность кэш-памяти поддерживается на аппаратном уровне, что не избавляет, однако, от накладных расходов на ее поддержание. В отличие от классических SMP систем память становится трехуровневой:

1) кэш-память процессора;

2) локальная оперативная память;

3) удаленная оперативная память.

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

Перечисленные обстоятельства значительно ограничивают возможности по наращиванию производительности ccNUMA систем путем простого увеличения числа процессоров. Тем не менее, эта технология позволяет в настоящее время создавать системы, содержащие до 256 процессоров с общей производительностью порядка 200 млрд. операций в секунду. Системы этого типа серийно производятся многими компьютерными фирмами как многопроцессорные серверы с числом процессоров от 2 до 128 и прочно удерживают лидерство в классе малых суперкомпьютеров. Типичными представителями данного класса суперкомпьютеров являются компьютеры SUN StarFire 15K, SGI Origin 3000, HP Superdome [10].

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

Проблемы, присущие многопроцессорным системам с общей памятью, простым и естественным образом устраняются в системах с массовым параллелизмом (MPP - Massively Parallel Processing). Компьютеры этого типа представляют собой многопроцессорные системы с распределенной памятью, в которых с помощью некоторой коммуникационной среды объединяются однородные вычислительные узлы (рисунок. 2).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 2 Архитектура систем с распределенной памятью

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

Процессоры в таких системах имеют прямой доступ только к своей локальной памяти. Доступ к памяти других узлов реализуется обычно с помощью механизма передачи сообщений. Такая архитектура вычислительной системы устраняет одновременно как проблему конфликтов при обращении к памяти, так и проблему когерентности кэш-памяти. Это дает возможность практически неограниченного наращивания числа процессоров в системе, увеличивая тем самым ее производительность. Успешно функционируют MPP системы с сотнями и тысячами процессоров (ASCI White - 8192, Blue Mountain - 6144). Производительность наиболее мощных систем достигает 10 триллионов оп/сек (10 Tflops). Важным свойством MPP систем является их высокая степень масштабируемости. В зависимости от вычислительных потребностей для достижения необходимой производительности требуется просто собрать систему с нужным числом узлов [2].

Однако, устранение одних проблем, как это обычно бывает, порождает другие. Для MPP систем на первый план выходит проблема эффективности коммуникационной среды. Различные производители MPP систем использовали разные топологии. В компьютерах Intel Paragon процессоры образовывали прямоугольную двумерную сетку. Для этого в каждом узле достаточно четырех коммуникационных каналов. Каждая из рассмотренных топологий имеет свои преимущества и недостатки. Отметим, что при обмене данными между процессорами, не являющимися ближайшими соседями, происходит трансляция данных через промежуточные узлы. Очевидно, что в узлах должны быть предусмотрены какие-то аппаратные средства, которые освобождали бы центральный процессор от участия в трансляции данных. В последнее время для соединения вычислительных узлов чаще используется иерархическая система высокоскоростных коммутаторов, как это впервые было реализовано в компьютерах IBM SP2. Такая топология дает возможность прямого обмена данными между любыми узлами, без участия в этом промежуточных узлов [5].

Системы с распределенной памятью идеально подходят для параллельного выполнения независимых программ, поскольку при этом каждая программа выполняется на своем узле и никаким образом не влияет на выполнение других программ. Однако при разработке параллельных программ приходится учитывать более сложную, чем в SMP системах, организацию памяти. Оперативная память в MPP системах имеет 3-х уровневую структуру:

1) кэш-память процессора;

2) локальная оперативная память узла;

3) оперативная память других узлов.

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

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

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

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 3 Архитектура кластера

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

Разработано множество технологий соединения компьютеров в кластер. Наиболее широко в данное время используется технология Fast Ethernet. Это обусловлено простотой ее использования и низкой стоимостью коммуникационного оборудования. Однако за это приходится расплачиваться заведомо недостаточной скоростью обменов. В самом деле, это оборудование обеспечивает максимальную скорость обмена между узлами 10 Мб/сек, тогда как скорость обмена с оперативной памятью составляет 250 Мб/сек и выше. Разработчики пакета подпрограмм ScaLAPACK, предназначенного для решения задач линейной алгебры на многопроцессорных системах, в которых велика доля коммуникационных операций, формулируют следующим образом требование к многопроцессорной системе: "Скорость межпроцессорных обменов между двумя узлами, измеренная в Мб/сек, должна быть не менее 1/10 пиковой производительности вычислительного узла, измеренной в Mflops". Таким образом, если в качестве вычислительных узлов использовать компьютеры класса Pentium III 500 Мгц (пиковая производительность 500 Mflops), то аппаратура Fast Ethernet обеспечивает только 1/5 от требуемой скорости. Частично это положение может поправить переход на технологии Gigabit Ethernet [2].

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

Глава 2. Оценивание ускорения параллельных вычислений

2.1 Методика оценивания предельного ускорения параллельных вычислений

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

Ку = ?Ti / W, для всех i

Здесь Ti - время выполнения задачи i,

W - время параллельного выполнения вычислительного процесса.

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

Ку пред = ?Ti / Ткр. (2)

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

Трн i = max{ Тро j} = max{ Трн j + Т j }, для всех j>i

Т j - время выполнения (длина) задачи j.

Расчет Трн начинают с задач первого (верхнего) яруса. Для всех задач, лежащих на верхнем ярусе момент времени раннего начала выполнения задачи равен нулю, т.к. эти задачи не имеют предшественников и готовы к выполнению в начальный момент времени. Далее рассчитываются моменты времени раннего начала выполнения задач второго, затем третьего и так далее ярусов.

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

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

Ткр = мах{ Тро j} = max{ Трн j + Т j }, для всех j

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

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

Закон Амдала и его следствия

К примеру, в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение S может быть получено на компьютере из p процессоров при данном значении f, можно воспользоваться законом Амдала:

(3)

Очень наглядно действие закона Амдала демонстрирует таблица 1.

Таблица 1 Ускорение работы программы в зависимости от доли непараллельного кода

Подобные документы

• Разработка средств анализа информационных обменов в параллельных программах на языке IBM X10

  Понятие вычислительных систем, их классификация по различным признакам. Модели параллельных вычислений PGAS и APGAS. Разработка программного продукта для анализа информационных обменов в параллельных программах на языке IBM X10. Расчёт его себестоимости.
  
  дипломная работа [1,6 M], добавлен 10.06.2013
  

• Моделирование и анализ параллельных вычислений

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

• Параллельные вычисления в Matlab

  Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.
  
  курсовая работа [1,1 M], добавлен 15.12.2010
  

• Введение в проблематику разработки параллельных программ

  Знакомство с историей развития многопроцессорных комплексов и параллельных вычислений. Персональные компьютеры как распространенные однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем.
  
  презентация [1,1 M], добавлен 22.02.2016
  

• Моделирование и анализ параллельных вычислений

  Пакетный метод как основной способ выполнения коммуникационных операций, его содержание и предъявляемые требования. Оценка трудоемкости операции передачи данных между двумя узлами кластера. Этапы разработки параллельных алгоритмов (распараллеливания).
  
  презентация [318,1 K], добавлен 10.02.2014
  

• Применение технологии "Nvidia CUDA" для неграфических вычислений

  Сравнение центрального и графического процессора компьютера в параллельных расчётах. Пример применения технологии CUDA для неграфических вычислений. Вычисление интеграла и сложение векторов. Технические характеристики ПК, применяемого для вычислений.
  
  курсовая работа [735,9 K], добавлен 12.07.2015
  

• Обзор параллельных вычислительных систем

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

• Оценка эффективности параллельных вычислений

  Показатели эффективности параллельного алгоритма: ускорение, эффективность использования процессоров, стоимость вычислений. Оценка максимально достижимого параллелизма. Закон Амдала, Закон Густафсона. Анализ масштабируемости параллельного алгоритма.
  
  презентация [493,0 K], добавлен 11.10.2014
  

• Характеристика параллельных вычислений

  Алгоритм логарифмического сдваивания. Средняя степень параллелизма. Характеристики векторных компьютеров. Модель ускорения для параллельной вычислительной системы. Суммирование методом рекурсивного удвоения. Условия выполнения несогласованного алгоритма.
  
  лекция [183,2 K], добавлен 22.10.2014
  

• Проблемы создания эффективного параллельного программного обеспечения

  Области применения быстрых вычислений. Проблемы эффективности последовательных и параллельных программ. Отображение циклов с условными операторами на асинхронные архитектуры. Рассмотрение исследовательских университетских распараллеливающих систем.
  
  презентация [833,3 K], добавлен 07.08.2015
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам