Efficient index generation for compiling two-level mappings in data-parallel programs

This paper presents compilation techniques used to compress holes, which ar e caused by the nonunit alignment stride in a two-level data-processor mapp ing. Holes are the memory locations mapped by useless template cells. To fu lly utilize the memory space, memory holes should be removed, In a two-leve l data-processor mapping, there is a repetitive pattern for array elements mapped onto processors. We classify blocks into classes and use a class tab le to record the distribution of each class in the first repetitive data di stribution pattern. Similarly, data distribution on a processor also has a repetitive pattern. We use a compression table to record the distribution o f each block in the first repetitive data distribution pattern on a process or. By using a class table and a compression table, hole compression can be easily and efficiently achieved. Compressing holes can save memory usage, improve spatial locality and further improve system performance, The propos ed method is efiicient, stable, and easy to implement. The experimental res ults do confirm the advantages of our proposed method over existing methods . (C) 2000 Academic Press.