ACCOUNTING FOR MEMORY BANK CONTENTION AND DELAY IN HIGH-BANDWIDTH MULTIPROCESSORS

For years, the computation rate of processors has been much faster tha n the access rate of memory banks, and this divergence in speeds has b een constantly increasing in recent years. As a result, several shared -memory multiprocessors consist of more memory banks than processors. The object of this paper is to provide a simple model (with only a few parameters) for the design and analysis of irregular parallel algorit hms that will give a reasonable characterization of performance on suc h machines. For this purpose, we extend Valiant's bulk-synchronous par allel (ssp) model with two parameters: a parameter for memory bank del ay, the minimum time for servicing requests at a bank, and a parameter for memory bank expansion, the ratio of the number of banks to the nu mber of processors. We call this model the (d, x)-BSP. We show experim entally that the (d, x)-BSP captures the impact of bank contention and delay on the GRAY C90 and J90 for irregular access patterns, without modeling machine-specific details of these machines. The model has cla rified the performance characteristics of several unstructured algorit hms on the GRAY C90 and J90, and allowed us to explore tradeoffs and o ptimizations for these algorithms. In addition to modeling individual algorithms directly, we also consider the use of the (d, x)-BSP as a b ridging model for emulating a very high-level abstract model, the Para llel Random Access Machine (PRAM). We provide matching upper and lower bounds for emulating the EREW and QRQW PRAMS on the (d, x)-BSP.