|
Abstract : |
This paper describes the WPRAM programming model, supported on a derivative of the Bulk Synchronous Parallel (BSP) architecture. The WPRAM provides a weakly coherent shared address space with asynchronous concurrent requests for shared variables. All operations have an associated time cost, and are scalable with respect to increasing machine size. This provides a basis for designing scalable parallel algorithms whose time complexity accounts for all overheads. A simulator for the WPRAM enables absolute performance to be estimated, using machine parameters from Inmos T9000 and C104 components. We outline a programming methodology in which an algorithm is first expressed in terms of the more abstract Strong PRAM model. This algorithm is then transformed onto the WPRAM model by considering practical issues of data locality, process synchronization and granularity. The scalability characteristics of the algorithm can then be analysed; a new approach to assessing scalability is proposed. Experimental results from the simulator may be used to validate this analysis. These ideas are demonstrated using the Simplex method for linear programming as a case study. 1, |
