Optimization of GPUs and Clusters for the Development of Large-scale Socio-economic Models on Supercomputers
Table of contents
Share
QR
Metrics
Optimization of GPUs and Clusters for the Development of Large-scale Socio-economic Models on Supercomputers
Annotation
PII
S207751800011122-3-1
Publication type
Article
Статус публикации
Published
Authors
Vladimir Abramov 
Occupation: Research fellow
Affiliation: Central Economics and Mathematics Institute
Address: Russian Federation, Moscow
Dmitry Evdokimov
Occupation: Junior researcher
Affiliation: Central Economics and Mathematics Institute
Address: Russian Federation, Moscow
Abstract

The article is devoted to the analysis of supercomputers performance optimization technology for the development of large-scale economic models based on two theses. First, the paper presents a parallelized architecture of an optimized environment for the development of multidimensional dynamic stochastic economic models. Second, an algorithm for vectorization of computational cores for AVX processors is described. 

Keywords
high-performance computing, macroeconomics, public finance, adaptive sparse grids, heterogeneous systems
Received
05.08.2020
Date of publication
05.09.2020
Number of purchasers
21
Views
1247
Readers community rating
0.0 (0 votes)
Cite Download pdf
Additional services access
Additional services for the article
Additional services for all issues for 2020
1

Введение

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

2

В настоящее время существует несколько областей, в которых за последние 10–20 лет детерминированные модели МПП эффективно применялись для анализа налоговой и фискальной политики. Для того, чтобы иметь возможность более детально решать важные политические вопросы, в прототип модели должна быть включена случайная вероятность события, основанная на статистических данных за последние годы, а также учтены экономические процессы в сфере государственного управления и вероятность наступления событий, которые влияют на будущие управленческие решения [12]. Зачастую при проведении подобных экспериментов, исследователи, которые используют теорию вероятности в моделях, сталкиваются с неустойчивым равновесием, поскольку стохастические совокупные шоки влияют на каждого агента по-разному. Эти эффекты не компенсируются даже с учетом усреднения совокупности всех факторов.

3

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

4

Современные суперкомпьютеры и их производительность. Производительность суперкомпьютеров растет и позволяет решать сложнейшие вычислительные задачи. Первым компьютером, который преодолел отметку в один петафлопс, является суперкомпьютер IBM Roadrunner [15]. В целом, технологии, связанные с высокопроизводительными вычислительными машинами, изначально были предназначены для моделирования ядерных реакций [1]. На сегодняшний день наработки в этой области шагнули далеко вперед, и суперкомпьютеры используются для решения различных задач и моделирования всевозможных детализированных процессов с огромным объемом вычислений. Одним из важнейших показателей в развитии суперкомпьютерных технологий является суммарный коэффициент производительности, который рассчитывается отдельно для каждой страны. Далее (см. рис. 1) представлены показатели суммарного коэффициента для России, США, Китая, Евросоюза и Японии.

5

Рисунок 1. Суммарная производительность всех суперкомпьютеров США (US), стран Евросоюза (EU), России (RU), Китая (CH) и Японии (JP). Источник: [1]

6 Ярко выраженный скачок по показателю суммарной производительности суперкомпьютеров в интервале с 1994 по 2018 гг. продемонстрировали Япония, США и Евросоюз. Набрав стремительный рост, Китай вырвался в лидеры к 2015 году, опередив Японию и Евросоюз. В 2019 году Китай и США практически сравнялись в этом показателе, и время от времени меняют друг друга на лидирующей позиции.
7

Наряду со стремительным развитием суперкомпьютерных технологий особое внимание уделяется задачам, связанным с оптимизацией вычислений. Скорость, помноженная на эффективность, дает результат, который позволяет выйти в лидеры в области развития высокопроизводительной техники. Далее в работе приведены новые технологии оптимизации вычислений, которые могут быть применены в контексте АОМ и МПП [6].

8

Метод, основанный на адаптивных разреженных сетях.

Методы построения адаптивных разреженных сетей (далее – АРС) активно используются для решения оптимизационных задач, которые возникают из-за парадигмы многомерного пространства состояний, а именно повторного построения и оценки многовариантных функций [11, 14].

9 Рассмотрим представление отрезка-d-линейной функции f: Ω → R для некоторой ширины сетки hn = 21 − n с уровнем дискретизации n ∈ N. С целью дискретизации Ω можно выполнить ограничение области интересов компактом Ω = [0, 1] d, где d - размерность модели МПП. Такая ситуация может быть достигнута для большинства других областей путем повторного масштабирования и усечения исходной области. Чтобы сгенерировать приближение u функции f, используется разложение:
10 f (x)u (x) := j=1αjφj(x)                      1
11 Для N базисных функций φj и коэффициентов αj используются одномерные функции:
12 φl,ix=1,                                                       l=i=1,                max1-2l-1x-xl,i, 0,      i=0,, 2l-1>1,                2
13 После применения метода интерполяции разреженных сеток, основанного на иерархической декомпозиции пространства основной аппроксимации, вводятся иерархические наборы индексов Il:
14 xl,i=0.5,  l=i=1,                i21-l,     i=0,, 2l-1, l>1,         3
15 Использование метода интерполяции разреженных сеток, основанного на иерархической декомпозиции пространства основной аппроксимации подразумевает введение иерархических наборов индексов Il, которые приводят к иерархическим подпространствам Wl, представленным в виде соответствующего базиса φl: = {φl,i (x), i ∈ Il}.
16 Ili=1                                    if l=1,0i2,i even              if l=2,0i2lt-1, i odd                 else,          (4)
17 Иерархические базисные функции распространяются на многовариантный случай с использованием тензорных произведений:
18  φl,ixt=1dφlt,itxt,                   4,
19 где l и i - мультииндексы, указывающие на уровень и индекс основных одномерных функций верхнего слоя для каждого измерения. Они охватывают многомерные подпространства:
20 Wlspanφl,i:iIl                  (5)
21 с набором индексов Il , заданным многомерным расширением:
22 Ili :it=1,1td                         if l=1i:0it2,iteven, 1td   if l=2i:0it2lt-1, it odd,1td    else.          (6)
23 Пространство отрезка линейных функций Vn на декартовой сетке с размером ячейки hn для данного уровня n определяется прямой суммой пространств приращений:
24 Vnwl, lmax lt. ln           1td                     (7)
25 Затем, может быть однозначно приведен интерполянт функции f, а именно u x Vn  :
26 fxux=lniIlαl,iφl,ix.             (8)
27 Коэффициенты αli R , обычно вызывают иерархические сдвиги. Они представляют собой разницу между значениями функций на текущем и предыдущем уровнях интерполяции. Для достаточно гладкой функции f асимптотическая ошибка убывает как O(hn2) , но за счет затрат Ohn-2=O(h2nd) точек сетки, таким образом «страдая» от размерности [10]. Как следствие возникает вопрос, как можно построить дискретные аппроксимационные пространства, которые лучше, чем Vn, в том смысле, что одно и то же количество вложенных точек сетки приводит к более высокому порядку точности. Как вариант, для решения этой задачи может быть введение функции со смешанными и ограниченными вторыми производными. С помощью них можно показать, что иерархические коэффициенты быстро убывают, а именно αli=O (2-2|l|1) . Следовательно, иерархическое разбиение подпространства позволяет выбирать те Wl, которые вносят наибольший вклад в общую аппроксимацию. Это может быть сделано путем предыдущего выбора, в результате чего пространство разреженной сетки VnS уровня n определяется как:
28 VnS|l|1n+d-1Wl, |l|1=i=1dlt.         9,
29 где V3S состоит из иерархических пространств приращений W(l1, l2) для 1l1, l2n=3 . Число точек сетки, требуемых пространством VnS , будут иметь порядок O (2nnd-1) , что является значительным сокращением количества точек сетки, вычислительных затрат и требований к хранению информации, если проводить сравнение с декартовым пространством сетки. Затем, функцию f  VnS  vn можно разложить на:
30 f(x)u(x)= ln+d-1iIlαl,iφl,i(x),                 (10)
31

В случае, если функции не удовлетворяют требованиям гладкости или демонстрируют различные локальные особенности, они могут быть решены с помощью разреженных сеток, если используется пространственная адаптивность. Классическая конструкция разреженной сетки определяет априорный выбор точек сетки, оптимальный для функций с ограниченными смешанными производными второго порядка, а адаптивное уточнение может быть сделано на основе локального анализа ошибок выбора [10, 17, 18].

32

Повышение скорости выполнения суперкомпьютером интерполяции функции на примере стохастической модели МПП.

В данном разделе описан пример стохастической модели МПП, разработанной в виде массивной параллельной версии алгоритма временной итерации [16] для смешанных многомерных непрерывных/дискретных состояний, которые используют одну АРС на z ∈ Z на каждом шаге итерации. В [8] проведено распараллеливание данного алгоритма по гибридной схеме с использованием MPI [21], TBB [19] и CUDA, если на вычислительном узле присутствует GPU, а также вычислительных ядер, использующих AVX, AVX2 или AVX-512 векторизацию.

33

Существенным слабым местом в производительности при вычислении крупномасштабных экономических задач зачастую является задача интерполяции функций предыдущего шага итерации. При поиске решения системы уравнений в заданной точке для заданного скачка z алгоритм должен часто интерполироваться по функциям политик всех состояний pnext Ns = 16 из предыдущего шага итерации за один раз. Эти интерполяции обычно занимают до 99% времени вычислений, необходимого (см. пример [9]) для решения нелинейного набора уравнений, и при этом должны выполняться как можно быстрее, чтобы гарантировать быстрое принятия решения. Несмотря на наличие широко применяемого формата данных с плотной матрицей (см., например, [9]), для которого существуют высоко оптимизированные алгоритмы для выполнения задач, связанных с интерполяцией, необходимо внедрение нового, общего метода сжатия данных для АРС [20]. Данный метод позволит работать с 16 непрерывными измерениями, то есть с 59-мерными АРС одновременно. Сохранение вышеупомянутого плотного матричного формата для хранения функции политики предыдущей итерации для интерполяции гораздо меньше загружает объем памяти, что, в свою очередь, существенно замедляет интерполяцию и, следовательно, повышает скорость вычислений.

34

Заключение

В статье приведены позиции различных стран в рейтинге суммарной производительности суперкомпьютеров. Представлена наглядная демонстрация того, что, объединение АРС с эффективными структурами данных, алгоритмом итерации по времени (который имеет дело с рекурсивным характером постановки задачи), и с гибридными вычислительными парадигмами высокопроизводительных вычислений (которые резко сокращают время расчетов), оказывается эффективным методом для решения задач, связанных с разработкой АОМ- и МПП-моделей, а также проведения имитационных экспериментов на более сложных уровнях [3, 4]. Также в работе приведена гибридная схема распараллеливания, в которой используются современные парадигмы параллельных вычислений. Кроме того, представлена схема сжатия данных для АРС, которая позволяет сократить время вычислений, затрачиваемое на интерполяции, примерно в 4 раза.

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

References

1. Abramov S.M. Analiz razvitiya superkomp'yuternoj otrasli v Rossii i v mire // Programmnye sistemy: teoriya i prilozheniya. Institut programmnykh sistem im. A.K. Ajlamazyana Rossijskoj akademii nauk. 2019, № 3(42).

2. Makarov V.L., Bakhtizin A.R., Sushko E.D. Mul'tiagentnye sistemy i superkomp'yuternye tekhnologii v obschestvennykh naukakh // Nejrokomp'yutery: razrabotka, primenenie. Radiotekhnika. 2017, № 5.

3. Makarov V.L., Bakhtizin A.R., Sushko E.D., Sushko G.B. Modelirovanie sotsial'nykh protsessov na superkomp'yuterakh: novye tekhnologii // Vestnik RAN. 2018, Tom 88, №6.

4. Makarov V.L., Bakhtizin A.R., Sushko E.D., Sushko G.B. Razrabotka agent-orientirovannoj demograficheskoj modeli Rossii i ee superkomp'yuternaya realizatsiya // Trudy mezhdunarodnoj konferentsii. Superkomp'yuternyj konsortsium universitetov Rossii, Rossijskaya akademiya nauk. 2018. S. 758-769.

5. Okrepilov V.V., Makarov V.L., Bakhtizin A.R., Kuz'mina S.N. Primenenie superkomp'yuternykh tekhnologij dlya modelirovaniya sotsial'no-ehkonomicheskikh sistem // Ehkonomika regiona. Institut ehkonomiki Ural'skogo otdeleniya RAN. 2015, № 2 (42).

6. Rakitskij A.A., Ryabko B.Ya. Teoretiko-informatsionnyj podkhod k otsenke proizvoditel'nosti superkomp'yuterov // Vychislitel'nye tekhnologii. Institut vychislitel'nykh tekhnologij Sibirskogo otdeleniya RAN. 2018, № 1.

7. Bellman R. Adaptive Control Processes: A Guided Tour // Rand Corporation. Research studies. Princeton University Press. 1961.

8. Brumm J., Mikushin D., Scheidegger S., Schenk O. Scalable high-dimensional dynamic stochastic economic modeling // Journal of Computational Science. 2015, vol. 11.

9. Brumm J., Scheidegger S. Using adaptive sparse grids to solve high-dimensional dynamic models // Econometrica. 2017, vol. 85, № 5.

10. Bungartz H.-J., Dirnstorfer S. Multivariate quadrature on adaptive sparse grids // Computing. 2003, vol. 71.

11. Bungartz H.-J., Griebel M., Sparse grids // Acta Numerica. 2004, vol. 13.

12. David K. L. J., Bizer S. Taxation and uncertainty // The American Economic Review. 1989, vol. 79, №. 2.

13. Diamond P. A. National debt in a neoclassical growth model // American Economic Review. 1965, vol. 55, №. 5

14. Garcke J., Griebel M. Sparse Grids and Applications // Lecture Notes in Computational Science and Engineering. Springer. 2012.

15. Jones M.T. Optimizing supercomputer resource management with SLURM // IBM. URL: https://www.ibm.com/developerworks/ru/library/l-slurm-utility/index.html

16. Judd K. L. Numerical methods in economics // The MIT press. 1998.

17. Ma X., Zabaras N. An adaptive hierarchical sparse grid collocation algorithm for the solution of stochastic differential equations // J. Comput. Phys. 2009, vol. 228, № 8.

18. Pfluger D. Spatially adaptive refinement // In Sparse Grids and Applications, ser. Lecture Notes in Computational Science and Engineering, Garcke J., Griebel M. Eds. Berlin Heidelberg: Springer. 2012. pp. 243–262.

19. Reinders J. Intel Threading Building Blocks // 1st ed. Sebastopol, CA, USA: O’Reilly & Associates, Inc. 2007.

20. Scheidegger S., Mikushin D., K?ubler F., Schenk O. Rethinking large-scale economic modeling for efficiency: optimizations for GPU and Xeon Phi clusters // IEEE International Parallel and Distributed Processing Symposium. 2018. pp. 610-619.

21. Skjellum A., Gropp W., Lusk E. Using MPI // MIT Press. 1999.

Comments

No posts found

Write a review
Translate