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-coreembedded systems
KTH, School of Industrial Engineering and Management (ITM), Machine Design (Dept.).
2017 (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 parallel application as a set of nodes or tasks and a set of edges or communication messages between nodes.

In this thesis scheduling is limited to the management of multiple cores on a multi-core platform for the execution of application tasks. Tasks are mapped onto the cores and their start times are determined afterwards. A toolchain is implemented to develop and schedule parallel applications on a Epiphany E16 developing board, which is a low-cost board with a 16 core chip called Epiphany. The toolchain is limited to the usage of offline scheduling algorithms which compute a schedule before running the application.

The programmer has to draw a directed acyclic graph with the main attributes of the application. The toolchain then generates the code for the target which automatically handles the inter-task communication. Some metrics are established to help evaluate the performance of applications on the target platform, such as the execution time and the energy consumption. Measurements on the Epiphany E16 developing board are performed to estimate the energy consumption 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 toolchain works correctly. They cover different aspects: join nodes, fork nodes, more than one entry node, more than one exit node, different tasks weights and different communication costs.

A use case is given, the development of a brake-by-wire demonstration platform. The platform aims to use the Epiphany board. Three experiments are performed to analyze the performance of parallel computing for the use case. Three brake-by-wire applications are implemented, one for a single core system and two for a multi-core system. The parallel application scheduled with a list-based algorithm requires 266% more time and 1346% more energy than the serial application. The parallel application scheduled with a task duplication algorithm requires 46% less time and 134% more energy than the serial application.

The toolchain system has proven to be a useful tool for developing parallel applications since it automatically handles the inter-task communication. However, future work can be done to automatize the decomposition of serial applications from the source code. The conclusion is that this communication system is suitable for coarse granularity, where the communication overhead does not affect so much. Task duplication is better to use for fine granularity since inter-core communication is avoided by doing extra computations.

Abstract [sv]

Detta examensarbete utför en studie av om schemaläggningsalgoritmer för parallella applikationer. Huvudfokus är deras användning för flerkärniga inbyggda systemapplikationer. En parallell applikation kan beskrivas genom en riktad acyklisk graf. En riktad acyklisk graf är en matematisk modell som representerar den parallella applikationen som en uppsättning av noder, eller uppgifter, och en uppsättning av pilar, eller meddelanden, mellan noder.

I denna uppsats är schemaläggning begränsad till hanteringen av flera kä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. En speciell verktygskedja kallad ett ”toolchain system” har tagits fram för att utveckla och schemalägga parallella applikationer på ett Epiphany E16 kort, vilket är ett billigt kort med ett 16-kärnigt chip som kallas Epiphany. Toolchain systemet är begränsat till användningen av offline schemaläggningsalgoritmer som 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 hanterar kommunikationen mellan uppgifterna. Ett antal prestandamått defineras för att kunna utvärdera applikationer på målplattformen, såsom genomförandetid och energiförbrukning. Mätningar på Epiphany E16 kortet genomförs för att uppskatta energiförbrukningen som en funktion av antalet lediga kärnor.

En uppsättning av 12 riktade acykliska grafer används för att kontrollera att toolchain systemet fungerar korrekt. De täcker olika aspekter: noder som gå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 demonstrations plattform. Plattformen syftar till att använda Epiphany kortet. Tre experiment utfö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ärnsystem och två för ett multikärnigt system. Den parallella applikationen som var schemalagd med en algoritm baserad på listor kräver 266% mer tid och 1346% mer energi än den seriella applikationen. Den parallella applikationen som var schemalagd med en uppgiftsduplicerings-algoritm kräver 46% mindre tid och 134% mer energi än den seriella applikationen.

Toolchain systemet har visat sig att vara ett användbart verktyg för att utveckla parallella applikationer eftersom det automatiskt hanterar kommunikation mellan uppgifter. Däremot kan framtida arbete göras för att automatisera nedbrytningen av seriella program från källkod. Slutsatsen är att detta kommunikationssystem är lämpligt för grovkorning parallellism, där kommunikationskostnaden inte påverkar lika mycket. Uppgiftsdupliceringen är bättre att använda för finkorning parallellism eftersom kommunikation mellan kärnor undviks genom att göra extra beräkningar.

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

Open Access in DiVA

fulltext(6713 kB)54 downloads
File information
File name FULLTEXT01.pdfFile size 6713 kBChecksum SHA-512
2c8fa7256b827431f2ddd6af624353a71a23f46f914453882da8b9bc834ade21b301364a3bedf2e8e87ca9550b69b50f07ac4d30ffdae2de8a9b74851124233f
Type fulltextMimetype application/pdf

By organisation
Machine Design (Dept.)
Mechanical Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 54 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: 77 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