Performance evaluation of iterative parallel algorithms

Abstract

Purpose

With the availability of powerful personal computers (PCs), workstations and networking devices, the recent trend in parallel computing is to connect a number of individual workstations (PC and PC symmetric multiprocessor systems (SMP)) to solve computation‐intensive tasks in parallel way on such clusters (networks of workstations (NOW), SMP and Grid). In this sense, it is not more true to consider traditionally evolved parallel computing and distributed computing as two separate research disciplines. Current trends in high performance computing are to use NOW (and SMP) as a cheaper alternative to traditionally used massively parallel multiprocessors or supercomputers and to profit from unifying of both mentioned disciplines. The purpose of this paper is to consider the individual workstations could be so single PC as parallel computers based on modern SMP implemented within workstation.

Design/methodology/approach

Such parallel systems (NOW and SMP), are connected through widely used communication standard networks and co‐operate to solve one large problem. Each workstation is threatened similarly to a processing element as in a conventional multiprocessor system. But, personal processors or multiprocessors as workstations are far more powerful and flexible than the processing elements in conventional multiprocessors. To make the whole system appear to the applications as a single parallel computing engine (a virtual parallel system), run‐time environments such as OpenMP, Java (SMP), message passing interface, Java (NOW) are used to provide an extra layer of abstraction.

Findings

To exploit the parallel processing capability of such cluster, the application program must be paralleled. The effective way how to do it for (parallelisation strategy) belongs to a most important step in developing effective parallel algorithm (optimisation). To behaviour analysis, all overheads that have the influence to performance of parallel algorithms (architecture, computation, communication, etc.) have to be taken into account. In this paper, such complex performance evaluation of iterative parallel algorithms (IPA) and their practical implementations are discussed (Jacobi and Gauss‐Seidel iteration). On real application example, the various influences in process of modelling and performance evaluation and the consequences of their distributed parallel implementations are demonstrated.

Originality/value

The paper usefully shows that better load balancing can be achieved among used network nodes (performance optimisation of parallel algorithm). Generally, it claims that the parallel algorithms or their parts (processes) with more communication (similar to analyzed Gauss‐Seidel parallel algorithm) will have better speed‐up values using modern SMP parallel system as its parallel implementation in NOW. For the algorithms or processes with small communication overheads (similar to analysed Jacobi parallel algorithm) the other network nodes can be used based on single processors.

Citation

Hanuliak, I. and Hanuliak, P. (2010), "Performance evaluation of iterative parallel algorithms", Kybernetes, Vol. 39 No. 1, pp. 107-126. https://doi.org/10.1108/03684921011021309