Эффективные параллельные алгоритмы восстановления данных по известным значениям в узлах равномерной сетки
Рассмотрены вычислительные аспекты решения в реальном времени задачи восстановления данных по известным значениям в узлах. Описан один из известных подходов к решению поставленной задачи, обладающий низкой вычислительной сложностью и хорошим потенциалом в смысле параллелизма по данным. Рассматриваются параллельные алгоритмы восстановления данных по известным значениям в узлах равномерной сетки. Такие алгоритмы могут как иметь самостоятельное значение, так и быть составной частью решения многих вопросов прикладного характера. Исследуются способы распараллеливания по данным и организации вычислений, при этом используется подход с применением абстрактных моделей параллельных вычислений. Построена модель блочно-синхронно-конвейерного параллелизма (БСКП) для обработки потока данных в реальном времени, в основу которой положена широко известная модель параллельных вычислений общего назначения BSP (Bulk Synchronous Parallel). Параллельные алгоритмы восстановления данных сформулированы в терминах модели БСКП. Оценена вычислительная и коммуникационная сложность предложенных алгоритмов. Выведены зависимости между размерностями задачи и параметрами модели БСКП. Описана программная реализация предложенных алгоритмов в виде библиотеки функций.
Авторы: А. Р. Лисс, Г. Ю. Пуеров, Е. И. Сергеева
Направление: Информатика, вычислительная техника и управление
Ключевые слова: Восстановление данных, многопроцессорные системы, блочно-синхронный параллелизм, системы реального времени, проектирование программного обеспечения, параллельная обработка, модель вычислительной системы
Открыть полный текст статьи