Decomposition and performance in parallel algorithms
Gary Harkin, Robert E. Lord · 1988
The effect of decomposition decisions on the performance of parallel algorithms is studied. The general task graph model of concurrency and an MIMD architecture are the basis for investigating a model of decomposition, synchronization and their effect on algorithm performance. Decomposition is reduced to a set of statistical parameters which describe the process; task selection, task partitioning, replacement subtask selection and synchronization reassignment. A simple linear model of synchronization cost is developed and applied to three specific architectures; shared-memory, bus-connected and network-connected. The model is analyzed to determine the relationships between machine architecture, algorithm characteristics, decomposition decisions and algorithm performance. It is shown that the probability distributions for task size and the number of synchronizations on a task are approximately exponential and a function for execution time is derived using Extreme Value Statistics. The growth of synchronization cost is shown to be bounded above as the number of tasks increases. A simulation of model behaviour is used to validate the model and to test more complex decomposition decisions.