Beeldverwerkingstaal Halide belooft snelheid en leesbaarheid

Onderzoekers van het MIT hebben een nieuwe programmeertaal voor beeldverwerking ontwikkeld. 'Halide' zou het eenvoudiger moeten maken om software te schrijven, en optimalisaties zouden automatisch worden uitgevoerd.

Volgens de MIT-ontwikkelaars kent het schrijven van beeldverwerkingssoftware in reguliere programmeertalen diverse nadelen. Zo zou programmacode bijvoorbeeld vaak vrijwel onleesbaar zijn voor ontwikkelaars die een applicatie willen porten, omdat er veelal complexe optimalisaties worden gebruikt. Hierdoor moeten developers regelmatig geheel nieuwe code schrijven.

Developers van het Computer Science and Artificial Intelligence Laboratory van het MIT hebben daar naar eigen zeggen een oplossing voor, in de vorm van Halide. Deze programmeertaal voor beeldverwerking zou niet alleen leesbare code opleveren, maar ook automatisch optimalisaties kunnen uitvoeren. Door bestaande algoritmen in Halide te herschrijven zou de code niet alleen veel compacter worden, maar ook aanzienlijk beter presteren; bij bepaalde routines zou een snelheidswinst met een factor 70 mogelijk zijn.

De prestatiewinst zou te danken zijn aan het opsplitsen van de code: het algoritme wordt in Halide-code losgekoppeld van het processing schedule. Bij het porten van Halide-code naar een ander platform zou alleen het processing schedule aangepast hoeven te worden om de code voor de betreffende hardware te optimaliseren. Daarnaast kunnen experimentele optimalisaties sneller getest worden.

De Halide-programmeertaal is vrijgegeven onder een opensourcelicentie. De code kan gecompileerd worden op ARM-, x86- en gpu-architecturen.

Reacties (21)

[Xthemes.us]

Opensource license zal dan wel MIT license zijn aangezien het van de MIT komt. Erg interessant want dan zou het in principe bij The Gimp er in mogen worden gestopt.
Geen flauw idee of het makkelijk als 'drop in' replacement er tussen kan worden gestoken maar licentietechnisch zou mogelijk moeten zijn

Kan ze geen ongelijk erin geven dat beeldverwerkingscode moeilijk leesbaar is, ben erg benieuwd wat voor soort code dit dan moet zijn, iets XML achtigs, SQL achtigs? Ik ga eens even kijken of ik voorbeelden kan vinden.

[koelpasta]

Hier de vergelijking tussen C++ en halide (uit de paper)

(a) Clean C++ : 9.94 ms per megapixel

void blur(const Image &in, Image &blurred) {
Image tmp(in.width(), in.height());
for (int y = 0; y < in.height(); y++)
for (int x = 0; x < in.width(); x++)
tmp(x, y) = (in(x-1, y) + in(x, y) + in(x+1, y))/3;
for (int y = 0; y < in.height(); y++)
for (int x = 0; x < in.width(); x++)
blurred(x, y) = (tmp(x, y-1) + tmp(x, y) + tmp(x, y+1))/3;
}


(b) Fast C++ (for x86) : 0.90 ms per megapixel

void fast_blur(const Image &in, Image &blurred) {
m128i one_third = _mm_set1_epi16(21846);
#pragma omp parallel for
for (int yTile = 0; yTile < in.height(); yTile += 32) {
m128i a, b, c, sum, avg;
m128i tmp[(256/8)*(32+2)];
for (int xTile = 0; xTile < in.width(); xTile += 256) {
m128i *tmpPtr = tmp;
for (int y = -1; y < 32+1; y++) {
const uint16_t *inPtr = &(in(xTile, yTile+y));
for (int x = 0; x < 256; x += {
a = _mm_loadu_si128(( m128i*)(inPtr-1));
b = _mm_loadu_si128(( m128i*)(inPtr+1));
c = _mm_load_si128(( m128i*)(inPtr));
sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
avg = _mm_mulhi_epi16(sum, one_third);
_mm_store_si128(tmpPtr++, avg);
inPtr += 8;
}}
tmpPtr = tmp;
for (int y = 0; y < 32; y++) {
m128i *outPtr = ( m128i *)(&(blurred(xTile, yTile+y)));
for (int x = 0; x < 256; x += {
a = _mm_load_si128(tmpPtr+(2*256)/8);
b = _mm_load_si128(tmpPtr+256/8);
c = _mm_load_si128(tmpPtr++);
sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
avg = _mm_mulhi_epi16(sum, one_third);
_mm_store_si128(outPtr++, avg);
}}}}}


(c) Halide : 0.90 ms per megapixel

Func halide_blur(Func in) {
Func tmp, blurred;
Var x, y, xi, yi;
// The algorithm
tmp(x, y) = (in(x-1, y) + in(x, y) + in(x+1, y))/3;
blurred(x, y) = (tmp(x, y-1) + tmp(x, y) + tmp(x, y+1))/3;
// The schedule
blurred.tile(x, y, xi, yi, 256, 32)
.vectorize(xi, .parallel(y);
tmp.chunk(x).vectorize(x, 8);
return blurred;
}

(edit, jammer van de smilies maar ik mag dat blijkbaar niet achteraf veranderen).

[Reactie gewijzigd door koelpasta op 24 juli 2024 18:30]

[Angelus1753]

Het lijkt wel wat op linq als ik dat zo zie (visueel)

[MSalters]

Hmm, misschien moet ik mijn M.Sc thesis uit 1999 eens opsturen. Ik heb daar al laten zien dat de tegenstelling tussen "Clean" en "Fast" C++ een schijntegenstelling is. Met Template MetaProgramming kun je de benodigde optimalisaties door de C++ compiler laten uitvoeren. Die hoeft niet extreem slim te zijn: de C++ template functionaliteit is Turing-compleet. Dat wil zeggen dat je met templates alle problemen kunt oplossen die met computers oplosbaar zijn.

[Chip.]

Titel van thesis?

[thomasv]

Ik denk meer wiskundige complexe algoritmes, met o.a. matrix en vector berekeningen

[Xthemes.us]

Ik ken geen C(++) dus ik snap niet precies wat er in de whitepaper staat maar het lijkt er meer op dat ze een set chainable functies hebben gemaakt dan een programmeertaal. Sommige voorbeelden hebben bijna iets van jQuery weg maar het is inderdaad een stuk korter en overzichtelijker.

De snelheidswinst lijkt hem vooral in het parallelliseren (spelling?) te zitten.

[Tiberianchan]

Als ik de paper even skim dan lijkt een ander deel van de winst te komen doordat de programmeur kan aangeven of er direct doorgerekend kan worden met een output van een functie.

Soms is het bijvoorbeeld nodig om een heel plaatje te processen met één functie voordat de volgende functie aangesproken kan worden. Het tussenresultaat moet dus even in het geheugen opgeslagen worden. Maar als dit niet nodig is kan je gelijk door naar de volgende functie, zonder het geheugen aan te spreken. En dit levert naast de parallelisatie extra tijdswinst op.

Ook is het zo dat bepaalde beelverwerkings algoritmes veel efficienter werken als de invoer ter grootte is van machten van 2 (bijv 32, 128) . Misschien dat deze taal de plaatjes onderverdeeld in kleinere plaatjes met deze groottes, zodat deze sneller verwerkt kunnen worden.


Het is wel heel gaaf dat dit ook op de ARM architectuur werkt. Misschien zou je hiermee zelfs real time beeldverwerking op mobiele telefoons kunnen uitvoeren. Dan zijn hele gave dingen mogelijk (kan alleen nu even niks bedenken)

Edit:wilde nog even deze quote uit de white paper delen:

closing this gap requires ninja programming skills

[Reactie gewijzigd door Tiberianchan op 24 juli 2024 18:30]

[froggie]

Het pipelined executeren van operaties op een kleiner deel van een image kan voor zo'n enorme snelheidswinst zorgen doordat de data van begin tot eind in CPU cache blijft en niet tussentijds van en naar memory gekopieerd hoeft te worden. Dit is dezelfde reden waarom sommige algoritmen in bepaalde block grootes opereren omdat deze dan in een of meer cache lines passen.

In essentie is dit een van de redenen waarom GPU's zo ontzettend veel sneller zijn in het uitvoeren van deze algoritmen; de architectuur is er volledig op gericht deze berekeningen zo parallel en met minimaal kopieren tussen memory segmenten uit te voeren als mogelijk.

[Verwijderd]

Soms is het bijvoorbeeld nodig om een heel plaatje te processen met één functie voordat de volgende functie aangesproken kan worden. Het tussenresultaat moet dus even in het geheugen opgeslagen worden. Maar als dit niet nodig is kan je gelijk door naar de volgende functie, zonder het geheugen aan te spreken. En dit levert naast de parallelisatie extra tijdswinst op.

Dat lijkt wel op barriers in opencl, Waarmee je in het programma kan aangeven dat het moet wachten to alle threads op dat punt zijn aangekomen. Zodat je afhankelijkheden kan creëren tussen threads in de zelfde werkgroep .

[Reactie gewijzigd door Verwijderd op 24 juli 2024 18:30]

[nnk]

Die quote "closing this gap requires ninja programming skills" verwijst naar een recent artikel van Intel onderzoekers:
"Can traditional programming bridge the Ninja performance gap for parallel computing applications?".

[Reactie gewijzigd door nnk op 24 juli 2024 18:30]

[Nactive]

Ziet er veelbeloven uit. Zeker indien gpu ondersteuning goed werkt kan dit nog wel echt een grote verbetering zijn.

[Xthemes.us]

De whitepaper heeft een hoofdstuk over het compileren voor CUDA dus GPU ondersteuning is aanwezig. Het lijkt erop dat ze wel naar OpenCL gekeken hebben maar niet gebruikt.

[Chip.]

Ben benieuwd... Probleem met beeldverwerking is vaak dat je een aantal verschillende algorithms hebt die je erop moet worden uitgevoerd. Deze algo's moet vaak over het gehele plaatje uitgevoerd worden. Stel dus het plaatje voor als een matrix, dan heb je vaak 2 loops nodig voor iedere functie. Al deze loops van de verschillende functies kun je eigenlijk samenvoegen waarna het vaak veel sneller draait. Dit is echter heel ingewikkeld omdat het ene algo 2x2 pixels nodig heeft, het andere 4x4, 3x1 etc... Je moet hier dan rekening meehouden, een bepaald algo mag dus niet zomaar starten maar pas als het algo daarvoor het aantal pixels heeft verwerkt dat het algo daarna nodig heeft.

[Reactie gewijzigd door Chip. op 24 juli 2024 18:30]

[trogdor]

Maar als je die individuele algorithmes al een factor n kan versnellen en toch leesbaar kan houden (zoals in de voorbeelden hier boven) dan heb je al een hele winst te pakken.

[koelpasta]

Algo is leuk enzo, maar die moet ook nog efficient naar de hardware gemapt kunnen worden.
Hierbij moet je rekening houden met cache, beschikbare rekeneenheden, SIMD woordlengte, geheugen bandbreedte, threading, etc,etc...
Kan dus zijn dat een algo op papier snel is, maar dat een implementatie op een GPU niet eens 10% performance weet te halen.
Het kan op een GPU bijvoorbeeld zo zijn dat het veel efficienter is om eerst 1 algo over alle data te doen en dan pas de volgende terwijl op een superscaler het sneller is om de twee algos achter elkaar op een stukje data uit te voeren.

En dat probleem lost die taal, voor zover ik het berijp, in ieder geval ten dele op.

[Cyberwizzard]

Het is jammer dat ze geen voorbeeld-code geven; de taal zelf bepaald in hoge mate hoe snel de acceptatie is. Overigens is het mooi dat de schedule (welke bepaald welk onderdeel van het algoritme waar draait en waar data vandaan komt en heen gaat) los staat van het algoritme zelf maar dat hebben we bijvoorbeeld in CUDA ook al: kernels.

Kortom: ik vraag me af of hun nieuwe taal een nieuwe wereldstandaard gaat worden (of zo bedoeld is) of dat het een academisch onderzoeksplatform is (wat ook verklaart dat we geen code en downloads er bij krijgen)...

[Herko_ter_Horst]

Give me da codez!

Func blur_3x3(Func input) {
Func tmp, blurred;
Var x, y, xi, yi;

// The algorithm - no storage or order
tmp(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3;
blurred(x, y) = (tmp(x, y-1) + tmp(x, y) + tmp(x, y+1))/3;

// The schedule - defines order, locality; implies storage
blurred.tile(x, y, xi, yi, 256, 32)
.vectorize(xi, .parallel(y);
tmp.chunk(x).vectorize(x, 8);

return blur_y;
}

[Reactie gewijzigd door Herko_ter_Horst op 24 juli 2024 18:30]

[Xorgye]

Euh, ik vindt t stoer klinken en ze hebben helemaal gelijk dat hun manier sneller is in de voorbeelden die ze gebruiken. Maar met de juiste software ontwerp patronen kan je ook gewoon cross-platform portable libraries maken die het algoritme los hebben liggen van domein specifieke context, en ultra-high performance zijn.

En als je het niet op kan lossen met software ontwerpen om het snel genoeg te krijgen en portable en threaded op de juiste manier en overzichtelijk, dan kan je altijd nog uitwijken naar code generatie...

Oftewel: leuk, Halide, zal vast wel een markt voor zijn. Maar een performance en onderhoudbaarheid unicum? Neuh, vast niet. En zo wordt het wel gebracht.

(Maar zelf zo'n platform ontwikkelen in C++ met de libraries en de codegeneratie als dit er al is, is een commerciële afweging waar andere factoren mee spelen dan de 'nadelen' en 'voordelen' die in het artikel genoemd zijn.)

[trisje]

sorry

[mg794613]

Ik vind het leuk dat ze iets nieuws proberen. Maar het lijkt wel alsof we tegenwoordig niet meer eerlijk kunnen zijn in onderzoeken.

Ze hebben gewoon een dialect gevormd met veelgebruikte algoritmes in videobewerking.
Een soort avisynth maar dan met C syntax.

Maar het wordt wel aangeprezen als "DE TOEKOMST" "ULTRASNEL".

Hou toch eens op! wees gewoon eerlijk en zeg dat je lekker aan het prutten bent want dat is het voorlopig. Niks nieuws.