Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-04-12

AUTHORS

Alexander E. Andreev , Andrea E. F. Clementi , Paolo Penna , José D. P. Rolim

ABSTRACT

We address the problem of organizing a set T of shared data into the memory modules of a Distributed Memory Machine (DMM) in order to minimize memory access conflicts during read operations. In this paper we present a new randomized scheme that, with high probability, performs any set of r unrelated read operations on the shared data set T in O(log r + log log|T|) parallel time with no memory conflicts and using O(r) processors. The set T is distributed into m DMM memory modules where m is polynomial in r and logarithmic in T, and the overall size of the shared memory used by our scheme is not larger than (1 + 1/ log |T|)|T|(this means that there is “almost” no data replication). The memory organization scheme and most part of all the computations of our method do not depend on the read requests, so they can be performed once and for all during an off-line phase. This is a relevant improvement over the previous deterministic method recently given in [1] when “real-time” applications are considered. More... »

PAGES

68-77

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49116-3_6

DOI

http://dx.doi.org/10.1007/3-540-49116-3_6

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Broadcom (United States)", 
          "id": "https://www.grid.ac/institutes/grid.471058.f", 
          "name": [
            "LSI Logic, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Andreev", 
        "givenName": "Alexander E.", 
        "id": "sg:person.012322036405.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322036405.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, \u201cTor Vergata\u201d University of Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Clementi", 
        "givenName": "Andrea E. F.", 
        "id": "sg:person.011027660123.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, \u201cTor Vergata\u201d University of Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Geneva", 
          "id": "https://www.grid.ac/institutes/grid.8591.5", 
          "name": [
            "Centre Universitaire d\u2019Informatique, University of Geneva, CH"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "id": "sg:person.013274060005.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274060005.11"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/12130.12146", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004659632"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00264615", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007326756", 
          "https://doi.org/10.1007/bf00264615"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00264615", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007326756", 
          "https://doi.org/10.1007/bf00264615"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/165231.165245", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010158266"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/828.1892", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010797045"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/320064.320068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016419288"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01940878", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025366447", 
          "https://doi.org/10.1007/bf01940878"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01940878", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025366447", 
          "https://doi.org/10.1007/bf01940878"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49543-6_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025474991", 
          "https://doi.org/10.1007/3-540-49543-6_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/7531.7926", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031240671"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(90)90192-k", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032459149"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/143369.143421", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037396887"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/5925.5928", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039057305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/258533.258609", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051069655"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/276698.276723", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052112212"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1995.492461", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093241746"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-04-12", 
    "datePublishedReg": "2002-04-12", 
    "description": "We address the problem of organizing a set T of shared data into the memory modules of a Distributed Memory Machine (DMM) in order to minimize memory access conflicts during read operations. In this paper we present a new randomized scheme that, with high probability, performs any set of r unrelated read operations on the shared data set T in O(log r + log log|T|) parallel time with no memory conflicts and using O(r) processors. The set T is distributed into m DMM memory modules where m is polynomial in r and logarithmic in T, and the overall size of the shared memory used by our scheme is not larger than (1 + 1/ log |T|)|T|(this means that there is \u201calmost\u201d no data replication). The memory organization scheme and most part of all the computations of our method do not depend on the read requests, so they can be performed once and for all during an off-line phase. This is a relevant improvement over the previous deterministic method recently given in [1] when \u201creal-time\u201d applications are considered.", 
    "editor": [
      {
        "familyName": "Meinel", 
        "givenName": "Christoph", 
        "type": "Person"
      }, 
      {
        "familyName": "Tison", 
        "givenName": "Sophie", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49116-3_6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65691-3", 
        "978-3-540-49116-3"
      ], 
      "name": "STACS 99", 
      "type": "Book"
    }, 
    "name": "Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines", 
    "pagination": "68-77", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49116-3_6"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9db67dc0c6972daeff5b59c43cf4111b6f512eced48020c5661ecc088d442e65"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033106345"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49116-3_6", 
      "https://app.dimensions.ai/details/publication/pub.1033106345"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000345_0000000345/records_64100_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-49116-3_6"
  }
]
 

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/3-540-49116-3_6'

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/3-540-49116-3_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49116-3_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49116-3_6'


 

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

142 TRIPLES      23 PREDICATES      40 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49116-3_6 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N62318a665d56415392f6a8cb8e1ddb83
4 schema:citation sg:pub.10.1007/3-540-49543-6_17
5 sg:pub.10.1007/bf00264615
6 sg:pub.10.1007/bf01940878
7 https://doi.org/10.1016/0304-3975(90)90192-k
8 https://doi.org/10.1109/sfcs.1995.492461
9 https://doi.org/10.1145/12130.12146
10 https://doi.org/10.1145/143369.143421
11 https://doi.org/10.1145/165231.165245
12 https://doi.org/10.1145/258533.258609
13 https://doi.org/10.1145/276698.276723
14 https://doi.org/10.1145/320064.320068
15 https://doi.org/10.1145/5925.5928
16 https://doi.org/10.1145/7531.7926
17 https://doi.org/10.1145/828.1892
18 schema:datePublished 2002-04-12
19 schema:datePublishedReg 2002-04-12
20 schema:description We address the problem of organizing a set T of shared data into the memory modules of a Distributed Memory Machine (DMM) in order to minimize memory access conflicts during read operations. In this paper we present a new randomized scheme that, with high probability, performs any set of r unrelated read operations on the shared data set T in O(log r + log log|T|) parallel time with no memory conflicts and using O(r) processors. The set T is distributed into m DMM memory modules where m is polynomial in r and logarithmic in T, and the overall size of the shared memory used by our scheme is not larger than (1 + 1/ log |T|)|T|(this means that there is “almost” no data replication). The memory organization scheme and most part of all the computations of our method do not depend on the read requests, so they can be performed once and for all during an off-line phase. This is a relevant improvement over the previous deterministic method recently given in [1] when “real-time” applications are considered.
21 schema:editor N7f789213a47b49cfbe11aae3fb0a0065
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N5e4c7e362684498b8ea4f87212655b33
26 schema:name Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines
27 schema:pagination 68-77
28 schema:productId N1dcf3cde540d484584058571e1a9d72a
29 N330029c1d98e43d194046b569843a52f
30 N368a8cf6973f4d68b1be8d0a146f6c74
31 schema:publisher Nf16c2a3a254f4c9a8ede90e40921afc1
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033106345
33 https://doi.org/10.1007/3-540-49116-3_6
34 schema:sdDatePublished 2019-04-16T05:25
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N511c687626aa4f33a356c85ef5b16340
37 schema:url https://link.springer.com/10.1007%2F3-540-49116-3_6
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N08c3f8013c004a8fbb70339232b17a43 rdf:first sg:person.013274060005.11
42 rdf:rest rdf:nil
43 N1dcf3cde540d484584058571e1a9d72a schema:name doi
44 schema:value 10.1007/3-540-49116-3_6
45 rdf:type schema:PropertyValue
46 N330029c1d98e43d194046b569843a52f schema:name readcube_id
47 schema:value 9db67dc0c6972daeff5b59c43cf4111b6f512eced48020c5661ecc088d442e65
48 rdf:type schema:PropertyValue
49 N368a8cf6973f4d68b1be8d0a146f6c74 schema:name dimensions_id
50 schema:value pub.1033106345
51 rdf:type schema:PropertyValue
52 N511c687626aa4f33a356c85ef5b16340 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N5bad9d4f65b846588aa233684aa7529c rdf:first sg:person.013624103516.76
55 rdf:rest N08c3f8013c004a8fbb70339232b17a43
56 N5d8b22820b54499dbdbbdbbf7b065e10 schema:familyName Tison
57 schema:givenName Sophie
58 rdf:type schema:Person
59 N5e4c7e362684498b8ea4f87212655b33 schema:isbn 978-3-540-49116-3
60 978-3-540-65691-3
61 schema:name STACS 99
62 rdf:type schema:Book
63 N62318a665d56415392f6a8cb8e1ddb83 rdf:first sg:person.012322036405.59
64 rdf:rest Ndf142cc939e54e638003060ad5d316a3
65 N7f789213a47b49cfbe11aae3fb0a0065 rdf:first Ne3ccdbad507e4fd59d4c8696b77a1660
66 rdf:rest Nf219c8fab1bd49e2b447557497c6ae7b
67 Ndf142cc939e54e638003060ad5d316a3 rdf:first sg:person.011027660123.21
68 rdf:rest N5bad9d4f65b846588aa233684aa7529c
69 Ne3ccdbad507e4fd59d4c8696b77a1660 schema:familyName Meinel
70 schema:givenName Christoph
71 rdf:type schema:Person
72 Nf16c2a3a254f4c9a8ede90e40921afc1 schema:location Berlin, Heidelberg
73 schema:name Springer Berlin Heidelberg
74 rdf:type schema:Organisation
75 Nf219c8fab1bd49e2b447557497c6ae7b rdf:first N5d8b22820b54499dbdbbdbbf7b065e10
76 rdf:rest rdf:nil
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
81 schema:name Artificial Intelligence and Image Processing
82 rdf:type schema:DefinedTerm
83 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
84 schema:familyName Clementi
85 schema:givenName Andrea E. F.
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
87 rdf:type schema:Person
88 sg:person.012322036405.59 schema:affiliation https://www.grid.ac/institutes/grid.471058.f
89 schema:familyName Andreev
90 schema:givenName Alexander E.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322036405.59
92 rdf:type schema:Person
93 sg:person.013274060005.11 schema:affiliation https://www.grid.ac/institutes/grid.8591.5
94 schema:familyName Rolim
95 schema:givenName José D. P.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274060005.11
97 rdf:type schema:Person
98 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
99 schema:familyName Penna
100 schema:givenName Paolo
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
102 rdf:type schema:Person
103 sg:pub.10.1007/3-540-49543-6_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025474991
104 https://doi.org/10.1007/3-540-49543-6_17
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf00264615 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007326756
107 https://doi.org/10.1007/bf00264615
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf01940878 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025366447
110 https://doi.org/10.1007/bf01940878
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0304-3975(90)90192-k schema:sameAs https://app.dimensions.ai/details/publication/pub.1032459149
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1109/sfcs.1995.492461 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093241746
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1145/12130.12146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004659632
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1145/143369.143421 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037396887
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/165231.165245 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010158266
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/258533.258609 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051069655
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/276698.276723 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052112212
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/320064.320068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016419288
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/5925.5928 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039057305
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/7531.7926 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031240671
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/828.1892 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010797045
133 rdf:type schema:CreativeWork
134 https://www.grid.ac/institutes/grid.471058.f schema:alternateName Broadcom (United States)
135 schema:name LSI Logic, CA, USA
136 rdf:type schema:Organization
137 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
138 schema:name Dipartimento di Matematica, “Tor Vergata” University of Rome, Italy
139 rdf:type schema:Organization
140 https://www.grid.ac/institutes/grid.8591.5 schema:alternateName University of Geneva
141 schema:name Centre Universitaire d’Informatique, University of Geneva, CH
142 rdf:type schema:Organization
 




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


...