Isoefficiency Maps for Divisible Computations in Hierarchical Memory Systems

In this paper we analyze impact of memory hierarchy on divisible load processing. Current computer systems have hierarchical memory systems. The core memory is fast but small, the external memory is large but slow. It is possible to avoid using external memory by parallelizing computations or by processing smaller work chunks sequentially. We will analyze how a combination of these two options improves efficiency of the computations. For this purpose divisible load theory representing data-parallel applications is used. A mathematical model for scheduling divisible computations is formulated as a mixed integer linear program. The model allows for executing multiple load installments sequentially or in parallel. The efficiency of the schedule is analyzed with respect to the impact of load size and machines number. The results are visualized as isoefficiency maps.