Многопроцессорные эвм и распараллеливание программ реферат

Обновлено: 03.07.2024

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

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

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

Многопроцессорные ЭВМ и распараллеливание программ . [4]

Важным средством современного программирования является возможность распараллеливания программы . Недостатком всех трех языков является отсутствие таких средств на языковом уровне. [5]

Для оценки такта выдачи команд управления при распараллеливании программы на несколько транспьютеров целесообразно декомпозировать второй блок. Время вычисления процедур данного блока при небольшом числе транспьютеров будет обратно пропорционально их количеству. [7]

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

Эффективность использования матричных ( параллельных) ВС зависит от возможностей распараллеливания программ ( параллельное программирование), что во многих случаях связано с большими трудностями. [10]

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

Спекулятивный параллелизм представляет собой такую парадигму, когда делаются некоторые допущения, способствующие распараллеливанию программы . [13]

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

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

1.1 Параллельное программирование. 3

1.2 Автоматизация распараллеливания. 5

1.3 Статический анализ. 6

1.4 Динамический анализ. 8

1.5 Распараллеливание во время выполнения. 9

1.6 Цель работы.. 10

2 Постановка задачи. 11

2.1 Зависимости по данным. 11

2.2 Система автоматизации распараллеливания. 12

2.3 Задача анализатора. 13

3 Динамический анализ. 14

3.1 Схема работы динамического анализатора. 14

3.2 Динамический анализ с использованием дерева контекстов. 15

3.3 Динамический анализ с использованием глобальных номеров итераций. 17

3.4 Преимущества и недостатки динамического анализа. 19

4 Практическая реализация. 22

4.1 Инструментация. 22

4.2 Формат результатов. 24

4.3 Внутреннее устройство анализатора. 26

4.4 Результаты тестирования. 28

5 Заключение. 30

6 Литература. 31

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

1.1 Параллельное программирование

Параллельным программированием будем называть процесс написания программы для многопроцессорной системы. Разумеется, параллельное программирование имеет ряд особенностей по сравнению с традиционным последовательным программированием. Кроме того, в зависимости от типа многопроцессорной системы применяются различные средства программирования:

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

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

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

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

1.2 Автоматизация распараллеливания

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

Процесс распараллеливания можно разделить на две части:

Анализ исходной программы.

Синтез параллельной программы.

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

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

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

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

Другим примером системы автоматизации распараллеливания может служить проект V-Ray [2]. Эта система включает статический анализ структуры программы и информационных зависимостей, присутствующих в программе, а также динамический анализ параллельных программ. Система позволяет оптимизировать существующие программы, а также получить эффективные реализации программ для различных аппаратных платформ путем анализа лежащего в основе программ алгоритмического подхода.

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

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

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

Анализ технического задания

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

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

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

Четвертым пунктом я избрал Модели связи и архитектуру памяти, т.к. это дает общее представление о процессах происходящих на физическом уровне.

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

2 Многопроцессорные системы

2.1 Описание многопроцессорных систем

2.2 Общие требования, предъявляемые к многопроцессорным

Отношение стоимость / производительность. Появление любого нового направления в вычислительной технике определяется требованиями компьютерного рынка. Поэтому у разработчиков компьютеров нет одной единственной цели. Большая универсальная вычислительная машина (мейнфрейм) или суперкомпьютер стоят дорого. Для достижения поставленных целей при проектировании высокопроизводительных конструкций приходится игнорировать стоимостные характеристики. Суперкомпьютеры фирмы Cray Research и высокопроизводительные мейнфреймы компании IBM относятся именно к этой категории компьютеров. Другим крайним примером может служить низкостоимостная конструкция, где производительность принесена в жертву для достижения низкой стоимости. К этому направлению относятся персональные компьютеры различных клонов IBM PC. Между этими двумя крайними направлениями находятся конструкции, основанные на отношении стоимость/ производительность, в которых разработчики находят баланс между стоимостными параметрами и производительностью. Типичными примерами такого рода компьютеров являются миникомпьютеры и рабочие станции.

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

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

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

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

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

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

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

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

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

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

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

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

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

Универсальные приборы, эквивалентные по значению транзистору, которые создаются на тонких кремниевых пластинках СБИС, в настоящее время так миниатюрны и дешевы, что чрезвычайно большое число процессоров может быть объединено в единую сеть. В 1978г. 100. 000 элементов было успешно интегрировано в ЗУ объемом 64Кбит. В 1981г. фирма Hewlett-Packard объявила о создании микропроцессорного кристалла, содержащего 450. 000 элементов. Следовательно, многопроцессорные компьютеры "среднего класса" с числом кристаллов от нескольких тысяч и до нескольких миллионов скоро станут реальностью. Т. е. отдельный компьютер может содержать 10 х 10 =10 элементов .

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

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

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

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

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

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

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

Читайте также: