Параллелизм как основа высокопроизводительных вычислений - Реферат

Распишем процесс поподробнее, введем туда тактовую частоту: Первая часть полученного произведения - количество инструкций, выполняемых за один такт, вторая - количество тактов процессора в единицу времени, тактовая частота. Таким образом, для увеличения производительности нужно или поднимать тактовую частоту или увеличивать количество инструкций, выполняемых за один такт. Так, например, при выполнении простейшей программы a = 1 b = 2 c = a b операции присвоения можно выполнять одновременно, за один такт, следовательно, программа выполняется не за три шага, а за два. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, STMD, MIMD. Представителями этого класса являются, прежде всего, классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда инициирует одну операцию с одним потоком данных.Методы и средства реализации параллелизма зависят от того, на каком уровне он должен обеспечиваться. Этот уровень реализуется на ВС с множеством процессоров в многозадачном режиме. Части одной задачи выполняются па множестве процессоров. Данный уровень достигается на параллельных ВС. Определим понятия крупнозернистого (coarse grained), среднезернистого (medium grained) и мелкозернистого (fine grained) параллелизма.Основным средством реализации параллелизма на уровне заданий служат многопроцессорные и многомашинные вычислительные системы, в которых задания распределяются по отдельным процессорам или машинам. Однако, если трактовать каждое задание как совокупность независимых задач, реализация данного уровня возможна и в рамках однопроцессорной ВС. Когда выполняемое задание требует ввода/вывода, такая операция запускается, а до ее завершения остальные ресурсы ВС передаются другому заданию. По завершении ввода/вывода ресурсы ВС возвращаются заданию, инициировавшему эту операцию. ВС обрабатывает задания, классифицируемые как малое (S), среднее (М) и большое (L), Для выполнения малых заданий требуется один, средних - два, а больших заданий - четыре процессора.О параллелизме на уровне программы имеет смысл говорить в двух случаях. Во-первых, когда в программе могут быть выделены независимые участки, которые допустимо выполнять параллельно. Пусть имеется робот, запрограммированный на обнаружение электрических розеток, когда уровень напряжения в его аккумуляторах падает. В процесс вовлечены три подсистемы робота: зрение, манипуляция и движение. Каждая подсистема управляется своим процессором, то есть подсистемы при выполнении разных действий способны работать параллельно.Параллелизм на уровне команд имеет место, когда обработка нескольких команд или выполнение различных этапов одной и той же команды может перекрываться во времени. Разработчики вычислительной техники издавна прибегали к методам, известным под общим названием «совмещения операций», при котором аппаратура ВМ в любой момент времени выполняет одновременно более одной операции.Параллельные вычисления весьма специфичны, поэтому для оценки их эффективности имеются специальные характеристики. Одной из таких характеристик является профиль параллелизма программы - функция времени, являющаяся графическим представлением числа параллельно выполняющих задачу процессоров многопроцессорной системы. Это число называют степенью параллелизма и обозначают D(t) (или DOP, Degree Of Parallelism). Предположим, что система состоит из n процессоров, максимальный параллелизм в профиле равен m и в идеале n>>m.Ряд исследователей высказывают свои сомнения о возможности широкого практического применения параллельных вычислений в силу следующего набора причин: Высокая стоимость параллельных систем;Как правило, в каждой программе имеется фрагмент кода, который принципиально должен выполняться последовательно и только одним из процессоров. Это может быть часть программы, отвечающая за запуск задачи и распределение распараллеленного кода по процессорам, либо фрагмент программы, обеспечивающий операции ввода/вывода. Здесь идеальным был бы вариант, когда параллельные ветви программы постоянно загружали бы все процессоры системы, причем так, чтобы нагрузка на каждый процессор была одинакова. Джин Амдал (Gene Amdahl) - один из разработчиков всемирно известной Системы IBM 360, в своей работе, опубликованной в 1967 году, предложил формулу, отражающую зависимость ускорения вычислений, достигаемого на многопроцессорной ВС, от числа процессоров и соотношения между последовательной и параллельной частями программы. Обозначим долю операций, которые должны выполняться последовательно одним из процессоров, через f, где 0 <=f<= 1 (здесь доля понимается не по числу строк кода, а по числу реально выполняемых операций).Известную долю оптимизма в оценку, даваемую законом Амдала, вносят исследования, проведенные Джоном Густафсоном из NASA Ames Research. Решая на вычислительной системе из 1024 процессоров три больших задачи, для которых доля последовательного кода/лежала в предела

Содержание

Введение

1. Параллелизм

1.1 Уровни параллелизма

1.2 Параллелизм уровня задания

1.3 Параллелизм уровня программ

1.4 Параллелизм уровня команд

1.5 Профиль параллелизма программы

2. Недостатки и ограничения параллелизма

2.1 Закон Амдала

2.2 Закон Густафсона

2.3 Закон Гроша

2.4 Гипотеза Минского

Заключение

Список литературы

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

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

Возьмем самую общую формулу производительности:

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

Распишем процесс поподробнее, введем туда тактовую частоту:

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

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

Как уже было сказано выше, прием увеличения частоты не оправдал себя. В связи с этим начал использоваться прием параллелизма - прием, при котором несколько инструкций выполняются за один такт параллельно. Так, например, при выполнении простейшей программы a = 1 b = 2 c = a b операции присвоения можно выполнять одновременно, за один такт, следовательно, программа выполняется не за три шага, а за два.

Классификация параллельных вычислительных систем

Среди всех рассматриваемых систем классификации ВС наибольшее признание получила классификация, предложенная в 1966 году М. Флинном. В ее основу положено понятие потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, STMD, MIMD.

SISD

SISD (Single Instruction Stream/Single Data Stream) - одиночный поток команд и одиночный поток данных (рис. 1, а). Представителями этого класса являются, прежде всего, классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда инициирует одну операцию с одним потоком данных. То, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка, не имеет значения, поэтому в класс SISD одновременно попадают как ВМ CDC 6000 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными. Некоторые специалисты считают, что к SISD-системам можно причислить и векторно-конвейерные ВС, если рассматривать вектор как неделимый элемент данных для соответствующей команды.

MISD

MISD (Multiple Instruction Stream/Single Data Stream) - множественный поток" команд и одиночный поток данных (рис. 1, б). Из определения следует, что в архитектуре ВС присутствует множество процессоров, обрабатывающих один и тот же поток данных. Примером могла бы служить ВС, на процессоры которой подается искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с помощью своего алгоритма фильтрации. Тем не менее ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не сумели представить убедительный пример реально существующей вычислительной системы, построенной изданном принципе. Ряд исследователей относят к данному классу конвейерные системы, однако это не нашло окончательного признанияю. Отсюда принято считать, что пока данный класс пуст. Наличие пустого класса не следует считать недостатком классификации Флинна. Такие классы, по мнению некоторых исследователей, могут стать чрезвычайно полезными для разработки принципиально новых концепций в теории и практике построения вычислительных систем.

Рис. 1. Архитектура вычислительных систем по Флинну: а - SISD; б - MISD; в-SIMD; г- MIMD

SIMD

SIMD (Single Instruction Stream/Multiple Data Stream) - одиночный поток команд и множественный поток данных (рис. 1, в). ВМ данной архитектуры позволяют выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Бесспорными представителями класса SIMD считаются матрицы процессоров, где единое управляющее устройство контролирует множество процессорных элементов. Все процессорные элементы получают от устройства управления одинаковую команду и выполняют ее над своими локальными данными В принципе в этот класс можно включить и векторно-конвейерные ВС, если каждый элемент вектора рассматривать как отдельный элемент потока данных.

MIMD

MIMD (Multiple Instruction Stream/Multiple Data Stream) - множественный поток команд в множественный поток данных (рис. 1, г). Класс предполагает наличие в вычислительной системе множества устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, ранее упоминавшиеся векторно-конвейерные ВС можно вполне отнести и к классу MIMD, если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) над множественным скалярным потоком.

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