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

383 Downloads (Orbit)

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	2009 IEEE 27th NORCHIP Conference - Trondheim, Norway Duration: 16 Nov 2009 → 17 Nov 2009 Conference number: 27 https://ieeexplore.ieee.org/xpl/conhome/5374435/proceeding

Conference

Conference	2009 IEEE 27th NORCHIP Conference
Number	27
Country/Territory	Norway
City	Trondheim
Period	16/11/2009 → 17/11/2009
Internet address	https://ieeexplore.ieee.org/xpl/conhome/5374435/proceeding

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

OpenUrl availability

Full text

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.; 2009 IEEE 27th NORCHIP Conference ; Conference date: 16-11-2009 Through 17-11-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",

url = "https://ieeexplore.ieee.org/xpl/conhome/5374435/proceeding",

}

TY - GEN

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

AU - Stuart, Matthias Bo

AU - Sparsø, Jens

N1 - Conference code: 27

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 - 2009 IEEE 27th NORCHIP Conference

Y2 - 16 November 2009 through 17 November 2009

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this