VTechWorks staff will be away for the Memorial Day holiday on Monday, May 27, and will not be replying to requests at that time. Thank you for your patience.

Show simple item record

dc.contributor.authorBijinemula, Sandeep Kumaren_US
dc.description.abstractEngine-triggered tasks are real-time tasks that are released when the crankshaft arrives at certain positions in its path of rotation. This makes the rate of release of these jobs a function of the crankshaft's angular speed and acceleration. In addition, several properties of the engine triggered tasks like the execution time and deadlines are dependent on the speed profile of the crankshaft. Such tasks are referred to as adaptive-variable rate (AVR) tasks. Existing methods to calculate the worst-case demand of AVR tasks are either inaccurate or computationally intractable. We propose a method to efficiently calculate the worst-case demand of AVR tasks by transforming the problem into a variant of the knapsack problem. We then propose a framework to systematically narrow down the search space associated with finding the worst-case demand of AVR tasks. Experimental results show that our approach is at least 10 times faster, with an average runtime improvement of 146 times for randomly generated task sets when compared to the state-of-the-art technique.en_US
dc.publisherVirginia Techen_US
dc.rightsThis item is protected by copyright and/or related rights. Some uses of this item may be deemed fair and permitted by law even without permission from the rights holder(s), or the rights holder(s) may have licensed the work for use under certain conditions. For other uses you need to obtain permission from the rights holder(s).en_US
dc.subjectAdaptive variable rate tasken_US
dc.subjectdemand bound functionen_US
dc.subjectworst-case demanden_US
dc.subjectknapsack problemen_US
dc.titleAn Efficient Knapsack-Based Approach for Calculating the Worst-Case Demand of AVR Tasksen_US
dc.contributor.departmentElectrical and Computer Engineeringen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Engineeringen_US
dc.contributor.committeechairChantem, Thidapaten_US
dc.contributor.committeememberYu, Guoqiangen_US
dc.contributor.committeememberGerdes, Ryan M.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record