SCALABILITY EVALUATION OF ONE-LEVEL RECURSION PARALLEL STRASSEN’S ALGORITHM ON MULTICORE PROCESSORS

Abstract

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.