Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG Tasks Article Swipe
Niklas Ueter
,
Mario Günzel
,
Jian-Jia Chen
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2101.11053
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2101.11053
Real-time systems increasingly use multicore processors in order to satisfy thermal, power, and computational requirements. To exploit the architectural parallelism offered by the multicore processors, parallel task models, scheduling algorithms and response-time analyses with respect to real-time constraints have to be provided. In this paper, we propose a reservation-based scheduling algorithm for sporadic constrained-deadline parallel conditional DAG tasks with probabilistic execution behaviour for applications that can tolerate bounded number of deadline misses and bounded tardiness. We devise design rules and analyses to guarantee bounded tardiness for a specified bounded probability for $k$-consecutive deadline misses without enforcing late jobs to be immediately aborted.
Related Topics
Concepts
Tardiness
Computer science
Bounded function
Probabilistic logic
Parallel computing
Scheduling (production processes)
Exploit
Multi-core processor
Reservation
Distributed computing
Mathematical optimization
Job shop scheduling
Mathematics
Embedded system
Artificial intelligence
Routing (electronic design automation)
Mathematical analysis
Computer security
Computer network
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2101.11053
- https://arxiv.org/pdf/2101.11053
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4287367432
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4287367432Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2101.11053Digital Object Identifier
- Title
-
Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG TasksWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-01-26Full publication date if available
- Authors
-
Niklas Ueter, Mario Günzel, Jian-Jia ChenList of authors in order
- Landing page
-
https://arxiv.org/abs/2101.11053Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2101.11053Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2101.11053Direct OA link when available
- Concepts
-
Tardiness, Computer science, Bounded function, Probabilistic logic, Parallel computing, Scheduling (production processes), Exploit, Multi-core processor, Reservation, Distributed computing, Mathematical optimization, Job shop scheduling, Mathematics, Embedded system, Artificial intelligence, Routing (electronic design automation), Mathematical analysis, Computer security, Computer networkTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4287367432 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2101.11053 |
| ids.doi | https://doi.org/10.48550/arxiv.2101.11053 |
| ids.openalex | https://openalex.org/W4287367432 |
| fwci | |
| type | preprint |
| title | Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG Tasks |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10933 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9991999864578247 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1708 |
| topics[0].subfield.display_name | Hardware and Architecture |
| topics[0].display_name | Real-Time Systems Scheduling |
| topics[1].id | https://openalex.org/T10054 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9958999752998352 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1708 |
| topics[1].subfield.display_name | Hardware and Architecture |
| topics[1].display_name | Parallel Computing and Optimization Techniques |
| topics[2].id | https://openalex.org/T10904 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.992900013923645 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1708 |
| topics[2].subfield.display_name | Hardware and Architecture |
| topics[2].display_name | Embedded Systems Design Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2778047078 |
| concepts[0].level | 4 |
| concepts[0].score | 0.8701094388961792 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q82299449 |
| concepts[0].display_name | Tardiness |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.7861562967300415 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C34388435 |
| concepts[2].level | 2 |
| concepts[2].score | 0.7605130672454834 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[2].display_name | Bounded function |
| concepts[3].id | https://openalex.org/C49937458 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6618295907974243 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2599292 |
| concepts[3].display_name | Probabilistic logic |
| concepts[4].id | https://openalex.org/C173608175 |
| concepts[4].level | 1 |
| concepts[4].score | 0.5973321795463562 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[4].display_name | Parallel computing |
| concepts[5].id | https://openalex.org/C206729178 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5884094834327698 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2271896 |
| concepts[5].display_name | Scheduling (production processes) |
| concepts[6].id | https://openalex.org/C165696696 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5198060274124146 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q11287 |
| concepts[6].display_name | Exploit |
| concepts[7].id | https://openalex.org/C78766204 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5053141713142395 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q555032 |
| concepts[7].display_name | Multi-core processor |
| concepts[8].id | https://openalex.org/C2777632111 |
| concepts[8].level | 2 |
| concepts[8].score | 0.5032898783683777 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1937518 |
| concepts[8].display_name | Reservation |
| concepts[9].id | https://openalex.org/C120314980 |
| concepts[9].level | 1 |
| concepts[9].score | 0.35909503698349 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q180634 |
| concepts[9].display_name | Distributed computing |
| concepts[10].id | https://openalex.org/C126255220 |
| concepts[10].level | 1 |
| concepts[10].score | 0.29393821954727173 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[10].display_name | Mathematical optimization |
| concepts[11].id | https://openalex.org/C55416958 |
| concepts[11].level | 3 |
| concepts[11].score | 0.24305999279022217 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q6206757 |
| concepts[11].display_name | Job shop scheduling |
| concepts[12].id | https://openalex.org/C33923547 |
| concepts[12].level | 0 |
| concepts[12].score | 0.13417497277259827 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[12].display_name | Mathematics |
| concepts[13].id | https://openalex.org/C149635348 |
| concepts[13].level | 1 |
| concepts[13].score | 0.09153521060943604 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q193040 |
| concepts[13].display_name | Embedded system |
| concepts[14].id | https://openalex.org/C154945302 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[14].display_name | Artificial intelligence |
| concepts[15].id | https://openalex.org/C74172769 |
| concepts[15].level | 2 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q1446839 |
| concepts[15].display_name | Routing (electronic design automation) |
| concepts[16].id | https://openalex.org/C134306372 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[16].display_name | Mathematical analysis |
| concepts[17].id | https://openalex.org/C38652104 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q3510521 |
| concepts[17].display_name | Computer security |
| concepts[18].id | https://openalex.org/C31258907 |
| concepts[18].level | 1 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q1301371 |
| concepts[18].display_name | Computer network |
| keywords[0].id | https://openalex.org/keywords/tardiness |
| keywords[0].score | 0.8701094388961792 |
| keywords[0].display_name | Tardiness |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.7861562967300415 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/bounded-function |
| keywords[2].score | 0.7605130672454834 |
| keywords[2].display_name | Bounded function |
| keywords[3].id | https://openalex.org/keywords/probabilistic-logic |
| keywords[3].score | 0.6618295907974243 |
| keywords[3].display_name | Probabilistic logic |
| keywords[4].id | https://openalex.org/keywords/parallel-computing |
| keywords[4].score | 0.5973321795463562 |
| keywords[4].display_name | Parallel computing |
| keywords[5].id | https://openalex.org/keywords/scheduling |
| keywords[5].score | 0.5884094834327698 |
| keywords[5].display_name | Scheduling (production processes) |
| keywords[6].id | https://openalex.org/keywords/exploit |
| keywords[6].score | 0.5198060274124146 |
| keywords[6].display_name | Exploit |
| keywords[7].id | https://openalex.org/keywords/multi-core-processor |
| keywords[7].score | 0.5053141713142395 |
| keywords[7].display_name | Multi-core processor |
| keywords[8].id | https://openalex.org/keywords/reservation |
| keywords[8].score | 0.5032898783683777 |
| keywords[8].display_name | Reservation |
| keywords[9].id | https://openalex.org/keywords/distributed-computing |
| keywords[9].score | 0.35909503698349 |
| keywords[9].display_name | Distributed computing |
| keywords[10].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[10].score | 0.29393821954727173 |
| keywords[10].display_name | Mathematical optimization |
| keywords[11].id | https://openalex.org/keywords/job-shop-scheduling |
| keywords[11].score | 0.24305999279022217 |
| keywords[11].display_name | Job shop scheduling |
| keywords[12].id | https://openalex.org/keywords/mathematics |
| keywords[12].score | 0.13417497277259827 |
| keywords[12].display_name | Mathematics |
| keywords[13].id | https://openalex.org/keywords/embedded-system |
| keywords[13].score | 0.09153521060943604 |
| keywords[13].display_name | Embedded system |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2101.11053 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2101.11053 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2101.11053 |
| locations[1].id | doi:10.48550/arxiv.2101.11053 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2101.11053 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5081007355 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6722-4805 |
| authorships[0].author.display_name | Niklas Ueter |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ueter, Niklas |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5031334628 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7575-7014 |
| authorships[1].author.display_name | Mario Günzel |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Günzel, Mario |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5000417436 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-8114-9760 |
| authorships[2].author.display_name | Jian-Jia Chen |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Chen, Jian-Jia |
| authorships[2].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2101.11053 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG Tasks |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10933 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9991999864578247 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1708 |
| primary_topic.subfield.display_name | Hardware and Architecture |
| primary_topic.display_name | Real-Time Systems Scheduling |
| related_works | https://openalex.org/W2011810134, https://openalex.org/W2050497389, https://openalex.org/W1568976062, https://openalex.org/W2960025371, https://openalex.org/W2367625138, https://openalex.org/W2019537266, https://openalex.org/W2012711731, https://openalex.org/W2017891857, https://openalex.org/W2141506759, https://openalex.org/W4312208395 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2101.11053 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2101.11053 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2101.11053 |
| primary_location.id | pmh:oai:arXiv.org:2101.11053 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2101.11053 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2101.11053 |
| publication_date | 2021-01-26 |
| publication_year | 2021 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 47, 86 |
| abstract_inverted_index.In | 42 |
| abstract_inverted_index.To | 15 |
| abstract_inverted_index.We | 75 |
| abstract_inverted_index.be | 40, 99 |
| abstract_inverted_index.by | 21 |
| abstract_inverted_index.in | 6 |
| abstract_inverted_index.of | 69 |
| abstract_inverted_index.to | 8, 35, 39, 81, 98 |
| abstract_inverted_index.we | 45 |
| abstract_inverted_index.DAG | 56 |
| abstract_inverted_index.and | 12, 30, 72, 79 |
| abstract_inverted_index.can | 65 |
| abstract_inverted_index.for | 51, 62, 85, 90 |
| abstract_inverted_index.the | 17, 22 |
| abstract_inverted_index.use | 3 |
| abstract_inverted_index.have | 38 |
| abstract_inverted_index.jobs | 97 |
| abstract_inverted_index.late | 96 |
| abstract_inverted_index.task | 26 |
| abstract_inverted_index.that | 64 |
| abstract_inverted_index.this | 43 |
| abstract_inverted_index.with | 33, 58 |
| abstract_inverted_index.order | 7 |
| abstract_inverted_index.rules | 78 |
| abstract_inverted_index.tasks | 57 |
| abstract_inverted_index.design | 77 |
| abstract_inverted_index.devise | 76 |
| abstract_inverted_index.misses | 71, 93 |
| abstract_inverted_index.number | 68 |
| abstract_inverted_index.paper, | 44 |
| abstract_inverted_index.power, | 11 |
| abstract_inverted_index.bounded | 67, 73, 83, 88 |
| abstract_inverted_index.exploit | 16 |
| abstract_inverted_index.models, | 27 |
| abstract_inverted_index.offered | 20 |
| abstract_inverted_index.propose | 46 |
| abstract_inverted_index.respect | 34 |
| abstract_inverted_index.satisfy | 9 |
| abstract_inverted_index.systems | 1 |
| abstract_inverted_index.without | 94 |
| abstract_inverted_index.aborted. | 101 |
| abstract_inverted_index.analyses | 32, 80 |
| abstract_inverted_index.deadline | 70, 92 |
| abstract_inverted_index.parallel | 25, 54 |
| abstract_inverted_index.sporadic | 52 |
| abstract_inverted_index.thermal, | 10 |
| abstract_inverted_index.tolerate | 66 |
| abstract_inverted_index.Real-time | 0 |
| abstract_inverted_index.algorithm | 50 |
| abstract_inverted_index.behaviour | 61 |
| abstract_inverted_index.enforcing | 95 |
| abstract_inverted_index.execution | 60 |
| abstract_inverted_index.guarantee | 82 |
| abstract_inverted_index.multicore | 4, 23 |
| abstract_inverted_index.provided. | 41 |
| abstract_inverted_index.real-time | 36 |
| abstract_inverted_index.specified | 87 |
| abstract_inverted_index.tardiness | 84 |
| abstract_inverted_index.algorithms | 29 |
| abstract_inverted_index.processors | 5 |
| abstract_inverted_index.scheduling | 28, 49 |
| abstract_inverted_index.tardiness. | 74 |
| abstract_inverted_index.conditional | 55 |
| abstract_inverted_index.constraints | 37 |
| abstract_inverted_index.immediately | 100 |
| abstract_inverted_index.parallelism | 19 |
| abstract_inverted_index.probability | 89 |
| abstract_inverted_index.processors, | 24 |
| abstract_inverted_index.applications | 63 |
| abstract_inverted_index.increasingly | 2 |
| abstract_inverted_index.architectural | 18 |
| abstract_inverted_index.computational | 13 |
| abstract_inverted_index.probabilistic | 59 |
| abstract_inverted_index.requirements. | 14 |
| abstract_inverted_index.response-time | 31 |
| abstract_inverted_index.$k$-consecutive | 91 |
| abstract_inverted_index.reservation-based | 48 |
| abstract_inverted_index.constrained-deadline | 53 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/8 |
| sustainable_development_goals[0].score | 0.5400000214576721 |
| sustainable_development_goals[0].display_name | Decent work and economic growth |
| citation_normalized_percentile |