Современные информационные технологии/1. Компьютерная инженерия

Канд. техн. наук А.К. Мельников,

ЗАО «ИнформИнвестГрупп», Москва, Россия

Канд. техн. наук Дордопуло А.И.

Южный научный центр Российской академии наук, г. Ростов-на-Дону, Россия

пути модернизации РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ*

Более 80% современных многопроцессорных вычислительных систем (МВС) построены по кластерному принципу, основная идея которого состоит в следующем. Из нескольких вычислительных элементов (ВЭ) составляется вычислительный узел (ВУЗ), обычно физически изготовляемый в виде самостоятельного вычислительного блока (ВБ), включающего в себя набор ВЭ, а также индивидуальные системы электропитания, управления, памяти и адаптеров внутренних и внешних информационных обменов и т.п. Для достижения нужной производительности МВС вычислительные узлы (блоки) объединяются в кластер (вычислительный кластер) высокоскоростными каналами. Для ускорения разработки и уменьшения стоимости МВС для формирования ВУЗ используют ВЭ высокой степени готовности (off-the-shelf).

Использование для построения МВС в качестве ВЭ отдельных ПЛИС либо функциональных устройств на базе ПЛИС открыло целое направление по разработке реконфигурируемых вычислительных систем (РВС) [3]. МВС на базе ПЛИС получили название мультиконвейерных реконфигурируемых вычислительных систем, общая концепция создания которых представлена в [4] и целом ряде работ тех же авторов.

Рассмотрим характеристики вычислительных узлов мультиконвейерных РВС, построенных по кластерному принципу. Будем полагать, что проблемная область, для решения задач которой используется РВС во время t, содержит проблемы вычислительной сложности K=К(t). Вычислительная сложность задач проблемной области выражается степенной функцией и имеет вид

К(t) = А ^ν(t),

где ν(t) – размерность или значность задачи, ν(t)N - множеству натуральных чисел и является возрастающей функцией, А=const от 2 до 256.

Также положим что, РВС во время t содержит n(t) однородных вычислительных элементов (ВЭ) производительностью p(t) решений в секунду каждый и РВС решает задачи сложности К(t) за время Т, т.е.

А ^ν(t) / ( n(t) × p(t) ) = Т. (1)

Рассмотрим, как изменятся требования к характеристикам ВЭ, удовлетворяющим условию (1), через время Δ, когда необходимо будет решать задачу большей значности ν(t+Δ) за то же время Т.

Обозначим число ВЭ (блоков) РВС во время t+Δ через n(t+Δ) РВС при сохранении их производительности т.е.

p(t+Δ) = p(t),

назовем этот путь экстенсивным путем модернизации РВС.

Из поставленных условий должно выполняться равенство

А ^ν(t+Δ) / ( n(t+Δ) × p(t) ) = Т. (2)

Учитывая (1), получаем отношение

n(t+Δ) / n(t) = А ^{ν(t+Δ) - ν(t)}, (3)

определяющее, во сколько раз мы должны увеличить число ВЭ РВС для решения задачи повышенной значности ν(t+Δ_i) за то же время Т. В таблице 1 для разных значений А приведены коэффициенты увеличения количества ВЭ РВС при увеличении значности решаемых задач предметной области, обозначим их через - α_А ( ν(t+Δ_i) - ν(t) ).

Теперь определим производительность ВЭ p(t+Δ) РВС при сохранении их количества т.е.

n(t+Δ) = n(t),

назовем этот путь интенсивным путем модернизации РВС.

Таблица 1. Коэффициенты роста значений технических характеристик РВС

^ν(^t^+^Δ i^)^-^ν(^t^) А	1	2	4	8	10
2	2	4	16	256	1024
10	10	100	10 000	100 000 000	10 000 000 000
26	26	676	456 976	208827064576	~ 1,41 × 10^14
32	32	1024	1048576	~ 1,09 × 10^12	~ 1,12 × 10^15
256	265	65536	16777216	~ 1,84 × 10^19	~ 1,20 × 10^24

Из поставленных условий должно выполняться равенство

А ^ν(t+Δ) / ( n(t) × p(t+Δ) ) = Т. (4)

Учитывая (1) получаем отношение

p(t+Δ) / p(t) = А ^{ν(t+Δ) - ν(t)}. (5)

Определим (5) как коэффициент прироста производительности ВЭ.

Анализируя (3) и (5), видим, что таблица 1 содержит общие коэффициенты роста технических характеристик РВС, определяемые параметрами задачи предметной области.

При использовании экстенсивного пути модернизации РВС даже при увеличении значности задачи на 1 для А=2 необходимо увеличить количество оборудования вдвое, что по финансовым затратам сопоставимо с построением уже имеющейся РВС. При значительном росте значений параметров задачи модернизация экстенсивным путем вряд ли практически выполнима и имеет смысл. Рассмотрим интенсивный путь модернизации РВС. В качестве вычислительных элементов (ВЭ) построения РВС используются функциональные устройства (вычислительные платы), состоящие из нескольких ПЛИС. Прирост производительности ВЭ при использовании ПЛИС разных поколений [6] приведен в таблице 2.

Анализ значений коэффициентов прироста производительности α(i)из таблицы 2 показывает, что при переходе от одной версии кристалла к другой версии их значения уменьшаются, а само значение коэффициента увеличения производительности позволяет увеличить значность задачи лишь на 1 и то при наименьшем А=2, смотри значения α_А(ν(t+Δ_i)-ν(t)) в таблице 1.

Таблица 2. Коэффициенты прироста производительности ВЭ РВС

Тип ПЛИС Характеристики	XC4000Virtex	Virtex-2	Virtex-2 Pro	Virtex-4	Virtex-5	Virtex-6	Virtex-7	Virtex-8 Ultra Scale
Индекс версии кристалла - i	1	2	3	4	5	6	7	8
Год выпуска (ti)	2000	2002	2004	2006	2007	2009	2012	2015
Производительность ВЭ max p(ti) 10^9 (реш./сек.)			17	50	140	360	785
Коэффициент прироста производительности α( i )= p(ti+1) / p(ti)			2,94	2,80	2,57	2,18

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

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

n(t+Δ) > n(t), p(t+Δ) > p(t). (6)

Поскольку увеличение производительности за счет применения кристаллов новых версий не позволяет добиться требуемого увеличения производительности ВЭ, попробуем найти путь, который наряду с использованием кристаллов новых версий позволит добиться необходимого значения коэффициента повышения производительности большего α(i) из таблицы 2.

Напомним, что в данной работе в качестве вычислительных элементов (ВЭ) построения РВС рассматривались функциональные устройства (вычислительные платы), состоящие из нескольких ПЛИС, блоков питания, адаптеров коммуникационных сред и т.д. По аналогии с приведенной классификацией МВС назовем данные ВЭ универсальными в смысле построения РВС, а построенные на их основе РВС – универсальными РВС.

Для увеличения производительности ВЭ пойдем по пути разработки проблемно ориентированных ВЭ, а разработанные на их основе РВС будем называть проблемно ориентированными РВС (ПОРВС).

Рассмотрим подробнее путь разработки ВЭ для ПОРВС, решающей задачи проблемной области сложности К(t) (1), эффективно разбивающиеся на подзадачи, временная сложность которых может быть значительно снижена путем сохранения уже вычисленных решений подзадач.

Будем считать, что ВЭ характеризуется следующими показателями:

р(t) - производительность в решениях в секунду;

i(t) – скорость доступа к локальной памяти, количество операций чтения с произвольным доступом в секунду.

ПОРВС, построенная на основе n(t) ВЭ, обладает объемом общей памяти M(t).

Предположим, что для решения проблемы со сложностью К(t) (1) используется метод разумного компромисса «время/память» (time-memory tradeoff), например, так называемых радужных таблиц [7]. Допустим, что заранее, один раз выполнен объем вычисления O(К(t)), по результатам которого рассчитана хеш-таблица, занимающая объем памяти M≤M(t), и требуется обеспечить время решения задачи (время поиска в таблице) не больше T.

Тогда, исходя из [7], характеристики ВЭ и ПОРВС в целом должны удовлетворять следующим требованиям:

M(t) max (7)

и

iu(t) = , (8)

где l – объем памяти, необходимый для хранения одной «цепочки» в методе радужных таблиц. Для самого широкого круга практических задач можно считать, что l не превосходит 16 байт, iu(t) – удельная интенсивность запросов к памяти.

Таким образом, при выполнении для всех ВЭ ПОРВС условий (7) и (8) и имеющейся производительности р(t) при применении метода разумного компромисса «время/память» согласно [7] мы сможем решить на нашем ПОРВС за время Т задачу значности ν(t+Δ), определяемую выражением

А ^ν(t+Δ) = . (9)

Учитывая условие (1), получаем

А ^ν(t+Δ) = (10)

Проведя операцию логарифмирования, имеем

ν(t+Δ) = - + + ν(t). (11)

Следовательно, увеличение значности решения задачи на ПОРВС с имеющимися техническими характеристиками, но при применении метода разумного компромисса «время/память», определяется следующим соотношением:

ν(t+Δ) - ν(t) = С + - ν(t) , (12)

где константа С имеет значение

С = - . (13)

Числовые значения полученных оценок при различных значениях параметров решаемой задачи А и ν(t) приведены в таблице 3.

Типовые значения IOPS при случайном чтении 4Кб блоков приведены в таблице 4 по материалам из [8].

Таблица 3. Требования к ВЭ и ПОРВС в зависимости от сложности задачи K(t)

Параметры задачи - А и ν(t) Параметры ВЭ и ПОРВС	А=2 ν(t)=56	А=10 ν(t)=18	А=26 ν(t)=14
K(t) - вычислительная сложность (число решений)	~7,2×10^16	10^18	~6,45×10^19
T - время решения задачи (сек.)	100	100	100
p(t), производительность одного ВЭ, (решений/cек.)	10^9	10^9	10^9
n(t) - количество ВЭ	100	100	100
P - общая производительность ПОРВС (решений/cек.) P= n(t) × p(t)	10^12	10^12	10^12
M - объем памяти (Тб) (~10^12 байт)	0,007	1,03	66,38
S - интенсивность запросов к памяти, IOPS. (операций чтения с произвольным доступом/сек.)	140 000	140 000	140 000
iu(t)– удельная интенсивность запросов к памяти, iu(t) =S / n(t)	1400	1400	1400

Использование RAID-контроллеров позволяет увеличивать общее количество IOPS (линейно при малом количестве дисков) до тех пор, пока определяющими не станут ограничения самого контроллера RAID и интерфейса доступа к хранилищу данных.

Таблица 4. Значения IOPS для различных типов накопителей

№ п/п	Устройство	IOPS
1	HDD 7200 RPMSATA	100
2	HDD 15KRPMSAS	180
3	SSD Intel X25 SATA II	5000 – 8000
3	SSDOCZ SATAIII	до 100000
4	RAMDISK, PCIe SSD	до 250000

Соотношения (7) – (8) показывают, что для рассмотренного класса задач время их решения взаимоувязанно определяется как производительностью ВЭ, так и объемом и скоростью доступа к различным видам памяти системы.

Анализ соотношений (7) – (8) и сравнение получившихся в таблице 3 значений с данными таблицы 4 позволяет дать технико-экономическое обоснование выбора типов и объемов локальной и общей памяти для всего жизненного цикла ПОРВС. В частности, если развитие ПОРВС планируется вести «экстенсивным» методом, когда относительный рост числа ВЭ опережает относительный рост производительности отдельных ВЭ, то при росте общей интенсивности запросов к памяти их удельная интенсивность снижается и допустимо ограничится наиболее бюджетным из подходящих по скорости решений. Наоборот, при «интенсивном» развитии требования к скорости интерфейсов доступа к памяти будут расти, и необходимо закладывать наиболее скоростное из доступных решений.

Соотношение (12) показывает, что увеличение объема памяти М для увеличения значности решаемой задачи с ν(t) до ν(t+Δ) зависит не только от самой величины, на которую мы хотим повысить значность ν(t+Δ) - ν(t), но и от того уже достигнутого нами значения значности ν(t), с которого мы это повышение хотим произвести. Также это соотношение показывает, что каждый следующий шаг в повышении значности решаемой задачи требует все больших увеличений ресурсов ПОРВС.

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

- использование при проектировании ВЭ кристаллов ПЛИС новых поколений дает возможность увеличить производительность ВЭ более чем в два раза;

- использование в ВЭ дополнительной памяти произвольного доступа (RAMmodel) позволяет применять методы, повышающие производительность вычислений и дающие возможность решать задачи значительно большей вычислительной сложности;

- увеличение в модернизируемом ПОРВС количества ВЭ (вычислительных блоков) может обеспечить рост производительности, близкий к линейному;

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

Литература

1. Левин В.К. Этапы развития суперкомпьютеров // Виртуальный компьютерный музей. http://www.computer-museum.ru/histussr/super_phase_0.htm (дата обращения 23.02.2015).

2. Воеводин Вл.В. Суперкомпьютеры: вчера, сегодня и завтра. // Наука и жизнь, 2000. № 5. - С. 76 – 83.

3. Каляев А.В, Левин И.И. «Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений», Москва «Янус-К», 2003. – 380 с.

4. Каляев И. А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. – Ростов н/Д: Издательство ЮНЦ РАН, 2008. – 320 с.

5. Корнеев В.В. «Параллельные вычислительные системы», - М., «Нолидж», 1999. – 320 с., ил.

6. Левин И.И., Мельников А.К. Методы управления реконфигурируемыми вычислительными комплексами // Материалы 5-й Всероссийской мультиконференции по проблемам управления, - Таганрог: изд-во ТТИ ЮФУ, 2013. – 370 с.

7. Philippe Oechslin. Making a Faster Cryptoanalytic Time-Memory Trade-Off - CRYPTO’03.

8. Как правильно мерять производительность диска – www.habrahabr.ru/post/154235/(дата обращения 23.02.2015).

______________________________________

*Работа выполнена при финансовой поддержке Министерства образования и науки РФ по Соглашению о предоставлении субсидии №14.578.21.0006 от 05.06.2014, уникальный идентификатор RFMEFI57814X0006, гранту Южного федерального университета №213.01-2014/014 и НИР №2257 базовой части государственного задания №2014/174.