More Web Proxy on the site http://driver.im/

research-article

Dynamic task mapping for Network-on-Chip based systems

Authors:

Saif U.R. Malik,

Sajjad A. MadaniAuthors Info & Claims

Journal of Systems Architecture: the EUROMICRO Journal, Volume 61, Issue 7

Pages 293 - 306

https://doi.org/10.1016/j.sysarc.2015.06.001

Published: 01 August 2015 Publication History

Abstract

Efficiency of Network-on-Chip (NoC) based multi-processor systems largely depends on optimal placement of tasks onto processing elements (PEs). Although number of task mapping heuristics have been proposed in literature, selecting best technique for a given environment remains a challenging problem. Keeping in view the fact that comparisons in original study of each heuristic may have been conducted using different assumptions, environment, and models. In this study, we have conducted a detailed quantitative analysis of selected dynamic task mapping heuristics under same set of assumptions, similar environment, and system models. Comparisons are conducted with varying network load, number of tasks, and network size for constantly running applications. Moreover, we propose an extension to communication-aware packing based nearest neighbor (CPNN) algorithm that attempts to reduce communication overhead among the interdependent tasks. Furthermore, we have conducted formal verification and modeling of proposed technique using high level Petri nets. The experimental results indicate that proposed mapping algorithm reduces communication cost, average hop count, and end-to-end latency as compared to CPNN especially for large mesh NoCs. Moreover, proposed scheme achieves up to 6% energy savings for smaller mesh NoCs. Further, results of formal modeling indicate that proposed model is workable and operates according to specifications.

References

[1]

A. Kumar Singh, W. Jigang, A. Kumar, T. Srikanthan, Run-time mapping of multiple communicating tasks on MPSoC platforms, International Conference on Computational Science, ICCS 2010, May 2010, 1 (1) (2010) 1019-1026.

[2]

A. Kumar Singh, T. Srikanthan, A. Kumar, W. Jigang, Communication-aware heuristics for run-time task mapping on NoC-based MPSoC platforms, J. Syst. Architect., 56 (2010) 242-255.

Digital Library

[3]

Vincenzo Rana, David Atienza, Marco Domenico Santambrogio, Donatella Sciuto, Giovanni De Micheli, A reconfigurable Network-on-Chip architecture for optimal multi-processor SoC communication, 16th IFIP/IEEE International Conference on Very Large Scale Integration, Rhodes, Greece, October 13-15, 2008.

[4]

Pradip Kumar Sahu, Santanu Chattopadhyay, A survey on application mapping strategies for Network-on-Chip design, J. Syst. Architect., 59 (2013) 60-76.

Digital Library

[5]

Carvalho, Ewerson, Ney Calazans, Fernando Moraes, Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs, Rapid System Prototyping, 2007, RSP 2007, 18th IEEE/IFIP International Workshop on IEEE, 2007.

[6]

Ewerson Carvalho, César Marcon, Ney Calazans, Fernando Moraes, Evaluation of static and dynamic task mapping algorithms in NoC-based MPSoCs, International Symposium on System-on-Chip, (2009) 087-090.

[7]

L. Benini, G. De Micheli, Networks on chips: a new SoC paradigm, Computer, 35 (2002) 70-78.

Digital Library

[8]

W.J. Dally, B. Towles, Route packets, not wires: on-chip interconnection networks, Design Automation Conference, 2001, Proceedings, (2001) 684-689.

[9]

Bharati B. Sayankar, S.S. Limaye, Overview of network on chip architecture, 2nd National Conference on Information and Communication Technology (NCICT), 2011.

[10]

Wikipedia, The Free Encyclopedia, Network on a chip, http://en.wikipedia.org/w/index.php?title=Network_on_a_chip&oldid=578090376, 2013 Online}.

[11]

S. Subha, A scheduling algorithm for network on chip, International Conference on Advances in Computing, Control, and Telecommunication Technologies, (2009) 289-291.

Digital Library

[12]

S. Subha, An optimized algorithm for network on chip, Int. J. Comput. Appl., 3 (2010).

[13]

S. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, P. Iyer, A. Singh, T. Jacob, S. Jain, S. Venkataraman, Y. Hoskote, N. Borkar, An 80-tile 1.28tflops network-on-chip in 65nm cmos, Solid-State Circuits Conference, 2007, ISSCC 2007, Digest of Technical Papers, IEEE International, (2007) 98-589.

[14]

First 100-core processor with the new tile-gx family, http://www.tilera.com/news & events/press release 091026.php, 2009.

[15]

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

Digital Library

[16]

Ahmed Hemani, Axel Jantsch, Shashi Kumar, Adam Postula, Johnny Öberg, Mikael Millberg, Dan Lindqvist, Network on a chip: an architecture for billion transistor era, 18th NORCHIP Conference, Turku, Finland, November 2000, 166-173.

[17]

Wen-Chung Tsai, Ying-Cherng Lan, Yu-Hen Hu, Sao-Jie Chen, Networks on chips: structure and design methodologies, J. Electric. Comput. Eng., 2012 (2012) 15.

[18]

Suleyman Tosun, Cluster-based application mapping method for Network-on-Chip, Adv. Eng. Softw., 42 (2011) 868-874.

Digital Library

[19]

Ashwini Raina, V. Muthukumar, Traffic aware scheduling algorithm for network on chip, Sixth International Conference on Information Technology: New Generations, 2009, 877-882.

Digital Library

[20]

Jingcao Hu, Radu Marculescu, Energy-aware communication and task scheduling for network-on-chip architectures under real-time constraints, Design, Automation and Test in Europe Conference and Exhibition, 1, 2004, 234-239.

[21]

Jingcao Hu, Radu Marculescu, Energy-aware mapping for tile-based NoC architectures under performance constraints, 2003, 233-239.

[22]

Bin. Xie, Tianzhou. Chen, Hu. Wei, Xingsheng. Tang, Dazhou. Wang, An energy-aware online task mapping algorithm in NoC-based system, J. Supercomput., 64 (2013) 1021-1037.

[23]

Chen-Ling Chou, Radu Marculescu, Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 29 (2010).

[24]

Chen-Ling Chou, Radu Marculescu, User-aware dynamic task allocation in networks-on-chip, Design, Automation and Test in Europe, 2008, 1232-1237.

[25]

Armin Mehran, Ahmad Khademzadeh, Samira Saeidi, DSM: a heuristic dynamic spiral mapping algorithm for network on chip, IEICE Electron. Exp., 5 (2008) 464-471.

[26]

Mohammad Abdullah Al Faruque, Rudolf Krist, Jörg Henkel, ADAM: run-time agent-based distributed application mapping for on-chip communication, Proceedings of the 45th Annual Design Automation Conference, 2008, 760-765.

[27]

Ewerson Carvalho, Ney Calazans, Fernando Moraes, Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs, 18th IEEE/IFIP International Workshop on Rapid System Prototyping, 2007, 34-40.

[28]

Ewerson. Carvalho, Ney. Calazans, Fernando. Moraes, Dynamic task mapping for MPSoCs, J. IEEE Des. Test, 27 (2010) 26-35.

Digital Library

[29]

Jia Huang, Christian Buckl, Andreas Raabe, Alois Knoll, Energy-aware task allocation for Network-on-Chip based heterogeneous multiprocessor systems, 19th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), 2011, 447-454.

Digital Library

[30]

Chen-Ling Chou, Radu Marculescu, Contention-aware application mapping for Network-on-Chip communication architectures, IEEE International Conference on Computer Design, 2008, 164-169.

[31]

S. Tosun, O. Ozturk, M. Ozen, An ILP formulation for application mapping onto Network-on-Chips, International Conference on Application of Information and Communication Technologies (AICT), 2009, 1-5.

[32]

Suleyman Tosun, Cluster-based application mapping method for Network-on-Chip, J.: Adv. Eng. Softw., 42 (2011) 868-874.

Digital Library

[33]

Wenbiao Zhou, Yan Zhang, Zhigang Mao, An application specific NoC mapping for optimized delay, International Conference on Design and Test of Integrated Systems in Nanoscale Technology, 2006, 184-188.

[34]

Leandro Möller, Leandro Soares Indrusiak, Luciano Ost, Fernando Moraes, Manfred Glesner, Comparative analysis of dynamic task mapping heuristics in heterogeneous NoC-based MPSoCs, International Symposium on System on Chip (SoC), 2012, 1-4.

[35]

S. Kaushik, A.K. Singh, T. Srikanthan, Computation and communication aware run-time mapping for NoC-based MPSoC platforms, SOC Conference (SOCC), 2011 IEEE International, 26-28 September 2011, 185-190.

[36]

Atitallah, Rabie Ben, et al., Estimating energy consumption for an MPSoC architectural exploration, Architecture of Computing Systems-ARCS 2006, Springer Berlin Heidelberg, 2006, 298-310.

[37]

Loghi, Mirko, Massimo Poncino, Luca Benini. Cycle-accurate power analysis for multiprocessor systems-on-a-chip, Proceedings of the 14th ACM Great Lakes symposium on VLSI, ACM, 2004.

[38]

T.T. Ye, L. Benini, G. De Micheli, Analysis of power consumption on switch fabrics in network routers, Design Automation Conference, 2002, Proceedings, 39th, 2002, 524-529.

[39]

Jun Ho Bahn, Overview of Network-on-Chip, http://gram.eng.uci.edu/comp.arch/lab/NoCOverview.htm (accessed 03.9.14 (Online)).

[40]

Omnet++, HNOCS-Network on Chip Simulation Framework. http://www.omnetpp.org/omnetpp/doc_details/2231-inoc-network-on-chip-simulation-framework, 2011 (Online).

[41]

T. Murata, Petri nets: properties, analysis and applications, Proc. IEEE, 77 (1989) 541-580.

[42]

De Moura, Leonardo, Nikolaj Bjørner. Z3: An Efficient SMT solver. Tools and Algorithms for the Construction and Analysis of Systems, Springer, Berlin Heidelberg, 2008, pp. 337-340.

[43]

Liyang Zhou, Ming-e Jing, Xiaoyang Zeng, Task-binding Based branch-and-bound algorithm for NoC mapping, IEEE International Symposium on Circuits and Systems (ISCAS), May 2012, 648-651.

[44]

E.W. Brião, D. Barcelos, F. Wronski, F.R. Wagner, Impact of task migration in NoC-based MPSoCs for soft real-time applications, Very Large Scale Integration, 2007, VLSI-SoC 2007, IFIP International Conference on IEEE, 2007, October, 296-299.

[45]

W. Quan, A.D. Pimentel, A system-level simulation framework for evaluating task migration in MPSoCs. Compilers, Architecture and Synthesis for Embedded Systems (CASES), 2014 International Conference on IEEE, 2014, October, 1-9.

[46]

A. Das, A. Kumar, Fault-aware task re-mapping for throughput constrained multimedia applications on NoC-based MPSoCs, Rapid System Prototyping (RSP), 2012 23rd IEEE International Symposium on IEEE, 2012, October, 149-155.

[47]

Y. Wang, H. Liu, D. Liu, Z. Qin, Z. Shao, E.H.M. Sha, Overhead-aware energy optimization for real-time streaming applications on multiprocessor system-on-chip, ACM Trans. Des. Automat. Electron. Syst. (TODAES), 16 (2011) 14.

[48]

A. Das, A.K. Singh, A. Kumar, Energy-aware dynamic reconfiguration of communication-centric applications for reliable MPSoCs. Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), 2013 8th International Workshop on IEEE, 2013, July, 1-7.

Cited By

Cakin ADilek STosun S(2024)Energy-aware application mapping methods for mesh-based hybrid wireless network-on-chipsThe Journal of Supercomputing10.1007/s11227-024-06062-480:11(15582-15612)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-06062-4
Xiao CHe XYang ZXiao XWang YGong RTie JWang LXu W(2023)Hierarchical Mapping of Large-Scale Spiking Convolutional Neural Networks Onto Resource-Constrained Neuromorphic ProcessorIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334407043:5(1442-1455)Online publication date: 18-Dec-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3344070
Rizk MMartin KDiguet J(2022)Run-Time Remapping Algorithm of Dataflow Actors on NoC-Based Heterogeneous MPSoCsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317795733:12(3959-3976)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3177957
Show More Cited By

Dynamic task mapping for Network-on-Chip based systems
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Virtual point-to-point connections for NoCs
Special issue on the 2009 ACM/IEEE international symposium on networks-on-chip

In this paper, we aim to improve the performance and power metrics of packet-switched network-on-chips (NoCs) and benefits from the scalability and resource utilization advantages of NoCs and superior communication performance of point-to-point ...
A low-cost and latency bypass channel-based on-chip network

The number of cores on the chip increases rapidly; therefore, scalability is the most important design choice. Mesh-based Networks-on-Chip (NoC) are the most widely used topologies as a scalable alternative for traditional shared bus in many-core chips ...
Design and evaluation of Mesh-of-Tree based Network-on-Chip using virtual channel router

Network-on-Chip (NoC) has emerged as a new paradigm to integrate large number of cores on a single silicon die. This paper presents a detailed study of Mesh-of-Tree (MoT) topology and explores its promise in communication infrastructure design for 2-D ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Systems Architecture: the EUROMICRO Journal

Journal of Systems Architecture: the EUROMICRO Journal Volume 61, Issue 7

August 2015

52 pages

ISSN:1383-7621

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 August 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cakin ADilek STosun S(2024)Energy-aware application mapping methods for mesh-based hybrid wireless network-on-chipsThe Journal of Supercomputing10.1007/s11227-024-06062-480:11(15582-15612)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-06062-4
Xiao CHe XYang ZXiao XWang YGong RTie JWang LXu W(2023)Hierarchical Mapping of Large-Scale Spiking Convolutional Neural Networks Onto Resource-Constrained Neuromorphic ProcessorIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334407043:5(1442-1455)Online publication date: 18-Dec-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3344070
Rizk MMartin KDiguet J(2022)Run-Time Remapping Algorithm of Dataflow Actors on NoC-Based Heterogeneous MPSoCsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317795733:12(3959-3976)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3177957
Ali JMaqsood TKhalid NMadani S(2022)Communication and aging aware application mapping for multicore based edge computing serversCluster Computing10.1007/s10586-022-03588-126:1(223-235)Online publication date: 30-Mar-2022
https://dl.acm.org/doi/10.1007/s10586-022-03588-1
Manu DHuang SDing CYang LChen YZhirnov VSasan ASavidis I(2021)Co-Exploration of Graph Neural Network and Network-on-Chip Design Using AutoMLProceedings of the 2021 Great Lakes Symposium on VLSI10.1145/3453688.3461741(175-180)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3453688.3461741
Paul SChatterjee NGhosal P(2021)Dynamic task allocation and scheduling with contention-awareness for Network-on-Chip based multicore systemsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2021.102020115:COnline publication date: 1-May-2021
https://dl.acm.org/doi/10.1016/j.sysarc.2021.102020
Ali HTariq UHardy JZhai XLu LZheng YBensaali FAmira AFatema KAntonopoulos N(2021)A survey on system level energy optimisation for MPSoCs in IoT and consumer electronicsComputer Science Review10.1016/j.cosrev.2021.10041641:COnline publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100416
Gupta MBhargava LIndu S(2021)Mapping techniques in multicore processors: current and future trendsThe Journal of Supercomputing10.1007/s11227-021-03650-677:8(9308-9363)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s11227-021-03650-6
Boroumand BYaghoubi EBarekatain B(2021)An enhanced cost-aware mapping algorithm based on improved shuffled frog leaping in network on chipsThe Journal of Supercomputing10.1007/s11227-020-03271-577:1(498-522)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s11227-020-03271-5
Mazaheri Kalahroudi PYaghoubi EBarekatain B(2021)IAM: an improved mapping on a 2-D network on chip to reduce communication cost and energy consumptionPhotonic Network Communications10.1007/s11107-020-00911-x41:1(78-92)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11107-020-00911-x
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents