CADSE: communication aware design space exploration for efficient run-time MPSoC management
CADSE: communication aware design space exploration for efficient run-time MPSoC management
Amit Kumar SINGH1,3(), Akash KUMAR1, Jigang WU2, Thambipillai SRIKANTHAN3
1. Department of Electrical and Computer Engineering, National University of Singapore, Singapore 119077, Singapore; 2. School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300160, China; 3. School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore
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.
Corresponding Author(s):
SINGH Amit Kumar,Email:eleaks@nus.edu.sg
引用本文:
. CADSE: communication aware design space exploration for efficient run-time MPSoC management[J]. Frontiers of Computer Science, 2013, 7(3): 416-430.
Amit Kumar SINGH, Akash KUMAR, Jigang WU, Thambipillai SRIKANTHAN. CADSE: communication aware design space exploration for efficient run-time MPSoC management. Front Comput Sci, 2013, 7(3): 416-430.
Kistler M, Perrone M, Petrini F. Cell multiprocessor communication network: built for speed. IEEE Micro , 2006, 26(3): 10-23 doi: 10.1109/MM.2006.49
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 doi: 10.1145/1331331.1331333
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 doi: 10.1109/TC.1987.5009446
4
Stuijk S, Geilen M, Basten T. SDF3: SDF for free. In: Proceedings of the 6th International Conference on Application of Concurrency to System Design . 2006, 276-278 doi: 10.1109/ACSD.2006.23
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 doi: 10.1109/ACSD.2006.33
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 doi: 10.1016/j.sysarc.2007.01.004
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 doi: 10.1109/TVLSI.2007.912097
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 doi: 10.1016/j.procs.2010.04.113
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 doi: 10.1016/j.sysarc.2010.04.007
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 doi: 10.1145/581199.581226
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 doi: 10.1049/iet-cdt.2010.0030
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 doi: 10.1007/978-3-642-01929-6_4
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 doi: 10.1145/1297666.1297683
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 doi: 10.1145/1455229.1455230
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 doi: 10.1145/1278480.1278674
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 doi: 10.1109/DATE.2010.5457211
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 doi: 10.1145/2038698.2038726
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 doi: 10.1145/1367045.1367049
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 doi: 10.1109/ESTMED.2008.4696986
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 doi: 10.1109/DSD.2009.145
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 doi: 10.1109/ISSOC.2008.4694878
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 doi: 10.1109/ISSOC.2006.321966
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 doi: 10.1109/SOCC.2011.6085078
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 doi: 10.1109/TII.2010.2062192
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 doi: 10.1109/MDT.2002.1018132
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/
