Radu Calinescu August 1997, 26pp.
This report presents a scheme for the bulk-synchronous parallel (BSP) scheduling of generic, untightly nested loops. Being targeted at the BSP model of computation, the novel of parallelisation scheme yields parallel code which is scalable, portable, and whose cost can be accurately analysed. The scheme comprises three stages: data dependence analysis and potential parallelism identification, data and computation partioning, and synchronisation and communication generation. New algorithms tackling each of the three stages are presented in the report, together with an algorithm for assessing the cost of the resulting BSP schedules.