Communication-aware allocation and scheduling framework for stream-oriented multi-processor systems-on-chip

ABSTRACT

This paper proposes a complete allocation and scheduling framework, where an MPSoC virtual platform is used to accurately derive input parameters, validate abstract models of system components and assess constraint satisfaction and objective function optimization. The optimizer implements an efficient and exact approach to allocation and scheduling based on problem decomposition. The allocation subproblem is solved through Integer Programming while the scheduling one through Constraint Programming. The two solvers can interact by means of no-good generation, thus building an iterative procedure which has been proven to converge to the optimal solution. Experimental results show significant speedups w.r.t. pure IP and CP exact solution strategies as well as high accuracy with respect to cycle accurate functional simulation. A case study further demostrates the practical viability of our framework for real-life systems and applications.

REFERENCES

• 1: Mirko Loghi , Federico Angiolini , Davide Bertozzi , Luca Benini , Roberto Zafalon, Analyzing On-Chip Communication in a MPSoC Environment, Proceedings of the conference on Design, automation and test in Europe, p.20752, February 16-20, 2004
• 2: S. Prakash and A. Parker, "SOS: Synthesis of Application-Specific Heterogeneous Multiprocessor Systems", Journal of Parallel and Distributed Computing, pp. 338--351, 1992.
• 3: Chunho Lee , Miodrag Potkonjak , Wayne Wolf, System-Level Synthesis of Application Specific Systems using A* Search and Generalized Force-Directed Heuristics, Proceedings of the 9th international symposium on System synthesis, p.2, November 06-08, 1996
• 4: A. Bender, MILP based task mapping for heterogeneous multiprocessor systems, Proceedings of the conference on European design automation, p.190-197, September 1996, Geneva, Switzerland
• 5: Y. Li and W. H. Wolf, "Hardware/Software Co-Synthesis with Memory Hierarchies", 1999 IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1405--1417, 1999.
• 6: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 7: Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002 [doi>10.1109/TVLSI.2002.1043323]
• 8: P. Palazzari and L. Baldini and M. Coli, "Synthesis of Pipelined Systems for the Contemporaneous Execution of Periodic and Aperiodic Tasks with Hard Real-Time Constraints", 18th International Parallel and Distributed Processing Symposium - IPDPS'04, pp. 121--128, Apr. 2004.
• 9: Radoslaw Szymanek , Krzysztof Kuchcinski, A constructive algorithm for memory-aware task assignment and scheduling, Proceedings of the ninth international symposium on Hardware/software codesign, p.147-152, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371706]
• 10: G. Fohler and K. Ramamritham, "Static Scheduling of Pipelined Periodic Tasks in Distributed Real-Time Systems", Procs. of the 9th EUROMICRO Workshop on Real-Time Systems - EUROMICRO-RTS '97, pp. 128--135, June 1997.
• 11: Jakob Axelsson, Architecture Synthesis and Partitioning of Real-Time Systems: A Comparison of Three Heuristic Search Strategies, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.161, March 24-26, 1997
• 12: P. Eles, Z. Peng, K. Kuchcinski and A. Doboli, "System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu search", Design Automation for Embedded Systems, pp. 5--32, 1997.
• 13: Sharath Kodase , Shige Wang , Zonghua Gu , Kang G. Shin, Improving Scalability of Task Allocation and Scheduling in Large Distributed Real-Time Systems Using Shared Buffers, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.181, May 27-30, 2003
• 14: P. Eles , K. Kuchcinski , Z. Peng , A. Doboli , P. Pop, Scheduling of conditional process graphs for the synthesis of embedded systems, Proceedings of the conference on Design, automation and test in Europe, p.132-139, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 15: K. Kuchcinski, "Embedded System Synthesis by Timing Constraint Solving", IEEE Transactions on CAD, pp. 537--551, 1994.
• 16: Erlendur S. Thorsteinsson, Branch-and-Check: A Hybrid Framework Integrating Mixed Integer Programming and Constraint Logic Programming, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.16-30, November 26-December 01, 2001
• 17: Andrew Eremin , Mark Wallace, Hybrid Benders Decomposition Algorithms in Constraint Logic Programming, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.1-15, November 26-December 01, 2001
• 18: Vipul Jain , Ignacio E. Grossmann, Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems, INFORMS Journal on Computing, v.13 n.4, p.258-276, September 2001 [doi>10.1287/ijoc.13.4.258.9733]
• 19: J. N. Hooker, "A Hybrid Method for Planning and Scheduling", Procs. of the 10th Intern. Conference on Principles and Practice of Constraint Programming - CP 2004, pp. 305--316, Sept. 2004.
• 20: Poletti Francesco , Poggiali Antonio , Paul Marchal, Flexible Hardware/Software Support for Message Passing on a Distributed Shared Memory Architecture, Proceedings of the conference on Design, Automation and Test in Europe, p.736-741, March 07-11, 2005 [doi>10.1109/DATE.2005.156]
• 21: M. Ruggiero, F. Angiolini, F. Poletti, D. Bertozzi, L. Benini, R. Zafalon, "Scalability Analysis of Evolving SoC Interconnect Protocols", Int. Symposium on System-on-Chip, 2004.
• 22: J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik, pp. 238--252, 1962.
• 23: Mirko Loghi , Federico Angiolini , Davide Bertozzi , Luca Benini , Roberto Zafalon, Analyzing On-Chip Communication in a MPSoC Environment, Proceedings of the conference on Design, automation and test in Europe, p.20752, February 16-20, 2004
• 24: J. N. Hooker and G. Ottosson, "Logic-based Benders decomposition", Mathematical Programming, pp. 33--60, 2003.
• 25: RTEMS Home Page, http://www.rtems.com