Algorithm optimization on HPM model

摘要

Algorithm and program optimization for parallel computation is discussed in this paper. The discussion is based on the HPM model for parallel computation. A parallel HPM algorithm consists of a set of independent sub-algorithms (which is Enhanced RAM) algorithm). These sub-algorithms are interacted through some data interactive points. The performance of an HPM parallel algorithm mainly depends on two kinds of factors: The parallelism and the overhead of the data interactive points: vertical (memory) interactive points and crossing (communication) interactive points. We will discuss the influence of vertical (memory) interactive and crossing interactive points on the performance, and give some optimization methods for the memory hierarchy k and k~+. The "fix point", blocking and 'horizontal-vertical' blocking macro pipelining strategies are discussed in this paper. Practical results are also given.