A Massive Parallel Cellular GPU Implementation of Neural Network to Large Scale Euclidean TSP View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Hongjian Wang , Naiyu Zhang , Jean-Charles Créput

ABSTRACT

This paper proposes a parallel model of the self-organizing map (SOM) neural network applied to the Euclidean traveling salesman problem (TSP) and intended for implementation on the graphics processing unit (GPU) platform. The plane is partitioned into an appropriate number of cellular units, that are each responsible of a certain part of the data and network. The advantage of the parallel algorithm is that it is decentralized and based on data decomposition, rather than based on data duplication, or mixed sequential/parallel solving, as often with GPU implementation of optimization metaheuristics. The processing units and the required memory are with linear increasing relationship to the problem size, which makes the model able to deal with very large scale problems in a massively parallel way. The approach is applied to Euclidean TSPLIB problems and National TSPs with up to 33708 cities on both GPU and CPU, and these two types of implementation are compared and discussed. More... »

PAGES

118-129

Book

TITLE

Advances in Soft Computing and Its Applications

ISBN

978-3-642-45110-2
978-3-642-45111-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45111-9_10

DOI

http://dx.doi.org/10.1007/978-3-642-45111-9_10

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032286271


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France", 
          "id": "http://www.grid.ac/institutes/grid.23082.3b", 
          "name": [
            "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Hongjian", 
        "id": "sg:person.01054015167.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01054015167.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France", 
          "id": "http://www.grid.ac/institutes/grid.23082.3b", 
          "name": [
            "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Naiyu", 
        "id": "sg:person.010124537263.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010124537263.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France", 
          "id": "http://www.grid.ac/institutes/grid.23082.3b", 
          "name": [
            "IRTES-SeT, Universit\u00e9 de Technologie de Belfort-Montb\u00e9liard, 90010, Belfort, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cr\u00e9put", 
        "givenName": "Jean-Charles", 
        "id": "sg:person.07630635475.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07630635475.53"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "This paper proposes a parallel model of the self-organizing map (SOM) neural network applied to the Euclidean traveling salesman problem (TSP) and intended for implementation on the graphics processing unit (GPU) platform. The plane is partitioned into an appropriate number of cellular units, that are each responsible of a certain part of the data and network. The advantage of the parallel algorithm is that it is decentralized and based on data decomposition, rather than based on data duplication, or mixed sequential/parallel solving, as often with GPU implementation of optimization metaheuristics. The processing units and the required memory are with linear increasing relationship to the problem size, which makes the model able to deal with very large scale problems in a massively parallel way. The approach is applied to Euclidean TSPLIB problems and National TSPs with up to 33708 cities on both GPU and CPU, and these two types of implementation are compared and discussed.", 
    "editor": [
      {
        "familyName": "Castro", 
        "givenName": "F\u00e9lix", 
        "type": "Person"
      }, 
      {
        "familyName": "Gelbukh", 
        "givenName": "Alexander", 
        "type": "Person"
      }, 
      {
        "familyName": "Gonz\u00e1lez", 
        "givenName": "Miguel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-45111-9_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-45110-2", 
        "978-3-642-45111-9"
      ], 
      "name": "Advances in Soft Computing and Its Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "GPU implementation", 
      "neural network", 
      "self-organizing map (SOM) neural network", 
      "graphics processing unit (GPU) platform", 
      "map neural network", 
      "large scale problems", 
      "data duplication", 
      "parallel algorithm", 
      "parallel solving", 
      "type of implementation", 
      "data decomposition", 
      "processing units", 
      "problem size", 
      "unit (GPU) platform", 
      "TSPLIB problems", 
      "optimization metaheuristic", 
      "parallel model", 
      "scale problems", 
      "salesman problem", 
      "parallel way", 
      "network", 
      "implementation", 
      "appropriate number", 
      "Euclidean TSP", 
      "GPU", 
      "CPU", 
      "metaheuristics", 
      "algorithm", 
      "platform", 
      "solving", 
      "certain parts", 
      "Euclidean", 
      "model", 
      "memory", 
      "advantages", 
      "TSPS", 
      "TSP", 
      "way", 
      "decomposition", 
      "units", 
      "data", 
      "number", 
      "part", 
      "cellular units", 
      "city", 
      "size", 
      "types", 
      "duplication", 
      "plane", 
      "relationship", 
      "problem", 
      "paper", 
      "approach", 
      "processing unit (GPU) platform", 
      "Euclidean TSPLIB problems", 
      "National TSPs", 
      "Massive Parallel Cellular GPU Implementation", 
      "Parallel Cellular GPU Implementation", 
      "Cellular GPU Implementation", 
      "Large Scale Euclidean TSP", 
      "Scale Euclidean TSP"
    ], 
    "name": "A Massive Parallel Cellular GPU Implementation of Neural Network to Large Scale Euclidean TSP", 
    "pagination": "118-129", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032286271"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-45111-9_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-45111-9_10", 
      "https://app.dimensions.ai/details/publication/pub.1032286271"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_292.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-45111-9_10"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45111-9_10'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45111-9_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45111-9_10'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45111-9_10'


 

This table displays all metadata directly associated to this object as RDF triples.

145 TRIPLES      23 PREDICATES      87 URIs      80 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-45111-9_10 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N1bbffb3906b24ffea9a710c3fb3e7d62
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description This paper proposes a parallel model of the self-organizing map (SOM) neural network applied to the Euclidean traveling salesman problem (TSP) and intended for implementation on the graphics processing unit (GPU) platform. The plane is partitioned into an appropriate number of cellular units, that are each responsible of a certain part of the data and network. The advantage of the parallel algorithm is that it is decentralized and based on data decomposition, rather than based on data duplication, or mixed sequential/parallel solving, as often with GPU implementation of optimization metaheuristics. The processing units and the required memory are with linear increasing relationship to the problem size, which makes the model able to deal with very large scale problems in a massively parallel way. The approach is applied to Euclidean TSPLIB problems and National TSPs with up to 33708 cities on both GPU and CPU, and these two types of implementation are compared and discussed.
7 schema:editor N959d4e5c1b814eb6b61dabffe2b03992
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9d08eae356a14ff288242ef72171ee15
12 schema:keywords CPU
13 Cellular GPU Implementation
14 Euclidean
15 Euclidean TSP
16 Euclidean TSPLIB problems
17 GPU
18 GPU implementation
19 Large Scale Euclidean TSP
20 Massive Parallel Cellular GPU Implementation
21 National TSPs
22 Parallel Cellular GPU Implementation
23 Scale Euclidean TSP
24 TSP
25 TSPLIB problems
26 TSPS
27 advantages
28 algorithm
29 approach
30 appropriate number
31 cellular units
32 certain parts
33 city
34 data
35 data decomposition
36 data duplication
37 decomposition
38 duplication
39 graphics processing unit (GPU) platform
40 implementation
41 large scale problems
42 map neural network
43 memory
44 metaheuristics
45 model
46 network
47 neural network
48 number
49 optimization metaheuristic
50 paper
51 parallel algorithm
52 parallel model
53 parallel solving
54 parallel way
55 part
56 plane
57 platform
58 problem
59 problem size
60 processing unit (GPU) platform
61 processing units
62 relationship
63 salesman problem
64 scale problems
65 self-organizing map (SOM) neural network
66 size
67 solving
68 type of implementation
69 types
70 unit (GPU) platform
71 units
72 way
73 schema:name A Massive Parallel Cellular GPU Implementation of Neural Network to Large Scale Euclidean TSP
74 schema:pagination 118-129
75 schema:productId N627697f2c2da4fbcb1537d6203d556d8
76 N8b8343029bfd4788b307d23a71f80764
77 schema:publisher N9c583d07fa6e432db0b4b9edbd02d3dc
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032286271
79 https://doi.org/10.1007/978-3-642-45111-9_10
80 schema:sdDatePublished 2021-11-01T18:54
81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
82 schema:sdPublisher N5866e71c2fcf470f872df7f1dbf24901
83 schema:url https://doi.org/10.1007/978-3-642-45111-9_10
84 sgo:license sg:explorer/license/
85 sgo:sdDataset chapters
86 rdf:type schema:Chapter
87 N15320d599011413d91aeb9ee2164f753 schema:familyName Castro
88 schema:givenName Félix
89 rdf:type schema:Person
90 N1bbffb3906b24ffea9a710c3fb3e7d62 rdf:first sg:person.01054015167.32
91 rdf:rest N8c82b3f30de447218caa7207929e250f
92 N4aaad8e57bb4458a8ea2307a34713cb5 schema:familyName Gelbukh
93 schema:givenName Alexander
94 rdf:type schema:Person
95 N5866e71c2fcf470f872df7f1dbf24901 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N627697f2c2da4fbcb1537d6203d556d8 schema:name dimensions_id
98 schema:value pub.1032286271
99 rdf:type schema:PropertyValue
100 N7cf769294f2b4478a0c023f65a3a2de6 schema:familyName González
101 schema:givenName Miguel
102 rdf:type schema:Person
103 N8b8343029bfd4788b307d23a71f80764 schema:name doi
104 schema:value 10.1007/978-3-642-45111-9_10
105 rdf:type schema:PropertyValue
106 N8c82b3f30de447218caa7207929e250f rdf:first sg:person.010124537263.25
107 rdf:rest Nc6d9a3aa2a5a4b91a44c17f71c9113ac
108 N959d4e5c1b814eb6b61dabffe2b03992 rdf:first N15320d599011413d91aeb9ee2164f753
109 rdf:rest Ne8927acb4f5e428e815fad76fabe8d2a
110 N9c583d07fa6e432db0b4b9edbd02d3dc schema:name Springer Nature
111 rdf:type schema:Organisation
112 N9d08eae356a14ff288242ef72171ee15 schema:isbn 978-3-642-45110-2
113 978-3-642-45111-9
114 schema:name Advances in Soft Computing and Its Applications
115 rdf:type schema:Book
116 Nc3ac980d12e941dabcdc75373e0ba773 rdf:first N7cf769294f2b4478a0c023f65a3a2de6
117 rdf:rest rdf:nil
118 Nc6d9a3aa2a5a4b91a44c17f71c9113ac rdf:first sg:person.07630635475.53
119 rdf:rest rdf:nil
120 Ne8927acb4f5e428e815fad76fabe8d2a rdf:first N4aaad8e57bb4458a8ea2307a34713cb5
121 rdf:rest Nc3ac980d12e941dabcdc75373e0ba773
122 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
123 schema:name Information and Computing Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
126 schema:name Artificial Intelligence and Image Processing
127 rdf:type schema:DefinedTerm
128 sg:person.010124537263.25 schema:affiliation grid-institutes:grid.23082.3b
129 schema:familyName Zhang
130 schema:givenName Naiyu
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010124537263.25
132 rdf:type schema:Person
133 sg:person.01054015167.32 schema:affiliation grid-institutes:grid.23082.3b
134 schema:familyName Wang
135 schema:givenName Hongjian
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01054015167.32
137 rdf:type schema:Person
138 sg:person.07630635475.53 schema:affiliation grid-institutes:grid.23082.3b
139 schema:familyName Créput
140 schema:givenName Jean-Charles
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07630635475.53
142 rdf:type schema:Person
143 grid-institutes:grid.23082.3b schema:alternateName IRTES-SeT, Université de Technologie de Belfort-Montbéliard, 90010, Belfort, France
144 schema:name IRTES-SeT, Université de Technologie de Belfort-Montbéliard, 90010, Belfort, France
145 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...