Structure-based automatic extraction of the program heterogeneity

Heterogeneous computing is a new branch of parallel processing and is expected to reach super-speedup. It is an important step for heterogeneous computing to extract the heterogeneity hiding in a program. Such work is rather difficult, and some concepts and terminology are ambiguous. From the point of view of program structure, this paper presents formal definitions of SISD, SIMD and MIMD, which are the foundations for extracting program heterogeneity. Moreover, some heterogeneity criteria for several types of loop programs are proposed.