{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/78658"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/78658","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The delay composition theorem on pipeline systems with non-preemptive priority varying scheduling algorithms","abstract":"The delay composition theorem, by taking into account the fact that pipeline systems allow concurrent execution, expresses the upper-bounded delay of a real-time task as the sum of two summations, where the first one is linear to the number of stages of the system, and the second one is linear to the number of tasks running on the system. The schedulability analysis based on delay composition theorem performs better than traditional analysis techniques. In this paper we break one assumption that has been hold by previous works on delay composition theorem, namely each task has the same relative priority across all stages. We extend the theorem to pipeline systems running non-preemptive scheduling algorithm which may assign different relative priorities to a task on different stages.","abstract_html":"The delay composition theorem, by taking into account the fact that pipeline systems allow concurrent execution, expresses the upper-bounded delay of a real-time task as the sum of two summations, where the first one is linear to the number of stages of the system, and the second one is linear to the number of tasks running on the system. The schedulability analysis based on delay composition theorem performs better than traditional analysis techniques. In this paper we break one assumption that has been hold by previous works on delay composition theorem, namely each task has the same relative priority across all stages. We extend the theorem to pipeline systems running non-preemptive scheduling algorithm which may assign different relative priorities to a task on different stages.","abstract_has_math":false,"creators":["Lu, Yi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-07-22T22:33:49Z","date_published":"2015-07-22T22:33:49Z","updated_at":"2026-07-22T22:26:12Z","subjects":["real-time scheduling","pipeline systems"],"languages":["en"],"rights":["Copyright 2015 Yi Lu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/78658","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lu, Yi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-07-22T22:33:49Z","2017-07-23T09:15:38Z","2015-05","2015-04-23","2015-5"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["real-time scheduling","pipeline systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Yi Lu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/78658"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The delay composition theorem, by taking into account the fact that pipeline systems allow concurrent execution, expresses the upper-bounded delay of a real-time task as the sum of two summations, where the first one is linear to the number of stages of the system, and the second one is linear to the number of tasks running on the system. The schedulability analysis based on delay composition theorem performs better than traditional analysis techniques. In this paper we break one assumption that has been hold by previous works on delay composition theorem, namely each task has the same relative priority across all stages. We extend the theorem to pipeline systems running non-preemptive scheduling algorithm which may assign different relative priorities to a task on different stages.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-05-01","The student, Yi Lu, accepted the attached license on 2015-04-22 at 15:41.","The student, Yi Lu, submitted this Thesis for approval on 2015-04-22 at 15:47.","This Thesis was approved for publication on 2015-04-23 at 14:22.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8032 on 2015-07-22 at 14:18:39","Made available in DSpace on 2015-07-22T22:33:49Z (GMT). No. of bitstreams: 2 LU-THESIS-2015.pdf: 499391 bytes, checksum: 9f7d9e76fd2c3ee3b431ed4e5d279286 (MD5) LICENSE.txt: 4202 bytes, checksum: 73ba1baff29c8bf91b20b7e227425a2d (MD5) Previous issue date: 2015-04-23","Embargo set by: Seth Robbins for item 79899 Lift date: 2017-07-22T22:34:16Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 79899 on 2017-07-23T09:15:38Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The delay composition theorem on pipeline systems with non-preemptive priority varying scheduling algorithms"]}]}],"canonical_facts":{"dc:creator":["Lu, Yi"],"dc:date":["2015-07-22T22:33:49Z","2017-07-23T09:15:38Z","2015-05","2015-04-23","2015-5"],"dc:description":["The delay composition theorem, by taking into account the fact that pipeline systems allow concurrent execution, expresses the upper-bounded delay of a real-time task as the sum of two summations, where the first one is linear to the number of stages of the system, and the second one is linear to the number of tasks running on the system. The schedulability analysis based on delay composition theorem performs better than traditional analysis techniques. In this paper we break one assumption that has been hold by previous works on delay composition theorem, namely each task has the same relative priority across all stages. We extend the theorem to pipeline systems running non-preemptive scheduling algorithm which may assign different relative priorities to a task on different stages.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-05-01","The student, Yi Lu, accepted the attached license on 2015-04-22 at 15:41.","The student, Yi Lu, submitted this Thesis for approval on 2015-04-22 at 15:47.","This Thesis was approved for publication on 2015-04-23 at 14:22.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8032 on 2015-07-22 at 14:18:39","Made available in DSpace on 2015-07-22T22:33:49Z (GMT). No. of bitstreams: 2 LU-THESIS-2015.pdf: 499391 bytes, checksum: 9f7d9e76fd2c3ee3b431ed4e5d279286 (MD5) LICENSE.txt: 4202 bytes, checksum: 73ba1baff29c8bf91b20b7e227425a2d (MD5) Previous issue date: 2015-04-23","Embargo set by: Seth Robbins for item 79899 Lift date: 2017-07-22T22:34:16Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 79899 on 2017-07-23T09:15:38Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/78658"],"dc:language":["en"],"dc:rights":["Copyright 2015 Yi Lu"],"dc:subject":["real-time scheduling","pipeline systems"],"dc:title":["The delay composition theorem on pipeline systems with non-preemptive priority varying scheduling algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:12Z"}