Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Analysis of task scheduling for multi-core embedded systems
KTH, School of Industrial Engineering and Management (ITM), Machine Design (Dept.).
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Analys av schemaläggning för multikärniga inbyggda system (Swedish)
Abstract [en]

This thesis performs a research on scheduling algorithms for parallel applications.The main focus is their usage on multi-core embedded systems’ applications.A parallel application can be described by a directed acyclic graph.A directed acyclic graph is a mathematical model that represents the parallelapplication as a set of nodes or tasks and a set of edges or communicationmessages between nodes.In this thesis scheduling is limited to the management of multiple coreson a multi-core platform for the execution of application tasks. Tasks aremapped onto the cores and their start times are determined afterwards. Atoolchain is implemented to develop and schedule parallel applications on aEpiphany E16 developing board, which is a low-cost board with a 16 core chipcalled Epiphany. The toolchain is limited to the usage of offline schedulingalgorithms which compute a schedule before running the application.The programmer has to draw a directed acyclic graph with the main attributesof the application. The toolchain then generates the code for the targetwhich automatically handles the inter-task communication. Some metrics areestablished to help evaluate the performance of applications on the target platform,such as the execution time and the energy consumption. Measurementson the Epiphany E16 developing board are performed to estimate the energyconsumption of the multi-core chip as a function of the number of idle cores.A set of 12 directed acyclic graphs are used to verify that the toolchainworks correctly. They cover different aspects: join nodes, fork nodes, morethan one entry node, more than one exit node, different tasks weights anddifferent communication costs.A use case is given, the development of a brake-by-wire demonstrationplatform. The platform aims to use the Epiphany board. Three experimentsare performed to analyze the performance of parallel computing for the usecase. Three brake-by-wire applications are implemented, one for a single coresystem and two for a multi-core system. The parallel application scheduledwith a list-based algorithm requires 266% more time and 1346% more energythan the serial application. The parallel application scheduled with a taskduplication algorithm requires 46% less time and 134% more energy than theserial application.The toolchain system has proven to be a useful tool for developing parallelapplications since it automatically handles the inter-task communication.However, future work can be done to automatize the decomposition of serialapplications from the source code. The conclusion is that this communicationsystem is suitable for coarse granularity, where the communication overheaddoes not affect so much. Task duplication is better to use for fine granularitysince inter-core communication is avoided by doing extra computations.

Abstract [sv]

Detta examensarbete utför en studie av om schemaläggningsalgoritmer förparallella applikationer. Huvudfokus är deras användning för flerkärniga inbyggdasystemapplikationer. En parallell applikation kan beskrivas genom enriktad acyklisk graf. En riktad acyklisk graf är en matematisk modell somrepresenterar den parallella applikationen som en uppsättning av noder, elleruppgifter, och en uppsättning av pilar, eller meddelanden, mellan noder.I denna uppsats är schemaläggning begränsad till hanteringen av flerakärnor på en multikärnig plattform för genomförandet av applikationens uppgifter.Uppgifter mappas på kärnorna och deras starttider bestäms efteråt. Enspeciell verktygskedja kallad ett ”toolchain system” har tagits fram för attutveckla och schemalägga parallella applikationer på ett Epiphany E16 kort,vilket är ett billigt kort med ett 16-kärnigt chip som kallas Epiphany. Toolchainsystemet är begränsat till användningen av offline schemaläggningsalgoritmersom beräknar ett schema innan du kör programmet.Programmeraren måste rita en riktad acyklisk graf med de viktigaste attributen.Toolchain systemet genererar därefter kod som automatiskt hanterarkommunikationen mellan uppgifterna. Ett antal prestandamått defineras föratt kunna utvärdera applikationer på målplattformen, såsom genomförandetidoch energiförbrukning. Mätningar på Epiphany E16 kortet genomförs för attuppskatta energiförbrukningen som en funktion av antalet lediga kärnor.En uppsättning av 12 riktade acykliska grafer används för att kontrolleraatt toolchain systemet fungerar korrekt. De täcker olika aspekter: noder somgår ihop, noder som går isär, fler än en ingångsnod, fler än en utgångsnod,olika vikter på uppgifterna och olika kommunikationskostnader.Ett användningsfall ges, utveckling av en brake-by-wire demonstrationsplattform. Plattformen syftar till att använda Epiphany kortet. Tre experimentutförs för att analysera resultatet av parallella beräkningar för användningsfallet.Tre brake-by-wire applikationer genomförs, en för ett enda kärnsystemoch två för ett multikärnigt system. Den parallella applikationen somvar schemalagd med en algoritm baserad på listor kräver 266% mer tid och1346% mer energi än den seriella applikationen. Den parallella applikationensom var schemalagd med en uppgiftsduplicerings-algoritm kräver 46% mindretid och 134% mer energi än den seriella applikationen.Toolchain systemet har visat sig att vara ett användbart verktyg för attutveckla parallella applikationer eftersom det automatiskt hanterar kommunikationmellan uppgifter. Däremot kan framtida arbete göras för att automatiseranedbrytningen av seriella program från källkod. Slutsatsen är att dettakommunikationssystem är lämpligt för grovkorning parallellism, där kommunikationskostnadeninte påverkar lika mycket. Uppgiftsdupliceringen är bättreatt använda för finkorning parallellism eftersom kommunikation mellan kärnorundviks genom att göra extra beräkningar.

Place, publisher, year, edition, pages
2013. , p. 118
Series
MMK 2013:49 MDA 462
National Category
Mechanical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-202548OAI: oai:DiVA.org:kth-202548DiVA, id: diva2:1077324
Supervisors
Examiners
Available from: 2017-02-27 Created: 2017-02-27 Last updated: 2017-02-27Bibliographically approved

Open Access in DiVA

fulltext(6713 kB)24 downloads
File information
File name FULLTEXT01.pdfFile size 6713 kBChecksum SHA-512
736691762e7bdfa40198a597e8e8f88a71af569fdfa122997a415952cd2b185861190db933baaad97da7e994b8ac2cecec7cee5c891f4ef3fbbc67d1aef49c4b
Type fulltextMimetype application/pdf

By organisation
Machine Design (Dept.)
Mechanical Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 24 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 178 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.34-SNAPSHOT
|