Scheduler implementation in MP SoC design

ABSTRACT

In the design of a heterogeneous multiprocessor system on chip, we face a new design problem; scheduler implementation. In this paper, we present an approach to implementing a static scheduler, which controls all the task executions and communication transactions of a system according to a pre-determined schedule. For the scheduler implementation, we consider both intra-processor and inter-processor synchronization. We also consider scheduler overhead, which is often neglected. In particular, we address the issue of centralized implementation versus distributed implementation. We investigate the pros and cons of the two different scheduler implementations. Through experiments with synthetic examples and a real world multimedia application, we show the effectiveness of our approach.

REFERENCES

• 1: Ahmed Amine Jerraya , Sungjoo Yoo , Diederik Verkest , Norbert Wehn, Embedded Software for Soc, Kluwer Academic Publishers, Norwell, MA, 2003
• 2: Youngchul Cho , Ganghee Lee , Sungjoo Yoo , Kiyoung Choi , Nacer-Eddine Zergainoh, Scheduling and Timing Analysis of HW/SW On-Chip Communication in MP SoC Design, Proceedings of the conference on Design, Automation and Test in Europe: Designers' Forum, p.20132, March 03-07, 2003
• 3: JoAnn M. Paul , Alex Bobrek , Jeffrey E. Nelson , Joshua J. Pieper , Donald E. Thomas, Schedulers as model-based design elements in programmable heterogeneous multiprocessors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775938]
• 4: Janez Brest , Viljem Zumer, A Performance Evaluation of List Scheduling Heuristics for Task Graphs without Communication Costs, Proceedings of the 2000 International Workshop on Parallel Processing, p.421, August 21-24, 2000
• 5: Petru Eles , Zebo Peng , Paul Pop , Alex Doboli, Scheduling with bus access optimization for distributed embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.472-491, Oct., 2000 [doi>10.1109/92.894152]
• 6: M. Engels and T. Meng, "Rapid prototyping of a real-time video encoder," Proc. International Workshop on Rapid System Prototyping, pp. 8--15, 1994.
• 7: J. L. Pino and E. A. Lee, "Hierarchical static scheduling of dataflow graph onto multiprocessors," Proc. International Conference on Acoustics, Speech, and Signal Processing, pp. 2643--2646, 1995.
• 8: Faraydon Karim , Alain Mellan , Anh Nguyen , Utku Aydonat , Tarek Abdelrahman, A Multilevel Computing Architecture for Embedded Multimedia Applications, IEEE Micro, v.24 n.3, p.56-66, March 2004 [doi>10.1109/MM.2004.1]
• 9: Babak Falsafi , David A. Wood, Scheduling Communication on an SMP Node Parallel Machine, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.128, February 01-05, 1997
• 10: J.-Y. Colin and M. Nakechbandi, "Scheduling tasks with communication delays on a two-level virtual distributed system," in Proc. Euromicro Workshop on Parallel and Distributed Processing, pp. 344--348, 1999.
• 11: K. Lahiri, A. Raghunathan, and S. Dey, "System-level performance analysis for designing on-chip communication architecture," IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 6, pp. 768--783, 2001.
• 12: ARM Inc., AMBA#8482; Specification (Rev 2.0), available in http://www.arm.com/.
• 13: ARM, Inc., ARM9#8482; FAMILY, available in http://www.arm.com.
• 14: NEC Inc., "IC memory selection guide," available in http://www.nec.com.
• 15: Redhat Inc., eCos, available in http://www.redhat.com/embedded/technologies/ecos/.