Runtime Optimisation Approaches for a Real-Time Evacuation Assistant View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Armel Ulrich Kemloh Wagoum , Bernhard Steffen , Armin Seyfried

ABSTRACT

This paper presents runtime optimisation approaches for a real-time evacuation assistant. The pedestrian model used for the forecast is a modification of the centrifugal force model which operates in continuous space. It is combined with an event driven route choice algorithm which encompasses the local shortest path, the global shortest path and a combination with the quickest path. A naive implementation of this model has the complexity of O(N2), N being the number of pedestrians. In the first step of the optimisation the complexity is reduced to O(N) using special neighbourhood lists like Verlet-List or Linked-Cell commonly used in molecular dynamics. The next step in this optimisation process is parallelisation on a multicore system. The Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) application programming interfaces are used to this extend. The simulation is performed on the Juropa cluster installed at the Jülich Supercomputing Centre. The speedup factors obtained are ~10 for the linked-cells, ~4 for 8 threads and ~3 for the parallelisation on 5 nodes using a static domain decomposition. More... »

PAGES

386-395

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31464-3_39

DOI

http://dx.doi.org/10.1007/978-3-642-31464-3_39

DIMENSIONS

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


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": "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8385.6", 
          "name": [
            "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kemloh Wagoum", 
        "givenName": "Armel Ulrich", 
        "id": "sg:person.01354440050.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354440050.77"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8385.6", 
          "name": [
            "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Steffen", 
        "givenName": "Bernhard", 
        "id": "sg:person.013270457265.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013270457265.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8385.6", 
          "name": [
            "J\u00fclich Supercomputing Centre, Forschungszentrum J\u00fclich GmbH, Leo-Brandt-Strasse, 52428, J\u00fclich, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seyfried", 
        "givenName": "Armin", 
        "id": "sg:person.014676264157.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014676264157.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "This paper presents runtime optimisation approaches for a real-time evacuation assistant. The pedestrian model used for the forecast is a modification of the centrifugal force model which operates in continuous space. It is combined with an event driven route choice algorithm which encompasses the local shortest path, the global shortest path and a combination with the quickest path. A naive implementation of this model has the complexity of O(N2), N being the number of pedestrians. In the first step of the optimisation the complexity is reduced to O(N) using special neighbourhood lists like Verlet-List or Linked-Cell commonly used in molecular dynamics. The next step in this optimisation process is parallelisation on a multicore system. The Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) application programming interfaces are used to this extend. The simulation is performed on the Juropa cluster installed at the J\u00fclich Supercomputing Centre. The speedup factors obtained are ~10 for the linked-cells, ~4 for 8 threads and ~3 for the parallelisation on 5 nodes using a static domain decomposition.", 
    "editor": [
      {
        "familyName": "Wyrzykowski", 
        "givenName": "Roman", 
        "type": "Person"
      }, 
      {
        "familyName": "Dongarra", 
        "givenName": "Jack", 
        "type": "Person"
      }, 
      {
        "familyName": "Karczewski", 
        "givenName": "Konrad", 
        "type": "Person"
      }, 
      {
        "familyName": "Wa\u015bniewski", 
        "givenName": "Jerzy", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31464-3_39", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31463-6", 
        "978-3-642-31464-3"
      ], 
      "name": "Parallel Processing and Applied Mathematics", 
      "type": "Book"
    }, 
    "keywords": [
      "Message Passing Interface", 
      "evacuation assistant", 
      "shortest path", 
      "application programming interface", 
      "J\u00fclich Supercomputing Centre", 
      "static domain decomposition", 
      "route choice algorithm", 
      "global shortest path", 
      "programming interface", 
      "runtime optimization", 
      "multicore systems", 
      "Supercomputing Center", 
      "speedup factor", 
      "naive implementation", 
      "neighborhood list", 
      "number of pedestrians", 
      "quickest path", 
      "domain decomposition", 
      "linked cells", 
      "continuous space", 
      "choice algorithm", 
      "parallelisation", 
      "pedestrian model", 
      "optimization approach", 
      "optimization process", 
      "Verlet lists", 
      "complexity", 
      "assistants", 
      "next step", 
      "path", 
      "optimization", 
      "interface", 
      "algorithm", 
      "first step", 
      "nodes", 
      "implementation", 
      "pedestrians", 
      "threads", 
      "model", 
      "step", 
      "system", 
      "space", 
      "simulations", 
      "forecasts", 
      "list", 
      "clusters", 
      "force model", 
      "decomposition", 
      "number", 
      "process", 
      "extend", 
      "combination", 
      "dynamics", 
      "center", 
      "events", 
      "modification", 
      "molecular dynamics", 
      "factors", 
      "approach", 
      "paper"
    ], 
    "name": "Runtime Optimisation Approaches for a Real-Time Evacuation Assistant", 
    "pagination": "386-395", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028875876"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31464-3_39"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31464-3_39", 
      "https://app.dimensions.ai/details/publication/pub.1028875876"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_370.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31464-3_39"
  }
]
 

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-31464-3_39'

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-31464-3_39'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31464-3_39'

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-31464-3_39'


 

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

149 TRIPLES      23 PREDICATES      86 URIs      79 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31464-3_39 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nea85b36858bf477891d07b68f4788302
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description This paper presents runtime optimisation approaches for a real-time evacuation assistant. The pedestrian model used for the forecast is a modification of the centrifugal force model which operates in continuous space. It is combined with an event driven route choice algorithm which encompasses the local shortest path, the global shortest path and a combination with the quickest path. A naive implementation of this model has the complexity of O(N2), N being the number of pedestrians. In the first step of the optimisation the complexity is reduced to O(N) using special neighbourhood lists like Verlet-List or Linked-Cell commonly used in molecular dynamics. The next step in this optimisation process is parallelisation on a multicore system. The Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) application programming interfaces are used to this extend. The simulation is performed on the Juropa cluster installed at the Jülich Supercomputing Centre. The speedup factors obtained are ~10 for the linked-cells, ~4 for 8 threads and ~3 for the parallelisation on 5 nodes using a static domain decomposition.
7 schema:editor N8b0e136f6804470c825fcc0fb7896262
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N18990bdc81a043f78d0fcf58d3e62032
12 schema:keywords Jülich Supercomputing Centre
13 Message Passing Interface
14 Supercomputing Center
15 Verlet lists
16 algorithm
17 application programming interface
18 approach
19 assistants
20 center
21 choice algorithm
22 clusters
23 combination
24 complexity
25 continuous space
26 decomposition
27 domain decomposition
28 dynamics
29 evacuation assistant
30 events
31 extend
32 factors
33 first step
34 force model
35 forecasts
36 global shortest path
37 implementation
38 interface
39 linked cells
40 list
41 model
42 modification
43 molecular dynamics
44 multicore systems
45 naive implementation
46 neighborhood list
47 next step
48 nodes
49 number
50 number of pedestrians
51 optimization
52 optimization approach
53 optimization process
54 paper
55 parallelisation
56 path
57 pedestrian model
58 pedestrians
59 process
60 programming interface
61 quickest path
62 route choice algorithm
63 runtime optimization
64 shortest path
65 simulations
66 space
67 speedup factor
68 static domain decomposition
69 step
70 system
71 threads
72 schema:name Runtime Optimisation Approaches for a Real-Time Evacuation Assistant
73 schema:pagination 386-395
74 schema:productId N1cb1f01fb8a64dc38e63d665e1b87d66
75 N252cb4774da54a818b7e99e9c40a22a1
76 schema:publisher N7571e4f45da948fea82f29af6a418262
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028875876
78 https://doi.org/10.1007/978-3-642-31464-3_39
79 schema:sdDatePublished 2022-05-20T07:47
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher Nf8968da28aaf4ebba3bf7c852d4af7d0
82 schema:url https://doi.org/10.1007/978-3-642-31464-3_39
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N18990bdc81a043f78d0fcf58d3e62032 schema:isbn 978-3-642-31463-6
87 978-3-642-31464-3
88 schema:name Parallel Processing and Applied Mathematics
89 rdf:type schema:Book
90 N1cb1f01fb8a64dc38e63d665e1b87d66 schema:name doi
91 schema:value 10.1007/978-3-642-31464-3_39
92 rdf:type schema:PropertyValue
93 N237143c8422748c2b9642f87f0b9808c rdf:first Nb63d2e685cc74dc4b444f117d5e0851f
94 rdf:rest N6e876a2f385b4475934692ad6d84da53
95 N252cb4774da54a818b7e99e9c40a22a1 schema:name dimensions_id
96 schema:value pub.1028875876
97 rdf:type schema:PropertyValue
98 N6e876a2f385b4475934692ad6d84da53 rdf:first N90f032600380428e9114280895a69e94
99 rdf:rest N7058d238e3164848b122d7ad92494841
100 N7058d238e3164848b122d7ad92494841 rdf:first Nf2b67cc6fa67483e83ca21a52499662a
101 rdf:rest rdf:nil
102 N7571e4f45da948fea82f29af6a418262 schema:name Springer Nature
103 rdf:type schema:Organisation
104 N8b0e136f6804470c825fcc0fb7896262 rdf:first Ne9b60a0d0f484d39bac38163215951ed
105 rdf:rest N237143c8422748c2b9642f87f0b9808c
106 N90f032600380428e9114280895a69e94 schema:familyName Karczewski
107 schema:givenName Konrad
108 rdf:type schema:Person
109 N994934beef2e4a7287bceaa9e9204e6f rdf:first sg:person.013270457265.00
110 rdf:rest Nc5ade663d4f24c73a022f1988ecac4f2
111 Nb63d2e685cc74dc4b444f117d5e0851f schema:familyName Dongarra
112 schema:givenName Jack
113 rdf:type schema:Person
114 Nc5ade663d4f24c73a022f1988ecac4f2 rdf:first sg:person.014676264157.39
115 rdf:rest rdf:nil
116 Ne9b60a0d0f484d39bac38163215951ed schema:familyName Wyrzykowski
117 schema:givenName Roman
118 rdf:type schema:Person
119 Nea85b36858bf477891d07b68f4788302 rdf:first sg:person.01354440050.77
120 rdf:rest N994934beef2e4a7287bceaa9e9204e6f
121 Nf2b67cc6fa67483e83ca21a52499662a schema:familyName Waśniewski
122 schema:givenName Jerzy
123 rdf:type schema:Person
124 Nf8968da28aaf4ebba3bf7c852d4af7d0 schema:name Springer Nature - SN SciGraph project
125 rdf:type schema:Organization
126 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
127 schema:name Information and Computing Sciences
128 rdf:type schema:DefinedTerm
129 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
130 schema:name Artificial Intelligence and Image Processing
131 rdf:type schema:DefinedTerm
132 sg:person.013270457265.00 schema:affiliation grid-institutes:grid.8385.6
133 schema:familyName Steffen
134 schema:givenName Bernhard
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013270457265.00
136 rdf:type schema:Person
137 sg:person.01354440050.77 schema:affiliation grid-institutes:grid.8385.6
138 schema:familyName Kemloh Wagoum
139 schema:givenName Armel Ulrich
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354440050.77
141 rdf:type schema:Person
142 sg:person.014676264157.39 schema:affiliation grid-institutes:grid.8385.6
143 schema:familyName Seyfried
144 schema:givenName Armin
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014676264157.39
146 rdf:type schema:Person
147 grid-institutes:grid.8385.6 schema:alternateName Jülich Supercomputing Centre, Forschungszentrum Jülich GmbH, Leo-Brandt-Strasse, 52428, Jülich, Germany
148 schema:name Jülich Supercomputing Centre, Forschungszentrum Jülich GmbH, Leo-Brandt-Strasse, 52428, Jülich, Germany
149 rdf:type schema:Organization
 




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


...