Loop scheduling to minimize cost with data mining and prefetching for heterogeneous DSP

Meikang Qiu, Zhiping Jia, Chun Xuc, Zili Shao, Ying Liu, Edwin H.M. Sha

Research output: Journal article publicationConference articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

In real-time embedded systems, such as multimedia and video applications, cost and time are the most important issues and loop is the most critical part. Due to the uncertainties in execution time of some tasks, this paper models each varied execution time as a probabilistic random variable. We proposes a novel algorithm to minimize the total cost while satisfying the timing constraint with a guaranteed confidence probability. First, we use data mining to predict the distribution of execution time and find the association rules between execution time and different inputs from history table. Then we use rotation scheduling to obtain the best assignment for total cost minimization, which is called the HAP problem in this paper. Finally, we use prefetching to prepare data in advance at run time. Experiments demonstrate the effectiveness of our algorithm. Our approach can handle loops efficiently. In addition, it is suitable to both soft and hard real-time systems.
Original languageEnglish
Pages (from-to)572-577
Number of pages6
JournalProceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems
Publication statusPublished - 1 Dec 2006
Event18th IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2006 - Dallas, TX, United States
Duration: 13 Nov 200615 Nov 2006

Keywords

  • Data mining
  • Heterogeneous
  • Prefetch
  • Probability
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this