PERFORMANCE EVALUATION OF TREE STRUCTURED PROGRAMS, ON HYPERCUBES

Abstract

Some programs unfold recursively into subtasks giving a tree structure where nodes represent tasks and edges represent communication between tasks. Nodes in a particular level can be executed simultaneously i.e. in parallel. So this kind of programs is ideally suitable for multiprocessing. This dissertation reports the work for evaluating the performance of a hypercube multiprocessor, through simulation, under designed static scheduling strategy for tree structured programs. The work aims at simultaneous minimization of communication overhead and load imbalance among processors. The behavior of programs is abstracted by generating arbitrary task tree. Hypercubes of various sizes are simulated. The designed scheduling strategy is tested on the hypercube for various trees of different depths, degrees of parallelization and fanouts. It is observed that for complete binary tree, the performances is ideal with no load imbalance. For other cases also the performances is observed to be quite good. (