Структурное согласование алгоритмов глобальной оптимизации с архитектурой графических процессоров

Аннотация

Использование современных метаэвристических алгоритмов глобальной оптимизации требует применения параллельных вычислительных систем, в частности графических процессорных устройств со сложной архитектурой. Параллельная эффективность алгоритма оптимизации сильно зависит от выбранного отображения алгоритма на вычислительную систему. Предложен алгоритм согласования параллельного метаэвристического оптимизационного алгоритма с архитектурой графических процессорных устройств. Рассмотрена постановка задачи согласования как задачи определения оптимальной стратегии параметризованного алгоритма и оптимального отображения этого алгоритма на архитектуру вычислительной системы. Предложено математическое представление графовых отображений и ограничений отображений. Отображение алгоритма на вычислительную систему представлено как отображение графовой параметризованной модели параллельного алгоритма с островной моделью параллелизма на совокупность графовых моделей графического процессора. Множество допустимых отображений на основе указанных ограничений формализует особенности архитектуры вычислительной системы и модели параллелизма алгоритма. Предложен алгоритм структурного согласования, основанный на совместном решении задачи оптимизации и задачи структурной оптимизации допустимых отображений. Рассмотрен критерий параллельной эффективности, оцениваемый как экспериментально, так и аналитически по графовым моделям и их отображениям, что позволяет проводить оптимизацию для различных сценариев поиска отображений. Приведены результаты вычислительного эксперимента со сравнением параллельной эффективности параллельного алгоритма, основанного на алгоритме структурного согласования, и классического алгоритма для класса тестовых задач оптимизации из пакета CEC (Congress of Evolutionary Computing)

Просьба ссылаться на эту статью следующим образом:

Селиверстов Е.Ю. Структурное согласование алгоритмов глобальной оптимизации с архитектурой графических процессоров. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2022, № 2 (139), с. 42--59. DOI: https://doi.org/10.18698/0236-3933-2022-2-42-59

Литература

[1] Nvidia Ampere GA102 GPU аrchitecture. 2020. nvidia.com: веб-сайт. URL: https://www.nvidia.com/content/PDF/nvidia-ampere-ga-102-gpu-architecture-whitepaper-v2.pdf (дата обращения: 10.09.2021).

[2] Kwok Y.K., Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 1999, vol. 31, no. 4, pp. 406--471. DOI: https://doi.org/10.1145/344588.344618

[3] Sinnen O. Task scheduling for parallel systems. New York, Wiley-Interscience, 2007.

[4] Hendrickson B., Kolda T.G. Graph partitioning models for parallel computing. Parallel Comput., 2000, vol. 26, no. 12, pp. 1519--1534. DOI: https://doi.org/10.1016/S0167-8191(00)00048-X

[5] Chen S., Eshaghian M.M., Wu Y.C. Mapping arbitrary non-uniform task graphs onto arbitrary non-uniform system graphs. Proc. Int. Conf. on Parallel Processing, 1995, vol. 2, pp. 191--195.

[6] Berman F., Snyder L. On mapping parallel algorithms into parallel architectures. J. Parallel Distrib. Comput., 1987, vol. 4, no. 5, pp. 439--458. DOI: https://doi.org/10.1016/0743-7315(87)90018-9

[7] Kirk D.B., Hwu W.W. Programming massively parallel processors. Morgan Kaufmann, Elsevier, 2013.

[8] Izzo D., Rucinski M., Ampatzis C. Parallel global optimisation metaheuristics using an asynchronous island-model. IEEE CEC’09, 2009, pp. 2301--2308. DOI: https://doi.org/10.1109/CEC.2009.4983227

[9] Lorion Y., Bogon T., Timm I.J., et al. An agent based parallel particle swarm optimization --- APPSO. IEEE Swarm Intelligence Symp., 2009, pp. 52--59. DOI: https://doi.org/10.1109/SIS.2009.4937844

[10] Seliverstov E.Y., Karpenko A.P. Hierarchical model of parallel metaheuristic optimization algorithms. Procedia Comput. Sc., 2019, vol. 150, pp. 441--449. DOI: https://doi.org/10.1016/j.procs.2019.02.075

[11] Skillicorn D.B., Talia D. Models and languages for parallel computation. ACM Comput. Surv., 1998, vol. 30, no. 2, pp. 123--169. DOI: https://doi.org/10.1145/280277.280278

[12] Селиверстов Е.Ю. Графовые модели графического процессора. Системы компьютерной математики и их приложения: Матер. XVIII Междунар. науч. конф., 2007, с. 117--119.

[13] Messmer B.T., Bunke H. Efficient subgraph isomorphism detection: a decomposition approach. IEEE Trans. Knowl. Eng., 2000, vol. 12, no. 2, pp. 307--323. DOI: https://doi.org/10.1109/69.842269

[14] Griva I., Nash S., Sofer A. Linear and nonlinear optimization. Philadelphia, SIAM, 2008.

[15] Li X., Tang K., Omidvar M.N., et. al. Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization. URL: http://www.tflsgo.org/assets/cec2018/cec2013-lsgo-benchmark-tech-report.pdf (дата обращения: 10.09.2021).

[16] Kennedy J., Eberhart R. Swarm intelligence. Morgan Kaufmann, Elsevier, 2001.

[17] Parhami B. Introduction to parallel processing: algorithms and architectures. Nature Switzerland AG, Springer, 1999.