一种基于分支定界和表调度的SoC设计方案搜索算法

A SoC Design Exploration Algorithm Based on Branch-and-Bound and List Scheduling

电子系统日趋复杂,需要采用自动化的方法来寻找最优的设计方案.提出了一种基于分支定界和表调度的片上系统(SoC)设计方案搜索算法.该算法分3个层次,前2个层次分别对模块的选择与共享方案采用分支定界法进行严格搜索,最后采用表调度方法进行任务调度.算法考虑任务的多种实现方式,并且充分搜索模块共享的可能.对多种不同规模的任务图进行了测试,并与现有方法进行了对比.结果表明,对于中小规模的系统设计,该算法能够在较短的时间内找到表调度策略下的最优方案.

As the electronic systems got more and more complicated, automatic design methods are needed to find the best solution. A design exploration algorithm based on branch-and-bound and list scheduling is proposed. The algorithm has architecture of three stages. At the first and second stage the module selection and sharing schemes are explored by the branch-and-bound method, while the list scheduling method is used to schedule the tasks in the third stage. Multiple module choices for the tasks are considered, and all the module sharing possibilities are fully explored. Several tests have been made for various task graphs of different scales. The performance of this algorithm is compared with those existing methods. The results indicate that for systems of small or medium scale with the list scheduling strategy the proposed algorithm can find the best solution in a short time.