Communication aware multiprocessor binding for shared memory systems

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Downloads (Pure)

Abstract

We present a three-step binding algorithm for applications in the form of directed acyclic graphs (DAGs) of tasks with deadlines, that need to be bound to a shared memory multiprocessor platform. The aim of the algorithm is to obtain a good binding that results in low makespans of the schedules of the DAGs. It first clusters tasks assuming unlimited resources using a deadline-aware shared memory extension of the existing dominant sequence clustering algorithm. Second, the clusters produced are merged based on communication dependencies to fit into the number of available platform resources. As a final step, the clusters are allocated to the available resources by balancing the workload. The approach is compared to the state of the art bounded dominant sequence clustering (BDSC) algorithm that also performs clustering on a limited number of resources. We show that our three-step algorithm makes better use of the shared memory communication structure and produces significantly lower makespans than BDSC on benchmark cases.
Original languageEnglish
Title of host publication11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages1-10
Number of pages10
ISBN (Electronic)978-1-5090-2282-3
DOIs
Publication statusPublished - 2016
Event11th IEEE International Symposium on Industrial Embedded Systems (SIES 2016), May 23-25, 2016, Krakow, Poland - Krakow, Poland
Duration: 23 May 201625 May 2016
http://sies2016.org/

Conference

Conference11th IEEE International Symposium on Industrial Embedded Systems (SIES 2016), May 23-25, 2016, Krakow, Poland
Abbreviated titleSIES 2016
CountryPoland
CityKrakow
Period23/05/1625/05/16
Internet address

Fingerprint

Data storage equipment
Clustering algorithms
Communication

Cite this

Adyanthaya, S., Geilen, M. C. W., Basten, T., Voeten, J. P. M., & Schiffelers, R. R. H. (2016). Communication aware multiprocessor binding for shared memory systems. In 11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016 (pp. 1-10). Piscataway: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/SIES.2016.7509438
Adyanthaya, S. ; Geilen, M.C.W. ; Basten, T. ; Voeten, J.P.M. ; Schiffelers, R.R.H. / Communication aware multiprocessor binding for shared memory systems. 11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016. Piscataway : Institute of Electrical and Electronics Engineers, 2016. pp. 1-10
@inproceedings{5838a98c4408442f9340921ccf7bb06c,
title = "Communication aware multiprocessor binding for shared memory systems",
abstract = "We present a three-step binding algorithm for applications in the form of directed acyclic graphs (DAGs) of tasks with deadlines, that need to be bound to a shared memory multiprocessor platform. The aim of the algorithm is to obtain a good binding that results in low makespans of the schedules of the DAGs. It first clusters tasks assuming unlimited resources using a deadline-aware shared memory extension of the existing dominant sequence clustering algorithm. Second, the clusters produced are merged based on communication dependencies to fit into the number of available platform resources. As a final step, the clusters are allocated to the available resources by balancing the workload. The approach is compared to the state of the art bounded dominant sequence clustering (BDSC) algorithm that also performs clustering on a limited number of resources. We show that our three-step algorithm makes better use of the shared memory communication structure and produces significantly lower makespans than BDSC on benchmark cases.",
author = "S. Adyanthaya and M.C.W. Geilen and T. Basten and J.P.M. Voeten and R.R.H. Schiffelers",
year = "2016",
doi = "10.1109/SIES.2016.7509438",
language = "English",
pages = "1--10",
booktitle = "11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016",
publisher = "Institute of Electrical and Electronics Engineers",
address = "United States",

}

Adyanthaya, S, Geilen, MCW, Basten, T, Voeten, JPM & Schiffelers, RRH 2016, Communication aware multiprocessor binding for shared memory systems. in 11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016. Institute of Electrical and Electronics Engineers, Piscataway, pp. 1-10, 11th IEEE International Symposium on Industrial Embedded Systems (SIES 2016), May 23-25, 2016, Krakow, Poland, Krakow, Poland, 23/05/16. https://doi.org/10.1109/SIES.2016.7509438

Communication aware multiprocessor binding for shared memory systems. / Adyanthaya, S.; Geilen, M.C.W.; Basten, T.; Voeten, J.P.M.; Schiffelers, R.R.H.

11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016. Piscataway : Institute of Electrical and Electronics Engineers, 2016. p. 1-10.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Communication aware multiprocessor binding for shared memory systems

AU - Adyanthaya, S.

AU - Geilen, M.C.W.

AU - Basten, T.

AU - Voeten, J.P.M.

AU - Schiffelers, R.R.H.

PY - 2016

Y1 - 2016

N2 - We present a three-step binding algorithm for applications in the form of directed acyclic graphs (DAGs) of tasks with deadlines, that need to be bound to a shared memory multiprocessor platform. The aim of the algorithm is to obtain a good binding that results in low makespans of the schedules of the DAGs. It first clusters tasks assuming unlimited resources using a deadline-aware shared memory extension of the existing dominant sequence clustering algorithm. Second, the clusters produced are merged based on communication dependencies to fit into the number of available platform resources. As a final step, the clusters are allocated to the available resources by balancing the workload. The approach is compared to the state of the art bounded dominant sequence clustering (BDSC) algorithm that also performs clustering on a limited number of resources. We show that our three-step algorithm makes better use of the shared memory communication structure and produces significantly lower makespans than BDSC on benchmark cases.

AB - We present a three-step binding algorithm for applications in the form of directed acyclic graphs (DAGs) of tasks with deadlines, that need to be bound to a shared memory multiprocessor platform. The aim of the algorithm is to obtain a good binding that results in low makespans of the schedules of the DAGs. It first clusters tasks assuming unlimited resources using a deadline-aware shared memory extension of the existing dominant sequence clustering algorithm. Second, the clusters produced are merged based on communication dependencies to fit into the number of available platform resources. As a final step, the clusters are allocated to the available resources by balancing the workload. The approach is compared to the state of the art bounded dominant sequence clustering (BDSC) algorithm that also performs clustering on a limited number of resources. We show that our three-step algorithm makes better use of the shared memory communication structure and produces significantly lower makespans than BDSC on benchmark cases.

U2 - 10.1109/SIES.2016.7509438

DO - 10.1109/SIES.2016.7509438

M3 - Conference contribution

SP - 1

EP - 10

BT - 11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

ER -

Adyanthaya S, Geilen MCW, Basten T, Voeten JPM, Schiffelers RRH. Communication aware multiprocessor binding for shared memory systems. In 11th IEEE International Symposium on Industrial Embedded Systems (SIES), Krakow, Poland, 23-25 May 2016. Piscataway: Institute of Electrical and Electronics Engineers. 2016. p. 1-10 https://doi.org/10.1109/SIES.2016.7509438