Effects of communication media on parallel algorithms for a cluster


A cluster is a type of parallel or distributed processing system, which consists of a collection of interconnected stand alone computers (nodes) working together as a single integrated computing resource.

A node can be a single or multiprocessor system (PCs, workstation or SMPs) with memory, I/O facilities of an operating system. A cluster generally refers to two or more nodes connected together. The nodes can exist in a single cabinet or be physically separated and connected via a LAN. An interconnect (LAN based) cluster of computers can appear as a single system to users and applications.

Communication software offers a means of fast and reliable data communication among cluster nodes. Clusters with special network switch use communication protocols such as active messages for best communication among the nodes. They bypass the operating system and thus remove the critical communication overheads providing direct user level access to the network interface. The approach maximizes the range of options that provides mechanisms for evaluating alternatives and thus reduces the cost of backtracking from wrong choices.

The four distinct stages are: partitions, communications, agglomerations and mappings. Partitioning is decomposing the task (computational activities and the data it operates) into several small tasks. The communication aspect focuses on the flow of information and co-ordination among the tasks that are created during the partitioning stage. In the agglomerations, the tasks and communication structures defined in the first 2 stages are evaluated in terms of performance requirements and implementations costs. Finally, the mapping is concerned with assigning each task to a processor such that it maximizes utilization of system resources (such as CPU) while minimizing the communication costs. These decisions can be taken statically or dynamically at run time.

The challenge here is to improve the effect of communication media for improved performance on applications on clusters built using the above methodology. The Master/Slave structure is selected for the parallel programming paradigm.


The goal is to share processes between clusters in such a way that the transfer rate among cluster nodes is minimized and the utilization of the resources (such as CPU) is maximized.


A dynamic table is created in the master node of the cluster that keeps track of the memory cycles and memory available in all the nodes of the cluster. A copy of it is also made available at all the nodes. The network layout is layered based on distance and media bandwidth to the node from the master. Graph theory is used to give weights to the communication media between the nodes. Longer the distance from the master, larger is the weight on the link (media) multiplied by bandwidth. The hierarchy of an enterprise is followed here for layering.

When a task is received by the master, it divides it into smaller tasks depending on the machine time required to execute them. They are then sorted in an array. The dynamic table at the master is checked to find the resource availability at the nodes. The task (data and processes) is then distributed based on the layers. Larger tasks are allowed to the nodes at the lower layers and smaller tasks to the nodes at the higher layers so as to reduce the latency on the communication media and improve the performance. In the hierarchy the nodes at the higher level can also share the master load.