Принципы организации параллелизма выполнения машинных команд в процессорах (стр. 11 из 11)
Джин Амдал (GeneAmdahl) — один из разработчиков всемирно известной системы IBM 360, в своей работе, опубликованной в 1967 году, предложил формулу, отражающую зависимость ускорения вычислений, достигаемого на многопроцессорной ВС, от числа процессоров и соотношения между последовательной и параллельной частями программы. Показателем сокращения времени вычислений служит такая метрика, как «ускорение». Напомним, что ускорение S— это отношение времени Ts, затрачиваемого на проведение вычислений на однопроцессорной ВС (в варианте наилучшего последовательного алгоритма), ко времени Тр решения той же задачи на параллельной системе (при использовании наилучшего параллельного алгоритма):
Оговорки относительно алгоритмов решения задачи сделаны, чтобы подчеркнуть тот факт, что для последовательного и параллельного решения лучшими могут оказаться разные реализации, а при оценке ускорения необходимо исходить именно из наилучших алгоритмов.
Проблема рассматривалась Амдалом в следующей постановке (рисунок 7.1). Прежде всего, объем решаемой задачи с изменением числа процессоров, участвующих в ее решении, остается неизменным. Программный код решаемой задачи состоит из двух частей: последовательной и распараллеливаемой. Обозначим долю операций, которые должны выполняться последовательно одним из процессоров, через f, где 0
f 1 (здесь доля понимается не по числу строк кода, а по числу реально выполняемых операций). Отсюда доля, приходящаяся на распараллеливаемую часть программы, составит 1-f. Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Распараллеливаемая часть программы равномерно распределяется по всем процессорам.С учетом приведенной формулировки имеем:
В результате получаем формулу Амдала, выражающую ускорение, которое может быть достигнуто на системе из nпроцессоров:
Формула выражает простую и обладающую большой общностью зависимость. Характер зависимости ускорения от числа процессоров и доли последовательной части программы показан на рисунке 7.2.
Если устремить число процессоров к бесконечности, то в пределе получаем:
Это означает, что если в программе 10% последовательных операций (то есть f=0,1), то, сколько бы процессоров ни использовалось, убыстрения работы программы более чем в десять раз никак ни получить, да и то, 10 — это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных факторов нет. Следует отметить, что распараллеливание ведет к определенным издержкам, которых нет при последовательном выполнении программы. В качестве примера таких издержек можно упомянуть дополнительные операции, связанные с распределением программ по процессорам, обмен информацией между процессорами [4].
Решая на вычислительной системе из 1024 процессоров три больших задачи, для которых доля последовательного кода f лежала в пределах от 0,4 до 0,8%, Джон Густафсон из NASAAmesResearchполучил значения ускорения по сравнению с однопроцессорным вариантом, равные соответственно 1021,1020 и 1016. Согласно закону Амдала для данного числа процессоров и диапазона f, ускорение не должно было превысить величины порядка 201. Пытаясь объяснить это явление, Густафсон пришел к выводу, что причина кроется в исходной предпосылке, лежащей в основе закона Амдала: увеличение числа процессоров не сопровождается увеличением объема решаемой задачи. Реальное же поведение пользователей существенно отличается от такого представления. Обычно, получая в свое распоряжение более мощную систему, пользователь не стремится сократить время вычислений, а, сохраняя его практически неизменным, старается пропорционально мощности ВС увеличить объем решаемой задачи. И тут оказывается, что наращивание общего объема программы касается главным образом распараллеливаемой части программы. Это ведет к сокращению значения f. Примером может служить решение дифференциального уравнения в частных производных. Если доля последовательного кода составляет 10% для 1000 узловых точек, то для 100 000 точек доля последовательного кода снизится до 0,1%. Сказанное иллюстрирует рисунок 7.3, который отражает тот факт, что, оставаясь практически неизменной, последовательная часть в общем объеме увеличенной программы имеет уже меньший удельный вес.
Было отмечено, что в первом приближении объем работы, которая может быть произведена параллельно, возрастает линейно с ростом числа процессоров в системе. Для того чтобы оценить возможность ускорения вычислений, когда объем последних увеличивается с ростом количества процессоров в системе (при постоянстве общего времени вычислений), Густафсон рекомендует использовать выражение, предложенное Е. Барсисом (Е. Barsis):
Данное выражение известно как закон масштабируемого ускорения или закон Густафсона (иногда его называют также законом Густафсона-Барсиса). В заключение отметим, что закон Густафсона не противоречит закону Амдала. Различие состоит лишь в форме утилизации дополнительной мощности ВС, возникающей при увеличении числа процессоров [4].
Развитие вычислительной техники характеризуется тем, что на каждом этапе новых разработок требования к производительности значительно превышают возможности элементной базы.
Это обусловлено задачами сложных систем управления в реальном времени, централизованным решением задач в сетях, имитационным моделированием сложных процессов (например, в ядерной физике), оперативным планированием и управлением. Такие задачи требуют концентрации вычислительных мощностей, постоянно поддерживая высокую актуальность проблемы создания супер-ЭВМ.
Добиваться повышения производительности компьютеров только за счет увеличения тактовой частоты становится все сложнее, так как появляется проблема отвода тепла. Поэтому разработчики обратили свое внимание на параллелизм как на средство ускорения вычислений. Параллелизм может вводиться на разных уровнях, как на самых нижних, где элементы очень жестко связаны друг с другом, так и на верхних, где связи весьма слабые.
Параллелизм на уровне команд имеет место, когда обработка нескольких команд или выполнение различных этапов одной и той же команды может перекрываться во времени. Разработчики вычислительной техники прибегают к методам, известным под общим названием «совмещения операций», при котором аппаратура ВМ в любой момент времени выполняет одновременно более одной операции.
В работе мы рассмотрели принципы организации параллелизма на уровне команд, ознакомились с работой конвейера, суперскалярного конвейера, матричного процессора, убедились в том, что параллелизм – эффективный способ повышения производительности при неизменной тактовой частоте процессора.
1. Корнеев В.В. Вычислительные системы.-М.:Гелиос APB, 2004.-512с., ил.- с. 34-46
2. Таненбаум, Э. Архитектуракомпьютера/Пер. сангл.- 4-е изд. Учебник для вузов.-СПб.: Питер, 2003 698 с. : ил.
3. Барский А.Б. Параллельные информационные технологии: Учебное пособие/А.Б. Барский.-М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007.-503 с.: ил.,таб.-(серия «Основы информационных технологий»)- с.20-28, с.56-58.
4. Цилькер, Б. Я. Организация ЭВМ и систем : Учебник для вузов.-СПб.: Питер, 2007.-668с.: ил- с. 481-492
5. Куприянов М.С., Петров Г.А., Пузанков Д.В. Процессор Pentium: Архитектура и программирование. /ГЭТУ-СПб., 1995.-277с -с. 11-17
6. Гук М, Юров В. Процессоры Pentium 4, Atlon и Duron.-СПб.: Питер, 2001.-512 с.: ил- с. 42-46
7. Головкин Б.А. Параллельные вычислительные системы. - М.: Наука, 1980. - 518 с.
8. Шпаковский Г.И. Архитектура параллельных ЭВМ: Учеб. пособие для вузов. - Мн.: Университетское, 1989. - 192 с.
9. Коуги П.М. Архитектура конвейерных ЭВМ / Пер. с англ. - М.: Радио и связь, 1985. - 360 с.
10. Хокни З., Джессхоуп К. Параллельные ЭВМ. - М.: Радио и связь, 1986. - 389 с.
11. http://www.tver.mesi.ru/e-lib/res/628/11/2.html - Интернет-университет информационных технологий - дистанционное образование