Abstract:In the high level synthesis of application-specific DSP, pipeline scheduling is a difficult and urgent problem. In this paper the theory of normalized scheduled data flow graph(NSDFG) which has the clear physical meaning is discussed. Based on the node movements in the NSDFG, the intrinsic mechanism of legal pipeline scheduling is studied in detail. The study proves that from any initial point in the design space any legal scheduling can be searched through the legal node movements. The self-contained set of legal transformations derived in this paper provides a key for the search-based algorithms to be applied in pipeline scheduling. Results for some examples are presented also.