Rust és jelfeldolgozás

Az alábbi bejegyzésben írtam, hogy általános célokra jó, de jelfeldolgozásra lassú a Rust, ezért utóbbira ha kellett a tempó, FFI-vel C-kódot raktam bele. Eddig.
Ugyanis a Rust fórumon megmutatták, hogy van erre is megoldás, ami még csak a nightly ágban van benne, de bíztató.

 

Ez a lassabb futású Rust által garantált eredményű kód:

   acc += sample[i] * coeff[j];

Ez pedig a "biztonsági öv kikapcs" és mehet a párhuzamosítás (NEON, SSE, AVX):

   #![feature(core_intrinsics)]
   use std::intrinsics::{fadd_fast, fmul_fast};

   unsafe {
      acc = fadd_fast(acc, fmul_fast(sample[i], coeff[j]));
   }

Mérésem szerint ilyen trükkök alkalmazásával a C-hez képest a jelfeldolgozás tempója mindössze 1,065-szörös lassulást mutat, azaz tulajdonképpen azonos sebességű lett.

A fent említett bejegyzésemben írtak tehát szintén megoldódni látszanak, így a jövőben a nagy futástempót igénylő jelfeldolgozó algoritmusok is C betét beillesztése nélkül, tisztán Rust-ban gyorsra megírhatóak.
Egyelőre viszont mint írtam, ez a trükk a nightly-build ágban található csak meg. Remélem az elkövetkezendő hónapokban a beta ágba majd a stable-ba kerül.

 

Az ilyenek mögött húzódó Rust filozófia is rendszeresen elgondolkoztat. Bár a Rust eddig is meglepett a biztonsági törekvéseivel, például hogy ilyen alaphibát se tudj ennyire belesimulóan a kódodban hagyni Rust esetén:

#include <stdio.h>

int main() {
    float a = 1./3.;
    int c = 4./a;
    int d = 4 /a;
    printf("4/(1/3) = %d\n", c);
    printf("4/(1/3) = %d\n", d);
}

Ellenben arra még kevésbé gondol a legtöbbünk, hogy a helyes eredményhez a sorrendhelyes végrehajtás is hozzátartozik. Mert hiába gyorsabb a párhuzamosítás (NEON, SSE, AVX), a nem azonos sorrendű aritmetikai utasítás végrehajtás okozhat a programban leírt algoritmustól várhatótól eltérő eredményt adó számítási hibát. Ez a hiba vagy elfogadható vagy nem az adott számításnál. Ezért a programozó ha el akar térni a Rust által garantált sorrendhelyes aritmetikától, például párhuzamosítható műveleteket akar helyette, akkor írja be az adott számításhoz az unsafe { ... } kulcsszót, és innentől a Rust átadja az ezzel járó felelősséget is a programozónak. Itt a programozó már szabadon eltérhet például a tempó miatt a sorendhelyes aritmetikától.

Hozzászólások

a nem azonos sorrendű aritmetikai utasítás végrehajtás okozhat a programban leírt algoritmustól várhatótól eltérő eredményt adó számítási hibát

Ezt kifejtenéd bővebben? A párhuzamosítás során (többek között) nem ugyanazok a véges pontosságú számábrázolásból származó problémák jönnek elő, mint soros végrehajtás esetén (pl. ha egy nagyon nagy számhoz akarok egy nagyon picit hozzáadni, akkor elveszhet a pontosság)? Legfeljebb "máshogy" hibás a végeredmény. Nem látom, hogy a Rust hogyan akadályozná meg a fenti problémát lebegőpontos számoknál.

Ráérezteél a lényegre. Más mértékben lesz hibás az eredmény, mint ahogy a matematikus az algoritmus alkalmazhatóságának vizsgálatakor kiszálmolta. És itt a lényeg.
Alapból a Rust például egy for () -ban levő { összeadás; kivonás; ... } részt ilyen sorrendben fog ismételve végrehajtani. Ezt a merev sorrendiséget csak akkor dobhatod gyorsan számolható szabadsorrendűre, ha kikapcsolod a Rust kontrolljait az unsafe { ... } kulcsszóval. Innentől egyúttal azt a felelősséget is átvetted, amitől eddig a Rust mentesített. Így van megoldva az, hogy a Rust biztonságos, de ahol kell, ott a kontrollt mégis képes neked átadni. Lásd: https://miro.medium.com/max/2406/1*fr1Gjc_bt6gB06fUlfQNPQ.jpeg

Innen visszatekintve a C nyelv annyiból gázos, hogy például van egy -O2 kapcsolóval fordított kódod, benne az érzékeny algoritmusoddal és sok például jelfeldolgozó cuccal. Az egyik okos kitalálja, hogy tempót kell növelni, -Ofast és a jelfeldolgozás csodásan megtáltosodik, a te precíz számításod, amit a matematikus megtervezett, a véges precizitás + ezúttal már szabadsorrendű aritmetika miatt a tervezettnél nagyobb hibázással számol.

Rust esetén nincs globális -Ofast, amivel az iménti C-s probléma előállna. Helyette unsafe { ... } környezetben lehet Rust kontrollja nélkül programozóként huncutkodni.
A kód felülvizsgálatakor (code review) pedig ezekre az unsafe { ... } blokkokra kell olyan szemmel figyelni, ahogy a kontroll nélküli C teljes kódbázisát kellene valójában felülvizsgálni.

Igen, azt értem, hogy a Rust e szempontból teljesen transzparens, azaz expliciten meg kell jelölni a "problémás" részeket egy unsafe blokkal. Én csak azt próbáltam mondani, hogy hiába használnék tisztán safe Rust kódot egy egyenlet kiszámolásához, ha lebegőpontos számokról van szó, akkor így is könnyen előfordulhat a véges számábrázolásból származó hiba. Ha kihasználom a hardver auto-vektorizációs képességeit, azzal nem feltétlenül lesz pontatlanabb a végeredmény, csak "máshogy" lehet hibás.

Nagyfrekvenciás jelfeldolgozást nem kódoltam még, azonban az alapkutatás során napi rutinfeladat volt parciális differenciálegyenletek megoldása 2 és 3D mezőkön GPU-val. Egy mai jó GPU felfogható egy ~5000 magos CPU-nak. Ha mondjuk egy float mezőn kell végeznem egy redukciót, akkor más lehet az eredmény, ha egyetlen thread megy végig a teljes mezőn, illetve ha thread-ek blokkjai végzik el párhuzamosan valamilyen felosztásban a redukciót a mező kijelölt részein, majd ezeket a részeredményeket a végén összeadogatom. Ettől a felosztástól nem szabad, hogy függjön a végeredmény. Ha mégis, akkor azt azt jelentette, hogy nem elég a számítás pontossága és át kell alakítani az algoritmust.

azzal nem feltétlenül lesz pontatlanabb a végeredmény, csak "máshogy" lehet hibás.

Előfordulhat, hogy soros végrehajtás esetén pontos a végeredmény, párhuzamos esetén meg teljesen rossz.
Ez pl. akkor fordulhat elő, hogy ha soros végrehajtás esetén minden lépés eredménye belefér a használt számábrázolás pontosságába, de párhuzamos esetén már nem.

Ez pl. akkor fordulhat elő, hogy ha soros végrehajtás esetén minden lépés eredménye belefér a használt számábrázolás pontosságába, de párhuzamos esetén már nem.

Mondanál valami egyszerű gyakorlati példát erre? Nem találkoztam még olyan problémával, ahol ez előfordult volna, kíváncsi vagyok.

Pl. Integer típus, a * b / c, ahol c != 0.  Ez matematikailag ugyanazt az eredményt adja (a * b) / c és a * (b / c) sorrendben elvégezve, sőt még (a / c) * b sorrendben is, de az egész számok halmazán nem. Pl. százalék számításnál (5 a 10-nek hány százaléka?): (100 * 5) / 10 = 500 /10 = 50%, de 100 * (5 / 10) = 100 * 0 = 0.
Biztos lehet találni jobban párhuzamosítható példát is, de hirtelen csak ez jutott eszembe.

Az általam használt terminológiában ez nem párhuzamosítási probléma, hanem inkább matematikai, hogy egy egyenlet milyen halmazon asszociatív.

A topikindítóban említett hardveres technológiák (SSE, AVX) meg SIMD megoldások, azaz ugyanazt a műveletet hajtják végre párhuzamosan egy adathalmazon. Én ebben a kontextusban használom a párhuzamosítás kifejezést, azaz hogy van mondjuk egy 100 millió elemből álló tömb, amin a GPU ~5000 magja blokkonként elvégez egy műveletet, mindenhol ugyanazt.

Lehet persze bizonyos fokig egy egyenletet is szétbontani különböző részeredményekre/részszámolásokra (MISD) és ezeket párhuzamosan kiszámítani egyetlen bemenő adaton, de ehhez elég spéci problémára van szükség. A párhuzamosítás akkor hatékony, ha a szálak kb. ugyanannyit számolnak. Ezt SIMD típusú megoldásnál sokkal könnyebb elérni szerintem, mint MISD típusúnál. (Bár hozzá tartozik, hogy MISD típusú problémát gyakorlatban még sosem kódoltam.)

Erre írtam, hogy nem a legjobb példa, de a párhuzamosításnál az utasítások végrehajtásának sorrendje változik a szekvenciálishoz képest, arra meg nagyon jó a példa.

Persze, ha az utasítások sorrendjének nincsen hatása egymásra, akkor nincs ilyen gond. Ha van hatása, akkor lehet ilyen gond.

Itt egy valós példa a sorrendre, Scala kód:

(1 to 4)
  .reduce((a, b) => a - b)

 Ennek az eredménye -8. Mivel 1 - 2 - 3 - 4 = -8.

(1 to 4)
  .par
  .reduce((a, b) => a - b)

Ugyanazt párhuzamosan futtatva, az eredménye 0. Mivel (1-2) - (3-4) = 0.

(100.000.000 elemre is működik)

Egy végtelenül leegyszerűsített aritmetikai példa, amin látszik hogy a kerekítési hibák miatt a precíz számítás követelményekor a sorrend nem térhet el a matematikus által előírttól:

fn main() {
    let a: f32 = 200.;
    let b: f32 = 190.;
    let c: f32 = 0.02;
    let d: f32 = 0.01;

    println!("a-b+c-d: {}", a-b+c-d);
    println!("a+c-b-d: {}", a+c-b-d);
}

És most képzeld el, te írod le a matematikus által megfogalmazott algoritmus-beli sorrendet, vagy engeded hogy a sebesség oltárán a precedencia szabályok mentén, de a fordító szabadon (véletlenszerűen) párhuzamosítson? Rust esetén unsafe { ... } és TE dönthetsz, hogy randomizálhat-e. Vagy maradunk a "default" safe-területen és a Rust megvédi a matematikustól származó eredeti műveletsorrendet.

Mas nyelveken ezt nem unsafe-fel oldjak meg, hanem reduce-szal (meg persze van map, filter, meg par hasonloan mukodo parancs). Ha szamit a muveletek sorrendje, akkor egy ciklust kuldesz vegig az adataidon, ami az altalad eloirt fix sorrendben csinal mindent. Ha nem szamit, akkor jon a map/reduce es tarsai, amik meghagyjak a dontest a fordito/futtato kornyezetnek, es az ha ugy gondolja atvarialja a muveleti sorrendet, ha szeretne parhuzamosit, esetleg kiszervezi GPU-ra/felhobe/akarmi. Az algoritmusod leirasa (a kod) meg nem valtozik attol, hogy az interpretered epp milyen beallitassal es hogy fut.

Regi, de jo: https://www.joelonsoftware.com/2006/08/01/can-your-programming-language…

When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin

Ezek az iterátorok Rust-ban is megvannak.

fn main() {
    let v: Vec<f32> = vec![200., 11., -190., 12., 0.02, 13., -0.01, 15.];
    let s: f32 = v.iter()
                  .filter(|&x| *x < 10. || *x > 20.)
                  .sum();
    println!("Eredmény: {}", s);
}

https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.map
https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold    = reduce
https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.filter

Ellenben Rust esetében ezek is sorrendhelyesek.
Ha ettől el akarsz térni, akkor kapcsold ki a biztonságot és C-hez hasonló szabadságot kapsz ebben az unsafe { ... } részben, akár bare metal programming célokra is.

Nem tudom melyik nyelvekről beszélsz, de általában ahol map, filter, reduce van, ott vagy mindegyik szekvenciálisan fut, vagy lehet valamilyen módon szabályozni, hogy szekvenciálisan vagy párhuzamosan fussanak.

Ez utóbbi jellemzi az FP nyelveket.

  • Egyrészről miért kellene máshogy megírni a szekvenciális futást, ha a map, filter, reduce, ... funkciókkal megírtat is lehet szekvenciálisan futtatni?
  • Másrészről, igazi FP nyelveknél nincs is ciklus. ;-) A majdnem igaziaknál meg nincs szükség rá (pl. Scala).

TLS-01-002: Elgondolkoztató. Ebbe a csapdába már párszor én is beleestem. Jó az unwrap(), kezdőként sokat segített. De ez tényleg az amit szintén módjával kell használni.

https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap
https://doc.rust-lang.org/std/result/enum.Result.html#method.unwrap

akármi().unwrap();      // Elszáll a startnál None/Err(_) esetén, de legalább tájékoztat a panic!()-ba dobott üzenettel az okáról.
...
loop {
      bigyó().unwrap(); // Jól gondold meg, a hónapok óta futó démonod ezért a trehányságért fog éjjel panic!()-kal kiugrani,
                        // miközben ténylegesen lekezelhető lett volna.
}

Helyette match ..., if let Some(x) = ...  vagy if akármi().is_some()  netán .is_none(). Result esetén .is_ok() vagy .is_err(). Le kell ténylegesen kezelni a hibát.
Esetleg unwrap_or(más) ... ez None/Err(_) esetén a más-t dobja be. De nem panic!()-ot. Az unwrap_or_else(függvény vagy closure). Továbbá ott van még a ? is, ami szintén jól használható.
Szóval van bőven szép megoldás a hibás érték lekezelésére az odahajított unwrap() helyett.

A többi ahogy elnézem, algoritmus implementálási hiba. Arról egyáltalán nem a nyelv tehet.

Szerkesztve: 2020. 06. 15., h - 14:20

sub

Amit nem lehet megirni assemblyben, azt nem lehet megirni.