Полуавтоматический подход к параллельному решению задач с использованием модели Multi-BSP

Модель Multi-Bulk Synchronous Parallel (Multi-BSP) - это модель параллельного программирования для многоядерных машин, которая расширяет классическую модель Bulk Synchronous Parallel. Multi-BSP направлена на поддержку разработки алгоритмов и оценки времени их работы. Эта модель в значительной степени опирается на правильное вычисление параметров, которые характеризуют оборудование. Конечно, использование оборудования также зависит и от особенностей задач и алгоритмов, применяемых для их решения. В этой статье представлен полуавтоматический подход к решению задач с применением параллельных алгоритмов на основе модели Multi-BSP. Во-первых, характеристики конкретного многоядерного компьютера определяются путем применения автоматической процедуры. После этого аппаратная архитектура, обнаруженная на предыдущем этапе, применяется для разработки переносимого параллельного алгоритма. Наконец, выполняется точная настройка параметров для повышения общей эффективности. Мы предлагаем тестовый набор для измерения параметров, которые характеризуют расходы на связь и синхронизацию в конкретном оборудовании. Наш подход обнаруживает иерархическую структуру многоядерной архитектуры и вычисляет параметры для каждого уровня. Вторым вкладом нашего исследования является предложение о системе поддержки Multi-BSP. Она позволяет разрабатывать алгоритмы, применяя рекурсивную методологию к иерархическому дереву, уже построенному с помощью тестового набора.

1. Alaniz M; Nesmachnow S; Goglin B.; Iturriaga S.; Gil Costa V.; Printista M. MBSPDiscover: An automatic benchmark for MultiBSP performance analysis. Communications in Computer and Information Science; vol. 485, pages 158–172 (2014)

2. Bisseling, R.: Parallel scientific computation: a structured approach using BSP and MPI. Oxford University Press, Oxford, UK (2004)

3. Bonorden, O., Juurlink, B., von Otte, I., Rieping, I.: The Paderborn University BSP (PUB) Library. Parallel Comput. 29(2), 187–207 (2003)

4. Broquedis, F., Clet-Ortega, J., Moreaud, S., Furmento, N., Goglin, B., Mercier, G., Thibault, S., Namyst, R.: Hwloc: A generic framework for managing hardware affinities in HPC applications. In: 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, pages 180–186 (2010)

5. Hill, J., McColl, B., Stefanescu, D., Goudreau, M., Lang, K., Rao, S., Suel, T., Tsantilas, T., Bisseling, R.: BSPlib: The BSP programming library. Parallel Computing 24(14), 1947–1980 (1998)

6. Nesmachnow, S. Computación científica de alto desempeño en la Facultad de Ingeniería, Universidad de la República. Revista de la Asociación de Ingenieros del Uruguay 61 (1), 12-15 (2010). Text in Spanish.

7. Savadi, A., Deldari, H.: Measurement latency parameters of the MultiBSP model: A multicore benchmarking approach. Journal of Supercomputing 67(2), 565–584 (2014)

8. Soudris, D., Jantsch, A. (eds.): Scalable Multi-core Architectures. Springer Science + Business Media (2012)

9. Valiant, L.: A bridging model for parallel computation. Communications of the ACM 33(8), 103–111(1990)

10. Valiant, L.: A bridging model for multi-core computing. Journal of Computing and System Sciences 77(1),154–166 (2011)

11. Yzelman, A. Fast sparse matrix-vector multiplication by partitioning and reordering. Ph.D. thesis, Utrecht University, Utrecht, the Netherlands (2011)

12. Yzelman, A., Bisseling, R., Roose, D., and Meerbergen, K.: MulticoreBSP for C: A High-Performance Library for Shared-Memory Parallel Programming. Int. J. Parallel Program. 42, 4, 619-642 (2014)