Gram–Schmidt Process in Different Parallel Platforms (Control Flow versus Data Flow)

Abstract—Important operations in numerical computing are vector orthogonalization. One of the well-known algorithms for vector orthogonalisation is Gram–Schmidt algorithm. This is a method for constructing a set of orthogonal vectors in an inner product space, most commonly the Euclidean space Rn. This process takes a finite, linearly independent set S = {b1, b2, …, bk} vectors for k ≤ n and generates an orthogonal set S1 = {o1, o2, …, ok}. Like the most of the dense operations and big data processing problems, the Gram–Schmidt process steps can be performed by using parallel algorithms and can be implemented in parallel programming platforms. The parallelized algorithm is dependent to the platform used and needs to be adapted for the optimum performance for each parallel platform. The paper shows the algorithms and the implementation process of the Gram –Schmidt vector orthogonalosation in three different parallel platforms. The three platforms are: a) control flow shared memory hardware systems with OpenMP, b) control flow distributed memory hardware systems with MPI and c) dataflow architecture systems using Maxeler Data Flow Engines hardware. Using as single running example a parallel implementation of the computation of the Gram –Schmidt vector orthogonalosation, this paper describes how the fundamentals of parallel programming, are dealt in these platforms. The paper puts into evidence the Maxeler implementation of the Gram– Schmidt algorithms compare to the traditional platforms. Paper treats the speedup and the overall performance of the three platforms versus sequential execution for 50-dimensional Euclidian space. Keywords—Gram-Schmidt Algorithm; Parallel programmin