Idiom Recognition and Program Scheme Recognition Based Program Transformations for Performance Tuning--Beyond Compiler Optimizations--

Much effort has been performed for performance tuning. However, it is becoming clear that performance tuning is much harder in complicated modern parallel architectures. For performance tuning, compiler approach was prevailing in the era of vector architecture. Today, instead, PSE approach which provides users with abstract programming emerges, which also has a problem in tuning fine points. Another approach is ¿ autotuning¿ which is a brute force attack for performance tuning. We have proposed that idiom recognition can be a bridge between abstract source programs and concrete architectures. This paper applies term rewriting theory -a very general framework to the idiom recognition system. Moreover, we apply higher order term rewriting to find better patterns. We show that tiling and recursive algorithm scheme patterns can be reinvented by the extended idiom recognition. Furthermore, we discuss a method of enrichment of candidates of optimizations by using the general framework of graph rewriting.