Temporal characterizations of parallel program demands for data movement
Bernardo Rodriguez, Harry F. Jordan · 1996
This work studies the temporal characterization of program demands for data movement. We concentrate on demands that are defined by data sharing, which can be estimated statically for programs that define sequences of operations to be executed by a fixed number of processes on a general class of shared memory multiprocessors. We present two program metrics that characterize the occurrence of reads to shared data that cause data to move across shared hardware components. We first present the Read Multiplicity metric and assume a simple execution model where processes execute in lock-step and there are no synchronization operations. We apply this metric to a set of program segments that read a shared vector and predict the effectiveness of the read-broadcast mechanism on the KSR multiprocessor. We show that even with our simplifying assumptions, the metric is useful to predict the behavior of simple program segments on complex architectures. To characterize complete programs we develop an execution model for barrier synchronized programs and relax our assumption of lock-step execution progress. We propose a metric that characterizes the demands for data movement that occur on the first read by a processor of data written by another processor (Intelprocess Read or IR). We develop a method for calculating the IR metric over programs with barrier and critical section synchronization and apply the metric to a set of programs that are part of the SPLASH benchmark suite. Our metric shows the non-uniform distribution of IRs in the programs examined. We run the programs over a bus network simulator and a shuffle and manhattan network simulators and show that characterization at small time scales is necessary to predict the contention for components in the interconnection networks, since the contention cannot be predicted from characterizations at the program scale.