TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip

Tutkimustuotos

Standard

Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip. / Orsila, Heikki.

Tampere University of Technology, 2011. 199 s. (Tampere University of Technology. Publication; Vuosikerta 972).

Tutkimustuotos

Harvard

Orsila, H 2011, Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip. Tampere University of Technology. Publication, Vuosikerta. 972, Tampere University of Technology.

APA

Orsila, H. (2011). Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip. (Tampere University of Technology. Publication; Vuosikerta 972). Tampere University of Technology.

Vancouver

Orsila H. Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip. Tampere University of Technology, 2011. 199 s. (Tampere University of Technology. Publication).

Author

Orsila, Heikki. / Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip. Tampere University of Technology, 2011. 199 Sivumäärä (Tampere University of Technology. Publication).

Bibtex - Lataa

@book{d8aecc8ec52b4e2a99d8d63e07671460,
title = "Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip",
abstract = "The objective of this Thesis is to analyze and improve MPSoC design space exploration, specifically the task mapping using Simulated Annealing (SA) with fully automatic optimization. The work concentrates mostly on application execution time optimization. However, a trade-off between memory buffer and time optimization and a trade-off between power and time optimization is also analyzed. Applications are represented as public Standard Task Graph sets and Kahn Process Networks (KPNs). Main focus is on SA as the optimization algorithm for task mapping. A state of the art survey is presented on using SA for task mapping. Thesis analyzes the impact of SA parameters on convergence. A systematic method is presented for automatically selecting parameters. The method scales up with respect to increasing HW and SW complexity. It is called Simulated Annealing with Automatic Temperature (SA+AT). Optimal subset mapping (OSM) algorithm is presented as a rapidly converging task mapping algorithm. SA+AT is compared with OSM, Group Migration, Random Mapping and a Genetic Algorithm. SA+AT gives the best results. OSM is the most efficient algorithm. Thesis presents new data on the convergence of annealing. Answers are given to global optimum convergence properties and the convergence speed in terms of mapping iterations. This covers optimization of the run-time of mapping algorithms so that a trade-off can be made between solution quality and algorithm's execution time. SA+AT saves up to half the optimization time without significantly decreasing solution quality. Recommendations are presented for using SA in task mapping. The work is intended to help other works to use SA. DCS task mapper, an open source simulator and optimization program, is presented and published to help development and evaluation of mapping algorithms. The data to reproduce Thesis experiments with the program is also published.",
author = "Heikki Orsila",
note = "Awarding institution:Tampere University of Technology<br/>Submitter:Submitted by Heikki Orsila (heikki.orsila@tut.fi) on 2011-05-11T20:37:07Z No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)<br/>Submitter:Approved for entry into archive by Kaisa Kulkki(kaisa.kulkki@tut.fi) on 2011-05-13T11:43:58Z (GMT) No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)<br/>Submitter:Made available in DSpace on 2011-05-13T11:43:58Z (GMT). No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)",
year = "2011",
month = "6",
day = "17",
language = "English",
isbn = "978-952-15-2585-8",
series = "Tampere University of Technology. Publication",
publisher = "Tampere University of Technology",

}

RIS (suitable for import to EndNote) - Lataa

TY - BOOK

T1 - Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip

AU - Orsila, Heikki

N1 - Awarding institution:Tampere University of Technology<br/>Submitter:Submitted by Heikki Orsila (heikki.orsila@tut.fi) on 2011-05-11T20:37:07Z No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)<br/>Submitter:Approved for entry into archive by Kaisa Kulkki(kaisa.kulkki@tut.fi) on 2011-05-13T11:43:58Z (GMT) No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)<br/>Submitter:Made available in DSpace on 2011-05-13T11:43:58Z (GMT). No. of bitstreams: 1 thesis-without-cover-2011-05-10.pdf: 6018965 bytes, checksum: 2fde471ec8ab26a7008a209bcd893e8c (MD5)

PY - 2011/6/17

Y1 - 2011/6/17

N2 - The objective of this Thesis is to analyze and improve MPSoC design space exploration, specifically the task mapping using Simulated Annealing (SA) with fully automatic optimization. The work concentrates mostly on application execution time optimization. However, a trade-off between memory buffer and time optimization and a trade-off between power and time optimization is also analyzed. Applications are represented as public Standard Task Graph sets and Kahn Process Networks (KPNs). Main focus is on SA as the optimization algorithm for task mapping. A state of the art survey is presented on using SA for task mapping. Thesis analyzes the impact of SA parameters on convergence. A systematic method is presented for automatically selecting parameters. The method scales up with respect to increasing HW and SW complexity. It is called Simulated Annealing with Automatic Temperature (SA+AT). Optimal subset mapping (OSM) algorithm is presented as a rapidly converging task mapping algorithm. SA+AT is compared with OSM, Group Migration, Random Mapping and a Genetic Algorithm. SA+AT gives the best results. OSM is the most efficient algorithm. Thesis presents new data on the convergence of annealing. Answers are given to global optimum convergence properties and the convergence speed in terms of mapping iterations. This covers optimization of the run-time of mapping algorithms so that a trade-off can be made between solution quality and algorithm's execution time. SA+AT saves up to half the optimization time without significantly decreasing solution quality. Recommendations are presented for using SA in task mapping. The work is intended to help other works to use SA. DCS task mapper, an open source simulator and optimization program, is presented and published to help development and evaluation of mapping algorithms. The data to reproduce Thesis experiments with the program is also published.

AB - The objective of this Thesis is to analyze and improve MPSoC design space exploration, specifically the task mapping using Simulated Annealing (SA) with fully automatic optimization. The work concentrates mostly on application execution time optimization. However, a trade-off between memory buffer and time optimization and a trade-off between power and time optimization is also analyzed. Applications are represented as public Standard Task Graph sets and Kahn Process Networks (KPNs). Main focus is on SA as the optimization algorithm for task mapping. A state of the art survey is presented on using SA for task mapping. Thesis analyzes the impact of SA parameters on convergence. A systematic method is presented for automatically selecting parameters. The method scales up with respect to increasing HW and SW complexity. It is called Simulated Annealing with Automatic Temperature (SA+AT). Optimal subset mapping (OSM) algorithm is presented as a rapidly converging task mapping algorithm. SA+AT is compared with OSM, Group Migration, Random Mapping and a Genetic Algorithm. SA+AT gives the best results. OSM is the most efficient algorithm. Thesis presents new data on the convergence of annealing. Answers are given to global optimum convergence properties and the convergence speed in terms of mapping iterations. This covers optimization of the run-time of mapping algorithms so that a trade-off can be made between solution quality and algorithm's execution time. SA+AT saves up to half the optimization time without significantly decreasing solution quality. Recommendations are presented for using SA in task mapping. The work is intended to help other works to use SA. DCS task mapper, an open source simulator and optimization program, is presented and published to help development and evaluation of mapping algorithms. The data to reproduce Thesis experiments with the program is also published.

M3 - Doctoral thesis

SN - 978-952-15-2585-8

T3 - Tampere University of Technology. Publication

BT - Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip

PB - Tampere University of Technology

ER -