Распараллеливание библиотеки основных операций линейной алгебры (BLAS) на общей памяти

Лунев В. В., Обувалин Д. М., Орлов И. Н., Сиволгин С. В.
Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. Тезисы докл. Междунар. математич. конф 1997. Вып.1. С. 29.

      Библиотека BLAS (Basic Linear Algebra Subprograms) является составной частью хорошо известного пакета LAPACK, предназначенного для решения задач численного анализа. В состав библиотеки BLAS входят часто используемые подпрограммы линейной алгебры. Пакет LAPACK построен на блочных алгоритмах — в качестве вычислительных блоков нижнего уровня максимально используются программы BLAS. Оптимизация (адаптация) библиотеки для конкретной архитектуры существенно повышает производительность пакета LAPACK в целом.
      Параллелизм на общей памяти (Shared Memory Parallelism) ориентирован на конфигурацию из нескольких процессоров, имеющих общую оперативную память. В таких системах память является глобальной для всех процессоров. В качестве основной рабочей станции использовалась Intel-платформа Altera, которая может содержать от одного до четырех процессоров Pentium Pro, соединенных общей шиной памяти. Подобная конфигурация обеспечивает полноценную работу операционных систем UNIX и Windows NT.
      Для реализации параллелизма на общей памяти создан пакет SMP, который представляет собой простой и эффективный инструмент создания параллельных приложений. Основными преимуществами пакета являются динамическая настройка на число процессоров в кластере и одноразовое использование дорогих механизмов системного администрирования подзадач. Созданный для распараллеливания программ из библиотеки BLAS пакет может применяться и в любых других SMP-приложениях.
      Подпрограммы библиотеки BLAS делятся на три уровня в зависимости от выполняемых ими операций. Подпрограммы первого уровня производят векторные операции, второго -матрично-векторные операции, подпрограммы третьего уровня выполняют матрично-матричные операции. Создание параллельных алгоритмов имело смысл только для программ третьего уровня, так как программы второго и особенно первого уровней имеют существенно меньший объем вычислений. Основная сложность реализации параллельных алгоритмов заключается в необходимости равномерной загрузки всех присутствующих в системе процессоров. Нарушение баланса ведет к снижению коэффициента распараллеливания. Характерной особенностью и одновременно узким звеном для систем с общей памятью является общая для всех процессоров шина, которая не может обрабатывать несколько запросов одновременно. Этот фактор является основным ограничителем для наращивания числа процессоров в системе. При проектировании параллельных алгоритмов приходилось выбирать такие варианты, которые сглаживают конфликты обращения к памяти.
      Программы третьего уровня оперируют с матрицами различного вида: общего, треугольного, симметричного. Для общности обзора описаны алгоритмы для матриц общего вида и симметричных матриц.
      В докладе представлены результаты распараллеливания. Для различных программ коэффициент распараллеливания имеет значение от 80 до 99%.