Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models

O. Mansour, Sandro Etalle, Th. Krol

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

31 Downloads (Pure)

Abstract

We address the problem of scheduling non-manifest data dependant periodic loops for high throughput DSP-applications based on a streaming data model. In contrast to manifest loops, non-manifest data dependant loops are loops where the number of iterations needed in order to perform a calculation is data dependant and hence not known at compile time. For the case of manifest loops, static scheduling techniques have been devised which produce near optimal schedules. Due to the lack of exact run-time execution knowledge of non-manifest loops, these static scheduling techniques are not suitable for tackling scheduling problems of DSP-algorithms with non-manifest loops embedded in them. We consider the case where (a) a-priori knowledge of the data distribution, and (b) worst case execution time of the non-manifest loop are known and a constraint on the total execution time has been given. Under these conditions dynamic schedules of the non-manifest data dependant loops within the DSP-algorithm are possible. We show how to construct hardware which dynamically schedules these non-manifest loops. The sliding window execution, which is the execution of a non-manifest loop when the data streams through it, of the constructed hardware will guarantee real time performance for the worst case situation. This is the situation when each non-manifest loop requires its maximum number of iterations.
Original languageUndefined
Title of host publication2nd PROGRESS workshop on Embedded Systems
EditorsF. Karelse
Place of PublicationUtrecht, The Netherlands
PublisherSTW
Pages153-160
Number of pages8
ISBN (Print)90-73461-26-X
Publication statusPublished - Oct 2001
Event2nd PROGRESS Workshop on Embedded Systems 2001 - Veldhoven, Netherlands
Duration: 18 Oct 200118 Oct 2001
Conference number: 2

Publication series

Name
PublisherSTW Technology Foundation

Workshop

Workshop2nd PROGRESS Workshop on Embedded Systems 2001
Abbreviated titlePROGRESS
CountryNetherlands
CityVeldhoven
Period18/10/0118/10/01

Keywords

  • EWI-957
  • periodic loops
  • Non-manifest loop scheduling
  • dynamic hardware scheduling
  • IR-36875
  • METIS-203304

Cite this

Mansour, O., Etalle, S., & Krol, T. (2001). Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. In F. Karelse (Ed.), 2nd PROGRESS workshop on Embedded Systems (pp. 153-160). Utrecht, The Netherlands: STW.
Mansour, O. ; Etalle, Sandro ; Krol, Th. / Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. 2nd PROGRESS workshop on Embedded Systems. editor / F. Karelse. Utrecht, The Netherlands : STW, 2001. pp. 153-160
@inproceedings{6c0b325ff4a14243b265b96207065c46,
title = "Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models",
abstract = "We address the problem of scheduling non-manifest data dependant periodic loops for high throughput DSP-applications based on a streaming data model. In contrast to manifest loops, non-manifest data dependant loops are loops where the number of iterations needed in order to perform a calculation is data dependant and hence not known at compile time. For the case of manifest loops, static scheduling techniques have been devised which produce near optimal schedules. Due to the lack of exact run-time execution knowledge of non-manifest loops, these static scheduling techniques are not suitable for tackling scheduling problems of DSP-algorithms with non-manifest loops embedded in them. We consider the case where (a) a-priori knowledge of the data distribution, and (b) worst case execution time of the non-manifest loop are known and a constraint on the total execution time has been given. Under these conditions dynamic schedules of the non-manifest data dependant loops within the DSP-algorithm are possible. We show how to construct hardware which dynamically schedules these non-manifest loops. The sliding window execution, which is the execution of a non-manifest loop when the data streams through it, of the constructed hardware will guarantee real time performance for the worst case situation. This is the situation when each non-manifest loop requires its maximum number of iterations.",
keywords = "EWI-957, periodic loops, Non-manifest loop scheduling, dynamic hardware scheduling, IR-36875, METIS-203304",
author = "O. Mansour and Sandro Etalle and Th. Krol",
note = "Imported from DIES",
year = "2001",
month = "10",
language = "Undefined",
isbn = "90-73461-26-X",
publisher = "STW",
pages = "153--160",
editor = "F. Karelse",
booktitle = "2nd PROGRESS workshop on Embedded Systems",

}

Mansour, O, Etalle, S & Krol, T 2001, Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. in F Karelse (ed.), 2nd PROGRESS workshop on Embedded Systems. STW, Utrecht, The Netherlands, pp. 153-160, 2nd PROGRESS Workshop on Embedded Systems 2001, Veldhoven, Netherlands, 18/10/01.

Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. / Mansour, O.; Etalle, Sandro; Krol, Th.

2nd PROGRESS workshop on Embedded Systems. ed. / F. Karelse. Utrecht, The Netherlands : STW, 2001. p. 153-160.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

TY - GEN

T1 - Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models

AU - Mansour, O.

AU - Etalle, Sandro

AU - Krol, Th.

N1 - Imported from DIES

PY - 2001/10

Y1 - 2001/10

N2 - We address the problem of scheduling non-manifest data dependant periodic loops for high throughput DSP-applications based on a streaming data model. In contrast to manifest loops, non-manifest data dependant loops are loops where the number of iterations needed in order to perform a calculation is data dependant and hence not known at compile time. For the case of manifest loops, static scheduling techniques have been devised which produce near optimal schedules. Due to the lack of exact run-time execution knowledge of non-manifest loops, these static scheduling techniques are not suitable for tackling scheduling problems of DSP-algorithms with non-manifest loops embedded in them. We consider the case where (a) a-priori knowledge of the data distribution, and (b) worst case execution time of the non-manifest loop are known and a constraint on the total execution time has been given. Under these conditions dynamic schedules of the non-manifest data dependant loops within the DSP-algorithm are possible. We show how to construct hardware which dynamically schedules these non-manifest loops. The sliding window execution, which is the execution of a non-manifest loop when the data streams through it, of the constructed hardware will guarantee real time performance for the worst case situation. This is the situation when each non-manifest loop requires its maximum number of iterations.

AB - We address the problem of scheduling non-manifest data dependant periodic loops for high throughput DSP-applications based on a streaming data model. In contrast to manifest loops, non-manifest data dependant loops are loops where the number of iterations needed in order to perform a calculation is data dependant and hence not known at compile time. For the case of manifest loops, static scheduling techniques have been devised which produce near optimal schedules. Due to the lack of exact run-time execution knowledge of non-manifest loops, these static scheduling techniques are not suitable for tackling scheduling problems of DSP-algorithms with non-manifest loops embedded in them. We consider the case where (a) a-priori knowledge of the data distribution, and (b) worst case execution time of the non-manifest loop are known and a constraint on the total execution time has been given. Under these conditions dynamic schedules of the non-manifest data dependant loops within the DSP-algorithm are possible. We show how to construct hardware which dynamically schedules these non-manifest loops. The sliding window execution, which is the execution of a non-manifest loop when the data streams through it, of the constructed hardware will guarantee real time performance for the worst case situation. This is the situation when each non-manifest loop requires its maximum number of iterations.

KW - EWI-957

KW - periodic loops

KW - Non-manifest loop scheduling

KW - dynamic hardware scheduling

KW - IR-36875

KW - METIS-203304

M3 - Conference contribution

SN - 90-73461-26-X

SP - 153

EP - 160

BT - 2nd PROGRESS workshop on Embedded Systems

A2 - Karelse, F.

PB - STW

CY - Utrecht, The Netherlands

ER -

Mansour O, Etalle S, Krol T. Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. In Karelse F, editor, 2nd PROGRESS workshop on Embedded Systems. Utrecht, The Netherlands: STW. 2001. p. 153-160