Top

Published in:

2019 | OriginalPaper | Chapter

KLSAT: An Application Mapping Algorithm Based on Kernighan–Lin Partition and Simulated Annealing for a Specific WK-Recursive NoC Architecture

Authors : XiaoJun Wang, Feng Shi, Hong Zhang

Published in: Network and Parallel Computing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Application mapping is a critical phase in NoC design because of the running time, the network latency and the power consumption. In order to reduce these problems of applications running on multicore architecture, we propose a novel application mapping algorithm, called KLSAT mapping algorithm. It is used for the triplet-based architecture (TriBA) topology which is WK-recursive based networks well conform to a modular design due to the properties of regularity and scalability. The KLSAT mapping algorithm exploits the advantage of both the Kernighan–Lin partitioning algorithm and simulated annealing algorithm to reduce the overall power consumption and network latency. Compared to the random mapping algorithm, the experiment results reveal that the solutions generated by the proposed mapping algorithm reduce average power consumption and network latency by 6.4%, 12.2% in mapping 27 cores and 29.5%, 26.7% in mapping 81 cores respectively.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Game-Based Multi-MD with QoS Computation Offloading for Mobile Edge Computing of Limited Computation Capacity

next chapter Modeling and Analysis of the Latency-Based Congestion Control Algorithm DX

Dally, W., Towles, B.: Route packets, not wires: on-chip interconnection networks. In: DAC 2001, pp. 684–689, June 2001

Benini, L., Micheli, G.: Networks on chips: a new SoC paradigm. IEEE Trans. Comput. 35(1), 70–78 (2002)

Farahabady, M., Sarbazi-Azad, H.: The WK-recursive pyramid: an efficient network topology. In: PAAN 2005, pp. 6–11, December 2005

Wang, Y., Juan, S.: Hamiltonicity of the basic WK-recursive pyramid with and without faulty nodes. J. Theor. Comput. Sci. 562(C), 542–556 (2015)MathSciNetCrossRef

Taylor, M.B., Lee, W., Miller, J., et al.: Evaluation of the raw microprocessor: an exposed-wire-delay architecture for ILP and streams. ACM SIGARCH Comput. Archit. News 32(2), 2–13 (2004)CrossRef

Hoskote, Y., Vangal, S., et al.: A 5-GHz mesh interconnect for a teraflops processor. IEEE Micro 27(5), 51–61 (2007)CrossRef

Shi, F., Ji, W., et al.: A triplet-based computer architecture supporting parallel object computing. In: IEEE ASSAP 2007, pp. 192–197, July 2007

Sahu, P., Manna, N., Shah, N., Chattopadhyay, S.: Extending Kernighan-Lin partitioning heuristic for application mapping onto network-on-chip. J. Syst. Archit. 60(7), 562–578 (2014)CrossRef

Zhu, D., Chen, L., Yue, S., Pedram, M.: Application mapping for express channel-based networks-on-chip. In: DATE 2014, pp. 1–6, March 2014

10.

Manna, K., Choubey, V., et al.: Thermal variance-aware application mapping for mesh based network-on-chip design using Kernighan-Lin partitioning. In: PDGC 2014, pp. 274–279. IEEE, December 2014

11.

Fang, J., Yu, L., et al.: KLGA: an application mapping algorithm for mesh-of-tree (MoT) architecture in network-on-chip design. J. Supercomputing 71(11), 4056–4071 (2015)MathSciNetCrossRef

12.

Manna, K., Teja, V., Chattopadhyay, S., et al.: TSV placement and core mapping for 3D mesh based network-on-chip design using extended Kernighan-Lin Partitioning. In: VLSI 2015, pp. 392–397. IEEE, July 2015

13.

Hu, J., Marculescu, R.: Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 24(4), 551–562 (2005)CrossRef

14.

Marcon, C., Moreno, E., Calazans, L., Moraes, F.: Comparison of network-on-chip mapping algorithms targeting low energy consumption. IET Comput. Digit. Tech. 2(6), 471–482 (2008)CrossRef

15.

Prasad, N., Mukherjee, P., Chattopadhyay, S., et al.: Design and evaluation of ZMesh topology for on-chip interconnection networks. J. Parall. Distrib. Comput. 113(2), 17–36 (2018)CrossRef

16.

Dong, Z., Yang, B., Hu, P., et al.: An efficient global energy optimization approach for robust 3D plane segmentation of point clouds. ISPRS J. Photogra. Remote Sens. 137(1), 112–133 (2018)CrossRef

17.

Orsila, H., Salminen, E., Timo, D.: Best practices for simulated annealing in multiprocessor task distribution problems. Tech. 4(2), 197–198 (2008)

18.

Yang, B., Liang, G., et al.: Parameter-optimized simulated annealing for application mapping on networks-on-chip. In: LIO 2012, pp. 307–322 (2012)

19.

Tosun, S., Ozturk, O., Ozkan, E., Ozen, M.: Application mapping algorithms for mesh-based network-on-chip architectures. J. Supercomputing 71(3), 995–1017 (2015)CrossRef

20.

Cheng, C., Chen, W.: Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms. J. Supercomputing 72(11), 1–14 (2016)CrossRef

21.

Zhong, L., Sheng, J., et al.: An optimized mapping algorithm based on simulated annealing for regular NoC architecture. In: ASIC 2011, pp. 389–392. IEEE, October 2011

22.

Larsson, T., Jesper, F.: Direct graph k-partitioning with a Kernighan-Lin like heuristic. Oper. Res. Lett. 34(6), 621–629 (2006)MathSciNetCrossRef

23.

Ye, T., Benini, L., Micheli, G.: Analysis of power consumption on switch fabrics in network routers. In: DAC 2002, pp. 524–529, June 2002

24.

Hu, J., Marculescu, R.: Energy-aware mapping for tile-based NoC architectures under performance constraints. In: ASPDAC 2003, pp. 233–239. IEEE (2003)

25.

Kahng, A., Li, B., Peh, L., Samadi, K.: ORION 2.0: a power-area simulator for interconnection networks. IEEE Trans. Very Large Scale Integr. Syst. 20(1), 191–196 (2012)CrossRef

26.

Bienia, C., Li, K.: PARSEC 2.0: a new benchmark suite for chip-multiprocessors. In: AWMBS 2009, pp. 1–9. IEEE (2009)

Title: KLSAT: An Application Mapping Algorithm Based on Kernighan–Lin Partition and Simulated Annealing for a Specific WK-Recursive NoC Architecture
Authors: XiaoJun Wang
Feng Shi
Hong Zhang
Publisher: Springer International Publishing
Book: Network and Parallel Computing
Print ISBN: 978-3-030-30708-0

Electronic ISBN: 978-3-030-30709-7

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-30709-7_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner