| Current trends in SOC (System-on-Chip) design impose ever greater productivity demands on designers to meet the functional and technological complexity challenges while meeting decreasing time-to-market pressure. How to efficiently schedule and map operations, data movement and variable storage on a practically constrained hardware platform is a crucial part of high quality digital system design. Current high-level flows use a manual divide and conquer approach. In particular, system level instances are partitioned into tasks which are composed of operations. The multi-level approach is due in part to the failure of scalability of existing scheduling and mapping algorithms. This work describes a hierarchical framework that can dramatically increase the scalability of existing scheduling and mapping algorithms while maintaining the same or superior quality. The framework does not rely on existing application hierarchy. Instead, it automatically builds a hierarchical representation from a flat one, and uses the hierarchy to globally guide the scheduling and mapping process. The result is a practical scheme enabling a two order of magnitude increase in problem scale (>10k operations) while maintaining near-optimal results. Further, this is achieved with sub-quadratic algorithmic complexity in contrast to current cubic heuristic complexity. This dramatic scalability improvement blurs the boundary between abstraction levels and promotes detailed scheduling and mapping optimization to the task level. |
