Optimized Static Allocation of Signal Processing Tasks onto Signal Processing Cores

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2023-08-21
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
59
Series
Abstract
Modern digital audio effect modelling devices offer advantages in cost, reliability and reproducibility compared to their analog alternatives. The device emulating a complete signal chain used for playing electric guitar or bass must perform its digital audio signal processing in real-time, and thus sufficient computation power is needed, usually through cores designed for digital signal processing. As the modelled signal chains become larger, multicore architectures become a necessity to meet the computation demands of the processing. This thesis studies the problem of allocating signal processing tasks to signal processing cores on an audio effect modelling device. Communication between tasks allocated on separate cores adds latency to the processing, and for a real-time audio processor, the total latency of the processing must be minimized. Each task consumes a fixed amount of various resources on the core it executes on, and thus we need to also efficiently utilize the available resources on the system. To preserve a pleasant user experience on the device, the algorithm allocating the tasks needs to run efficiently on an embedded system. We provide an overview into the existing task scheduling and allocation algorithms commonly used for similar problems optimizing latency and core utilization. Based on the prior work found, we implemented an efficient list scheduler that allows some minor brute-force optimization related to the specifics of the system hardware considered in this thesis. The implemented list scheduler was compared against an algorithm used to solve the same problem in an existing modeller product. We used both real-world and randomly generated signal task graphs to evaluate the latency, core utilization, and runtime performance of the algorithms. We determined that the greedy list scheduler utilizing system-specific heuristics can obtain effective results with an efficient and consistent execution time. Utilizing various list orders and recovery from greedy mistakes allowed us to minimize the effect of the greedy implementation, and obtain better results in less time compared to the baseline implementation.

Modernit digitaaliset audioefektimallinnuslaitteet tarjoavat etuja hinnassa, luotettavuudessa ja toistettavuudessa verrattuna analogisiin vaihtoehtoihin. Laitteen, joka mallintaa kokonaisen kitara- tai bassosignaaliketjun, täytyy suorittaa digitaalinen signaalinkäsittely reaaliajassa, ja täten laitteessa täytyy olla riittävästi laskentatehoa. Kun mallinnettavat signaaliketjut kasvavat isoiksi, tarvitaan prosessointia varten moniydinarkkitehtuuri. Tämä diplomityö tutkii signaalinkäsittelytehtävien allokointia signaalinkäsittely-ytimille osana audioefektejä mallintavaa laitetta. Eri ytimille allokoitujen tehtävien välinen kommunikaatio lisää prosessointiin latenssia, joka reaaliaikaisesti signaalia käsittelevässä laitteessa täytyy minimoida. Ytimelle allokoidut tehtävät sitovat resursseja ytimeltä, joten laitteen resursseja täytyy hyödyntää tehokkaasti. Jotta laitteen käyttäjäkokemus säilyy hyvänä, täytyy tehtävät allokoivan algoritmin suoritusajan olla lyhyt. Esitämme työssä katsauksen olemassa oleviin allokointi- ja aikataulutusalgoritmeihin, jotka pyrkivät optimoimaan latenssia ja ydinten hyödyntämistä. Näiden pohjalta toteutimme tehokkaan lista-aikataulutusalgoritmin, jonka nopea suoritusaika mahdollistaa tiettyjen systeemi- ja sovelluskohtaisten parametrien optimoinnin kokeilemalla kaikki vaihtoehdot läpi. Toteutettua algoritmia verrattiin tuotantokäytössä olevaan algoritmiin. Latenssia, ydinten täyttämistä ja algoritmin suoritusaikaa mitattiin sekä käyttäjien rakentamilla että satunnaisesti luoduilla audiosignaaliverkoilla. Tuloksena huomasimme, että toteuttamamme ahne lista-aikataulutusalgoritmi onnistui löytämään verrokkia pienempiä latensseja lyhyemmässä ja ennustettavassa suoritusajassa hyödyntämällä systeemikohtaisia heuristiikkoja. Useiden listajärjestysten käyttäminen ja ahneudesta aiheutuneiden virheiden korjaaminen mahdollisti algoritmin ahneuden aiheuttamien ongelmien minimoinnin, jolloin toteuttamamme algoritmi onnistui löytämään parempia tuloksia nopeammin kuin verrokkialgoritmi.
Description
Supervisor
Hirvisalo, Vesa
Thesis advisor
Frisk, Tatu
Keywords
list scheduling, latency, digital signal processing, multicore, optimization
Other note
Citation