A COMPARATIVE STUDY OF LOAD SHARING POLICIES IN HYPERCUBE MULTICOMPUTERS

Abstract

A MULTI COMPUTER is an interconnected collection of autonomous nodes, each of which consists of a processor with its own private memory. All these nodes are connected via an interconnection network. Among the interconnection networks presently existing, hypercube networks have spurred much attention over the past years because of their appealing properties such as high regularity, fault tolerance, high bandwidth and ability to host popular interconnection networks like rings, linear arrays, trees, meshes etc. Most of the commercial multicomputers are built on hypercube topology . In hypercube multicomputers interprocessor communication is done by explicit message passing directly or through intermediate processors. Random arrival of tasks in such multicomputer systems temporarily overload some nodes while leaving others idle or only lightly loaded. Load sharing (LS) improves performance of the overall system by transferring tasks from the highly loaded nodes to the lightly loaded nodes, where the tasks can take advantage of computing capacity that would otherwise go unused. For this thesis work four load sharing algorithms with different approaches are taken from the literature, (namely random selection, random probing, preferred list, bidding algorithm) simulated, and their performances are compared for hypercube multicomputer systems. They exhibited different performances under different conditions and performance metrics. Simulation is carried on TATA ELXSI dual platform using IRIX operating system (a multiprocessor implementation of UNIX.)The programs for all the algorithms are written in `C' language.