In dit artikel beschrijft de auteur hoe hij een FAST-feature-detector voor de ESP32-S3 microcontroller heeft geoptimaliseerd met behulp van 128-bit SIMD-instructies. Deze aanpak verhoogt de doorvoer van 5,1 MP/s naar 11,2 MP/s, waardoor een VGA-stream van 30 fps in real-time verwerkt kan worden.
Tijdens de implementatie werden twee belangrijke technische uitdagingen opgelost:
- Niet-uitgelijnde leesacties: De ISA staat geen directe misaligned reads toe. Dit is omzeild door slices van geconcateneerde registers te extraheren.
- Signed versus Unsigned integers: De chip ondersteunt enkel signed 8-bit vergelijkingen en maakt gebruik van saturating arithmetic. De auteur loste dit op via bit-manipulatie (
XOR 0x80), waardoor ongetekende pixelwaarden lineair werden verschoven naar een bruikbaar bereik.
Daarnaast heeft de auteur een eigen basis-register-allocator ontwikkeld, genaamd basm, om de assembly-code effectiever te beheren.
SIMD-versnelde computer vision op een microcontroller van $2
Voor zijn prijs is de ESP32-S3 een krachtpatser van een microcontroller. In de onopvallende plastic behuizing bevindt zich een dual-core CPU met een maximale snelheid van 240 MHz en een reeks randapparatuur, waaronder WiFi- en Bluetooth Low Energy-radio's. Tijdens het bestuderen van de technische handleiding ontdekte ik dat de chip een beperkte set SIMD-instructies ondersteunt. Voor hardware die goedkoper is dan de gemiddelde kop koffie, is dat behoorlijk indrukwekkend.
Tijdens het proces van het schrijven van een SIMD-versnelde FAST-corner-detector heb ik de basis van assembly op de ESP32-S3 geleerd, ben ik om zijn excentrieke beperkingen heen gewerkt en heb ik uiteindelijk mijn eigen basis-register-allocator geschreven: basm.
Motivatie en onderzoek
Na wat onderzoek op het web realiseerde ik me dat deze instructies niet echt geheim waren, maar eerder relatief onbekend. Ik wilde hier zelf mee experimenteren en geavanceerdere code schrijven dan wat ik online kon vinden. Omdat ik de laatste tijd erg geïnteresseerd ben in computer vision, besloot ik een SIMD-versnelde implementatie van de FAST-feature-detector voor de ESP32-S3 te schrijven.
Ik begon met het zoeken naar voorbeeldcode die SIMD-instructies gebruikt. Op het moment van schrijven kon ik slechts drie bronnen vinden:
- De blog van Larry Bank, waarin hij de functie onderzoekt en een minimaal voorbeeld geeft.
- De
esp-dsp bibliotheek van Espressif, gebruikt voor DSP-achtige functies (convoluties, FFT, etc.).
- De
esp-dl bibliotheek van Espressif, gebruikt voor AI-acceleratie op de chip.
Na het bestuderen hiervan was ik opgelucht te merken dat assembly op de ESP32-S3 niet zo erg is. Ik heb gekozen voor deze algemene structuur:
.section .rodata
# read-only data here
.section .text
.align 4
.global add
.type add,@function
# a simple function that adds two numbers
# int32_t add(int32_t a, int32_t b)
add:
entry sp, 48 # sp (stack pointer) is an alias for a1
#define r_a a2
#define r_b a3
# code here
add a2, r_a, r_b # a2 = a + b
retw.n # return, with a2 containing the return value.
De implementatie van de FAST-pretest
Vervolgens begon ik met het schrijven van een SIMD-versnelde versie van de FAST-corner-pretest. In essentie bemonstert deze één pixel in elke windrichting en controleert of er ten minste drie "extreme" pixels zijn. Een extreme pixel is in dit geval een pixel waarvan het absolute verschil met de centrale pixel boven een bepaalde drempelwaarde ligt.
Ik heb gekozen voor een functie die de telling van extrema's voor zestien pixels tegelijk berekent, aangezien elk vectorregister zestien acht-bit waarden kan opslaan. Dit wordt bereikt door vier "chunks" pixels in elke windrichting te bemonsteren en deze te vergelijken met hun respectievelijke centrale pixels.
Uitdaging 1: Niet-uitgelijnde leesacties
Hier stuitte ik op mijn eerste beperking: de ISA (Instruction Set Architecture) staat geen directe misaligned reads (niet-uitgelijnde leesacties) toe. Uitgaande van het feit dat de centrale pixel is uitgelijnd, zouden de oostelijke en westelijke blokken niet-uitgelijnd zijn: centrum | oost en west | centrum.
Gelukkig heeft de chip een instructie waarmee een slice van twee geconcateneerde registers kan worden geëxtraheerd naar een ander register. Met deze functionaliteit kon ik de oostelijke en westelijke blokken extraheren door slices te lezen en te extraheren uit de twee blokken die grenzen aan het centrale blok.
Uitdaging 2: Signed versus Unsigned integers
Zodra de pixeldata beschikbaar was, was het tijd voor vergelijkingen. Echter, de ESP32-S3 ondersteunt vergelijkingen alleen voor signed (getekende) acht-bit getallen. Dit maakte de verwerking lastiger, omdat al mijn pixeldata was opgeslagen als unsigned (ongetekende) acht-bit getallen.
Als je ongetekende data simpelweg interpreteert als getekende data, krijg je vreemde resultaten:
>>> np.int8(np.uint8(range(0, 256, 8)))
array([ 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80,
88, 96, 104, 112, 120, -128, -120, -112, -104, -96, -88,
-80, -72, -64, -56, -48, -40, -32, -24, -16, -8],
dtype=int8)
Het bereik [128, 255] wordt niet-lineair afgebeeld op [-128, -1], wat alle vergelijkingsoperaties onbruikbaar maakt. Om dit werkend te krijgen, moest ik het bereik van de waarden verschuiven van [0, 255] naar [-128, 127].
Dit had een eenvoudige aftrekking moeten zijn, maar de instructieset werkte opnieuw dwars: op de ESP32-S3 zijn alle SIMD-rekenoperaties saturating (verzadigend). Dit betekent dat alle pixelwaarden boven de 127 zouden worden afgeclapt op -128 in plaats van dat ze onderstromen naar hun juiste waarden.
De oplossing: Bit-manipulatie
Om dit probleem op te lossen, moest ik 128 van elk getal aftrekken in parallel, zonder de aftrekinstructie te gebruiken. De oplossing ligt in de bit-structuur. Laten we aannemen dat x het getal is. De plaatswaarden van de cijfers zijn: -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1
Aftrekken is hetzelfde als optellen met -128. Om x - 128 te berekenen, kunnen we het getal "incrementeren" met -128 door één op te tellen bij het meest significante cijfer van x, waarvan de plaatswaarde -128 is. Dit kunnen we bereiken door simpelweg de hoogste bit van x te flippen.
Omdat het XOR-en van een bit met 1 hetzelfde is als het nemen van de bitwise NOT, kunnen we selectief de hoogste bit van x flippen door deze te XOR-en met het bitmasker 0b10000000 (gelijk aan 0x80). Daarom geldt: x - 128 == x ^ 0x80.
Nu worden ongetekende acht-bit waarden bij het inladen ge-XOR'd met 0x80 om ze om te zetten naar een passend lineair bereik waarin rekenkunde en vergelijkingen weer logisch zijn.
Resultaten
Met deze twee trucs kon ik de beperkingen van de ESP32-S3 omzeilen en de SIMD-versnelde FAST-corner-pretest schrijven. Daarnaast heb ik een SIMD-versnelde scoring-functie geschreven met een vergelijkbare set operaties.
Uiteindelijk kon ik de doorvoer van de FAST-feature-detector met ongeveer 220% verbeteren, van 5,1 MP/s naar 11,2 MP/s in mijn tests. Dit valt ruim binnen het acceptabele prestatiebereik voor real-time computer vision-taken, waardoor de ESP32-S3 gemakkelijk een VGA-stream van 30 fps kan verwerken. Niet slecht voor $2!
SIMD-versnelde computer vision op een microcontroller van $2
Voor zijn prijs is de ESP32-S3 een krachtpatser van een microcontroller. In de onopvallende plastic behuizing bevindt zich een dual-core CPU met een maximale snelheid van 240 MHz en een reeks randapparatuur, waaronder WiFi- en Bluetooth Low Energy-radio's. Tijdens het bestuderen van de technische handleiding ontdekte ik dat de chip een beperkte set SIMD-instructies ondersteunt. Voor hardware die goedkoper is dan de gemiddelde kop koffie, is dat behoorlijk indrukwekkend.
Tijdens het proces van het schrijven van een SIMD-versnelde FAST-corner-detector heb ik de basis van assembly op de ESP32-S3 geleerd, ben ik om zijn excentrieke beperkingen heen gewerkt en heb ik uiteindelijk mijn eigen basis-register-allocator geschreven: basm.
Motivatie en onderzoek
Na wat onderzoek op het web realiseerde ik me dat deze instructies niet echt geheim waren, maar eerder relatief onbekend. Ik wilde hier zelf mee experimenteren en geavanceerdere code schrijven dan wat ik online kon vinden. Omdat ik de laatste tijd erg geïnteresseerd ben in computer vision, besloot ik een SIMD-versnelde implementatie van de FAST-feature-detector voor de ESP32-S3 te schrijven.
Ik begon met het zoeken naar voorbeeldcode die SIMD-instructies gebruikt. Op het moment van schrijven kon ik slechts drie bronnen vinden:
- De blog van Larry Bank, waarin hij de functie onderzoekt en een minimaal voorbeeld geeft.
- De
esp-dsp bibliotheek van Espressif, gebruikt voor DSP-achtige functies (convoluties, FFT, etc.).
- De
esp-dl bibliotheek van Espressif, gebruikt voor AI-acceleratie op de chip.
Na het bestuderen hiervan was ik opgelucht te merken dat assembly op de ESP32-S3 niet zo erg is. Ik heb gekozen voor deze algemene structuur:
.section .rodata
# read-only data here
.section .text
.align 4
.global add
.type add,@function
# a simple function that adds two numbers
# int32_t add(int32_t a, int32_t b)
add:
entry sp, 48 # sp (stack pointer) is an alias for a1
#define r_a a2
#define r_b a3
# code here
add a2, r_a, r_b # a2 = a + b
retw.n # return, with a2 containing the return value.
De implementatie van de FAST-pretest
Vervolgens begon ik met het schrijven van een SIMD-versnelde versie van de FAST-corner-pretest. In essentie bemonstert deze één pixel in elke windrichting en controleert of er ten minste drie "extreme" pixels zijn. Een extreme pixel is in dit geval een pixel waarvan het absolute verschil met de centrale pixel boven een bepaalde drempelwaarde ligt.
Ik heb gekozen voor een functie die de telling van extrema's voor zestien pixels tegelijk berekent, aangezien elk vectorregister zestien acht-bit waarden kan opslaan. Dit wordt bereikt door vier "chunks" pixels in elke windrichting te bemonsteren en deze te vergelijken met hun respectievelijke centrale pixels.
Uitdaging 1: Niet-uitgelijnde leesacties
Hier stuitte ik op mijn eerste beperking: de ISA (Instruction Set Architecture) staat geen directe misaligned reads (niet-uitgelijnde leesacties) toe. Uitgaande van het feit dat de centrale pixel is uitgelijnd, zouden de oostelijke en westelijke blokken niet-uitgelijnd zijn: centrum | oost en west | centrum.
Gelukkig heeft de chip een instructie waarmee een slice van twee geconcateneerde registers kan worden geëxtraheerd naar een ander register. Met deze functionaliteit kon ik de oostelijke en westelijke blokken extraheren door slices te lezen en te extraheren uit de twee blokken die grenzen aan het centrale blok.
Uitdaging 2: Signed versus Unsigned integers
Zodra de pixeldata beschikbaar was, was het tijd voor vergelijkingen. Echter, de ESP32-S3 ondersteunt vergelijkingen alleen voor signed (getekende) acht-bit getallen. Dit maakte de verwerking lastiger, omdat al mijn pixeldata was opgeslagen als unsigned (ongetekende) acht-bit getallen.
Als je ongetekende data simpelweg interpreteert als getekende data, krijg je vreemde resultaten:
>>> np.int8(np.uint8(range(0, 256, 8)))
array([ 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80,
88, 96, 104, 112, 120, -128, -120, -112, -104, -96, -88,
-80, -72, -64, -56, -48, -40, -32, -24, -16, -8],
dtype=int8)
Het bereik [128, 255] wordt niet-lineair afgebeeld op [-128, -1], wat alle vergelijkingsoperaties onbruikbaar maakt. Om dit werkend te krijgen, moest ik het bereik van de waarden verschuiven van [0, 255] naar [-128, 127].
Dit had een eenvoudige aftrekking moeten zijn, maar de instructieset werkte opnieuw dwars: op de ESP32-S3 zijn alle SIMD-rekenoperaties saturating (verzadigend). Dit betekent dat alle pixelwaarden boven de 127 zouden worden afgeclapt op -128 in plaats van dat ze onderstromen naar hun juiste waarden.
De oplossing: Bit-manipulatie
Om dit probleem op te lossen, moest ik 128 van elk getal aftrekken in parallel, zonder de aftrekinstructie te gebruiken. De oplossing ligt in de bit-structuur. Laten we aannemen dat x het getal is. De plaatswaarden van de cijfers zijn: -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1
Aftrekken is hetzelfde als optellen met -128. Om x - 128 te berekenen, kunnen we het getal "incrementeren" met -128 door één op te tellen bij het meest significante cijfer van x, waarvan de plaatswaarde -128 is. Dit kunnen we bereiken door simpelweg de hoogste bit van x te flippen.
Omdat het XOR-en van een bit met 1 hetzelfde is als het nemen van de bitwise NOT, kunnen we selectief de hoogste bit van x flippen door deze te XOR-en met het bitmasker 0b10000000 (gelijk aan 0x80). Daarom geldt: x - 128 == x ^ 0x80.
Nu worden ongetekende acht-bit waarden bij het inladen ge-XOR'd met 0x80 om ze om te zetten naar een passend lineair bereik waarin rekenkunde en vergelijkingen weer logisch zijn.
Resultaten
Met deze twee trucs kon ik de beperkingen van de ESP32-S3 omzeilen en de SIMD-versnelde FAST-corner-pretest schrijven. Daarnaast heb ik een SIMD-versnelde scoring-functie geschreven met een vergelijkbare set operaties.
Uiteindelijk kon ik de doorvoer van de FAST-feature-detector met ongeveer 220% verbeteren, van 5,1 MP/s naar 11,2 MP/s in mijn tests. Dit valt ruim binnen het acceptabele prestatiebereik voor real-time computer vision-taken, waardoor de ESP32-S3 gemakkelijk een VGA-stream van 30 fps kan verwerken. Niet slecht voor $2!
Groetjes,