Методы повышения быстродействия

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

 

1. За счет повышения быстродействия элементной базы (тактовой частоты). Быстродействие процессора растет пропорционально росту тактовой час-

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

2. За счет увеличения числа одновременно работающих в одной задаче

ЭВМ, процессоров, АЛУ, умножителей и так далее, то есть за счет параллелизма выполнения операций. Это требует использования сложных систем параллельного программирования. Это крупный недостаток метода.

 

Параллельные системы по архитектуре разделяются на два класса:

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

• Параллельные системы, когда множество команд одной программы одновременно выполняются множеством АЛУ или процессоров.

Рассмотрим примеры этих методов.

Тактовая частота (рис.1.1). Тактовая частота зависит от размеров конст-

руктива, кристалла, на котором расположены арифметико-логические элемен-

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

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

Конвейерные системы. Для примера рассмотрим конвейер команд известного микропоцессора Pentium.

Он содержит следующие ступени:

• ступень предвыборки PF (Prefetch), которая осуществляет упреждающую

выборку группы команд в соответствующий буфер;

• ступень декодирования полей команды D1 (Decoder 1);

• ступень декодирования D2 (Decoder 2), на которой производится вычисление абсолютного адреса операнда, если операнд расположен в памяти;

• на ступени исполнения EXE (Execution) производится выборка операндов из РОН или памяти и выполнение операции в АЛУ;

• на ступени записи результата WR (Write Back) производится передача полученного результата далее.

 

В таком конвейере на разных ступенях выполнения находится 5 команд.

После очередного такта на выходе конвейера получается новый результат (ка-

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

действие микропроцессора возрастает в 5 раз.

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

 

 

ЛЕКЦИЯ 2.

Параллелельные системы. Параллельная машина содержит множество

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

 

В параллельных ЭВМ межпроцессорный обмен данными является прин-

ципиальной необходимостью, и при медленном обмене однопроцессорный ва-

риант может оказаться быстрее многопроцессорного, поэтому количество про-

цессоров в параллельной ЭВМ определяется скоростью сетей обмена.

 

Формы параллелизма

Параллелизм — это возможность одновременного выполнения более од-

ной арифметико-логической операции или программной ветви. Возможность

параллельного выполнения этих операций определяется правилом Рассела, ко-

торое состоит в следующем:

Программные объекты A и B (команды, операторы, программы) являются

независимыми и могут выполняться параллельно, если выполняется следующее

условие:

(InB OutA) (InA OutB) (OutA OutB) = Ø, (1.1)

 

где In(A) — набор входных, а Out(A) — набор выходных переменных объекта

A. Если условие (1.1) не выполняется, то между A и B существует зависимость

и они не могут выполняться параллельно.

Если условие (1.1) нарушается в первом терме, то такая зависимость назы

вается прямой. Приведем пример:

A: R = R1 + R2

B: Z = R + C

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

Если условие нарушено во втором терме, то такая зависимость называется обратной:

A: R = R1 + R2

B: R1 = C1 + C2

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

Если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной:

A: R = R1 + R2

B: R = C1 + C2

Здесь одновременное выполнение дает неопределенный результат.

Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей.

Наиболее общей формой представления этих зависимостей является ин-

формационный граф задачи (ИГ). Пример ИГ, описывающего логику конкрет-

ной задачи, точнее порядок выполнения операций в задаче

В своей первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.

 

 

Более определенной формой представления параллелизма является яруснопараллельная форма (ЯПФ): алгоритм вычислений представляется в виде яру

сов, причем в нулевой ярус входят операторы (ветви), не зависящие друг от

друга, в первый ярус — операторы, зависящие только от нулевого яруса, во

второй — от первого яруса и т. д.

Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: b i — ширина i -го яруса; B — ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из b i, i = 1, 2,...); li — длина яруса (время операций) и L длина графа; ε — коэффициент заполнения ярусов; θ — коэффициент разброса указанных параметров и т. д.

Главной задачей настоящего издания является изучение связи между клас

сами задач и классами параллельных ЭВМ. Форма параллелизма обычно достаточно просто характеризует некоторый класс прикладных задач и предъявляет

определенные требования к структуре, необходимой для решения этого класса

задач параллельной ЭВМ.

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

дующие основные формы параллелизма:

• Мелкозернистый параллелизм (он же параллелизм смежных операций или скалярный параллелизм).

• Крупнозернистый параллелизм, который включает: векторный паралле-

лизм и параллелизм независимых ветвей..

 

Мелкозернистый параллелизм ( Fine Grain)

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

нении (i - 2)-й или (i - 3)-й операции. Тогда при соответствующем построении

вычислительной системы можно совместить во времени выполнение i -й опера-

ции с выполнением (i - 1)-й, (i - 2)-й,... операций. В таком понимании скаляр-

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

отличаются длиной ветвей и требуют разных вычислительных систем.

Рассмотрим пример. Пусть имеется программа для расчета ширины запрещенной зоны транзистора, и в этой программе есть участок — определение

энергии примесей по формуле

 

Тогда последовательная программа для вычисления E будет такой:

F1 = M * Q ** 4* P ** 2

F2 = 8 * E0 ** 2* E ** 2 * H** 2

E = F1/F2

Здесь имеется параллелизм, но при записи на Фортране или Ассемблере у нас нет возможности явно отразить его. Явное представление параллелизма для вычисления E задается ЯПФ

Ширина параллелизма первого яруса этой ЯПФ (первый такт) сильно зависит от числа операций, включаемых в состав ЯПФ. Так, в примере для l 1 = 4 параллелизм первого такта равен двум, для l 1 = 12 параллелизм равен пяти.

Поскольку это параллелизм очень коротких ветвей и с помощью операторов

FORK и JOIN описан быть не может (вся программа будет состоять в основ

ном из этих операторов), данный вид параллелизма должен автоматически вы-

являться аппаратурой ЭВМ в процессе выполнения машинной программы.

 

q

 

 

Для скалярного параллелизма часто используют термин мелкозернистый

параллелизм (МЗП), в отличие от крупнозернистого параллелизма (КЗП), к ко-

торому относят векторный параллелизм и параллелизм независимых ветвей.