PERFORMANCE STUDY OF A SIMULATED MULTIPROCESSOR FOR FUNCTIONAL PROGRAMS

Abstract

functional program, in general, unfolds recursively into subtasks giving it a tree structure. From Church-Rosser property of these languages, it follows that the final result of the program is independent of the order in which the subtasks are evaluated. This property makes the functional languages ideally suited to the domain of multiprocessing, since neither special techniques for extracting parallelism on the part of compiler nor special efforts to express parallelism on the part of programmer are required. This dissertation reports the work for evaluating the performance of a multiprocessor, through simulation, under different static schedulings for tree structured programs. The work aims at simultaneous minimization of communication and scheduling overheads, and load imbalances among processors. For simulating the multiprocessing environment, the behaviour of a functional program is abstracted by generating arbitrary task trees. Binary De Bruijn Multiprocessor (BDM) nets of variable sizes are simulated. Three static scheduling algorithms which map the arbitrary •task trees on BDM nets of different sizes are implemented and compared. Some results regarding the performance of the multiprocessor for different classes of problems are presented. An adaptive_to_load but static scheduling strategy has been developed which is shown to give a performance close to dynamic scheduling.