EFFICIENT PARALLEL ALGORITHMS FOR DATA RECOVERY ON UNIFORM GRID

The article is devoted to the computational aspects of real time data recovery problem. One of the known approaches to solving the problem is described. This approach has low computational complexity and good potential in data parallelism. Parallel algorithms for data recovery from known values at the nodes on uniform grid are considered. Such algorithms are widely used in various applied fields of information processing. Approaches to data-parallel computations in bulk-synchronous notation are studied and bulk-synchronous parallel (BSP) model is extended for real-time streaming data processing. A model of bulk-synchronous-pipeline parallelism (BSPP) is built for streaming processing in real time, which is based on the well-known general-purpose parallel computing model BSP. Parallel algorithms for data recovery are described in terms of this extended model. Computational and communicational complexity of the proposed algorithms is assessed. Dependences between the dimensions of the problem and the parameters of the extended model are derived. The software that implements proposed algorithms is described.

Authors: A. R. Liss, G. Yu. Puerov, E. I. Sergeeva

Direction: Informatics, Computer Technologies And Control

Keywords: Data recovery, multiprocessor system, bulk-synchronous parallelism (BSP), real-time system, signal processing, parallel prosesing, software desing

---

View full article