Efficient Sorting Using Registers and Caches View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001

AUTHORS

Lars Arge , Jeff Chase , Jeffrey S. Vitter , Rajiv Wickremesinghe

ABSTRACT

Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity, cache line fetching, and streaming behavior. Inadequate models lead to poor algorithmic choices and an incomplete understanding of algorithm behavior on real machines. A key step toward developing better models is to quantify the performance effects of features not reflected in the models. This paper explores the effect of memory system features on sorting performance. We introduce a new cache-conscious sorting algorithm, R-merge, which achieves better performance in practice over algorithms that are theoretically superior under the models. R-merge is designed to minimize memory stall cycles rather than cache misses, considering features common to many system designs. More... »

PAGES

51-62

Book

TITLE

Algorithm Engineering

ISBN

978-3-540-42512-0
978-3-540-44691-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44691-5_5

DOI

http://dx.doi.org/10.1007/3-540-44691-5_5

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arge", 
        "givenName": "Lars", 
        "id": "sg:person.010251111315.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chase", 
        "givenName": "Jeff", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wickremesinghe", 
        "givenName": "Rajiv", 
        "id": "sg:person.014145763433.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014145763433.55"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/48529.48535", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014013712"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity, cache line fetching, and streaming behavior. Inadequate models lead to poor algorithmic choices and an incomplete understanding of algorithm behavior on real machines. A key step toward developing better models is to quantify the performance effects of features not reflected in the models. This paper explores the effect of memory system features on sorting performance. We introduce a new cache-conscious sorting algorithm, R-merge, which achieves better performance in practice over algorithms that are theoretically superior under the models. R-merge is designed to minimize memory stall cycles rather than cache misses, considering features common to many system designs.", 
    "editor": [
      {
        "familyName": "N\u00e4her", 
        "givenName": "Stefan", 
        "type": "Person"
      }, 
      {
        "familyName": "Wagner", 
        "givenName": "Dorothea", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44691-5_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42512-0", 
        "978-3-540-44691-0"
      ], 
      "name": "Algorithm Engineering", 
      "type": "Book"
    }, 
    "name": "Efficient Sorting Using Registers and Caches", 
    "pagination": "51-62", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44691-5_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "84a8e8ef9eb3d692748af09c1899031712711ff19dd2c3797ccf65253d2fa718"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027848351"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44691-5_5", 
      "https://app.dimensions.ai/details/publication/pub.1027848351"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12:32", 
    "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/0000000001_0000000264/records_8663_00000260.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44691-5_5"
  }
]
 

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-44691-5_5'

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-44691-5_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44691-5_5'

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-44691-5_5'


 

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

93 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44691-5_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8908bb60c3924d6ab78dda356c4582af
4 schema:citation https://doi.org/10.1145/48529.48535
5 schema:datePublished 2001
6 schema:datePublishedReg 2001-01-01
7 schema:description Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity, cache line fetching, and streaming behavior. Inadequate models lead to poor algorithmic choices and an incomplete understanding of algorithm behavior on real machines. A key step toward developing better models is to quantify the performance effects of features not reflected in the models. This paper explores the effect of memory system features on sorting performance. We introduce a new cache-conscious sorting algorithm, R-merge, which achieves better performance in practice over algorithms that are theoretically superior under the models. R-merge is designed to minimize memory stall cycles rather than cache misses, considering features common to many system designs.
8 schema:editor N6fcf1f31f0b5431ea032078c8662e129
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N0c70015b19d946ee91ac354e22b5ea88
13 schema:name Efficient Sorting Using Registers and Caches
14 schema:pagination 51-62
15 schema:productId N4a694572be5245aab26abfbd9d270e12
16 N78394bd2e65e4060af1b493ce6895d4a
17 N970d1fb80eb5431e9ccb005cb510ab0a
18 schema:publisher N43d94b52523d4b6cafc7849d920a2594
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027848351
20 https://doi.org/10.1007/3-540-44691-5_5
21 schema:sdDatePublished 2019-04-15T12:32
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher N67ddfe38c49d4e95bb57a41eb9f87807
24 schema:url http://link.springer.com/10.1007/3-540-44691-5_5
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N0a6abbe93205496888578f914f6c5c09 rdf:first sg:person.014145763433.55
29 rdf:rest rdf:nil
30 N0c70015b19d946ee91ac354e22b5ea88 schema:isbn 978-3-540-42512-0
31 978-3-540-44691-0
32 schema:name Algorithm Engineering
33 rdf:type schema:Book
34 N118d531caef24d9686993b79280737ea schema:familyName Wagner
35 schema:givenName Dorothea
36 rdf:type schema:Person
37 N1cb2a82cf94541c48e8098455e19f992 rdf:first N118d531caef24d9686993b79280737ea
38 rdf:rest rdf:nil
39 N34663ac8a3a54f95b7103fe3659971bd rdf:first Nde5674d4ce994724bdb375f3b714442f
40 rdf:rest Nebccfa4a9ae14524b547e774ab4db81e
41 N43d94b52523d4b6cafc7849d920a2594 schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N4a694572be5245aab26abfbd9d270e12 schema:name readcube_id
45 schema:value 84a8e8ef9eb3d692748af09c1899031712711ff19dd2c3797ccf65253d2fa718
46 rdf:type schema:PropertyValue
47 N67ddfe38c49d4e95bb57a41eb9f87807 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N6fcf1f31f0b5431ea032078c8662e129 rdf:first Na58a2f69b80a4587ad877ef2987f6daf
50 rdf:rest N1cb2a82cf94541c48e8098455e19f992
51 N78394bd2e65e4060af1b493ce6895d4a schema:name doi
52 schema:value 10.1007/3-540-44691-5_5
53 rdf:type schema:PropertyValue
54 N8908bb60c3924d6ab78dda356c4582af rdf:first sg:person.010251111315.42
55 rdf:rest N34663ac8a3a54f95b7103fe3659971bd
56 N970d1fb80eb5431e9ccb005cb510ab0a schema:name dimensions_id
57 schema:value pub.1027848351
58 rdf:type schema:PropertyValue
59 Na58a2f69b80a4587ad877ef2987f6daf schema:familyName Näher
60 schema:givenName Stefan
61 rdf:type schema:Person
62 Nde5674d4ce994724bdb375f3b714442f schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
63 schema:familyName Chase
64 schema:givenName Jeff
65 rdf:type schema:Person
66 Nebccfa4a9ae14524b547e774ab4db81e rdf:first sg:person.0613677314.28
67 rdf:rest N0a6abbe93205496888578f914f6c5c09
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:person.010251111315.42 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
75 schema:familyName Arge
76 schema:givenName Lars
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42
78 rdf:type schema:Person
79 sg:person.014145763433.55 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
80 schema:familyName Wickremesinghe
81 schema:givenName Rajiv
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014145763433.55
83 rdf:type schema:Person
84 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
85 schema:familyName Vitter
86 schema:givenName Jeffrey S.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
88 rdf:type schema:Person
89 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
92 schema:name Department of Computer Science, Duke University, 27708 Durham, NC, USA
93 rdf:type schema:Organization
 




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


...