nach oben

The Journal of Supercomputing

Erschienen in:

01.04.2016

Performance evaluation of task migration in contiguous allocation for mesh interconnection topology

verfasst von: Mahnaz Rafie, Ahmad Khademzadeh, Akram Reza, Midia Reshadi

Erschienen in: The Journal of Supercomputing | Ausgabe 4/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, several efficient migration algorithms have been proposed to improve existing non-preemptive sub-mesh allocation strategies in multiprocessors which are two-row boundary migration algorithm (TRBMA) and different types of combined migration mechanisms. These methods are presented to solve the external fragmentation problem in contiguous allocation. In this process, the mentioned methods contain the algorithms, called the minimum threshold and prime number (MT&MPN), which determine the best sub-mesh size for the incoming job. These algorithms are used to increase continuity in multiprocessor systems. Using extensive simulations, we evaluated the proposed methods and compared them with previous strategies. Simulation outcomes clearly showed the TRBMA and the MT&MPN procedure produced the best average job execution time and average system utilization. Also, hybrid migration methods produced the best average job waiting time and average number of waiting jobs in comparison with the previous algorithms. Meanwhile, most of the traditional methods had better average job response time.

Vorheriger Artikel DRDDR: a lightweight method to detect data races in Linux kernel

Nächster Artikel Erratum to: Large-scale image colorization based on divide-and-conquer support vector machines

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Bani-Ahmad S (2011) Bounded gradual-request-partitioning-based allocation strategies in 2D mesh multicomputers. Proc Int J Digit Content Technol Appl 5(1):43–54CrossRef

Bani-Mohammad S, Ould-Khaoua M, Ababneh I, Machenzie L (2006) Non-contiguous processor allocation strategy for 2D mesh connected multicomputers based on sub-meshes available for allocation. In: Proceedings of the 12th international conference on parallel and distributed systems (ICPADS’06), vol 2. IEEE Computer Society Press, USA, pp 41–48

Ababneh I (2006) An efficient free-list submesh allocation scheme for two-dimensional mesh-connected multicomputers. In: Proceedings of the journal of systems and software, vol 79(8). Elsevier, New York, pp 1168–1179

Bani-Mohammad S, Ould-Khaoua M, Ababneh I, Machenzie L (2007) A fast and efficient processor allocation strategy which combines a contiguous and non-contiguous processor allocation algorithms. In: Technical report; TR-2007-229, DCS technical report series. Department of Computing Science, University of Glasgow

Windisch K, Lo V, Bose B (1995) Contiguous and non-contiguous processor allocation algorithms for \(k\)-ary \(n\)-cubes. In: Technical Report, University of Oregon, Oregon

ProcSimity V4.3 (1997) User’s manual. University of Oregon, Oregon

Bani-Mohammad S (2008) Efficient processor allocation strategies for mesh-connected multicomputers. PhD thesis, The Faculty of Information and Mathematical Sciences, University of Glasgow, Glasgow

Bani-Mohammad S, Ould-Khaoua M, Ababneh I, Mackenzie L (2009) Comparative evaluation of contiguous allocation strategies on 3D mesh multicomputers. Proc J Syst Softw 82(2):307–318CrossRef

Windisch KJ, Liu W, Nitzberg B (1997) Non-contiguous processor allocation algorithms for mesh-connected multicomputers. Proc IEEE Trans Parallel Distribut Syst 8(7):712–726CrossRef

10.

Chang CY, Mohapatra P (1998) Performance improvement of allocation schemes for mesh-connected computers. Proc J Parallel Distribut Comput 52(1):40–68CrossRefMATH

11.

Bani-Mohammad S, Ould-Khaoua M, Ababneh I (2007) A new processor allocation strategy with a high degree of contiguity in mesh-connected multicomputers. In: Proceedings of the simulation modelling practice and theory, pp 465–480

12.

Mao W, Chen J, Watson W (2005) Efficient subtorus processor allocation in a multi-dimensional torus. In: Proceedings of the 8th international conference on high-performance computing in Asia–Pacific region (HPCASIA’05). IEEE Computer society Press, New York, pp 53–60

13.

Adve V, Vernon M (1994) Performance analysis of mesh interconnection networks with deterministic routing. Proc IEEE Trans Parallel Distribut Syst 5(3):225–246CrossRef

14.

Goh LK, Veeravalli B (2008) Design and performance evaluation of combined first-fit task allocation and migration strategies in mesh multicomputer systems. Proc J Parallel Comput 34(9):508–520MathSciNetCrossRef

15.

Ding J, Bhuyan LN (1993) An adaptive submesh allocation strategy for two dimensional mesh connected systems. Proc Int Conf Parallel Process (ICPP) 2:193–200

16.

Li K, Cheng K (1991) A two-dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system. Proc J Parallel Distribut Comput 12(1):79–83CrossRef

17.

Chuang P, Tzeng N (1991) An efficient submesh allocation strategy for mesh computer systems. In: Proceedings of the 11th international conference on distributed computing systems, pp 256–263

18.

Zhu Y (1992) Efficient processor allocation strategies for mesh-connected parallel computers. Proc J Parallel Distribut Comput 16(4):328–337CrossRefMATH

19.

Ding J, Bhuyan LN (1993) An adaptive submesh allocation strategy for two-dimensional mesh connected systems. Proc Int Conf Parallel Process (ICPP) 2:193–200

20.

Sharma DD, Pradhan DK (1993) A fast and efficient strategy for submesh allocation in mesh-connected parallel computers. In: Proceedings of the fifth IEEE symposium on parallel and distributed processing, pp 682–689

21.

Kim J, Das CR, Lin W (1991) A top-down processor allocation scheme for hypercube computers. Proc IEEE Trans Parallel Distribut Syst 2(1):20–30CrossRef

22.

Yoo SM, Youn HY, Shirazi B (1997) An efficient task allocation scheme for 2D mesh architectures. Proc IEEE Trans Parallel Distribut Syst 8(9):934–942CrossRef

23.

Chmaj G, Zydek D, Koszalka L (2004) Allocation algorithms problems in mesh-connected systems

24.

Reza A, Rafie M (2015) performance improvement in multiprocessors using two-row boundary allocation method and online dynamic compaction algorithm. Proc Int J Comput Appl (IJCA) (USA) 123(1):14–20

25.

Shaw KA, Dally WJ (2002) Migration in single chip multiprocessors. Proc J IEEE Comput Archit Lett 1(1):12–12CrossRef

26.

Kandemir M, Chen G (2005) Locality-aware process scheduling for embedded MPSoCs. In: Proceedings of the design, automation and test in Europe conference (DATE), pp 870–875

27.

Bertozzi S, Acquaviva A, Bertozzi D, Poggiali A (2006) Supporting task migration in multi-processor systems-on-chip: a feasibility study. Proc Design Autom Test Eur (DATE) 1:15–20

28.

Wang NC, Chen TS (2004) Task migration in all-port wormhole-routed 2D mesh multicomputers. In: Proceedings of the 7th international symposium on parallel architectures, algorithms and networks, pp 123–128

29.

30.

Bhandarkar SM, Arabnia HR (1995) The Hough transform on a reconfigurable multi-ring network. Proc J Parallel Distrib Comput 24(1):107–114CrossRef

31.

Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor: theoretical properties and algorithms. Proc J Parallel Comput 21(11):1783–1806CrossRef

32.

Arabnia HR, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. Proc J Supercomput 10(3):243–270CrossRefMATH

33.

Bani-Ahmad S (2011) On improved processor allocation in 2D mesh-based multicomputers: controlled splitting of parallel requests. In: Proceedings of the international conference on communication, computing and security (ICCCS’11), pp 204–209

34.

Al-Lami ZM (2011) Communication impact on non-contiguous allocation strategies for 2-D mesh multicomputer systems. Master thesis, Middle East University, Amman-Jordan

35.

Arabnia HR, Oliver MA (1987) A transputer network for the arbitrary rotation of digitised images. Proc Comput J 30(5):425–433CrossRef

36.

Arabnia HRA (1995) Distributed stereocorrelation algorithm. In: Proceedings of the computer communications and networks (ICCCN’95). IEEE, New York, pp 479–482

37.

Kee GL (2005) Design and performance evaluation of migration-based submesh allocation strategies in mesh multicomputers. Master thesis, National University of Singapore, Singapore

38.

Zolfaghari R (2013) Efficient and quick algorithm for processor allocation in mesh multi-computers network. Proc Int J Eng Adv Technol (IJEAT) 2(5):517–523

Titel: Performance evaluation of task migration in contiguous allocation for mesh interconnection topology
verfasst von: Mahnaz Rafie
Ahmad Khademzadeh
Akram Reza
Midia Reshadi
Publikationsdatum: 01.04.2016
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 4/2016
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-016-1692-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 4/2016

Handling big data: research challenges and future directions

Reliability aware throughput management of chip multi-processor architecture via thread migration

Ancilla-input and garbage-output optimized design of a reversible quantum integer multiplier

Dynamic erasure coding decision for modern block-oriented distributed storage systems

Facing prefetching challenges in distributed shared memories for CMPs

SDN-based resource allocation for heterogeneous LTE and WLAN multi-radio networks