A new design paradigm for a parallel uniform block distribution (UBD)‎ algorithm

الملخص EN

In several areas of parallelism, the novelty of parallel algorithms is formed by decomposing the algorithm’s sequence either on the basis of data or tasks without touching the internal peculiarity of the original algorithms (serial algorithm).

Parallel hardware has experienced significant growth in recent years and is readily affordable, as for today; multicore hardware now exists in the vast majority of low-cost digital devices.

At the same pace, parallel libraries have demonstrated a noticeable improvement and ease in utilisation.

These facts play a vital role in significantly changing the way of designing an algorithm.

In this paper, a new design paradigm for a parallel uniform block distribution (UBD) algorithm is proposed by taking advantage of the capability of the parallel libraries during the design phase of the parallel algorithm, rather than making parallelisation as an improvement stage.

In particular, the main contribution of this work utilises a new mathematical calculation that uses the thread ID as a variable to explicitly decompose the data of a matrix (array) of one or multiple dimensions among several threads in parallel.

Experimental results show a considerable speedup compared to the serial version of the algorithm and comparable results to the original OpenMP implementation.