GEM: A geometric algorithm for scheduling
S. Raje, Majid Sarrafzadeh · 1993 IEEE International Symposium on Circuits and Systems · 2002
Scheduling in high-level synthesis is essentially assigning operations to different clock cycles or Csteps. A simple algorithm for scheduling in high-level synthesis is presented. The critical path (longest path) approach is used, schedules better than or comparable to the existing algorithms are obtained. The algorithm uses weighted geometric point dominance matching from the operations onto the control steps (Csteps) or the clock cycles. The time complexity of the algorithm is O(nplogp), where n is the number of disjoint paths in the CDFG, and p the number of nodes in the longest path. The algorithm can schedule a system with multiple loops or nested conditional branches incurring no extra penalty in terms of time complexity.>