Prof. Dr. Frank Dehne(Carleton University Ottawa)Realistic Parallel Algorithms: Limited Bandwidth, Large Local Memories, and Parallel Disks During the last decade, parallel algorithm design has experienced a dramatic change, away from fine grained shared memory and network models, and towards coarse grained models like Valiant's BSP (Batch Synchronous Parallel Machine) and our CGM (Coarse-Grained Multicomputer). The aim of these recent models is to bridge the previously wide gap between parallel algorithm design and the actual, commercially available, parallel hardware and programming tools used in practice. For parallel algorithms to be relevant, the theoretical analysis of its speed and other critical variables must match closely the empirical values of these variables observed in implementations on commercially available parallel machines. Important factors to be considered include not only limited bandwidth but also large local memories and parallel disks. In this presentation, we will outline the strengths and weaknesses of the CGM model in dealing with the realities of todays parallel processing architectures and applications. |