Analytical Derivation of Traffic Patterns in Shared Memory Architectures from Task Graphs

Matthias Bo Stuart; Jens Sparsø

doi:10.1109/NORCHP.2009.5397825

Analytical Derivation of Traffic Patterns in Shared Memory Architectures from Task Graphs

Matthias Bo Stuart, Jens Sparsø

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

308 Downloads (Pure)

Abstract

Task Graphs is a commonly used application model in research in computer-aided design tools for design space exploration of embedded systems, including system synthesis, scheduling and application mapping. These design tools need an estimate of the actual communication in the target system caused by the application modelled by the task graph. In this paper, we present a method for analytically deriving the worst-case traffic pattern when a task graph is mapped to a multiprocessor system-on-chip with a shared memory architecture. We describe the additionally needed information besides the dependencies in the task graph in order to derive the traffic pattern. Finally, we construct a simulator that we use to find the actual traffic pattern in a system and compare this to the derived pattern. Results show that our worst-case derivation overestimates the bandwidth by 9% for systems with small caches and between 32% and 52% for systems with large caches.

Original language	English
Title of host publication	NORCHIP, 2009
Publisher	IEEE
Publication date	2009
Pages	1-4
ISBN (Print)	978-1-4244-4310-9
ISBN (Electronic)	978-1-4244-4311-6
DOIs	https://doi.org/10.1109/NORCHP.2009.5397825
Publication status	Published - 2009
Event	NORCHIP, 2009 - Duration: 1 Jan 2009 → …

Conference

Conference	NORCHIP, 2009
Period	01/01/2009 → …

Bibliographical note

Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Access to Document

10.1109/NORCHP.2009.5397825

StuartFinal published version, 86.5 KB

Cite this

@inproceedings{1d5d7040bd7c4fd8a8c5d4f1a923d918,

title = "Analytical Derivation of Traffic Patterns in Shared Memory Architectures from Task Graphs",

abstract = "Task Graphs is a commonly used application model in research in computer-aided design tools for design space exploration of embedded systems, including system synthesis, scheduling and application mapping. These design tools need an estimate of the actual communication in the target system caused by the application modelled by the task graph. In this paper, we present a method for analytically deriving the worst-case traffic pattern when a task graph is mapped to a multiprocessor system-on-chip with a shared memory architecture. We describe the additionally needed information besides the dependencies in the task graph in order to derive the traffic pattern. Finally, we construct a simulator that we use to find the actual traffic pattern in a system and compare this to the derived pattern. Results show that our worst-case derivation overestimates the bandwidth by 9% for systems with small caches and between 32% and 52% for systems with large caches.",

author = "Stuart, {Matthias Bo} and Jens Spars{\o}",

note = "Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.; NORCHIP, 2009 ; Conference date: 01-01-2009",

year = "2009",

doi = "10.1109/NORCHP.2009.5397825",

language = "English",

isbn = "978-1-4244-4310-9",

pages = "1--4",

booktitle = "NORCHIP, 2009",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - Analytical Derivation of Traffic Patterns in Shared Memory Architectures from Task Graphs

AU - Stuart, Matthias Bo

AU - Sparsø, Jens

N1 - Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

PY - 2009

Y1 - 2009

N2 - Task Graphs is a commonly used application model in research in computer-aided design tools for design space exploration of embedded systems, including system synthesis, scheduling and application mapping. These design tools need an estimate of the actual communication in the target system caused by the application modelled by the task graph. In this paper, we present a method for analytically deriving the worst-case traffic pattern when a task graph is mapped to a multiprocessor system-on-chip with a shared memory architecture. We describe the additionally needed information besides the dependencies in the task graph in order to derive the traffic pattern. Finally, we construct a simulator that we use to find the actual traffic pattern in a system and compare this to the derived pattern. Results show that our worst-case derivation overestimates the bandwidth by 9% for systems with small caches and between 32% and 52% for systems with large caches.

AB - Task Graphs is a commonly used application model in research in computer-aided design tools for design space exploration of embedded systems, including system synthesis, scheduling and application mapping. These design tools need an estimate of the actual communication in the target system caused by the application modelled by the task graph. In this paper, we present a method for analytically deriving the worst-case traffic pattern when a task graph is mapped to a multiprocessor system-on-chip with a shared memory architecture. We describe the additionally needed information besides the dependencies in the task graph in order to derive the traffic pattern. Finally, we construct a simulator that we use to find the actual traffic pattern in a system and compare this to the derived pattern. Results show that our worst-case derivation overestimates the bandwidth by 9% for systems with small caches and between 32% and 52% for systems with large caches.

U2 - 10.1109/NORCHP.2009.5397825

DO - 10.1109/NORCHP.2009.5397825

M3 - Article in proceedings

SN - 978-1-4244-4310-9

SP - 1

EP - 4

BT - NORCHIP, 2009

PB - IEEE

T2 - NORCHIP, 2009

Y2 - 1 January 2009

ER -

Analytical Derivation of Traffic Patterns in Shared Memory Architectures from Task Graphs

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this