Оценки ускорения вычислений гибридными реконфигурируемыми системами

УДК 519.6

С.А. Степаненко

ОЦЕНКИ УСКОРЕНИЯ ВЫЧИСЛЕНИЙ ГИБРИДНЫМИ РЕКОНФИГУРИРУЕМЫМИ СИСТЕМАМИ

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

Гибридные вычислительные системы; MIMD-компонент; SIMD-компонент; рекон-фигурируемые системы.

S.A. Stepanenko

SPEEDUP PREDICTIONS FROM HYBRID RECONFIGURABLE SYSTEMS

This paper presents speedup predictions for a reconfigurable hybrid computing system containing a fixed number of processor cores and accelerators and switching components to vary connections between the processor cores and accelerators. Maximum acceleration criteria for given values of initial process parameters are specified. As distinct from FPGA-based reconfigurable systems, the systems considered in this paper contain only two components: a MIMD-component, being a set of universal processor cores, and a SIMD-component, being a set of arithmetic accelerators. Restricting the types of components to these two computing structures makes it possible to considerably simplify the algorithm of decomposition and reconfiguring. In particular, it resolves into (hardware- or software-) switched connection of processor cores and accelerators implemented based on the analysis of the values of initial process parameters. The relationships obtained show that if certain conditions are fulfilled, reconfiguring makes it possible to speed up the process of computations by hybrid systems significantly, but no more than by a factor of two, in comparison with non-reconfigurable systems. Vendors of computer components have established production of systems structurally identical to those studied in this paper. Application of the solutions proposed in the paper renders computing systems more efficient.

Hybrid computing system; MIMD-component; SIMD-component reconfigurable system.

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

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

Показаны зависимости коэффициентов ускорения вычислений гибридными системами от состава МГМБ- и SIMD-компонентов и первичных параметров вычислительного процесса.

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

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

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

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

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

Эта работа развивает и дополняет [1, 4]. В ней получены оценки ускорения, которое может быть достигнуто реконфигурируемой гибридной вычислительной системой, содержащей фиксированное количество процессорных ядер и ускорителей и средства коммутации, позволяющие варьировать соединениями ядер и ускорителей. Сформулированы критерии достижения максимального ускорения при заданных значениях первичных параметров вычислительного процесса.

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

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

1.1. Структура гибридного вычислителя. Гибридный вычислитель содержит q универсальных процессоров, реализующих МГМБ-вычисления, и г арифметических ускорителей; каждый ускоритель выполняет $ГМБ-вычисления. Структура гибридного вычислителя показана на рис. 1.

1 2 1  2D

л

2 ф к С m

• • с ^ •

• • I S S га Ü • •

q /L-N о ü

/1_К r

VV

MIMD

SIMD

Рис. 1. Структура реконфигурируемого вычислителя

Универсальные процессоры (точнее - ядра универсальных процессоров) образуют MIMD-компонент1. В качестве MIMD-компонента могут применяться вычислительные модули, содержащие универсальные одноядерные или многоядерные процессоры, SMP-системы или MPP-системы [6].

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

Программно-управляемый коммутатор позволяет соединять любые подмножества процессоров с любыми подмножествами ускорителей. Примером коммутатора является коммутатор PEX 8696, используемый фирмой Dell для реализации гибридных серверных блоков и позволяющий подключать и коммутировать 1, 2, 4, 8 и 16 ускорителей с несколькими (до восьми) вычислительными модулями [7].

1.2. Первичные параметры вычислительного процесса и длительности вычислений. Пусть решение задачи одним универсальным процессором требует интервал длительностью T1.

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

T = T + T

T 1,1 TM ^ T S '

где TM = Т1Ф

0 <ф< 1

длительность вычислений, выполняемых процессором,

доля вычислительного процесса, выполняемого универсальным про-

T

цессором (доля MIMD-фрагмента); T = (1 -ф) —

S Р

длительность вычислений,

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

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

Гибридный вычислитель из одного процессора и одного ядра называем элементарным вычислителем, а выполняемый им процесс - элементарным процессом.

В [1] получены оценки длительностей вычислений с указанными выше параметрами для режимов умножения и деления при различных М1МБ- и SIMD-компонентах. Эти оценки указаны в табл. 1.

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

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

Таблица1

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

Режим умножения Режим деления Состав вычислителя

Т*1 = Тр + Тх(1-р) а Р 7*1 = T Р + 71(1 -р)- q р q ядер, один ускоритель

1 Т1г = Тррг + Т1(1 -р)-Р 1 7 r = 7р+Ti(i-p)— гр одно ядро, г ускорителей

Т; = Т1(1 -р) £ р tr = 71Р + 71(1 -р)! ' И р q ядер, г ускорителей Г 1 а = —, М > 1 М

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

Таблица 2

Значения коэффициентов ускорения

Режим умножения Режим деления Состав вычислителя

г 4 <Р + (Х-Ф)-р К = р при а ^ да 1-р К, 1 > а при а < р К ,= а чл а р + (1 -р) а Р К = р при а ^ да аД 1 -р Ка, 1 > а при а < р q ядер, один ускоритель

Режим умножения Режим деления Состав вычислителя

~ г 1 — р pr +-- р К =1 при Г ^ ТО Р ~ ^ 1 — Р Kl > r при р >-1' 1 — pr r K1 r = 1 1 1 — p pr +--— P К = 1 при r r p fr ^ 1 — p Kr 1 > r при р>-1' 1 — pr одно ядро, r ускорителей

v 4 q ,q 1—p p+ р к q q,q 1—p p+ р q ядер, q ускорителей

~ ~ 1—p ~qi > к r при р> fr fr 1 — p к q 1 > K1 r при р > v q'1 1 r p q = r

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

режимов целесообразно увеличивать количество ядер, если р > 1—p.

p

2. Эффект реконфигурации

2.1. Оценки ускорения вычислений реконфигурируемыми гибридными средами. Пусть имеется вычислительная среда Sqq, содержащая q ядер и q ускорителей.

В [1] установлено, что вычислительный процесс с первичными параметрами p и р может быть выполнен этой системой в режиме умножения в течение интервала

f ] = Тгср + 7J (1 - ф) —, если задействованы q ядер и один ускоритель,

Р

либо

f = Tlp-q + Tl(l-p)—, если задействованы одно ядро и qускорителей, Р

либо

f =Т = Тер + 7(1-<р)—  если задействованы qядер иqускорителей.

м 1,1 1 1 р

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

к q к q к q

q1 n ,q' 1 q n Л' qq 1 —p

<p+ (1 — <p)— p- q + (1 — p)— p +--11

P P P

Наиболее «быстро» растущим является K , когда одновременно задейст-

q,q

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

Оценим возможности одновременного полного задействования оборудования

для этих вариантов и достижения большего по сравнению с к„„ ускорения вычис-

Ч' ч

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

Пусть гибридная система состоит из q ядер и q ускорителей. Полагаем, что эта система задействует ^-1) ядро и один ускоритель и выполняет в режиме умножения вычислительный процесс с параметрами р и р.

Для его выполнения этой системе понадобится интервал длительностью

Тну = Т (р+—(ч-1) ^

V р )

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

Т = Т

Т1,(ч-1) Т

р(Ч -1) -

\

Предположим, что оба процесса

Р J

выполняются

одновременно и

Т = Т = Т

Т(Ч-1), 1 Т1,(ч-1) Тя .

Повторим их q раз. В результате в течение интервала qTR будет выполнено 2q(q-1) элементарных вычислительных процессов.

Эти же вычислительные процессы потребуют интервала 2(q-1)Tq,q, если их выполнять, задействуя одновременно q ядер и q ускорителей, имеющихся в гибридной системе.

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

дТк < 2(ч -1)Т,ч,

т. е.

(

1 -р

Л

(

ЧТ р-—^(ч-1) <2(ч- 1)Т

V р )

Последнее выполняется, если

рр

р+

1 -р

Л

ч < 1 +

1 -р

Значение ускорения, достигаемое применением реконфигурации, можно оценить отношением

1(а кг 2(ч - 1)Т [р + ^ .

К = 2

чТ ч7 [р+^(ч-1)^ ч

где

р+

с =

1 -р р

р+^

< 1.

р

р

V

)

Таким образом, для заданного q, удовлетворяющего условию (1), ускорение, достигаемое рассматриваемой реконфигурацией, не превосходит 2 по отношению

к К

q. q

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

По сравнению с одним ядром универсального процессора ускорение, достигаемое реконфигурируемой системой, составляет

R

Подставляя Kq q и KR

q. q ,находим

Kq. q " KR •

Rq,q = 2-

q -1

p-

1 -p p

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

2.2. Критерии обратимости. Условием возможности задействования рассматриваемого механизма реконфигурации является выполнение равенства

T = T

1 (q-1). 1 11,

(q-1)•

Процесс, исполняемый (q-1) ядрами и одним ускорителем, назовем прямым, длительность его исполнения Т^.щ. Процесс, исполняемый одним ядром и ^-1) ускорителями, - обратный, его длительность Т1^-1). Подставляя выражения Т<11-1)л и Т1<ч-1), имеем

1

9 + i-S-(qV

Р

f

= 1

p2(q -1) -

1-P2 Р2

Л

В общем случае это равенство выполняется для разных Т и Т , р и р2,

Р1 и Р2 .

I

Если предположить, что Т = Т , т. е. оба процесса выполняются одним

ядром в течение одного интервала, то находим

г \ г

p+ ^-

Р

p2(q -1) +

1 -Р2 pi

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

1 -р

Р2 =

р1

Или

Р1 =

1 Р2 Р2

Если заданы значения параметров прямого процесса рфх и р , то из (4) находим р, а из (3) находим р .

3. Иллюстрации применения соотношений. Пример реконфигурируемой гибридной системы. Проиллюстрируем полученные соотношения.

Пусть Т = 100 с, Тг = 24 с, ^ = 20 с и Т5 = 4 с , тогда р= 0,2, Р1 = 20.

Поскольку р = 20 > 1 р = 4, увеличиваем количество ядер. р

Значения к и к для этого процесса приведены на рис. 2. Эффект реконфигурации достигается, если

ч < 1+рр^ = 6 .

к

1 -р

х 1 I 1 1 Л 1111

1 • ,

1 1

^^г^ 1 1.

1

-*-Ю,3=14,2 114.4=18.75

-115.5=22.2

-Кад К1,Ч

Рис. 2. Значения К ^ и К

0 8

Пусть q=4, тогда Т{д_ 1),1 = Т1(0,2 + -^3) = 0,32^ = Т^,. Находим из (4) р = ^^ = М = 0,04.

р1 20

(

Далее из

0,04 • 3-

1 - 0,04

Л

р2 )

В результате для Т = 100 с и q=4 получим

= 0,32 получаем р2 = 4,8.

Т(ч-цд = 100

( 1 -р ^ р + —р1 • 3

р

1 )

= 100 0,2 + — • 3 | = 32 с; 20

Тич-1) = 100

р2 • 3

1 -р2 р2

Л

= 1001 0,04• 3 + 096 1 = 100(0,12 + 0,2) = 32с.

Итак, обе задачи будут решены в течение 32 с, а набор из четырех пар этих задач - в течение 128 с.

Если решать задачи в линейном варианте гибридной системы, то первая за-

(

дача будет решена в течение Т4 4 = Т

р

1 -р

Л

р>

= 100• 0,24 = 24с .

1 )

Понадобится повторить ее трижды, всего на нее понадобится 72 с.

Вторая задача потребует Т = 1001 0,04

0,96

= 24 с.

На нее также потребуется 72 с, в сумме - 144 с, что больше 128 с.

144

Следовательно, ускорение здесь составляет К =-= 1 128

128

Коэффициент ускорения к в этом примере, согласно (2), равен

к=2 (1 - 4 ) с,

m 0,8

0,2 +--Q 24

где с =_20_= о_= 0 75 и =1,125, что совпадает с полученным

0,2 + 08 .4 0,32 , 20

выше.

По сравнению с одним ядром, которому понадобилось бы для выполнения 24-х процессов 2400 с, ускорение реконфигурируемой системой составило R44 =18,75 раз, нереконфигурируемой системой - К44 =16,6 раз.

Аналогично получаем указанные на рис. 2 значения: R 3 =14,2, К33 =12,5

для q = 3 и R 5 = 22,8 , К5 5 = 20,8 для q = 5.

Рассмотренный механизм может быть применен в реконфигурируемых гибридных системах Dell Power Edge C410X [7], позволяющих создавать для исполняемого процесса системы, содержащие до 8-ми вычислительных модулей с универсальными процессорами х86 и 1, 2, 4, 8 и 16 ускорителей М2050 фирмы Nvidia. Реконфигурация осуществляется программно-управляемым коммутатором РЕХ 8696 фирмы PLX Technology. Подробное описание системы Dell Power Edge C410X приводится в [7].

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Степаненко С.А. Оценки ускорения вычислений гибридными системами // Пленарные доклады Пятой Международной конференции «Параллельные вычисления и задачи управления» PACO 2010. Москва, 26-28 октября 2010 г. - М.: Институт проблем управления им. В.А.Трапезникова РАН, 2010. - С. 61-71.

2. Каляев И.А., Левин И.И. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач обработки информации и управления // Пленарные доклады Пятой Международной конференции «Параллельные вычисления и задачи управления» РАСО 2010. Москва, 26-28 октября, 2010 г. - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2010. - С. 23-38.

3. Bondalapati K., Prasanna V.K. Reconfigurable Computing Systems // Proc. IEEE. - 2002. - Vol. 90, № 7. - С. 1201-1217.

4. Степаненко С.А. Способ определения структуры гибридной вычислительной системы. Патент РФ № 2436151 на изобретение.

5. Oak Ridge changes Jaguar's spots from CPUs to GPUs. Режим доступа: http://www.theregister.co.uk/2011/10/11/oak_ridge_cray_ nvidia_titan/.

6. Цилькер Б.Я., С.А.Орлов. Организация ЭВМ и систем. - СПб., 2004. - 668 c.

7. http://content.dell.com/us/en/gen/ spredir.ashx/solutions/poweredge-c410x-thinkers.

REFERENCES

1. Stepanenko S.A. Otsenki uskoreniya vychisleniy gibridnymi sistemami [Evaluation of the acceleration of hybrid computing systems], Plenarnye doklady Pyatoy Mezhdunarodnoy konferentsii «Parallel'nye vychisleniya i zadachi upravleniya» PACO 2010. Moskva, 26-28 oktyabrya 2010 g [Plenary papers of the Fifth International conference "Parallel computations and control problems" PACO 2010. Moscow, 26-28 October 2010]. Moscow: Institut problem upravleniya im. V.A.Trapeznikova RAN, 2010, pp. 61-71.

2. Kalyaev I.A., Levin I.I. Rekonfiguriruemye mul'tikonveyernye vychislitel'nye sis-temy dlya resheniya potokovykh zadach obrabotki informatsii i upravleniya [Reconfigurable multiconference computing system for solving ow problems of information processing and management], Plenarnye doklady Pyatoy Mezhdunarodnoy konferentsii «Parallel'nye vychisleniya i zadachi upravleniya» PACO 2010. Moskva, 26-28 oktyabrya 2010 g [Plenary papers of the Fifth International conference "Parallel computations and control problems" PACO 2010. Moscow, 26-28 October 2010]. Moscow: Institut problem upravleniya im. V.A. Trapeznikova RAN, 2010, pp. 23-38.

3. Bondalapati K., Prasanna V.K. Reconfigurable Computing Systems, Proc. IEEE, 2002, Vol. 90, No. 7, pp. 1201-1217.

4. Stepanenko S.A. Sposob opredeleniya struktury gibridnoy vychislitel'noy sistemy [The way to define the structure of the hybrid computing system]. Patent RF № 2436151 na izobretenie.

5. Oak Ridge changes Jaguar's spots from CPUs to GPUs. Available at: http://www.theregister.co.uk/2011/10/11/oak_ridge_cray_ nvidia_titan/.

6. Tsil'ker B.Ya., S.A.Orlov. Organizatsiya EVM i system [Organization of computers and systems]. St. Petersburg, 2004, 668 p.

7. Available at: http://content.dell.com/us/en/gen/ spredir.ashx/solutions/poweredge-c410x-thinkers.

Статью рекомендовал к опубликованию д.т.н., профессор И.И. Левин.

Степаненко Сергей Александрович - Федеральное государственное унитарное предприятие «Российский федеральный ядерный центр - Всероссийский научно-исследовательский институт экспериментальной физики»; e-mail: ssa@vniief.ru; 607188, Нижегородская обл., г. Саров, пр. Мира, 37; главный научный сотрудник; д.ф.-м.н.

Stepanenko Sergey Alexandrovich - Federal State Unitary Enterprise "Russian Federal Nuclear Center - All-Russian Research Institute of Experimental Physics"; e-mail: ssa@vniief.ru; 37, Mira Avenue, Sarov, Nizhniy Novgorod region, 607188, Russia; chief research; dr. of phis.-math. sc.

УДК 004.382.2

А.К. Мельников

ИССЛЕДОВАНИЕ ПУТЕЙ МОДЕРНИЗАЦИИ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

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

Реконфигурируемые вычислительные системы; кластерные системы; программируемые логические интегральные схемы.