Search

There are few processes which display cyclically changing but predefined behavior. These processes can be represented using cyclo static data flow graphs (CSDFG). This capability results in a higher degree of parallelism. In this research we present the iteration bound for a CSDFG which is used to find the integral static schedule and determine whether a CSDFG is live or not based on some calculation. We also present an algorithm that schedules cyclo static data flow graphs without converting to their equivalent homogeneous graphs (EHG’s). Later we present an algorithm that schedules CSDFGs with different types of functional units, and also a technique called rotation scheduling which is applied for reducing the execution times of CSDFG and produce an optimal schedule. Finally all these are demonstrated with a suitable example.

The best way to increase the overall speed of a process is to increase the speed of the part of the process that takes the most time. Effective parallelization of iterative processes has been a focus of research, since the vast majority of computation performed by modern systems is iterative. For an iterative process to be parallelized, the operations that comprise the process must be organized into a schedule that will allow the hardware to correctly execute the instructions. The focus of our research is rotation scheduling, a list-scheduling-based method for producing compact, static schedules for iterative processes on parallel hardware. We develop a technique called rotation spanto compute the complete space of schedules that can be produced by rotation scheduling. We use rotation span as a basis of comparison for priority functions that can be used in rotation scheduling. We present three new heuristics based on rotation scheduling, half-rotation, random rotation, and best span, and compare them with existing methods. We discuss problems with existing methods, and show that random rotation is an effective alternative that avoids these problems.