CADSE: communication aware design space exploration for efficient run-time MPSoC management

Abstract

Real-time multi-media applications are increasingly mapped on modern embedded systems based on multiprocessor systems-on-chip (MPSoC). Tasks of the applications need to be mapped on the MPSoC resources efficiently in order to satisfy their performance constraints. Exploring all the possible mappings, i.e., tasks to resources combinations exhaustively may take days or weeks. Additionally, the exploration is performed at design-time, which cannot handle dynamism in applications and resources’ status. A runtime mapping technique can cater for the dynamism but cannot guarantee for strict timing deadlines due to large computations involved at run-time. Thus, an approach performing feasible compute intensive exploration at design-time and using the explored results at run-time is required. This paper presents a solution in the same direction. Communicationaware design space exploration (CADSE) techniques have been proposed to explore different mapping options to be selected at run-time subject to desired performance and available MPSoC resources. Experiments show that the proposed techniques for exploration are faster over an exhaustive exploration and provides almost the same quality of results.

Keywords

multiprocessor systems-on-chip / design space exploration / run-time mapping / synchronous dataflow graphs / throughput

References

[1] Kistler M, Perrone M, Petrini F. Cell multiprocessor communication network: built for speed. IEEE Micro, 2006, 26(3): 10-23

[2] Kim M, Banerjee S, Dutt N, Venkatasubramanian N. Energy-aware cosynthesis of real-time multimedia applications on mpsocs using heterogeneous scheduling policies. ACM Transactions on Embedded Computing Systems, 2008, 7(2): 1-19

[3] Lee E, Messerschmitt D. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Transactions on Computers, 1987, 100(1): 24-35

[4] Stuijk S, Geilen M, Basten T. SDF³: SDF for free. In: Proceedings of the 6th International Conference on Application of Concurrency to System Design. 2006, 276-278

[5] Ghamarian A H, Geilen M C W, Stuijk S, Basten T, Moonen A J M, Bekooij M J G, Theelen B D, Mousavi M R. Throughput analysis of synchronous data flow graphs. In: Proceedings of the 6th International Conference on Application of Concurrency to System Design. 2006, 25-36

[6] Ascia G, Catania V, Di Nuovo A, Palesi M, Patti D. Effcient design space exploration for application specific systems-on-a-chip. Journal of Systems Architecture, 2007, 53(10): 733-750

[7] Stuijk S, Geilen M, Basten T. A predictable multiprocessor design flow for streaming applications with dynamic behaviour. In: Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. 2010, 548-555

[8] Nollet V, Avasare P, Eeckhaut H, Verkest D, Corporaal H. Run-time management of a MPSoC containing FPGA fabric tiles. IEEE Transactions on Very Large Scale Integration Systems, 2008, 16(1): 24-33

[9] Singh A K, Jigang W, Kumar A, Srikanthan T. Run-time mapping of multiple communicating tasks on MPSoC platforms. Procedia Computer Science, 2010, 1(1): 1019-1026

[10] Singh A K, Srikanthan T, Kumar A, Jigang W. Communication-aware heuristics for run-time task mapping on NoC-based MPSoC platforms. Journal of Systems Architecture, 2010, 56(7): 242-255

[11] Yang P, Marchal P, Wong C, Himpe S, Catthoor F, David P, Vounckx J, Lauwereins R. Managing dynamic concurrent tasks in embedded real-time multimedia systems. In: Proceedings of the 15th International Symposium on System Synthesis. 2002, 112-119

[12] Ykman-Couvreur C, Avasare P, Mariani G, Palermo G, Silvano C, Zaccaria V. Linking run-time resource management of embedded multicore platforms with automated design-time exploration. IET Computers Digital Techniques, 2011, 5(2): 123 -135

[13] Singh A K, Kumar A, Jigang W, Srikanthan T. Communication-aware design space exploration for effcient run-time mpsoc management. In: Proceedings of the 4th International Symposium on Parallel Architectures, Algorithms and Programming. 2011, 72-76

[14] Moreira O, Valente F, Bekooij M. Scheduling multiple independent hard-real-time jobs on a heterogeneous multiprocessor. In: Proceedings of the 7th ACM & IEEE International Conference on Embedded software. 2007, 57-66

[15] Bonfietti A, Lombardi M, Milano M, Benini L. Throughput constraint for synchronous data flow graphs. In: Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 2009, 26-40

[16] Ahn Y, Han K, Lee G, Song H, Yoo J, Choi K, Feng X. SoCDAL: system-on-chip design accelerator. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(1): 1-38

[17] Keinert J, Schlichter T, Falk J, Gladigau J, Haubelt C, Teich J, Meredith M. Systemcodesigner — automatic ESL synthesis approach by design space exploration and behavioral synthesis for streaming applications. ACM Transactions on Design Automation of Electronic Systems, 2009, 14(1): 1-23

[18] Stuijk S, Basten T, Geilen M, Corporaal H. Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs. In: Proceedings of the 44th annual Design Automation Conference. 2007, 777-782

[19] Castrillon J, Tretter A, Leupers R, Ascheid G. Communication-aware mapping of KPN applications onto heterogeneous MPSoCs. In: Proceedings of the 49th Annual Design Automation Conference. 2012, 1266-1271

[20] Mariani G, Avasare P, Vanmeerbeeck G, Ykman-Couvreur C, Palermo G, Silvano C, Zaccaria V. An industrial design space exploration framework for supporting run-time resource management on multi-core systems. In: Proceedings of the 2010 Conference on Design, Automation and Test in Europe. 2010, 196-201

[21] Singh A, Kumar A, Srikanthan T. A hybrid strategy for mapping multiple throughput-constrained applications on MPSoCs. In: Proceedings of the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems. 2011, 175-184

[22] Singh A K, Kumar A, Srikanthan T. Accelerating throughput-aware runtime mapping for heterogeneous MPSoCs. ACM Transactions on Design Automation of Electronic Systems. To appear

[23] Kumar A, Fernando S, Ha Y, Mesman B, Corporaal H. Multiprocessor systems synthesis for multiple use-cases of multiple applications on FPGA. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(3): 40-66

[24] Benini L, Bertozzi D, Milano M. Resource management policy handling multiple use-cases in MPSoC platforms using constraint programming. In: Proceedings of the 24th International Conference on Logic Programming. 2008, 470-484

[25] Stralen v P, Pimentel A. Scenario-based design space exploration of MPSoCs. In: Proceedings of the 2010 IEEE International Conference on Computer Design. 2010, 305 -312

[26] Palermo G, Silvano C, Zaccaria V. Robust optimization of SoC architectures: a multi-scenario approach. In: Proceedings of the 2008 IEEE/ACM/IFIP Workshop on Embedded Systems for Real-Time Multimedia. 2008, 7 -12

[27] Singh A, Jigang W, Prakash A, Srikanthan T. Mapping algorithms for noc-based heterogeneous mpsoc platforms. In: Proceedings of the 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools. 2009, 133-140

[28] Carvalho E, Moraes F. Congestion-aware task mapping in heterogeneous MPSoCs. In: Proceedings of the 2008 International Symposium on System-on-Chip. 2008, 1-4

[29] Ykman-Couvreur C, Nollet V, Catthoor F, Corporaal H. Fast multidimension multi-choice knapsack heuristic for MP-SoC run-time management. In: Proceedings of the 2006 International Symposium on System-on-Chip. 2006, 1-4

[30] Kaushik S, Singh A K, Srikanthan T. Computation and communication aware run-time mapping for NoC-based MPSoC platforms. In: Proceedings of the 2011 IEEE International SOC Conference. 2011, 185-190

[31] Kaushik S, Singh A K, Jigang W, Srikanthan T. Run-time computation and communication aware mapping heuristic for noc-based heterogeneous mpsoc platforms. In: Proceedings of the 4th International Symposium on Parallel Architectures, Algorithms and Programming. 2011, 203 -207

[32] Schranzhofer A, Chen J J, Thiele L. Dynamic power-aware mapping of applications onto heterogeneous MPSoC platforms. IEEE Transactions on Industrial Informatics, 2010, 6(4): 692 -707

[33] Paulin P G, Pilkington C, Bensoudane E, Langevin M, Lyonnard D. Application of a multi-processor SoC platform to high-speed packet forwarding. In: Proceedings of the 2004 Conference on Design, Automation and Test in Europe. 2004, 58-63

[34] Rutten M, Van Eijndhoven J, Jaspers E, Van Der Wolf P, Gangwal O, Timmer A, Pol E. A heterogeneous multiprocessor architecture for flexible media processing. Design & Test of Computers, IEEE, 2002, 19(4): 39-50

[35] Murthy P K. Scheduling techniques for synchronous and multidimensional synchronous dataflow. PhD thesis, EECS Department, University of California, Berkeley, 1996

[36] Encyclopedia of integer sequences. http://oeis.org/

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg