Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

Вычислительная алгебра

Intel® Math Kernel Library PARDISO* – это широко известный параллельный прямой решатель из библиотеки Intel® MKL, который позволяет эффективно решать разреженные СЛАУ на многоядерных системах с использованием современных математических алгоритмов, а также архитектурных особенностей Интеловских процессоров. Процесс решения СЛАУ с помощью PARDISO* состоит из трех этапов: переупорядочивание матрицы A, факторизация (LU-разложение измененной матрицы А’) и решение полученной системы LUx=y. На первом этапе столбцы и строки исходной матрицы переставляются таким образом, чтобы максимально распараллелить этап факторизации, а также оптимизировать использование оперативной памяти для хранения LU факторов. Однако при решении очень больших СЛАУ LU факторы уже не помещаются в оперативную память, что требует модификации исходного алгоритма с учетом использования свободного дискового пространства. В Intel® MKL на основе PARDISO* реализована версия out-of-core (OOC) PARDISO*, позволяющая решать такие задачи. Основная проблема в реализации OOC алгоритма состоит в том, что время доступа к данным на диске существенно выше по сравнению с доступом к оперативной памяти. Поэтому на производительность алгоритма влияет не только скорость счета, но и время работы с диском. Обмен данными с диском зависит как от структуры матрицы, так и от соотношения общей памяти, требуемой для решения задачи, к имеющейся оперативной. Таким образом, производительность OOC алгоритма можно улучшать как ускорением вычислений, так и оптимизацией работы с диском. В Intel® MKL OOC PARDISO* разработан алгоритм, оптимально использующий доступную оперативную память. В частности, в нем данные, загруженные в память, анализируются и реорганизовываются путем удаления ненужных частей с их последующим уплотнением с целью уменьшения фрагментации данных. Это позволило значительно уменьшить число обращений к жесткому диску. Также, для сокращения числа операций с диском, была добавлена возможность совмещения процесса факторизации и прямого шага решения: Lz=y. В этом случае, после нахождении некоторого столбца матрицы L можно вычислить соответствующую часть z. Таким образом, примерно в два раза сокращается число операций с диском на этапе решения. Помимо предложенных оптимизаций работы с диском, OOC версия использует динамическую OMP параллелизацию этапа факторизации. Этот высокоуровневый алгоритм основан на одновременном разложении нескольких столбцов исходной матрицы. Теоретически, по сравнению с In-Core алгоритмом PARDISO*, масштабируемость OOC не может достигнуть 2 при переходе от одного на два процессора и 4 с одного на четыре. Несмотря на это, результаты тестирования показали высокую масштабируемость предложенного алгоритма, которая достигает соответственно 1,8 и 2,9. Исследования производительности показали, что параллельный OOC PARDISO* демонстрирует в большинстве случаев лучшие результаты по сравнению с основными конкурентами, такими как TAUCS и MUMPS.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:49:22)