Scalable Multicore Computing Using Dataflow and Task‐based Models
Georgakarakos, Georgios (2021-11-26)
Åbo Akademi University
26.11.2021
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Julkaisun pysyvä osoite on
https://urn.fi/URN:ISBN:978‐952‐12‐4115‐4
https://urn.fi/URN:ISBN:978‐952‐12‐4115‐4
Tiivistelmä
Most of modern digital electronic devices and systems rely nowadays on multicore processors, in order to deliver a growing list of added‐value features and services. In this way multicore architectures have been able to optimise the performance per watt ratio i.e. the application through‐ put with respect to its power consumption. However this new evolution in hardware architecture has created unprecedented challenges for software engineering. Traditional software models were not designed to optimally utilise the parallelism that applications potentially include. Therefore, the foundation of new software methodologies has been essential in order to increase application performance by exploiting parallel execution on multicore environment. This should result in increased application runtime speed‐up when processing resources (cores) increase. In this thesis we use the notion of scalability to describe how well an application can perform by exploiting a progressively greater number of cores.
Efficiently executing applications in multicore environment requires addressing the challenges of multicore scheduling. In order to obtain schedules with acceptable quality, hardware platform details are typically utilised. There is a motivation to design applications that scale, with minimum or no assumptions on underlying platforms. This would mean that upgrading the underlying hardware of a device with more cores would result in analogous ,ideally linear, application performance upgrade. This would also enable to seamlessly move applications to the Cloud, where the processing resources including the number of cores can be dynamically allocated. The availability of scalable software methodologies is thus impacting significantly the actual cost and quality of digital services.
This thesis’ scope is to contribute to the scalability of signal processing applications executed in multicore environment. The main goal is to provide methodologies and tools to leverage model‐based design and particularly to efficiently utilize the dataflow model towards the availability of scalable high performance application software. The concept of model‐based design is to decouple algorithm description from actual implementation in a hardware platform. The dataflow model algorithm description is based on the flow of data through its operations which are expressed as actors connected in a graph. Dataflow models can easily expose the potential parallelism of an algorithm and thus be an efficient methodology to analyse signal processing algorithms. However transforming dataflow models in executable code for multicore execution is challenging. This is due to the semantics ’gap’ between dataϐlow and traditional imperative programming languages. This thesis explores and proposes methodologies for leveraging dataflow based application design towards scalable application software development. In this way, popular signal processing algorithms that are efficiently modelled with dataflow graphs, could be also executed efficiently in multicore architectures.
In order to analyse how dataflow representations can be executed efficiently, this thesis gives insights regarding how well the traditional thread programming model can scale in order to support efficient parallel execution of signal processing algorithms such as image/video compression. Then a hypothesis is made that task programming models can scale better and overcome the scalability burdens of the thread model. This is justified by experimental results and related analysis.
Another claim of this thesis is that task programming models’ attributes correlate more accurately with the semantics of dataflow model of computation. Therefore, a methodology that combines synchronous dataflow and task programming models in order to enable scalable application execution is proposed. A task‐based code generator is developed and tested within a synchronous dataflow‐based application development framework. Furthermore, to optimise the dataflow to task‐based code transformation and extend its applicability in multicore platforms, a set of optimisation techniques are developed. As a result, the code generator can be used to scale the performance of applications with fine grain level of parallelism, independently from the number of cores. The generated code can also be utilised in both symmetric and asymmetric multicore environments. A set of experiments are performed that verify the proof of concept and the efficiency of the code generation process. The speed‐up and throughput of the task‐based code execution is evaluated against the equivalent thread‐based code execution for the same set of applications described as synchronous dataflow graphs. ----------
De flesta moderna digitala elektroniska enheter och system förut‐ sätter numera flerkärniga processorer för att kunna uppfylla de allt hårdare kraven på funktioner och tjänster med mervärde. Därmed har flerkärniga arkitekturer kunnat optimera förhållandet prestanda per watt, dvs. applikationsgenomströmning i relation till dess effektbehov. Denna utveckling inom maskinvaruarkitektur har skapat nya utmaningar för programvarutekniken. Traditionella programvarumodeller är inte utformade för att optimalt utnyttja den potential för parallellitet som kan finnas i tillämpningar. Därför har det varit avgörande att skapa nya pro‐ gramvarumetoder som ökar applikationsprestandan genom att utnyttja parallell exekvering i flerkärniga miljöer. Detta bör resultera i snabbare exekvering av tillämpningar när processresurserna (antalet kärnor) ökas. I denna avhandling använder vi begreppet skalbarhet för att beskriva hur väl en tillämpning kan prestera genom att utnyttja ett successivt större antal kärnor.
För att effektivt exekvera tillämpningar i en flerkärnig miljö måste man itu med utmaningarna med schemaläggning av flera kärnor. För att skapa scheman med acceptabel kvalitet utnyttjas vanligtvis detaljer i maskinvaruplattformen. Det finns ett incitament att skapa skalbara tillämpningar som i liten eller ingen grad förlitar sig på underliggande plattformar. Detta skulle innebära att uppgradering av den underliggande hårdvaran i en flerkärnig enhet skulle resultera i en analog, idealt linjär, uppgradering av dess tillämpningsprestanda. Detta skulle också göra det möjligt att sömlöst flytta tillämpningar till molnet, där exekveringsresurserna, inklusive antalet kärnor, kan allokeras dynamiskt. Tillgången till skalbara programvarumetoder påverkar därmed avsevärt de digitala tjänsternas faktiska kostnader och kvalitet.
Denna avhandling är avsedd att bidra till skalbarhet hos signalbehandlingstillämpningar som exekveras i en flerkärnig miljö. Det huvudsakliga målet är att tillhandahålla metoder och verktyg för att utnyttja modell‐ baserad design och särskilt att effektivt utnyttja dataflödesmodellen i syfte att tillgängliggöra skalbar högpresterande tillämpningsprogram‐ vara. Konceptet modellbaserad konstruktion handlar om att frikoppla algoritmbeskrivningen från själva implementeringen på en maskinvaru‐ plattform. Algoritmbeskrivningen för dataflödesmodellen baseras på dataflödet genom dess operationer, vilka uttrycks som aktörer som är sammankopplade i ett diagram. Dataflödesmodeller kan lätt exponera en algoritms potentiella parallellitet och är därmed en effektiv metod för att analysera signalbehandlingsalgoritmer. Att omvandla dataflödesmodeller till körbar kod för exekvering i en flerkärnig miljö är dock en utmaning. Detta beror på den semantiska ”klyftan” mellan dataflödet och traditionella tvingande programmeringsspråk. Denna avhandling utforskar och föres‐ lår metoder för att utnyttja dataflödesbaserad tillämpningskonstruktion med inriktning på utveckling av skalbar tillämpningsprogramvara. På så sätt skulle även populära signalbehandlingsalgoritmer som är resurssnålt modellerade med dataflödesgrafer kunna exekveras effektivt i flerkärniga arkitekturer.
För att analysera hur dataflödesrepresentationer kan exekveras effektivt ger denna avhandling insikter om hur väl den traditionella trådprogrammeringsmodellen kan skalas för att stödja effektiv parallell exekvering av signalbehandlingsalgoritmer – som bild‐/videokomprimering. Avhandlingen framlägger en hypotes om att uppgiftsprogrammeringsmodeller kan skala bättre och övervinna trådmodellens problem med skalbarhet. Detta underbyggs av experimentella resultat och relaterad analys.
I avhandlingen hävdas vidare att uppgiftsprogrammeringsmodellernas attribut korrelerar mer exakt med semantiken i dataflödesmodellen för databehandling. Därför föreslås en metod som kombinerar synkrona dataflödes‐ och uppgiftsprogrammeringsmodeller för att möjliggöra skalbar tillämpningsexekvering. En uppgiftsbaserad kodgenerator utvecklas och testas inom ett synkront dataflödesbaserat ramverk för tillämpningsutveckling. För att optimera dataflödet till uppgiftsbaserad kodtransformering och utöka dess tillämpbarhet på flerkärniga plattformar utvecklas dessutom en uppsättning optimeringstekniker. Som ett resultat kan kodgeneratorn användas för att skala prestanda för tillämpningar med detaljerad grad av parallellitet, oberoende av antalet kärnor. Den genererade koden kan också användas i både symmetriska och asymmetriska flerkärniga miljöer. En uppsättning experiment utförs som verifierar konceptet och effektiviteten hos kodgenereringsprocessen. Snabbheten och genomströmningen hos den uppgiftsbaserade kodex‐ ekveringen utvärderas mot motsvarande trådbaserade kodexekvering för samma uppsättning tillämpningar, vilka beskrivs som synkrona dataflödesgrafer.
Efficiently executing applications in multicore environment requires addressing the challenges of multicore scheduling. In order to obtain schedules with acceptable quality, hardware platform details are typically utilised. There is a motivation to design applications that scale, with minimum or no assumptions on underlying platforms. This would mean that upgrading the underlying hardware of a device with more cores would result in analogous ,ideally linear, application performance upgrade. This would also enable to seamlessly move applications to the Cloud, where the processing resources including the number of cores can be dynamically allocated. The availability of scalable software methodologies is thus impacting significantly the actual cost and quality of digital services.
This thesis’ scope is to contribute to the scalability of signal processing applications executed in multicore environment. The main goal is to provide methodologies and tools to leverage model‐based design and particularly to efficiently utilize the dataflow model towards the availability of scalable high performance application software. The concept of model‐based design is to decouple algorithm description from actual implementation in a hardware platform. The dataflow model algorithm description is based on the flow of data through its operations which are expressed as actors connected in a graph. Dataflow models can easily expose the potential parallelism of an algorithm and thus be an efficient methodology to analyse signal processing algorithms. However transforming dataflow models in executable code for multicore execution is challenging. This is due to the semantics ’gap’ between dataϐlow and traditional imperative programming languages. This thesis explores and proposes methodologies for leveraging dataflow based application design towards scalable application software development. In this way, popular signal processing algorithms that are efficiently modelled with dataflow graphs, could be also executed efficiently in multicore architectures.
In order to analyse how dataflow representations can be executed efficiently, this thesis gives insights regarding how well the traditional thread programming model can scale in order to support efficient parallel execution of signal processing algorithms such as image/video compression. Then a hypothesis is made that task programming models can scale better and overcome the scalability burdens of the thread model. This is justified by experimental results and related analysis.
Another claim of this thesis is that task programming models’ attributes correlate more accurately with the semantics of dataflow model of computation. Therefore, a methodology that combines synchronous dataflow and task programming models in order to enable scalable application execution is proposed. A task‐based code generator is developed and tested within a synchronous dataflow‐based application development framework. Furthermore, to optimise the dataflow to task‐based code transformation and extend its applicability in multicore platforms, a set of optimisation techniques are developed. As a result, the code generator can be used to scale the performance of applications with fine grain level of parallelism, independently from the number of cores. The generated code can also be utilised in both symmetric and asymmetric multicore environments. A set of experiments are performed that verify the proof of concept and the efficiency of the code generation process. The speed‐up and throughput of the task‐based code execution is evaluated against the equivalent thread‐based code execution for the same set of applications described as synchronous dataflow graphs.
De flesta moderna digitala elektroniska enheter och system förut‐ sätter numera flerkärniga processorer för att kunna uppfylla de allt hårdare kraven på funktioner och tjänster med mervärde. Därmed har flerkärniga arkitekturer kunnat optimera förhållandet prestanda per watt, dvs. applikationsgenomströmning i relation till dess effektbehov. Denna utveckling inom maskinvaruarkitektur har skapat nya utmaningar för programvarutekniken. Traditionella programvarumodeller är inte utformade för att optimalt utnyttja den potential för parallellitet som kan finnas i tillämpningar. Därför har det varit avgörande att skapa nya pro‐ gramvarumetoder som ökar applikationsprestandan genom att utnyttja parallell exekvering i flerkärniga miljöer. Detta bör resultera i snabbare exekvering av tillämpningar när processresurserna (antalet kärnor) ökas. I denna avhandling använder vi begreppet skalbarhet för att beskriva hur väl en tillämpning kan prestera genom att utnyttja ett successivt större antal kärnor.
För att effektivt exekvera tillämpningar i en flerkärnig miljö måste man itu med utmaningarna med schemaläggning av flera kärnor. För att skapa scheman med acceptabel kvalitet utnyttjas vanligtvis detaljer i maskinvaruplattformen. Det finns ett incitament att skapa skalbara tillämpningar som i liten eller ingen grad förlitar sig på underliggande plattformar. Detta skulle innebära att uppgradering av den underliggande hårdvaran i en flerkärnig enhet skulle resultera i en analog, idealt linjär, uppgradering av dess tillämpningsprestanda. Detta skulle också göra det möjligt att sömlöst flytta tillämpningar till molnet, där exekveringsresurserna, inklusive antalet kärnor, kan allokeras dynamiskt. Tillgången till skalbara programvarumetoder påverkar därmed avsevärt de digitala tjänsternas faktiska kostnader och kvalitet.
Denna avhandling är avsedd att bidra till skalbarhet hos signalbehandlingstillämpningar som exekveras i en flerkärnig miljö. Det huvudsakliga målet är att tillhandahålla metoder och verktyg för att utnyttja modell‐ baserad design och särskilt att effektivt utnyttja dataflödesmodellen i syfte att tillgängliggöra skalbar högpresterande tillämpningsprogram‐ vara. Konceptet modellbaserad konstruktion handlar om att frikoppla algoritmbeskrivningen från själva implementeringen på en maskinvaru‐ plattform. Algoritmbeskrivningen för dataflödesmodellen baseras på dataflödet genom dess operationer, vilka uttrycks som aktörer som är sammankopplade i ett diagram. Dataflödesmodeller kan lätt exponera en algoritms potentiella parallellitet och är därmed en effektiv metod för att analysera signalbehandlingsalgoritmer. Att omvandla dataflödesmodeller till körbar kod för exekvering i en flerkärnig miljö är dock en utmaning. Detta beror på den semantiska ”klyftan” mellan dataflödet och traditionella tvingande programmeringsspråk. Denna avhandling utforskar och föres‐ lår metoder för att utnyttja dataflödesbaserad tillämpningskonstruktion med inriktning på utveckling av skalbar tillämpningsprogramvara. På så sätt skulle även populära signalbehandlingsalgoritmer som är resurssnålt modellerade med dataflödesgrafer kunna exekveras effektivt i flerkärniga arkitekturer.
För att analysera hur dataflödesrepresentationer kan exekveras effektivt ger denna avhandling insikter om hur väl den traditionella trådprogrammeringsmodellen kan skalas för att stödja effektiv parallell exekvering av signalbehandlingsalgoritmer – som bild‐/videokomprimering. Avhandlingen framlägger en hypotes om att uppgiftsprogrammeringsmodeller kan skala bättre och övervinna trådmodellens problem med skalbarhet. Detta underbyggs av experimentella resultat och relaterad analys.
I avhandlingen hävdas vidare att uppgiftsprogrammeringsmodellernas attribut korrelerar mer exakt med semantiken i dataflödesmodellen för databehandling. Därför föreslås en metod som kombinerar synkrona dataflödes‐ och uppgiftsprogrammeringsmodeller för att möjliggöra skalbar tillämpningsexekvering. En uppgiftsbaserad kodgenerator utvecklas och testas inom ett synkront dataflödesbaserat ramverk för tillämpningsutveckling. För att optimera dataflödet till uppgiftsbaserad kodtransformering och utöka dess tillämpbarhet på flerkärniga plattformar utvecklas dessutom en uppsättning optimeringstekniker. Som ett resultat kan kodgeneratorn användas för att skala prestanda för tillämpningar med detaljerad grad av parallellitet, oberoende av antalet kärnor. Den genererade koden kan också användas i både symmetriska och asymmetriska flerkärniga miljöer. En uppsättning experiment utförs som verifierar konceptet och effektiviteten hos kodgenereringsprocessen. Snabbheten och genomströmningen hos den uppgiftsbaserade kodex‐ ekveringen utvärderas mot motsvarande trådbaserade kodexekvering för samma uppsättning tillämpningar, vilka beskrivs som synkrona dataflödesgrafer.