Introduction
Parallel computing is based on partition of a computational problem into
sub-problems to be executed simultaneously by several processing units
and is characterized by the potential to improve the performance, the
cost-performance, and the productivity [1]. The constant demand for more
significant computing power has evolved this area, from architecture to
systems and specialised libraries. Parallel Computing is firmly established
in intensive numerical processing [2]. Several parallel systems have been
proposed to solve numerical problems, e.g. in [3] a parallel solution of
Cholesky factorization is proposed to invert symmetric positive definite
linear systems; in [4] a parallel diffuse genetic mining algorithm is
proposed based on a master-slave architecture responsible for extracting
association rules. However, a parallel system not only has multiple
streams of instructions running simultaneously but also involves other
challenges, as communication structures, synchronisation and competition
between processes, coupled with the mapping process and workload
balance.
The cost-performance ratio of an algorithm is affected by its design, and
by the characteristics of the processing units. Methodologies such
as Partition, Communication, Agglomeration and Mapping (PCAM)
[4], Partition, Granularity, Agglomeration and Mapping (PGAM) [5],
and Decomposition, Agglomeration, Orchestation and Mapping (DAOM)
[6], expose the analysis and design of parallel algorithms as
decomposition and assignment tasks of different processing elements. We
propose a generic methodology that captures the main characteristics of
the current methodologies and adds the experience of expert
programmers through a pattern language [7]. Our proposal provides a
high-level methodology for fast prototyping of parallel algorithms
implementations reducing the execution time and with minimum
programming effort.
Section 2 describes the background, Sect. 3 the generic methodology for
parallel algorithm design, and Sect. 4 the strategies to parallel k-means.
Last section summarises the main conclusions and sketches future work.
2 Parallel Methodologies
A sequential algorithm consists of a single flow of instructions, each
executed exclusively at a given time by a single processing unit. In parallel
computing more than just one processing units execute instructions
simultaneously; aiming to achieve higher performance [4]. Our
methodology addresses the parallelism based on partition a computational
problem into a set of tasks, treated concurrently by a set of processing
units. Each task is composed by a series of instruction or data sets
processed simultaneously. The decomposition of the problem is
performed by three different mechanisms: Domain decomposition, where
the corresponding storage set is partitioned according to the processing
units; Functional decomposition, where the instruction set is divided
in clusters to be processed; and a combination of the above as activity
parallelism [3, 9]. A parallel computer consists of a set of processing
units, connected through communication channels in order to work
cooperatively [3, 7]. Any communication channel is determined by
processing and communications. For instance, in shared memory
environments, communication is quick and uniform in access time, due to
the closeness between processing units. In distributed memory systems,
the communication times variate depending on the characteristics of the
network, communication protocols, bandwidth and other factors causing
non-uniform access to memory. Furthermore, the granularity of the
processes should be analysed as the relationship between the amount of
computation and the communication structure formed by the processing
units. Finally, factors such as mapping and load balance directly affect the
performance of the algorithm. The uniform load distribution between the
processing units allows to perform a similar amount of work and to remain
busy for most of the time. Mapping strategies provide a load balance that
is not always ideal, however, they avoid occurrences of idle processors.