autor: Ing. Robert Krejčí, kategorie: Signály

Možnosti optimalizace algoritmů DSP

Vybrané metody softwarových optimalizací
Ilustrační obrázek: DSP

Doktorské pondělky
12.1.2009

Ing. Robert Krejčí

Školitel: Ing. Václav Hanžl, CSc.

V našem výzkumu se zabýváme se optimalizací algoritmů rozpoznávačů řeči pro vybrané hardwarové platformy. V tomto článku si řekneme o některých konkrétních metodách softwarové optimalizace algoritmů číslicového zpracování signálů. Pro úplné pochopení tohoto tématu je vhodné znát některé základní pojmy mikroprocesorové techniky vzhledem k číslicovému zpracování signálů. Jak jsme tyto teoretické poznatky využili, si můžete přečíst ve zhodnocení výsledků našeho dosavadního výzkumu.

Obsah:

  1. Hardwarové možnosti

  2. Softwarové optimalizace

  3. Výsledky

Softwarové optimalizace

  • Obecné

  • DSP

  • Závislé na architektuře

Existuje mnoho způsobů zvyšování efektivity programů. Některé jsou zcela obecné, jiné jsou vhodné pro oblast číslicového zpracování signálů a další jsou účinné pouze pro konkrétní architekturu procesoru (a pro jinou naopak můžou snižovat efektivitu). Zde se zmíníme o některých z nich.

Fixed point / Floating point

Jako příklad uveďme to, co zde již bylo naznačeno. Pokud máme k dispozici 32-bitový procesor pracující s čísly s pevnou řádovou čárkou, bude nejspíše neefektivní zpracovávat čísla ve formátu s plovoucí řádovou čárkou. Bude tedy vhodné přepsat program do aritmetiky s pevnou řádovou čárkou. Tento postup si ilustrujeme na následujících fragmentech kódu v jazyce C.

Výpočet v plovoucí řádové čárce:

float a[N], b[N];
float s = 0.0;

for (i = 0; i < N; i++)
s += a[i] * b[i];

Přepis do pevné řádové čárky:

#define SCALE 5

short a[N], b[N]; // data arrays in Q15 format
long long s = 0; // 64-bit accumulator
short r; // 16-bit result

for (i = 0; i < N; i++)
s += a[i] * b[i]; // accumulate Q1.30 products

s = s >> SCALE; // scaling

if (s > 0x7FFF) // positive saturation?
r = 0x7FFF; // clamp the result to +1
else if (s < -0x8000) // negative saturation?
r = -0x8000; // clamp the result to -1
else // no saturation
r = s & 0xFFFF; // discard redundant sign bits

Jak je vidět, je zároveň potřeba řešit saturaci výsledků.

Mohli bychom pokračovat dále až na úroveň assembleru s použitím DSP instrukcí, které při výpočtu zároveň zajistí správné ošetření saturace.

  • Saturace

  • Assembler, SIMD, ...

Plánování kódu (Code Scheduling)

  • Pipelining

  • Eliminace čekání (Pipeline Stall)

Optimalizace nespočívá jenom v přepsání kódu do instrukcí, které odpovídají architektuře procesoru. V případě použití procesoru s pipeliningem je potřeba naplánovat provádění kódu tak, aby každá instrukce pokud možno pracovala s již vypočítanými operandy, tedy aby nemusela čekat na výsledek, který je teprve postupně zpracováván v procesu pipeliningu (zřetězené zpracování instrukcí s překrýváním fází).

Rozvinutí cyklu (Loop Unrolling)

  • Režie na uspořádání cyklu je větší než jeho vlastní průběh

Tato metoda se používá v případech, kdy režie na uspořádání cyklu je větší než jeho vlastní průběh. Mějme následující kód:

#define N 3
short i;
short a[N], b[N];
long long s = 0; // 64-bit accumulator

for(i=0; i < N; i++)
s += a[i] * b[i];

  • N = konst.

Protože N je v době kompilace známá konstanta a je to malé číslo, bude efektivnější rozepsat cyklus takto:

s += a[0] * b[0];
s += a[1] * b[1];
s += a[2] * b[2];

  • Nulová režie na uspořádání cyklu

Tím se provede totéž, ale s nulovou režií na uspořádání cyklu.

Software pipelining

Původní kód (symbolicky):

Tato metoda se používá v případě, kdy na sebe vzájemně navazují výsledky operací, ale ve chvíli, kdy se začíná zpracovávat druhá operace, ještě není znám výsledek operace první (v důsledku vícekrokového zpracování pipeliningem). Procesor by tak musel čekat, až se dokončí první operace, aby mohl začít zpracovávat navazující operaci. Uveďme si takový případ na symbolickém kódu:

// original loop
for(i = 0; i < N; i++){
a = A(i);
b = B(a);
c = C(b);
}

Optimalizace: větší odstup operací

Řešením je ruční rozdělení operací tak, aby po sobě následovaly s větším odstupem:

// software-pipelined loop
a0 = A(0);
b1 = B(a0);
a1 = A(1);
for(i = 2; i < N; i++){
a = A(i);
b = B(a1);
c = C(b1);
a1 = a;
b1 = b;
}
b = B(a1);
c = C(b1);
c = C(b);

Pro pochopení tohoto příkladu je potřeba se nad ním chvíli zamyslet.

Práce s pamětí (Cache)

  • Mikrokontroléry: matematické operace nad registry i pamětí

  • Větší procesory: práce s pamětí je soušást optimalizace

Některé menší mikrokontroléry umožňují provávět matematické operace přímo s paměťovými buňkami. Jak jsme již řekli, u rychlejších procesorů tato možnost nepřipadá v úvahu a pro efektivnější práci s daty v paměti si pomáháme keší. Pokud přesuny mezi hlavní pamětí a keší nezajišťuje hardware samostatně, musí to být součástí návrhu optimalizovaného algoritmu.

SIMD

  • Menší přesnost: 32 -> 16 bitů

  • 2 x 16 bitů

  • 4 x 8 bitů

Pokud pro výpočet výsledku postačí omezená přesnost, např. místo 32-bitových operandů se spokojíme pouze s 16-bitovými, můžeme využít instrukcí typu SIMD, kdy se během jediného instrukčního cyklu spočítá více výsledků najednou.

V případě 32-bitového procesoru tak lze získat např. dva 16-bitové výsledky nebo čtyři 8-bitové.

Literatura

  • Dominic Sweetman: See MIPS run Linux. Morgan Kaufmann Publishers, 2007.

  • MIPS Technologies Inc.: Effective Programming of the 24KE™ and the 34K™ Core Families for DSP Code, 2007.

  • Oficiální dokumenty výrobců.

 
{e_like}
 
 
Nahoru