SCALABILITY EVALUATION OF ONE-LEVEL RECURSION PARALLEL STRASSEN’S ALGORITHM ON MULTICORE PROCESSORS - KAWU, AHMAD JIBIR; UMAR, AISHATU YAHAYA; BALA, SAMINU I. (BIMA JOURNAL OF SCIENCE AND TECHNOLOGY GOMBE, 2020)
Scalability plays a key role in determining the potential worthiness of a parallel system . It can be used to determine the performance of a parallel system on a large volume of data given a certain number of processors from known performance on fewer processors. Scalability is a measure of the ability of a parallel system (algorithm + architecture) to decrease the computation time in proportion to the number of available processors. The upper bound of scalability is the minimum number of processors for which the speedup takes the minimum value. Common parallel algorithm evaluation metric like Amdahl’s law and Gustafson –Barsis’s have the draw back that they do not take into account the parallel overhead and therefore overestimate the speedup. This makes them unsuitable for investigating scalability. The main characteristics of scalability are speedup and efficiency. The objective of this paper is to evaluate the scalability of One-Level Recursion parallel Strassen’s algorithm on multicore processors (Intel Dual core and AMD Quad-core). This algorithm is a variant of the Strassen’s algorithm where recursion stops at level one. Thus, as a new algorithm, there is need to determine its scalability. This is done by experimentally determining the fraction of sequential code of a parallel algorithm and the parallel overhead using Karp-Flatt metric (to determine whether they are responsible for or against speedup). The results obtained showed that both parallel overhead and fraction of sequential code have negligible impact on the performance of the One-Level Recursion Strassen algorithm. Furthermore, a super linear speedup was observed on the quad-core processor. This will help in prediction and decision making of parallel system combination for cost effective and efficient performance.