A Simple and Efficient Parallel Disk Mergesort View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2002-04

AUTHORS

R. D. Barve, J. S. Vitter

ABSTRACT

External sorting—the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks—is a fundamental subroutine in database systems[G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K,Section 5.4.9] recently identified SRM (which he calls ``randomized striping'') as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment[TPI]; whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM ), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM (since SRM requires fewer passes). The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel disks, including distribution sort and multiway partitioning of a file into several other files. Since both parallel disk merging and multimedia processing deal with streams that get ``consumed'' at nonuniform and partially predictable rates, our techniques for lookahead based upon forecasting data may have relevance in video server applications. More... »

PAGES

189-215

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-002-1031-0

DOI

http://dx.doi.org/10.1007/s00224-002-1031-0

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": {
          "name": [
            "Winphoria Networks, c/o B23 Swagat Mahakali Caves Road, rbarve@winphoria.com, Andheri, Mumbai 400 093, India, IN"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Barve", 
        "givenName": "R. D.", 
        "id": "sg:person.015413741305.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015413741305.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric and Biological Computing, Department of Computer Science,    Duke University, jsv@cs.duke.edu, Durham, NC 27708-0129, USA, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "J. S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-04", 
    "datePublishedReg": "2002-04-01", 
    "description": "External sorting\u2014the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks\u2014is a fundamental subroutine in database systems[G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K,Section 5.4.9] recently identified SRM (which he calls ``randomized striping'') as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment[TPI]; whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM ), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM (since SRM requires fewer passes). The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel disks, including distribution sort and multiway partitioning of a file into several other files. Since both parallel disk merging and multimedia processing deal with streams that get ``consumed'' at nonuniform and partially predictable rates, our techniques for lookahead based upon forecasting data may have relevance in video server applications.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-002-1031-0", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "35"
      }
    ], 
    "name": "A Simple and Efficient Parallel Disk Mergesort", 
    "pagination": "189-215", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "449b789b7013880cf9fb59dd8c7bcf111166a7fc1357d356e2a8f42643597420"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-002-1031-0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014401339"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-002-1031-0", 
      "https://app.dimensions.ai/details/publication/pub.1014401339"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T01:53", 
    "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_8700_00000487.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-002-1031-0"
  }
]
 

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/s00224-002-1031-0'

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/s00224-002-1031-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-002-1031-0'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-002-1031-0'


 

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

70 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-002-1031-0 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N01f59846586a41a887f7fa9a57565465
4 schema:datePublished 2002-04
5 schema:datePublishedReg 2002-04-01
6 schema:description External sorting—the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks—is a fundamental subroutine in database systems[G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K,Section 5.4.9] recently identified SRM (which he calls ``randomized striping'') as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment[TPI]; whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM ), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM (since SRM requires fewer passes). The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel disks, including distribution sort and multiway partitioning of a file into several other files. Since both parallel disk merging and multimedia processing deal with streams that get ``consumed'' at nonuniform and partially predictable rates, our techniques for lookahead based upon forecasting data may have relevance in video server applications.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N4111808b07b24f95a6654bd54f7e7b27
11 N9c656aa22a5040f38836e99c8af38bec
12 sg:journal.1052098
13 schema:name A Simple and Efficient Parallel Disk Mergesort
14 schema:pagination 189-215
15 schema:productId Nb21800c697664b6a9b70361e948e0dba
16 Nc2780bef566b486bb1489ab7bf4360e5
17 Nda0241af1ed741ee8324d95e2a1ce8aa
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014401339
19 https://doi.org/10.1007/s00224-002-1031-0
20 schema:sdDatePublished 2019-04-11T01:53
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N3a10e04f246045c2b38de38714c91b39
23 schema:url http://link.springer.com/10.1007/s00224-002-1031-0
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N012b2699f0344ae7be5da501585af390 schema:name Winphoria Networks, c/o B23 Swagat Mahakali Caves Road, rbarve@winphoria.com, Andheri, Mumbai 400 093, India, IN
28 rdf:type schema:Organization
29 N01f59846586a41a887f7fa9a57565465 rdf:first sg:person.015413741305.34
30 rdf:rest N6326dcc673134f9185807fe7a7b08829
31 N3a10e04f246045c2b38de38714c91b39 schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 N4111808b07b24f95a6654bd54f7e7b27 schema:volumeNumber 35
34 rdf:type schema:PublicationVolume
35 N6326dcc673134f9185807fe7a7b08829 rdf:first sg:person.0613677314.28
36 rdf:rest rdf:nil
37 N9c656aa22a5040f38836e99c8af38bec schema:issueNumber 2
38 rdf:type schema:PublicationIssue
39 Nb21800c697664b6a9b70361e948e0dba schema:name dimensions_id
40 schema:value pub.1014401339
41 rdf:type schema:PropertyValue
42 Nc2780bef566b486bb1489ab7bf4360e5 schema:name readcube_id
43 schema:value 449b789b7013880cf9fb59dd8c7bcf111166a7fc1357d356e2a8f42643597420
44 rdf:type schema:PropertyValue
45 Nda0241af1ed741ee8324d95e2a1ce8aa schema:name doi
46 schema:value 10.1007/s00224-002-1031-0
47 rdf:type schema:PropertyValue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
52 schema:name Information Systems
53 rdf:type schema:DefinedTerm
54 sg:journal.1052098 schema:issn 1432-4350
55 1433-0490
56 schema:name Theory of Computing Systems
57 rdf:type schema:Periodical
58 sg:person.015413741305.34 schema:affiliation N012b2699f0344ae7be5da501585af390
59 schema:familyName Barve
60 schema:givenName R. D.
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015413741305.34
62 rdf:type schema:Person
63 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
64 schema:familyName Vitter
65 schema:givenName J. S.
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
67 rdf:type schema:Person
68 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
69 schema:name Center for Geometric and Biological Computing, Department of Computer Science, Duke University, jsv@cs.duke.edu, Durham, NC 27708-0129, USA, US
70 rdf:type schema:Organization
 




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


...