Abstract:Flow dependence is a key factor influencing loop scheduling on VLIW (very long instruction word) architectures. Current research has not exploited the lockstep property of VLIWs. By making using of this property and centering on the concept of inclusion, a complete mathematical model for flow dependence analysis on VLIW architectures is presented in this paper. It is found that loop-carried flow dependencies form a set of disjoint linear ordered sets, and that there is one and only one basis that is independent and inclusive, making unnecessary all the other dependencies. The model allows multi-cycled operations and conditional branches. It lays a mathematical foundation for research on VLIWs, and is applicable to engineering practice.