<p>Det här examensarbetet beskriver en specifik optimeringsteknik och undersöker dess förmåga att öka exekveringshastigheten. Optimeringstekniken ersätter villkorliga hopp i form av if-satser med ovillkorligt hopp. Ett program har utvecklats som mäter exekveringstiden för flera små programkoder, som både använder respektive inte använder optimeringstekniken, så att de kan jämföras med varandra. Med hjälp av mätresultaten från programmet har optimeringstekniken utvärderats. Resultaten visar att optimeringstekniken inte kan öka exekveringshastigheten i de flesta av testerna, men i några specifika fall kan optimeringstekniken öka exekveringshastigheten.</p>

Det här examensarbetet beskriver en specifik optimeringsteknik och undersöker dess förmåga att öka exekveringshastigheten. Optimeringstekniken ersätter villkorliga hopp i form av if-satser med ovillkorligt hopp. Ett program har utvecklats som mäter exekveringstiden för flera små programkoder, som både använder respektive inte använder optimeringstekniken, så att de kan jämföras med varandra. Med hjälp av mätresultaten från programmet har optimeringstekniken utvärderats. Resultaten visar att optimeringstekniken inte kan öka exekveringshastigheten i de flesta av testerna, men i några specifika fall kan optimeringstekniken öka exekveringshastigheten.

Målet med projektet är att jämföra algoritmerna Perlin noise och Diamond-square för procedurell terränggererering inom exekveringstid och framkomlighet. Projektet implementerades i Unity i form utav ett editor-verktyg som både genererar terräng och utför diverse tester. Framkomlighetstestet för terrängen är en modifierad version av en Flood fill algoritm och mätningen av exekveringstid utförs med en timer. För att undvika att vara partisk mot någon av algoritmerna har det implementerats flera typer av terränger med varierande egenskaper. Mätningarna som utförs på varje terräng för respektive algoritm testas ett stort antal gång för olika givna storlekar och med varierande frön. Efteråt utförs en analys som visar att Diamond-square definitivtär den snabbaste av de två algoritmerna och att Diamond-square ger högre framkomlighet för större banor, medan Perlin noise visar en mer konsekvent framkomlighet. Framtida relaterade projekt bör inkludera flera modernare algoritmer för att se hur de förhåller sig till Perlin noise och Diamond-square.

Cloud computing has become increasingly popular over recent years, allowing computing resources to be scaled on-demand. Cloud Native applications are specifically created to run on the cloud service model. Currently, there is a research gap regarding the design and implementation of cloud native applications, especially regarding how design decisions affect metrics such as execution time and scalability of systems. The problem investigated in this thesis is whether the execution time and quality scalability, ηt of cloud native solutions are affected when housing the functionality of multiple use cases within the same cloud native application. In this work, a cloud native application for trading data analysis is presented, where the functionality of 3 use cases are implemented to the application: (1) creating reports of trade prices, (2) anomaly detection, and (3) analysis of relation diagram of trades. The execution time and scalability of the application are evaluated and compared to readily available solutions, which serve as a baseline for the evaluation. The results of use cases 1 and 2 are compared to Amazon Athena, while use case 3 is compared to Amazon Neptune. The results suggest that having functionalities combined into the same application could improve both execution time and scalability of the system. The impact depends on the use case and hardware configuration. When executing the use cases in a sequence, the mean execution time of the implemented system was decreased up to 17.2% while the quality scalability score was improved by 10.3% for use case 2. The implemented application had significantly lower execution time than Amazon Neptune but did not surpass Amazon Athena for respective use cases. The scalability of the systems varied depending on the use case. While not surpassing the baseline in all use cases, the results show that the execution time of a cloud native system could be improved by having functionality of multiple use cases within one system. However, the potential performance gains differ depending on the use case and might be smaller than the performance gains of choosing another solution. / Cloud computing har de senaste åren blivit alltmer populärt och möjliggör att skala beräkningskapacitet och resurser på begäran. Cloud native-applikationer är specifikt skapade för att köras på distribuerad infrastruktur. För närvarande finns det luckor i forskningen gällande design och implementering av cloud native applikationer, särskilt angående hur designbeslut påverkar mätbara värden som exekveringstid och skalbarhet. Problemet som undersöks i denna uppsats är huruvida exekveringstiden och måttet av kvalitetsskalbarhet, ηt påverkas när funktionaliteten av flera användningsfall intregreras i samma cloud native applikation. I det här arbetet skapades en cloud native applikation som kombinerar flera användningsfall för att analysera transaktionsbaserad börshandelsdata. Funktionaliteten av 3 användningsfall implementeras i applikationen: (1) generera rapporter över handelspriser, (2) detektering av avvikelser och (3) analys av relations-grafer. Applikationens exekveringstid och skalbarhet utvärderas och jämförs med kommersiella cloudtjänster, vilka fungerar som en baslinje för utvärderingen. Resultaten från användningsfall 1 och 2 jämförs med Amazon Athena, medan användningsfall 3 jämförs med Amazon Neptune. Resultaten antyder att systemets exekveringstid och skalbarhet kan förbättras genom att funktionalitet för flera användningsfall implementeras i samma system. Effekten varierar beroende på användningsfall och hårdvarukonfiguration. När samtliga användningsfall körs i en sekvens, minskar den genomsnittliga körtiden för den implementerade applikationen med upp till 17,2% medan kvalitetsskalbarheten ηt förbättrades med 10,3%för användningsfall 2. Den implementerade applikationen har betydligt kortare exekveringstid än Amazon Neptune men överträffar inte Amazon Athena för respektive användningsfall. Systemens skalbarhet varierade beroende på användningsfall. Även om det inte överträffar baslinjen i alla användningsfall, visar resultaten att exekveringstiden för en cloud native applikation kan förbättras genom att kombinera funktionaliteten hos flera användningsfall inom ett system. De potentiella prestandavinsterna varierar dock beroende på användningsfallet och kan vara mindre än vinsterna av att välja en annan lösning.

WebAssembly (Wasm) has emerged as a new technology for the web that enables complex and interactive web applications, while utilizing a compact and platform-independent bytecode format. Due to its flexibility, portability, and built-in security, it has since evolved to be used in many other embeddings, such as internet-of-things, server applications, and even mobile applications. While a goal of Wasm is near-native performance, research has found that its performance is not as great as initially expected. Due to this, projects like The WebAssembly Pre-Initializer (Wizer) have emerged as potential solutions to this problem. Wizer is a tool developed by the coalition Bytecode Alliance with the purpose of speeding up the startup time, or Critical Path to Interactive (CPTI), of a Wasm module by pre-initializing it and saving a snapshot of the Wasm instance state into a new Wasm module. Wizer has been evaluated using two benchmark programs. However, no larger-scale investigation into the CPTI improvement brought by its pre-initialization has been conducted. Furthermore, saving a snapshot of the module is likely to result in a larger module in terms of file size, leading to increased compile time or, for use cases where it is relevant, network latency. This project investigates, mainly within the field of Wasm in non-web environments, the extent to which Wizer is able to improve CPTI for a Wasm module. The purpose of this is to allow both Wasm maintainers and developers to form an opinion whether pre-initialization could be standardized for use in Wasm compilers and toolchains, or whether pre-initialization should be applied to their Wasm module based on its CPTI before pre-initialization. Results are obtained by compiling a number of sample software down to Wasm, measuring their CPTI in terms of elapsed CPU cycles both without and with pre-initialization using Wizer, and comparing them. This is made possible through an extension to the Sightglass benchmarking framework also developed by Bytecode Alliance. The results show that pre-initialization using Wizer increases the CPTI if the Wasm module cannot be compiled to native CPU instructions in advance. However, if compilation can be done in advance, Wizer is able to reduce the CPTI of a Wasm module by a factor of between two to six times, depending on how it is initialized. / WebAssembly (Wasm) har framträtt som en ny teknik för webben som möjligör komplexa och interaktiva webbapplikationer, genom ett kompakt och platformsoberoende bytekodformat. Tack vare teknikens flexibilitet, portabilitet och inbyggd säkerhet, har den även utvecklats till att användas i andra samanhang, exampelvis i sakernas internet, serverapplikationer, och även mobilapplikationer. Trots att ett mål med Wasm är prestanda jämförbar med native applikationer, har forskning funnit att den inte presterat så väl som man tidigare trott. Därför har project som The WebAssembly Pre-Initializer (Wizer) framträtt som möjliga lösningar till detta problem. Wizer är ett verktyg utvecklat av koalitionen Bytecode Alliance med syftet att snabba upp uppstartstider, även kallat Critical Path to Interactive (CPTI), av en Wasm modul genom att förinitialisera den och spara en ögonblicksbild av Wasm instansens tillstånd som en ny Wasm modul. Wizer har evaluerats genom två testprogram. Dock har inte någon storskalig undersökning utförts inom CPTI-förbättringen som dess förinitialisering kan medföra. Dessutom är det sannorlikt att sparandet av en ögonblicksbild av en modul leder till en filstorleksmässigt större modul, vilket gör att kompileringstiden, och även nätverkslatensen i användningsfall där det förekommer, kan öka. Det här projektet undersöker, huvudsakligen inom Wasm utanför webbläsaren, omfattningen av Wizers förbättring av CPTI för en Wasm modul. Syftet med detta är att möjliggöra för Wasm designers och utvecklare att förstå hurvida förinitialisering skulle kunna bli standardiserat i Wasm kompilerare eller verktyg, eller om förinitialisering borde tillämpas på en Wasm modul under utveckling baserat på dens CPTI innan förinitialisering. Resultat samlas genom att kompilera flera exempelprogram ner till Wasm, mäta deras CPTI genom passerade CPU cykler både med och utan förinitialisering med Wizer, och jämföra mätningarna. Detta möjligörs genom en utökning av testramverket Sightglass som också utvecklats av Bytecode Alliance. Resultaten visar att förinitialisering med Wizer ökar CPTI om Wasm modulen inte kan i förväg kompileras till instruktioner som kan köras på CPU:n. Om kompilering i förväg dock är möjlig kan Wizer minska CPTI för en given Wasm modul med en faktor av två upp till sex gånger, beroende på den typ av förinitialisering som den gör.

Computers can be used to classify various types of data, for example to filter email messages, detect computer viruses, detect diseases, etc. This thesis explores two classification algorithms, random forest and k-nearest neighbour, to understand how accurately and how quickly they classify data. A literature study was conducted to identify the various prerequisites and to find suitable data sets. Five different data sets, leukemia, credit card, heart failure, mushrooms and breast cancer, were gathered and classified by each algorithm. A train split and a 4-fold cross-validation for each data set was used. The Rust library SmartCore, which included numerous classification methods and tools, was used to perform the classification. The results gathered indicated that using the train split resulted in better classification results, as opposed to 4-fold cross-validation. However, it could not be determined if any attributes of a data set affect the classification accuracy. Random forest managed to achieve the best classification results on the two data sets heart failure and leukemia, whilst k-nearest neighbour achieved the best classification results on the remaining three data sets. In general the classification results on both algorithms were similar. Based on the results, the execution time of random forest was dependent on the number of trees in the ”forest”, in which a greater number of trees resulted in an increased execution time. In contrast, a higher k value did not increase the execution time of k-nearest neighbour. It was also found that data sets with only binary values (0 and 1) run much faster than a data set with arbitrary values when using random forest. The number of instances in a data set also leads to an increased execution time for random forest despite a small number of features. The same applied to k-nearest neighbour, but with the number of features also affecting the execution since time is needed to compute distances between data points. Random forest managed to achieve the fastest execution time on the two data sets credit card and mushrooms, whilst k-nearest neighbour executed faster on the remaining three data sets. The difference in execution time between the algorithms varied a lot and this depends on the parameter value chosen for the respective algorithm. / Datorer kan användas för att klassificera olika typer av data, t.ex att filtrera e-postmeddelanden, upptäcka datorvirus, upptäcka sjukdomar, etc. Denna avhandling utforskar två klassificeringsalgoritmer, slumpmässiga skogar och k-närmaste grannar, för att förstå hur precist och hur snabbt de klassificerar data. En litteraturstudie genomfördes för att identifiera de olika förutsättningarna och för att hitta lämpliga datamängder. Fem olika datamängder, leukemia, credit card, heart failure, mushrooms och breast cancer, samlades in och klassificerades av varje algoritm. En träningsfördelning och en 4-faldig korsvalidering för varje datamängd användes. Rust-biblioteket SmartCore, som inkluderade många klassificeringsmetoder och verktyg, användes för att utföra klassificeringen. De insamlade resultaten visade att användningen av träningsfördelning resulterade i bättre klassificeringsresultat i motsats till 4-faldig korsvalidering. Det gick dock inte att fastställa om några attribut för en datamängd påverkar klassificeringens noggrannhet. Slumpmässiga skogar lyckades uppnå det bästa klassificeringsresultaten på de två datamängderna heart failure och leukemia, medan k-närmaste granne uppnådde det bästa klassificeringsresultaten på de återstående tre datamängderna. I allmänhet var klassificeringsresultaten för båda algoritmerna likartade. Utifrån resultaten var utförandetiden för slumpmässiga skogar beroende av antalet träd i ”skogen”, då ett större antal träd resulterade i en ökad utförandetid. Däremot ökade inte ett högre k-värde exekveringstiden för k-närmaste grannar. Det upptäcktes även att datamängder med endast binära värden (0 och 1) körs mycket snabbare än datamängder med godtyckliga värden när man använder slumpmässiga skogar. Antalet instanser i en datamängd leder också till en ökad exekveringstid för slumpmässiga skogar trots ett litet antal egenskaper. Detsamma gällde för k-närmaste granne, men även antalet egenskaper påverkade exekveringstiden då tid behövs för att beräkna avstånd mellan datapunkter. Slumpmässiga skogar lyckades uppnå den snabbaste exekveringstiden på de två datamängderna credit card och mushrooms, medan k-närmaste granne exekverades snabbare på de återstående tre datamängderna. Skillnaden i exekveringstid mellan algoritmerna varierade mycket och detta beror på vilket parametervärde som valts för respektive algoritm.

Arbetet undersöker skillnader i prestanda mellan SOLID och mer hårdkodade algoritmer, i form av respektive beteendeträd och en enum-switch tillståndsmaskin. Testerna utförs i spelmotorn Unity genom en isolerad testmiljö där exekveringstiden mäts mellan i scenarion. Algoritmerna har implementerats så att de kan köra olika beteenden, dessa testas i olika scenarion för att få fram resultaten. Exekveringstid mäts genom profiler-verktyget i Unity som sedan analyseras och jämförs för att se hur mycket tid det tar att exekvera och om det finns skillnader mellan dem. Resultaten tyder på att den hårdkodade algoritmen presterade bättre än den som följde SOLID-principer, dock inte så markant att det utesluter användningen av den mer flexibla koden.

Företaget Nordicstation hanterar stora datamängder åt Swedbank där datalagringen sker i relationsdatabasen Microsoft SQL Server 2012 (SQL Server). Då det finns andra databashanterare designade för stora datavolymer är det oklart om SQL Server är den optimala lösningen för situationen. Detta examensarbete har tagit fram en jämförelse med hjälp av prestandatester, beträffande exekveringstiden av databasfrågor, mellan databaserna SQL Server, Cassandra och NuoDB vid hanteringen av stora datamängder. Cassandra är en kolumnbaserad databas designad för hantering av stora datavolymer, NuoDB är en minnesdatabas som använder internminnet som lagringsutrymme och är designad för skalbarhet. Resultaten togs fram i en virtuell servermiljö med Windows Server 2012 R2 på en testplattform skriven i Java. Jämförelsen visar att SQL Server var den databas mest lämpad för gruppering, sortering och beräkningsoperationer. Däremot var Cassandra bäst i skrivoperationer och NuoDB presterade bäst i läsoperationer. Analysen av resultatet visade att mindre access till disken ger kortare exekveringstid men den skalbara lösningen, NuoDB, lider av kraftiga prestandaförluster av att endast konfigureras med en nod. Nordicstation rekommenderas att uppgradera till Microsoft SQL Server 2014, eller senare, där möjlighet finns att spara tabeller i internminnet. / The company Nordicstation handles large amounts of data for Swedbank, where data is stored using the relational database Microsoft SQL Server 2012 (SQL Server). The existence of other databases designed for handling large amounts of data, makes it unclear if SQL Server is the best solution for this situation.  This degree project describes a comparison between databases using performance testing, with regard to the execution time of database queries.  The chosen databases were SQL Server, Cassandra and NuoDB. Cassandra is a column-oriented database designed for handling large amounts of data, NuoDB is a database that uses the main memory for data storage and is designed for scalability. The performance tests were executed in a virtual server environment with Windows Server 2012 R2 using an application written in Java. SQL Server was the database most suited for grouping, sorting and arithmetic operations. Cassandra had the shortest execution time for write operations while NuoDB performed best in read operations. This degree project concludes that minimizing disk operations leads to shorter execution times but the scalable solution, NuoDB, suffer severe performance losses when configured as a single-node. Nordicstation is recommended to upgrade to Microsoft SQL Server 2014, or later, because of the possibility to save tables in main memory.

Följande studie är utförd på uppdrag av företaget Nilar som tillverkar Nickel-Metallhydridbatterier (NiMH-batterier) vid sin produktionanläggning i Gävle. Den nuvarande beräkningen av State of Charge (SoC) sker på deras Battery Management Unit (BMU) och är implementerad i Structured Text i exekveringsmiljön CODESYS. Nilar vill flytta SoC-beräkningen från BMU:n så att den kan exekveras på en Interface Control Unit (ICU). Motiveringen till detta är för att distribuera SoC-beräkningen då ett flertal ICU:er finns tillgängliga per Battery Management System (BMS) men även för att i framtiden helt byta ut CODESY. Syftet med denna studie är att migrera implementationen av SoC-algoritmen till programmeringsspråket C så att algoritmen senare kan exekveras på ICU:n. Därefter optimeras algoritmen för att sänka exekveringstiden. Studien utforskar kodstrukturella och funktionella skillnader mellan implementationerna samt metoder för att optimera SoC-algoritmen. Migreringen av algoritmen fullföljdes utan större inverkan på noggrannheten. Algoritmen optimerades genom att skapa en variant av en LU-faktorisering som var specifikt anpassad för det aktuella problemet. Optimeringen av algoritmen resulterade i en minskning på 25% av den totala exekveringstiden för algoritmen. De nya implementationerna tar markant längre tid att exekvera då batteriet befinner sig under laddning jämfört när det befinner sig under urladdning, någonting som inte kan noteras för den gamla implementationen. / The following study was carried out on the behalf of Nilar, which manufactures Nickel–metal hydride batteries at its production site in Gävle. The current State of Charge (SoC) calculation is done on their Battery Manegment Unit (BMU) and is implemented in Structured Text for the CODESYS runtime. Nilar wants to move the SoC calculation from the BMU so that its executed on a Interface Control Unit (ICU). The reasoning behind this is to distribute the SoC computation as several ICUs are available per Battery Management System (BMS) but also to remove the CODESYS dependency in the future. The purpose of this study is to migrate the implementation of the SoC-algorithm to the programming language C so that the algorithm can be executed on an ICU in the future. Furthermore this study aims to optimize the the algorithm to lower the execution time. The study explores differences in code structure and functionallity between the implementations as well as methods to optimize the SoC algorithm. The migration of the algorithm was completed without major impact on the accuracy. The algorithm was optimized by creating a variant of a LU factorization that was specifically suited to LU factorize the given problem. The optimization of the algorithm resulted in a 25% lower total execution time. The new implementations suffers from a longer total execution time when the battery is charging compared to when it’s discharging, something that’s not prevalent for the old implementation.

The estimation of the worst-case execution time (WCET) of a task is a problem that concerns the field of embedded systems and, especially, real-time systems. Estimating a safe WCET for single-core architectures without speculative mechanisms is a challenging task and an active research topic. However, the advent of advanced hardware mechanisms, which often lack predictability, complicates the current WCET analysis methods. The field of Embedded Systems has high safety considerations and is, therefore, conservative with speculative mechanisms. However, nowadays, even safety-critical applications move to the direction of multiprocessor systems. In a multiprocessor system, each task that runs on a processing unit might affect the execution time of the tasks running on different processing units. In shared-memory symmetric multiprocessor systems, this interference occurs through the shared memory and the common bus. The presence of private caches introduces cachecoherence issues that result in further dependencies between the tasks. The purpose of this thesis is twofold: (1) to evaluate the feasibility of an existing one-pass WCET analysis method with an integrated cache analysis and (2) to design and implement a cachebased multiprocessor WCET analysis by extending the singlecore method. The single-core analysis is part of the KTH’s Timing Analysis (KTA) tool. The WCET analysis of KTA uses Abstract Search-based WCET Analysis, an one-pass technique that is based on abstract interpretation. The evaluation of the feasibility of this analysis includes the integration of microarchitecture features, such as cache and pipeline, into KTA. These features are necessary for extending the analysis for hardware models of modern embedded systems. The multiprocessor analysis of this work uses the single-core analysis in two stages to estimate the WCET of a task running under the presence of temporally and spatially interfering tasks. The first phase records the memory accesses of all the temporally interfering tasks, and the second phase uses this information to perform the multiprocessor WCET analysis. The multiprocessor analysis assumes the presence of private caches and a shared communication bus and implements the MESI protocol to maintain cache coherence. / Uppskattning av längsta exekveringstid (eng. worst-case execution time eller WCET) är ett problem som angår inbyggda system och i synnerhet realtidssystem. Att uppskatta en säker WCET för enkelkärniga system utan spekulativa mekanismer är en utmanande uppgift och ett aktuellt forskningsämne. Tillkomsten av avancerade hårdvarumekanismer, som ofta saknar förutsägbarhet, komplicerar ytterligare de nuvarande analysmetoderna för WCET. Inom fältet för inbyggda system ställs höga säkerhetskrav. Således antas en konservativ inställning till nya spekulativa mekanismer. Trotts detta går säkerhetskritiska system mer och mer i riktning mot multiprocessorsystem. I multiprocessorsystem påverkas en process som exekveras på en processorenhet av processer som exekveras på andra processorenheter. I symmetriska multiprocessorsystem med delade minnen påträffas denna interferens i det delade minnet och den gemensamma bussen. Privata minnen introducerar cache-koherens problem som resulterar i ytterligare beroende mellan processerna. Syftet med detta examensarbete är tvåfaldigt: (1) att utvärdera en befintlig analysmetod för WCET efter integrering av en lågnivå analys och (2) att designa och implementera en cache-baserad flerkärnig WCET-analys genom att utvidga denna enkelkärniga metod. Den enkelkärniga metoden är implementerad i KTH’s Timing Analysis (KTA), ett verktyg för tidsanalys. KTA genomför en så-kallad Abstrakt Sök-baserad Metod som är baserad på Abstrakt Interpretation. Utvärderingen av denna analys innefattar integrering av mikroarkitektur mekanismer, såsom cache-minne och pipeline, i KTA. Dessa mekanismer är nödvändiga för att utvidga analysen till att omfatta de hårdvarumodeller som används idag inom fältet för inbyggda system. Den flerkärniga WCET-analysen genomförs i två steg och uppskattar WCET av en process som körs i närvaron av olika tids och rumsligt störande processer. Första steget registrerar minnesåtkomst för alla tids störande processer, medans andra steget använder sig av första stegets information för att utföra den flerkärniga WCET-analysen. Den flerkärniga analysen förutsätter ett system med privata cache-minnen och en gemensamm buss som implementerar MESI protokolen för att upprätthålla cache-koherens.