Sándor Juhász
Budapest University of Technology and Economics
Department of Automation and Applied
Informatics
1111 Bp, Goldmann György tér 3. IV. em.
E-mail: juhasz.sandor@aut.bme.hu
Being built from
standard personal computers and connected with standard communication networks,
clusters provide a cheaper alternative for solving highly demanding
computational problems, because their modularity allows easier implementation
of fault tolerance and scalability than it is done in traditional
supercomputers. The general-purpose communication elements usually have smaller
throughput than the ones developed for a special hardware environment; that is
why the communication planning plays a more critical role in algorithm design
in the cluster systems. Every distributed solution raises the question, whether
the costs of distribution and organisation are really lower than the benefits
gained from the distribution of the task, that means, whether it is worth, and
if so, in what extent to solve the problem in a distributed way. Because of the lower communication
throughput in the clusters the question has an even greater emphasis.
The performance of the algorithms is
basically influenced by the distribution of the tasks between the nodes and by
the communication pattern used for creating the solution. This paper examines
the problem class that allows domain decomposition and generates its solution
in several iteration steps. A mathematical model will be introduced that
describes the distributed way of solution of this relatively general problem
class. From this model we will derive whether it is worth, and in what kind of
conditions it is optimal to solve the problem in a distributed way in a
selected hardware environment. The questions concerning the effect of the
number of nodes on the speed, on the cost, and on the efficiency of the
solution will also be answered.
The applicability of the model will
be demonstrated on the examples coming from the domain of linear algebra and
from the computer aided image synthesis.