Scheduling interval ordered tasks in parallel View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

S. Sunder , Xin He

ABSTRACT

We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority CRCW PRAM in O(log2n) time with O(n5) processors, or in O(log3n) time with O(n4) processors. The algorithm constructs the same schedule as the one produced by the sequential algorithm (list scheduling). On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-complete. More... »

PAGES

100-109

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-56503-5_13

DOI

http://dx.doi.org/10.1007/3-540-56503-5_13

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sunder", 
        "givenName": "S.", 
        "id": "sg:person.07401535357.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401535357.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority CRCW PRAM in O(log2n) time with O(n5) processors, or in O(log3n) time with O(n4) processors. The algorithm constructs the same schedule as the one produced by the sequential algorithm (list scheduling). On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-complete.", 
    "editor": [
      {
        "familyName": "Enjalbert", 
        "givenName": "P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Finkel", 
        "givenName": "A.", 
        "type": "Person"
      }, 
      {
        "familyName": "Wagner", 
        "givenName": "K. W.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-56503-5_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-56503-1", 
        "978-3-540-47574-3"
      ], 
      "name": "STACS 93", 
      "type": "Book"
    }, 
    "keywords": [
      "precedence constraints", 
      "unit length tasks", 
      "PRIORITY CRCW PRAM", 
      "first NC algorithm", 
      "sequential algorithm", 
      "NC algorithm", 
      "identical processors", 
      "CRCW PRAM", 
      "algorithm", 
      "processors", 
      "length tasks", 
      "list schedule", 
      "task", 
      "constraints", 
      "PRAM", 
      "interval orders", 
      "schedule", 
      "time", 
      "order", 
      "construction", 
      "parallel", 
      "one", 
      "hand", 
      "cases", 
      "intervals", 
      "same schedule"
    ], 
    "name": "Scheduling interval ordered tasks in parallel", 
    "pagination": "100-109", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038503798"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-56503-5_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-56503-5_13", 
      "https://app.dimensions.ai/details/publication/pub.1038503798"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "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_356.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-56503-5_13"
  }
]
 

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-56503-5_13'

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-56503-5_13'

Turtle is a human-readable linked data format.

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

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-56503-5_13'


 

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

103 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-56503-5_13 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N7a2f2dbc82a64bad9e272c9f28166770
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority CRCW PRAM in O(log2n) time with O(n5) processors, or in O(log3n) time with O(n4) processors. The algorithm constructs the same schedule as the one produced by the sequential algorithm (list scheduling). On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-complete.
7 schema:editor Nef75fe535d284da1bd3a9b398a879bb5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5795b7904692458dbab9657d056607bd
12 schema:keywords CRCW PRAM
13 NC algorithm
14 PRAM
15 PRIORITY CRCW PRAM
16 algorithm
17 cases
18 constraints
19 construction
20 first NC algorithm
21 hand
22 identical processors
23 interval orders
24 intervals
25 length tasks
26 list schedule
27 one
28 order
29 parallel
30 precedence constraints
31 processors
32 same schedule
33 schedule
34 sequential algorithm
35 task
36 time
37 unit length tasks
38 schema:name Scheduling interval ordered tasks in parallel
39 schema:pagination 100-109
40 schema:productId N76ee0270cca8481eacd6384d51c08b6f
41 Nb72d49a201944af1995dcdd90a845dfa
42 schema:publisher Na8cbee03a99f4f3cbb4335e5aea6252a
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038503798
44 https://doi.org/10.1007/3-540-56503-5_13
45 schema:sdDatePublished 2021-11-01T18:57
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N830b76a7d949457a851b36b94eb0da84
48 schema:url https://doi.org/10.1007/3-540-56503-5_13
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N2ada9ab8372f40f198f9bcaeb31dfb9b rdf:first Nd5c1455eca824f3795f7c1073a5d405d
53 rdf:rest rdf:nil
54 N5795b7904692458dbab9657d056607bd schema:isbn 978-3-540-47574-3
55 978-3-540-56503-1
56 schema:name STACS 93
57 rdf:type schema:Book
58 N5fc1bf5c1fcc43fe800e993e5516dbb4 rdf:first N8b1ea03e880b423e976bcf8d6cf0f440
59 rdf:rest N2ada9ab8372f40f198f9bcaeb31dfb9b
60 N76ee0270cca8481eacd6384d51c08b6f schema:name doi
61 schema:value 10.1007/3-540-56503-5_13
62 rdf:type schema:PropertyValue
63 N7a2f2dbc82a64bad9e272c9f28166770 rdf:first sg:person.07401535357.26
64 rdf:rest Nc50ecc2b65fb45cdb0e86311995830f4
65 N830b76a7d949457a851b36b94eb0da84 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N8b1ea03e880b423e976bcf8d6cf0f440 schema:familyName Finkel
68 schema:givenName A.
69 rdf:type schema:Person
70 Na8cbee03a99f4f3cbb4335e5aea6252a schema:name Springer Nature
71 rdf:type schema:Organisation
72 Nb72d49a201944af1995dcdd90a845dfa schema:name dimensions_id
73 schema:value pub.1038503798
74 rdf:type schema:PropertyValue
75 Nc50ecc2b65fb45cdb0e86311995830f4 rdf:first sg:person.011352641523.42
76 rdf:rest rdf:nil
77 Nd5c1455eca824f3795f7c1073a5d405d schema:familyName Wagner
78 schema:givenName K. W.
79 rdf:type schema:Person
80 Nde935973ace3453092b995a77b91e0be schema:familyName Enjalbert
81 schema:givenName P.
82 rdf:type schema:Person
83 Nef75fe535d284da1bd3a9b398a879bb5 rdf:first Nde935973ace3453092b995a77b91e0be
84 rdf:rest N5fc1bf5c1fcc43fe800e993e5516dbb4
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
89 schema:name Computer Software
90 rdf:type schema:DefinedTerm
91 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
92 schema:familyName He
93 schema:givenName Xin
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
95 rdf:type schema:Person
96 sg:person.07401535357.26 schema:affiliation grid-institutes:grid.273335.3
97 schema:familyName Sunder
98 schema:givenName S.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401535357.26
100 rdf:type schema:Person
101 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
102 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
103 rdf:type schema:Organization
 




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


...