Параллельные численные алгоритмы
Задача восстановления растровой карты высот земной поверхности по заданным горизонталям относится к классическим задачам цифровой картографии (к ней, например, сводится задача построения цифровых карт различного масштаба с использованием векторного представления рельефа местности, которая встает перед современными геоинформационными системами). Настоящая работа посвящена исследованию одного из алгоритмов решения этой задачи в постановке, предполагающей сохранение исходным набором горизонталей инварианта непрерывности поверхности [1]. Алгоритм опирается на параллелизм вертикальной обработки данных [2] и допускает несколько способов распараллеливания с различной степенью синхронизации параллельных процессов, различной интенсивностью информационных обменов между ними, а также различными механизмами балансировки вычислительной нагрузки. В работе рассмотрены три параллельных версии алгоритма, проведен сравнительный анализ временных характеристик их выполнения, полученных в результате проведенных на высокопроизводительном Linux-кластере MVS-1000M экспериментов, даны рекомендации по использованию того или иного подхода к распараллеливанию.
Работа выполнена частично при финансовой поддержке РФФИ, грант № 03-07-90239.
Литература.
[1] Kim P.A., Pyatkin V.P., Rusin E.V. Some EDT-Based Algorithms for the Computational Geometry Problem Solution. 6th German-Russian Workshop “Pattern Recognition and Image Understanding” (OGRW-6-2003). Workshop Proceedings. Novosibirsk, 2003. pp 100-104.
[2] W. Shooman, Parallel computing with vertical data, AFIPS Confer. Proc. – EJCC, 18, 1960, 111-115.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:06)