Interleaved Subtask Scheduling on Multi Processor SOC

The ever-progressing semiconductor processing technique has integrated more and more embedded processors on a single system-on-achip (SoC). With such powerful SoC platforms, and also due to the stringent time-to-market deadlines, many functionalities which used to be implemented in ASICs are migrating to embedded processors. Conventional embedded system design techniques that rely on manual partitioning and scheduling of software components are clearly not able to meet the requirements of today's dynamic software functionalities. The large amount of software components which are present in embedded systems require a novel high-level design methodology that can quickly explore the design space and hence map them onto the multiple embedded processors in an ef??cient manner. The Task Concurrency Management (TCM) methodology developed at IMEC since 1999 addresses the mapping of dynamic and concurrent tasks on multiple processors for real-time embedded systems, where energy consumption is often a major concern. The cornerstone of this methodology is a design-time/run-time combined scheduling method, which provides the required ??exibility at a low run-time overhead. In this thesis, we mainly focus on extending the previous scheduling algorithms of TCM at both design-time and run-time. We ??rst propose a hierarchical design-time scheduler that can deal with very large task models in a scalable way. A prototype of our hierarchical scheduler has achieved speed-ups up to 2 orders of magnitude than the previous design-time scheduler on large input task models. Then we extend the previous TCM run-time scheduling algorithm with an interleaving technique. The new run-time scheduling algorithm can provide an average performance improvement of 20% compared with the previous one. The effectiveness of our new algorithms has been veri??ed by experiments both on a cycle-accurate simulator and a real-life hardware platfor