| A Scheme for the BSP Scheduling of Generic Loop Nests (1997) | |||||||||||||||
Abstract | |||||||||||||||
| 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 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 partitioning, 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. 1 Introduction The prohibitive costs of parallel software design have led to an ever increasing interest in the automatic parallelisation of existing sequential code. As a result, remarkable advances have been made in areas such as data dependence analysis [6, 7, 24], code transformation [4, 22, 26], and potential parallelism identification [3, 18, 19]. Based... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||