ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

Область техники.

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

Предшествующий уровень техники.

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

Наиболее близким аналогом по совокупности существенных признаков к заявляемому изобретению является способ определения структуры гибридной вычислительной системы MIMD-SIMD (см. www.elsevier.com/locate/parco Parallel Computing 29 (2003) 21-36, MIMD- SIMD hybrid system— towards a new low cost parallel system, Leo Chin Sim, Heiko Schroder, Graham Leedham). Способ включает измерение длительности Т| получения решения задачи посредством выполнения программы одним процессором, измерение длительностей Т _м и T _s (в аналоге Т] и Т _S IMD соответственно) исполнения MIMD и SIMD фрагментов программы одним процессором и одним ускорителем соответственно, определение удельного ускорения р { в аналоге X) длительности выполнения SIMD фрагмента одним ускорителем по сравнению с длительностью выполнения этого фрагмента одним процессором и на основе полученных данных изменение количества ускорителей, входящих в структуру гибридной вычислительной системы, и оценку значения коэффициента ускорения вычислений, достигаемого этой системой.

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

Раскрытие изобретения.

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

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

Данный технический результат достигается тем, что в заявляемом способе определения структуры гибридной вычислительной системы, содержащей MIMD-компоненту, состоящую по крайней мере из одного процессора, и SIMD-компоненту, состоящую по крайней мере из одного ускорителя, включающем измерение длительности Ti получения решения задачи посредством выполнения программы одним процессором, измерение длительностей Т _м и T _s исполнения MIMD и SIMD фрагментов программы одним процессором и одним ускорителем соответственно, определение удельного ускорения р длительности выполнения SIMD фрагмента программы одним ускорителем по сравнению с длительностью выполнения этого фрагмента одним процессором и на основании полученных данных изменение количества процессоров, либо количества ускорителей, входящих в структуру гибридной вычислительной системы, в отличие от прототипа определяют долю φ длительности выполнения MIMD-фрагмента одним процессором и долю \ - φ длительности выполнения SIMD-фрагмента одним процессором относительно длительности выполнения программы одним процессором, сравнивают отношение доли длительности выполнения SIMD фрагмента одним процессором к доле длительности выполнения MIMD фрагмента одним

(1 - 0 7

процессором с величиной удельного ускорения р = -— длительности выполнения SIMD фрагмента одним ускорителем по сравнению с длительностью выполнения SIMD фрагмента одним процессором, при этом при р >-— - увеличивают количество процессоров MIMD

Ψ компоненты, а при р <-—— увеличивают количество ускорителей SIMD

Ψ

компоненты.

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

Краткое описание чертежей.

На фиг. 1- приведена структура гибридной вычислительной системы; на фиг. 2 - приведена схема определения доли длительности выполнения MIMD фрагмента и доли SIMD фрагмента и ускорения вычислений на этих фрагментах; на фиг.З -на приведена таблица 1 с оценками длительностей вычислений; фиг. 4— в таблице 2 приведены значения коэффициентов ускорения.

Осуществление изобретения.

Гибридная вычислительная система содержит q процессоров 1, образующих MIMD компоненту и выполняющих MIMD фрагмент программы вычислений, и г арифметических ускорителей 2, образующих SIMD компоненту и выполняющих SIMD фрагмент программы вычислений.

В качестве MIMD компоненты могут применяться любые вычислительные системы класса MIMD; процессор MIMD компоненты _ отдельный процессорный элемент системы класса MIMD [Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г.]

Примерами SIMD компонент, которые могут быть использованы при реализации способа, являются общеизвестные арифметические ускорители фирм NVIDIA и AMD, процессоры Cell фирмы IBM, ClearSpeed фирмы Intel, а также арифметический ускоритель Systola 1024, используемый в наиболее близком аналоге. Их общей чертой является наличие большого количества «простых» арифметических устройств, имеющих в совокупности существенно большую по сравнению с процессором производительность, достигаемую на специфичных фрагментах программ.

Для осуществления заявляемого способа:

-Измеряют системным таймером длительность Т требуемую для получения решения задачи посредством выполнения всей программы одним процессором.

-Измеряют системным таймером длительность Т _м выполнения MIMD фрагмента одним процессором.

-Измеряют системным таймером длительность T _s выполнения SIMD фрагмента одним ускорителем.

-Из полученных значений определяют долю длительности

Т

выполнения MIMD фрагмента φ = - ^Μ - , и величину удельного ускорения

(ΐ -^

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

Если р > -—— , то в вычислительной системе увеличивают количество φ процессоров. Если р < -— - , то увеличивают количество ускорителей.

φ

Работоспособность заявляемого способа подтверждается следующими соотношениями, которые излагаются применительно к распараллеливанию методом умножения для постоянного размера задачи (закон Густафсона, [см. например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г. стр.488-490]) и применительно к распраллеливанию методом деления измеряемого размера задачи (закон Амдаля [см. например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г. стр. 486-488]).

Для решения задачи одним процессором требуется интервал длительностью 7^ .

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

Т _\,\ - т _м + T _Si ^ где Т _м - Τ,φ - длительность выполнения MIMD фрагмента одним процессором;

0 < φ < 1 - доля длительности MIMD фрагмента;

Т

T _s = (1-φ)— - длительность выполнения SIMD фрагмента одним

Р

ускорителем ;

р > 1 - удельное ускорение длительности выполнения SIMD фрагмента, достигаемое применением ускорителя, по сравнению с процессором.

Изложенная декомпозиция вычислительного процесса применительно к распараллеливанию методом деления для q процессоров 1 и одного ускорителя 2 представлена на фиг.2.

Длительность вычислений в режиме умножения системой, содержащей q процессоров 1 и один ускоритель 2, вычисляется по формуле

f _q,x =T _x -<p + T,-{\-q>).±

Р (2)

Если система содержит 1 процессор 1 и г ускорителей 2,

ί; _Γ = 7;.ρτ + 7;.(ΐ-ρ)·-.

Р (3)

б деления системой, содержащей q процессоров 1 , один ускоритель 2 и, соответственно, один процессор 1 и г ускорителей 2.

Оценки длительностей вычислений сведены в таблице 1.

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

Коэффициент ускорения в режиме умножения системой, содержащей q процессоров 1 и один ускоритель 2, вычисляют по формуле

7 чл

Подставляя

Τ _4Λ = Τφ + Τ {\ - φ)- (5) в формулу (4) находим

Ψ + ( 1 - φ ) ^- Р

Очевидно, при q -» оо имеем максимальное значение К , = Р

' * ¹ \ - _φ

Чтобы выполнялось К _ц > q (то есть, чтобы применение ускорителей

2 имело смысл по сравнению с простым увеличением количества процессоров 1), необходимо выполнение условия процессоров 1), необходимо выполнение условия

(7)

Р

Это достигается, если q < р .

Для системы, содержащей один процессор и г ускорителей, коэффициент ускорения вычисляют по формуле

Очевидно К _г =— при г -» со .

^' Ψ

1 \ - φ

Значение K _{l r} > r , если г <

φ φρ

Коэффициент ускорения для системы, содержащей q процессоров и г

15

ускорителей, при q=r вычисляют по формуле

К ^Т] = ^q

Р Р

В общем случае К , = К _т , , если q>r, где т = - и К = К _{] п} , если q<r,

г

г

- _п где « =— ; полагаем, что q и таковы, что т или п - целые.

и q

Оценим условия, при которых f _{4 i} < f _{] (/} то есть увеличение количества процессоров 1 целесообразнее увеличения количества ускорителей 2.

Очевидно, для этого необходимо выполнение неравенства: 7 + , (1 - φ)— < 7 q + Т _х (1 - φ) - (10)

Р Р '

которое выполняется, если _р > ^L .

φ

Если р - ^{1 ~} Ψ .то увеличение количества процессоров, либо φ

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

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

Коэффициент ускорения в режиме деления системой, содержащей q процессоров и один ускоритель, вычисляется по формуле

Т,

_{Г] + Г| (1} _ ^) 1 (Н)

Я Р

Получаем

φ + (\ - φ)- ( 12)

Р

При q -> со имеем наибольшее значение

( 13)

При р >q выполняется > q

Для системы, содержащей один процессор и г ускорителей, получаем ^{l r} ₌ 1 ₌ ^Г \-φ

rp p

При r oo имеем

(15) φ

Значение < г, если

1 \-φ

г < - φ φ-ρ (16)

Коэффициент ускорения Ж достигаемый системой, содержащей q процессоров и г ускорителей при q=r , вычисляется по формуле

(17)

<р +

Р

Очевидно, K _{q r} = K _m , если q>r, где т = - и _{ц г} = M _{] fl} , если q<r, где п =— ; полагаем, что q иг таковы, что т или п - целые.

ч

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

Τ^ + Τ( -φ)-<Τφ + Τ _ι ^] -^- (18) q р ЧР ^' ю Τ ?- + Τ {\ - φ) - < Τ φ + Τ— ¹ ¥- (18)

q p q ^'

Это справедливо, если p > -—— .

φ

Если р = ^ ^{~ φ} ,το увеличение количества процессоров, либо

φ

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

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

Полученные для режимов умножения и деления коэффициенты ускорения вычислений приведены в таблице 2.

Отметим идентичность этих коэффициентов для обоих режимов при одинаковом количественном и качественном составе вычислителей. Для обоих режимов целесообразно увеличивать количество задействованных процессоров, если выполняется _р > ^{1 ~~ φ} .

φ

Пример осуществления способа

Определим структуру гибридной вычислительной системы для решения задачи определения значений потенциала Морзе, используемых в молекулярной динамике _^

Длительность вычислений одним процессором для задачи размером 55x55x55 периодов кристаллической решетки была измерена системным таймером, она составила Τι =22,98 с. Распараллеливание выполнялось в режиме умножения. Определяем для этой же задачи системным таймером длительность вычисления гибридной системой, содержащей q=l процессоров и г=1 ускоритель, она составила при этом длительность выполнения MIMD фрагмента одним процессором составила Т _м =7,05с, а длительность выполнения SIMD фрагмента одним ускорителем составила Т _§ =2,80 с. т

Из измеренных значении определяем «^ .^ - о з! ^и

Т _* '

(1 -^ _^

Т,

Поскольку р > zJ_ , то в структуре гибридной системы для этой φ

программы целесообразно увеличить количество процессоров.

Например, если в этой системе применить q=2 процессоров и г=1 ускоритель, то согласно (2) получаем Т _{2 1} = 12,70с . Измеренное системным таймером экспериментальное значение Т _{2 л} = 13,22с .

Соответствующие теоретическое и экспериментальное значения коэффициентов ускорения К ₂ « 3,70 и К ₂ , « 3,76

Если для решения этой задачи применить, следуя прототипу, гибридную систему, содержащую q=l процессор и г=2 ускорителей, то Г _{1 2} = 16,9с , К ₁₂ = 2,7 .

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

Аналогично, используя (2) и (6) и экспериментальные данные, можно показать, что гибридная система, содержащая q=4 процессора и г=1 ускоритель, позволяет решить указанную задачу в 1 ,67 раза быстрее по сравнению с системой из q=l процессора и г=4 ускорителей, построенной ранее известным способом.

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

Таблица 1 - Оценки длительностей вычислений

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Таблица 2 - Значения коэффициентов ускорения

. 15

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26)