flugi szakblogja

Egyik alkalommal előadásra készülve írtam egy klasszikus rekurzív visszalépéses keresést a 8 királynőre. Az OpenMP elhozta a kényelmes párhuzamosságot, így kipróbáltam a párhuzamosítását a rekurzív lépésnek. Ez azt jelenti, hogy a függvény több szálat indít arra, hogy a következő lépéslehetőségeket kiértékelje, amik szintén több szálat indítanak, stb, stb. Józan paraszti ésszel erre gondolva azt várja az ember, hogy a sokezer szál óriási overheadet okoz, és meghal, vagy belassul az egész folyamat.

Ehhez képest a program gyorsult, kb 1.6x sebességnövekedést mértem egy 32 bites Atomon, ami nem is igazi kétmagos, csak hyperthreadinges. Két lehetséges magyarázatot tudok elképzelni

• Az OpenMP runtime okos, és nem csinál overheadet, hanem csak egy kis létszámú szálcsoportot enged egyszerre futni, a többit altatja. Ebben az esetben ez egy kellemes technikai trükk.
• A feladat jellegéből adódóan a jó választások lehetősége a rekurzió mélységével csökken, és ez egyfajta önszabályozást valósít meg az egyébként limitálatlan szálszámok esetében is. Ebben az esetben ez egy izgalmas jelenség egy feladatcsoportról.

Ha lesz komment, talán rakok ide forrást is, játszani.

Olvastam többfelé a problémáról, de megoldást nem találtam, úgyhogy hátha közérdekű.

A probléma: a dselect a fejébe veszi, hogy kismillió csomagot akartál leszedni, köztük egy sor alapvetőt. Install közben rá is kérdez, hogy ugye tényleg tönkre akarod csapni a rendszert.

A reakció: néhányszor elindítod a dselectet, keresve azt az opciót, hogy "legyen minden olyan, mint most", de nem találod. Ezzel (a többszöri indítással) a backup fájlt is törölted, mellesleg.

A legszimpatikusabb rossz ötlet: apt-get purge dselect; apt-get install dselect, de sajnos nem működik, a purge általában töröl minden járulékos fájlt, de a dselect ellen nem véd.

A megoldás: sudo editorban megnyitod a /var/lib/dpkg/status fájlt, és replace "tus: deinstall" -> "tus: install"

class FM : public Danubius

Kis látványosság nagy munkáról itt.

Az egyik memóriakártyámon vírust találtam, ami nem hagyta magát letörölni, mert valahogy elhitette a windowssal, hogy a kártya írásvédett. Ezen az sem segített, hogy linux alól simán töröltem a trójai binárisát és indítóját (autorun.inf, elég botor). Formázni bizony nem tudtam utána sem, írásvédettség.

Bezzeg mikor beraktam a Nikon D80 fényképezőbe, az darálta a fájlrendszert kérdés nélkül. Legjobb. Ha formázni akarok, akkor nincs szükség lacafacára.

Az NVidia megnyitotta az early access programját, amihez azóta megkaptuk a hozzáférést. A letöltött OpenCL meghajtót teszteltük windows és linux alatt is, a korai CUDA teljesítményét hozza 8800GT-n, ami nagyon ígéretes.

Az AMD kiadta nyilvános béta verzióban a procin futtatott OpenCL-t. Kiváló debuggolni, próbálgatni, bár jelenleg sok szolgáltatás még nem készült el benne.

Haladunk. Most már szinte teljesen biztos, hogy tavaszi félévben kezdjük az oktatását.

Egy jóbarátom felhívta a figyelmemet a GCC 4.4 egy olyan portjára, ami nem a mingw project, hanem egy attól független csoport buildje. Egy nagyon windowsos release lett, aki szeret kattingatva installálni, annak kötelező.

Letölteni innen lehet

Letölt, indít, next-et kattingat, örül.

És ha ez nem lenne elég, még néhány lépésben a Code::Blocks(CB)-ban is beállítható. CB megnyit, Settings/Compiler menü, és a jól működő hagyományos MINGW GCC beállításait copy új néven, mondjuk GCC 4.4. Ezt kiválasztva a toolchain fül alatt a megfelelő neveket beállít (ez lényegében a "mingw-" előtétek törlését jelenti). Mivel OpenMP nélkül lassan nem élet az élet, emellett a Compiler settings fül alatti Other options ablakba egy "-fopenmp" kerül, és hogy le is forduljon, a linker settings alatti link libraries-be a libgomp.a a megfelelő helyről beírandó.

És máris megy a legfrissebb GCC, OpenMP támogatással windows alatt, színes-szagos fejlesztőkörnyezetben. Teszteltem az OpenMP-t, fájlkezelést, és wxWidget-et (wxSmith-el), ezek mennek, debugger is megy. Juhé!

Zenészekre szokás mondani, hogy

1. Először bénán és egyszerűen játszik
2. Aztán bonyolultan és rosszul
3. Aztán bonyolultan és jól
4. Végül egyszerűen és jól.

Nos, a programozásnál ez még sokkal inkább így van.

Igen, beadandókat javítok.

Jep. Összekaptam magam egy nehéz hét után, és legyűrve a lustaságot, nekiveselkedtem az új videókártyámat igazi programozóhoz méltó módon letesztelni.

A kártya egy AMD Ati HD4670, játékokat nagyon viszi, kicsit volt drágább húszezer forintnál.

Hozzávalók:

• Brook és Cal 1.2
• Visual Studio Express 2008 C++
• a kártya meghajtóprogramjai

A hozzávalókat feltelepítjük. Az első probléma, hogy az AMD Stream kit egy korábbi studioexpresshez készült, ezért a programok egy részét újra kell fordítani. Ezt arról lehet felismerni, ha esetleg azt a hibát kapnád, miszerint

No appropriate map technique found

Ez tehát azért van, mert nem stimmelnek a futásidejű állományok a verziók között, ezen viszont segíthetsz néhány egyszerű lépésben

1. Nyisd meg a  "$(BROOKROOT)\platform\brook.sln" projectet
2. Ha nem 32 bites rendszeren nyomod, javítsd ki a  'Project Properties' - 'Linker' - 'General' - 'Additional Library Directories' bejegyzést "$(CALROOT)\lib\LH64" vagy az egyéb platform nevére (kileshető a fájlnevekből)
3. illetve a 'Build Events' - 'Post-Build Event' - 'Command Line to read' 'copy "$(TargetDir)\$(TargetFileName)" "$(BROOKROOT)\sdk\lib\" (Program Files (x86)' bejegyzés verziótól függően tartalmazhat szóközöket, ezek hibásak, törölni kell
4. A "runtime" projectet fordítsd újra mind release mind debug módban. Ez a lényeg.
5. Végül a megfelelő .lib fájlokat másold át a "$(BROOKROOT)\platform\runtime\lib\xp_x86_64" típusú helyről (itt a saját platformod van) a "$(BROOKROOT)\sdk\lib" könyvtárba

(köszönet ezért bizonyos foxx1337 fórumozónak)

No most már nagyon jó a helyzet, ugyanis ha bármelyik példaprogramot megnyitod a VS2008-ban, frankón lefordul és fut.

A példaprogramok között sokféle van, nekem Gigaflop hajhászáshoz elsőre legmegfelelőbbnek az optimized-matmult tűnt. Egy egy unrolled mátrixszorzás, ami a Gigaflopvadászok mindenkori kedvenc totemállata. Hát még GPU-n, ugyebár.

Nos, a program az alapbeállítások mellett a GPU csúfos vereségét hozza ki, na de az alapbeállítás egy 64x64 mátrix egyszeri szorzása. Ez olyan, mintha Concorde járattal mennék a sarki trafikba. Egy tisztességes GPU-nak való feladat ennél szebb, egyrészt a mátrix nagyobb, másrészt ismételjük meg a műveletet néhányszor. Ez utóbbi már fekszik a GPU-nak, arra találták ki, hogy csörgedezzenek az adatfolyamok. 1280x1280 mátrixnál (semmi extra hátsó szándék, csak megúntam a 128x128-at), 1000 iteráció még kivárhatóan lefutott, körülbelül egy percig tartott. Ez pedig 56 GigaFlop.

Ha esetleg volt sok pénzed nagyobb videókártyákra, esetleg 4870x2-re, a fentieket futtasd le te is, kíváncsi vagyok az eredményekre. Ha skálázható az eredmény, akkor a HD4670 320 kisprocija mellett a 4870x2 1600 kisprocika az 56 GigaFlopot arányosan 280 GigaFlopra nyomja fel. (sőt, erős a gyanúm ennek komoly túlteljesítésére a megnövelt memóriasebesség miatt) Az előző postban teraflopokat ígértem, de ez egy gyakorlati feladat, nem igazán reális ezt elérni.

Miért nem lehet elérni a maximális elméleti teljesítményt? Mert ahhoz az kéne, hogy minden matematikai művelet pontosan annyi ideig tartson, ameddig a következő művelethez szükséges memóriaműveletek, így a kisproci nem vár a memóriára. A mátrixszorzásban csak szorzás van, ez vélhetően hamarabb befejeződik, mint a memóriamozgatás. Emellett jelentős overhead a szálak szinkronizálása, és az adat elosztása, ezek skálázhatósági kérdések is.

Update: elérhető a 72 GigaFlop is ugyanezzel a programmal

Hamarosan kezdődik, idén decemberre ígérik az OpenCL nyitását. Öröm és boldogság, ezt érdemes lesz követni.

Miről van szó?

Az OpenGL ugyanannak a Khronos csoportnak a neves terméke, és bár ellentmondó hírek jöttek a friss verzió fogadtatásáról, az OpenGL fundamentumához nem fér kétség, rendes ipari szabvány 3D grafikában. Ez pontosan az az alaposság, magabiztosság és piaci napi harcokon felül állóság, amire az OpenCL által érintett területnek szüksége van.

Vannak ugye a videókártyák. Ezen post írásakor már évek óta adott egy trend a videókártya architektúrákban, ami például az NVidiánál a 8000-es szériával indult, és aminek a lényege, hogy nem bedrótozott shader vagy textúrázó van a kártyán, hanem sok mindentudó kisproci. Ha az egyik alkalmazásnak sok shader kell, de alig kell textúrázó, akkor úgy programozza fel, egyébként akár fordítva.

Na most ez ugye örömteli, mert az ember azonnal neki akar állni ezeket megprogramozni valami egészen más célból, mondjuk képelemzés, hangelemzés, neuronhálózat, kódtörés, és hasonló számításigényes feladatokhoz. Ehhez az NVidia adta a CUDA-t, az ATI a CTM-et, majd a CAL-t. És most (kanyar vissza a főtémához) komoly esély van arra, hogy ugyanaz a dolog mindkettőn elmenjen. Ez lenne az OpenCL.

Ez azt jelenti, hogy néhány héttel a végleges megjelenés után lesz gyártófüggetlen hardvergyorsított fizikai szimuláció engine játékokhoz. Ez azt is jelenti, hogy mivel ma már csak elvétve lehet kapni videókártyát, ami nem általános GPU-val felszerelt, akár tetszőleges program nekiállhat használni a videókártyát! Tömörítés, codec, képfeldolgozás, stb.

És ez mitől kunszt? Attól, hogy jelenleg a videókártyák számítási teljesítménye kizárólag a számításhoz felhasználható utasításkészlet választékában maradnak el a CPU-któl, minden másban jobbak már, nyers sebességben egy csúcsvideókártya akár húszszor (!) gyorsabb lehet a processzornál. Ennek csak az a feltétele, hogy a problémának legyen jól párhuzamosítható (akár 800 szál fut a videókártyán) megoldása, amiben lehetőleg elemenként nincs elágazás, és többet kell összeadni-kivonni, mint kommunikálni a többi hardverrel. És hát ilyen minden sok-adat-kevés-változatosság probléma, mint a képfeldolgozók meg a kódtörők.

Azt jóslom, hogy 2009-ben a hardcore gamer arcokon kívül a hekkertársadalom is rajta fogja tartani a szemét a videókártya piacon, éppúgy, mint a csóró, szuperszámítógépetlen hazai kutatótársadalom. Itt vannak a teraflopok.

mégsem lesz párhuzamos neuronhálótanító, a 4.3-as mingw úgy tűnik nem tud fájlt olvasni az ifstream-ből. Mégiscsak meg kell várni a stable kiadást, vagy feltenni egy linuxot. Hmm..

Segíts nekem egy teszt kitöltésével. Néhány nap múlva, ha van érdeklődés, akkor csinálok egy bejegyzést arról, hogy mi is ez.

Szép párosnak ígérkezik. Az OpenMP egy párhuzamos programozási eszköz, nagyon finoman oldja meg a platformfüggetlenül párhuzamos vezérlést, egyetlen komoly baja, hogy üzenetalapon hatékony architektúrákon nem az igazi, dehát a mai sokmagos procik nem is ilyenek. A MINGW a GNU ingyenes fordítója Windowsra.

A GCC a 4.2 verzió óta tudja az OpenMP-t. Engem ez meglepett, mert az OpenMP #pragmákkal működik, és az utolsó tapasztalatom szerint a GCC nem szereti a pragmákat. Tényleg fura, hogy valamit teljesen a fordítóra bíznak, ki hogy akarja csinálni, de úgy tűnik az évek alatt hozzászoktak a gondolathoz. Mindenesetre azt mondják, hogy a GCC platformfüggetlenségéhez jól passzol az OpenMP. Ez pedig jogos.

Mármost, mint friss kétmagos processzor tulajdonos, viszketett a markom, hogy csak ki kéne próbálni a párhuzamosságot ezzel a cuccal. Korábban játszottam párhuzamos programozással PVM-ben egyetemi beadandók erejéig, meg SDL féle szálakkal, de az OpenMP eleganciája lenyűgözött, úgyhogy most ezzel kell.

Na most ez nem sétagalopp. A legfrissebb hivatalos MINGW-ben jelenleg a 4.1.2-es GCC van, amiben még nincs OpenMP. Úgyhogy le kellett rántani a alpha tesztes 4.3-asat. A friss hivatalos MINGW-t szépen lemásoltam, és az 4.3-assal amit lehetett, felülírtam.

Jött a parancs, hogy
C:\gcc430a\bin\g++.exe -fopenmp  main.cppDe ez fordítási hibával leállt:
c:/gcc430a/bin/../lib/gcc/mingw32/4.3.0/libgomp.a(parallel.o): (.text+0xe): undefined reference to `_imp__pthread_getspecific'
...
A hiba lényege, hogy nem csatolt kellőképpen libeket egy rosszul beállított .spec miatt.

A hibát okozó file:
lib\gcc\mingw32\4.3.0\libgomp.spec
A tartalma helyesen (érdekes módon egy francia oldalon találtam rá, most már francia mellett magyarul is fent van a neten:D) :
# This spec file is read by gcc when linking.  It is used to specify the
# standard libraries we need in order to link with -fopenmp.
*link_gomp: -lgomp -lpthread
És így már megy is.
Itt egy tesztprogram, hogy meg lehessen nézni, hogy működik-e:

/****************************************************************
* FILE: omp_hello.c
* DESCRIPTION:
*   OpenMP Example - Hello World - C/C++ Version
*   In this simple example, the master thread forks a parallel region.
*   All threads in the team obtain their unique thread number and print it.
*   The master thread only prints the total number of threads.  Two OpenMP
*   library routines are used to obtain the number of threads and each
*   thread's number.
* AUTHOR: Blaise Barney  5/99
* LAST REVISED: 04/06/05
****************************************************************/
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>

#include <cmath>

int main (int argc, char *argv[]) {

int nthreads, tid;

/* Fork a team of threads giving them their own copies of variables */
#pragma omp parallel private(nthreads, tid)
  {

  /* Obtain thread number */
  tid = omp_get_thread_num();
  printf("Hello World from thread = %d\n", tid);

  /* Only master thread does this */
  if (tid == 0)
    {
    nthreads = omp_get_num_threads();
    printf("Number of threads = %d\n", nthreads);
    }
   
  //everybody work for a while 
  double d;
  for (int i=0;i<1000000000;i++) {
    d += sqrt(i);
    if (i%100000000==0) printf("(%d %d) ",i/100000000,tid);
  }

  }  /* All threads join master thread and disband */

}
Magyarázat: A hivatalos példaprogramot kicsit átalakítottam, hogy meg lehessen nézni két dolgot. Az egyik, hogy mindkét procit láthatóan terheli-e (igen), a másik, hogy a párhuzamos blokkokban deklarált változók szál-privátak-e. Az int i a blokkban jól működik, amire bizonyíték, hogy mindkét szál (kétmagoson) mind a 10 alkalommal kiírja az értékét. Ha a két szál ugyanazt a változót használná, ennek a valószínűsége ilyen körülmények között igen alacsony.

Úgy érzem, hamarosan felturbózom a neuronháló tanító programot párhuzamosra! :)

Ez egy klasszikus probléma. A legtöbb informatikai oktatási intézményben az a szemlélet megy, hogy a program magától kikerekedik a hozzáértő programozó kezében, a kezdő kezében amolyan krumpli alakú, a rutinosnál meg szép sima gömbölyű. Emögött egy kettősség van.

Egyfelől a programozás mechanikusságát sugalló hozzáállás szerint a program csurom objektív ok alapján szigorúan következtetéses alapon előállítható. A rutinos már jobban ismeri a szabályokat, jobban tudja kihasználni azokat.

Másfelől a programozási készség kialakulása a klasszikus hmm. Valahogy lesz. Sokkal inkább példák alapján, mint szabályok alapján. Sok gyakorlással.

Próbáljuk meg ezt megfejteni. Ha épp erre jársz, egy kommentben a véleményed hagyd itt.

Jupi!

Finomított template kezelés, nyelvi elemek a párhuzamos programozáshoz, egyszerűsített szintaxis. Tisztára olyan ez, mint a reformáció, a C++ mára a katolikus egyház lomhaságával követi az idők szelét, lényegében minden valamirevaló nyelv már évek óta tartalmaz hasonló megoldásokat. Reméljük a változás megfontoltsága valóban kiforrott és időtálló megoldásokat eredményez. Mindenesetre már csak legfeljebb 610-et kell aludni, ha minden igaz, a C++0x már hivatalosan is C++09.

Néhány válogatott finomság a vonatkozó wikipédia oldalról:
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)Tehát a hosszadalmas iterátor deklaráció helyett egyszerűen auto. Úgyis világos a típusa a begin()-ből (ugye bizonyos nevű bizonyos paraméterlistájú függvénynek már egyértelmű a visszatérési típusa), és legalább használjuk valamire az "auto" kulcsszót is.

Aztán, lesz tuple:
A tuple ugye az a különleges öszvér, ami egyszerre rekord, mert különböző típusú elemekből álló közös adatszerkezet, és közben indexelhető, mint egy vektor. Eddig csak a boost könyvtárból ismertük, ahol template trükközéssel megoldották.