Designing and Modelling Distributed Algorithms for PC clusters

Juhász Sándor <sanyo@avalon.aut.bme.hu>

Budapesti Mûszaki és Gazdaságtudományi Egyetem

While World Wide Web provides a full solution to the unstructured data sharing on the whole planet, and the e-mail systems cover all types of the remote data exchange between people, the technology of sharing processing capacities via the network is still immature. The main reason behind this is the big number of contradictory requirements and the complexity of distributed software design. In this paper our goal is to present a mathematical model, that allows the optimization of different distributed algorithms running in a PC cluster environment. First, the terminology and design phases and the requirements of parallel and distributed algorithms are introduced.

The main part of this paper presents a model aiming to describe parallel algorithms in a cluster environment built up of PCs connected with a TCP/IP network. Being able to predict certain properties of an algorithm by making some calculation based on the parameters of the system and the task to solve, the optimization can be solved with simple mathematical tools. Here we consider the minimization of execution time as primary requirement.

To demonstrate the usability of this method for modeling and optimization, an example is presented, where the measured and the predicted execution time of a distributed database query algorithm is compared.