15.000 szál kezelése C++-ban

15.000 szál kezelése C++-ban
2010-08-01T00:18:10+02:00
2010-08-08T11:44:02+02:00
2022-11-18T18:20:41+01:00
bluediam
Létre kéne hoznom kb 15.000 objektumot amik gyakorlatilag egy mozgást szimulálnak.
Egy objektum elindul mondjuk 8:12:13mp-kor a célállomása pedig mondjuk 12:00:10mp.
Ilyenből lenne kb 15.000 egyszerre.
Ha beér akkor lefutna egy ellenőrzés a többi objektummal, hogy ütközik-e meg hasonlók. Minden célpontnak van egy egyedi azonosítója így egyszerű a képlet.

Első ránézésre minden objektumhoz rendelnék egy szálat csak nem tudom, hogy mit lépne erre a program és az OP rendszer (Linux), hogy egy programban létrehozok ilyen sok szálat.

Ha NEM külön szálon megy tartok tőle, hogy nem tud lefutni 1mp alatt az a függvény ami pl a mozgásukat figyeli és alakítja.
Mivel a szoftver valós időben fut így csak egy web-es betekintő felületet kéne készítenem ahol meg tudja nézni az user, hogy melyik objektum hol tart.
Mutasd a teljes hozzászólást!
Atomic műveletek a barátaid. Ha egy processzoron fut a két szál, akkor is összeakadhat, normál megoldással. Nézelődj Thread Building Blocks háza táján, az segítség lehet sok olyan problémára ami felmerült itt.
Mutasd a teljes hozzászólást!

  • Szia!
    Én a Windowst és az OpenCL-t javaslom a célodhoz. (Azért a Windowst, mert tudtommal ahhoz van nagyobb támogatása.)

    Ez a videó magáért beszél. Meg a többi is.
    A lényeg az, hogy a számítást a GPU-ra rakja át, ahol amint látod, töredékidő alatt elvégzi a sok kis, apró számítást.

    Nem használtam még soha, mert nem volt rá szükségem, de pl. Visual C++-ban nagyon egyszerű a használata. Biztosan találsz példakódokat a neten. Csak 15.000 testhez ne felejts el beszerezni egy tápos videókártyát.
    Mutasd a teljes hozzászólást!

  • Ha NEM külön szálon megy tartok tőle, hogy nem tud lefutni 1mp alatt az a függvény ami pl a mozgásukat figyeli és alakítja.


    Ekkora okorseget mar reg hallottam. 15000 szalon elvegezve ugyanazt a muveletet sokkal tovabb fog tartani mint 1 szalon, mivel a szamitasmennyiseg mellett meg a szalkezeles overheadjet (context switching es a szalkezelo sajat muveletigenye) is meg kell fizesd.

    Ha 1 szalon nem tudod megfeleloen optimalizalva kello ido alatt lefuttatni a szamitasokat, akkor tobb szalon se fogod tudni.
    Mutasd a teljes hozzászólást!
  • Ez 1 db. CPU esetén még talán igaz is lenne. De nem hiszem, hogy 1 magos a CPU-ja. A GPU-t felhasználva pedig a sebesség tovább nő, mert ott nagyon erőteljes a párhozamos feldolgozás.
    Nézd meg a belinkelt videót.

    Más: A félreértések elkerülése végett: Az OpenCL-nek semmi köze nincs a grafikához azt leszámítva, hogy a videókártya számítási teljesítményét használja ki.
    Mutasd a teljes hozzászólást!
  • Bocs, valoban, kicsit tul altalanosan fogalmaztam.

    Amit mondani akartam, hogy ha 1 szalon nem tudja idoben lefuttatni akkor 15 ezer szalon se fogja tudni idoben lefuttatni.

    Altalanossagban nem erdemes tobb szalat futtatni mint ahanyat a hardver tenylegesen parhuzamosan futtatni tud, ha nem kell valamire varnia a cpu-nak (ami tiszta szamitasi feladat eseten fennall).

    Egesz biztos vagyok benne hogy nem olyan gepen fogja a programot futtatni ami 15 ezer cpu core-al rendelkezik.
    Mutasd a teljes hozzászólást!
  • Még ezt akartam megmutatni. Itt közvetlenül megy az összehasonlítás és még a kódot is mutatják egy picit.
    Mutasd a teljes hozzászólást!
  • Altalanossagban nem erdemes tobb szalat futtatni mint ahanyat a hardver tenylegesen parhuzamosan futtatni tud, ha nem kell valamire varnia a cpu-nak (ami tiszta szamitasi feladat eseten fennall).


    Ez igaz.
    Mutasd a teljes hozzászólást!
  • Ha több magos a proci, akkor van értelme talán több szálra bontani (néhányra), de amúgy egy szál is elég erre.

    Időben nem tudom hogy jön ki, kérdés mennyi számítást kell végezni egy-egy objektumhoz.

    De ha nem túl bonyolult a feladat, akkor lazán tud számolni 15.000 objektumot a gép. Főleg ha sok lebegőpontos szorzás nincs benne. Nem tudom az 1mp "időlimit" honnan jön, de ha ügyes vagy akkor az sem okoz gondot, ha túlléped ezt.

    Az egyszerű feladat, hogy 15.000 változót minden körben (másodpercenként) növelsz egyel. Plusz vizsgálod, hogy elérte e a beállított időt.
    Kérdés, hogy az "ütközést" hogyan és mikor akarod vizsgálni. Ez lehet egyszerű is. De ha véletlenül több száz-ezer objektum ütközik, akkor túl léphetsz a megadott időn (főleg ha sok osztás-szorzás van). De ezt utólag megtudhatod, és korrigálhatod.
    De lehet ennél jobban kellene ismerni a feladatot, mert ez még homályos.
    Mutasd a teljes hozzászólást!
  • A több szálat azért akartam használni, hogy az OP rendszerre hárítsam a dolgot.

    A lényeg, hogy egy objektum elindul akkor csak azt kell figyelni, hogy:
    A, megszakítja-e az utat valami
    B, odaért-e a célba
    C, megváltozott-e a cél

    A leglényegesebb, hogy pontosan akkor érjen be amikorra írva van vagyis valós idejű legyen a dolog.

    Szálkezeléssel egyszerűbb lenne leprogramozni és nem kéne annyit vacakolni az optimalizálással.
    Ezen kívül stabilabb is talán, mert ha egy szál leakasztja a procit attól még a processzor elvileg meg tudja oldani, hogy attól elveszi a processzoridőt, de a többi rendesen fut.

    Amikor beér az objektum akkor van egy kicsit nagyobb számítási feladat végignézni, hogy ki van még ott és eldönteni mit csináljon.
    Ezzel szemben, ha egy szálon futtatom akkor minden "lépéskor" végig kell néznem, hogy mi mit csinált ami az esetek 99%-ban annyi, hogy semmit.

    Ellenben több szálon csak egy sleep vagy hasonlót kéne kiadnom:
    Ha az utazás 600 mp akkor sleep(600) és majd amikor odaért felébresztem.
    Ha meg közben történik valami akkor megszakítom a szálat.
    Mutasd a teljes hozzászólást!
  • Minél több a szál, annál lassabb. (Legalábbis akkor, ha több szál van, mint CPU (-mag))
    Mutasd a teljes hozzászólást!
  • Nekem az a benyomásom, hogy jobban értenénk az egészet, ha többet írnál a feladatról. Szerintem ráférne erre a problémára a modell átgondolása.

    Ezek a dolgaid pontszerűek? Egyenes mentén mozognak? Síkon, térben? Akkor szakítják meg egymás útját, ha összeütköznek?

    Amit leírtál abból én lehet, hogy még inkább a másik irányban gondolkoznék, és nem is objektumokat, hanem valami nagy állapottömböt csinálnék. És ha minden áron párhuzamosítani akarnék, akkor ezután bontanám a teret részekre. Az biztos világos, hogy 15000 objektum esetén ha bármelyik bármelyikkel kölcsönhatásba kerülhet, az 200 milló fölötti lehetőség.
    Mutasd a teljes hozzászólást!
  • Csak eljátszok a gondolattal, hogy ha van 15'000 szál és mindegyiknek van egy 1 megás stack-je, akkor az 15'000 megabyte = 15 GB > 4 GB, azaz 32 bites cuccon problémás lenne.
    Javítsatok ki ha tévedek.
    Mutasd a teljes hozzászólást!
  • Ja, 32 bites windowson altalaban max 1700-2000 szalat tudsz letrehozni.
    Mutasd a teljes hozzászólást!
  • PVM-el nem tartom lehetetlennek a dolgot, ráadásul skálázható is lenne. Ám ez valószínűleg az ágyúval verébre kategória lenne.
    Mutasd a teljes hozzászólást!
  • Ha a proci megszakíthatja az egyik objektum számításait, akkor az hibához is vezethet.

    -például ellenőrzöd, hogy ütközik e az objektum a másik 15.000 objektummal.
    -elérsz 10.000-ig, ekkor a proci megszakítja a feladatot és növeli az objektumok értékeit
    -ekkor ha folytatódik a számítás akkor megváltozott értékkel számolsz, így ha az előző időpillanatban ütköztél is egy objektummal, mostanra arébb ment és azt fogod számolni, hogy nem ütközik.

    Ez a program olyan lenne, mint egy vasúti menetrend? Vagy mihez hasonlítható? Térben egy vonalban mozognak az objektumok (mint egy számegyenes)? Vagy valami bonyolult hálón? A pontos idő az mindegyik számára ugyanaz? Csak meg van adva, hogy honnan és mikor indul, meg az, hogy hová mikor érkezik?

    Ha nincs nagy "tér", akkor a "térben" lehet jelezni, hogy az adott ponton melyik objektum áll, így az ütközés lekérdezése egyszerű, hisz nem kell 15.000 objektummal összehasonlítani minden elemet, csak megnézni, hogy az adott pozíción áll e már valaki.

    Szóval szerintem is az lehet a megoldás kulcsa, ha okosan van megtervezve a program működése. Többet nyerhetsz vele, mint erőből próbálni megoldani.
    Játékprogramokban is elég bonyolult számításokat kell elvégezni, de ott is megtalálják a módját, hogy elég gyors legyen.
    Mutasd a teljes hozzászólást!
  • Pontszerűek, avagy nem pontszerűek az objektumaid? Pontszerűnél szerintem jóval egyszerűbb. Amennyiben nem pontszerűek, akkor valamilyen befoglalót érdemes használni.
    Aztán el kell dönteni azt is, hogy diszkrét, vagy folytonos ütközésdetektálást használsz. A diszkrét nyilván egyszerűbb, de nem mindig alkalmazható.
    Az optimalizálást pedig meg lehet oldani valamiféle gráfba rendezéssel. Jelentősen lecsökkentheti az ütközéspárok számát.
    Egyébként pedig szerintem is GPU-ban érdemes gondolkodni. CUDA vagy OpenCL ami kell neked, ahogy azt fentebb említették. OpenCL-t sajnos annyira nem ismerem. CUDA-hoz az nvidia oldalán van rengeteg hasznos cucc. Ha jól emlékszek van egy példa amiben több 10K particle ütközését animálják valós időben. A CUDA rengeteg szálat kezel egyszerre, amik ráadásul lightweight threadek. Bár az is igaz, hogy ha most látod először, akkor elsőre tuti nem fogod megoldani benne a problémád. De szerintem érdemes rászánni az időt a tanulására.
    Mutasd a teljes hozzászólást!
  • Igazatok van a feladat nagy vonalakban átfogalmazva:

    Adva van 50.000 város ezek egy-egy objektum egy egyedi azonosítóval.

    Vannak vonatok amiket a felhasználók indíthatnak.
    Amikor elindul a vonat mondjuk "A" városból "B" városba kiszámolja a program az érkezési idejét. Legyen mondjuk 1h 12m 5s. Az nem érdekes, hogy helyileg hol van a vonat vagyis nem folyamatos a dolog, nincs térkép ahol jelölni kell.
    Csak annyit lát az user, hogy az X vonata éppen "A"-ból "B"-be tart még ennyi idő az út és pontosan ekkor érkezik meg.
    Ilyenből lehet 15.000 egyszerre

    Amikor beérkezik egy városba akkor pár műveletet el kell végezni, megjelölni, hogy beért, lepakolni a csomagokat stb...
    De ezt pontosan kell végezni, mert lehet egy másik felhasználó pontosan akkor akar belépni és tovább vinni a csomagokat.

    És mindez valós időben vagyis a normál órához hangolva.

    Kb ezt látja az user:

    "XY vonat;"A-B";1h 2m 2s;érkezés: 12:03:03"
    "ZZ vonat;"C-E";2h 2m 2s;érkezés: 13:03:03"

    Végül is a legjobb lenne, ha egy adott objektumnál ki tudnám adni, hogy 12:03:03 óráig ne csináljon semmit, de a megadott időben fusson le egy függvény.

    Mutasd a teljes hozzászólást!
  • Szerintem ehhez semmilyen szálak nem kellenek, egyszerűen időpont (szimulált időpont, természetesen) szerint rendezve kell tárolni az eseményeket egy listában, és időnként ránézni a lista elejére, hogy kell-e valamit csinálni.
    Mutasd a teljes hozzászólást!
  • vagyis minden másodpercben kéne ránézni, hogy ne legyen kiesés.
    És itt jön a probléma, hogy ha az egyik objektum valami miatt lefogja a programot akkor a többi késni fog. Pl egy objektum beér és a feldolgozás mondjuk 3-4mp-be telik.

    Viszont, ha mindegyiknek van külön szálja akkor azok a 3-4mp alatt is szépen feldolgozódnak max annyi történik, hogy ami ahhoz a "leakadt" objektumhoz tartozik várni fog, de így csak egy helyen lesz probléma ellentétben az 1-2 szálnál minden objektum várni fog.

    Vagyis a munka oroszlánrészét átadom az OP rendszernek, hogy ossze el ő az erőforrásokat igazságosan.
    Régen 15 évvel ezelőtt DOS-ban persze még magam írtam meg az ilyen "szálkezeléseket", de azért 2010-ben gondoltam már fejlődtünk egy kicsit :D
    Mutasd a teljes hozzászólást!
  • AAmikor célbaért, akkor csak annak az egy objektumnak a feldolgozását elindítod egy külön szálon, főleg ha ennyire időigényes!
    A főprogram ugyan úgy figfyeli hogy célbaért-e valami, ha igen indít még egy feldolgozást külön szálon azt is...
    Mutasd a teljes hozzászólást!
  • Igazad van, most láttam én is, hogy eddig a fát néztem az erdő előtt.
    Látszik, hogy nyár van és az ember esze nem a gép körül forog
    Mutasd a teljes hozzászólást!
  • Tulajdonképpen egyáltalán nem kell ennek valósidejűnek lenni, ha mondjuk a szimulált időben két óra hosszáig nem történik semmi, akkor tök felesleges valós időben is két órát várni...
    Mutasd a teljes hozzászólást!
  • Sajnos valós idejűnek kell lennie, hogy a felhasználók be tudjanak avatkozni.
    Játék lesz belőle, ha minden igaz...
    Mutasd a teljes hozzászólást!
  • Ez valami többfelhasználós, hálózatos kliens/szerver arhitektúra akar lenni? Annak a mikéntje már ki van találva?
    Mutasd a teljes hozzászólást!
  • Szeritnem annyi jó ötlet felmerült már, hogy a mozgatással biztos nem lesz gond. (Jól megírva talán még egy 286-os gép is elboldogul vele.)
    Kérdés, hogy ha beérkezik egy vonat egy állomásra, akkor mennyi számítást kell elvégezni, és mi van akkor ha 100 vonat ér be egyszerre. De ezeket a számításokat nem simerjük. De egy játékprogram a másodperc töredéke alatt is óriási mennyiségű számítást végez, így egy másodperc alatt nagyon soks számítást el lehet végezni.

    Esetleg készíts egy tesztet, hogy egyszerre 15.000 példányban végzed a legbonyolultabb számításokat (ami játék közben biztos nem lesz), és mérd le hogy mennyi ideig tart.

    Amúgy ha időben elhúzódik a játék, akkor lehet elég perc pontossággal számolni. Hálózatban, főleg neten játszva úgysem tudsz másodperc pontossággal kezelni dolgokat, mert az adatok küldése-fogadása is túlcsúszhat.

    Esetleg húzhatsz egy határt, mondjuk 100 esemény történhet egy másodpercben, és ha több esemény várható, akkor azokat később hajtod végre, esetleg kiíratod a felhasználónak, hogy a vonat 1 percet késik. Még valósághű is lesz .
    Mutasd a teljes hozzászólást!
  • Szerintem jobban jársz, ha hagyod a szálakan, vagy legalábbis mérsékled. Semmivel nem lesz gyorsabb, ha az oprendszernek kell ébresztenie 12:05-kor 20 szálat, amik esetleg mindannyian egy másodpercnél tovább dolgoznak, mint ha tényleg sorbaraknád (mikor időd van) és 12:05-kor végigszaladnál a teendőkön. ha tudod függetleniteni a részeket (városcsoportonként valahogy) az gyorsíthat, de gubanc kibogozását az oprendszer sem tudja jobban csinálni szerintem. Sőt.
    Mutasd a teljes hozzászólást!
  • Nem igazán értem a problémát.
    Ha egy-egy vonatot recordként kezelsz, ahol - gondolom - minden vonatnak van egyedi azonosítója, indulási és érkezési ideje, meg még egypár, az úton levés szempontjából érdektelen változója, 15000 record másodpercenkénti végigolvasása még brute force ciklussal se lehet probléma.
    De megindexelheted azonosító szerint, indulási és érkezési idő szerint és így az indexekben bináris kereséssel max 14 lépésben találod meg azt a néhány recordot, ami épp feldolgozást igényel. De ez olyan kis adatmennyiség, amit akármelyik adatbáziskezelő röhögve elbír real-time-ban és akkor nincs gondod még az indexelésekkel se.

    Persze nem ártana felmérni az extrém eseteket is. Pl. elméletileg ugyebár nem zárható ki, hogy mind a 15000 vonat ugyanabban a másodpercben ér célba. Stb.
    Mutasd a teljes hozzászólást!
  • A 'célba érés' hatására számítás igényes feladatot kell végrehajtani.
    Ez a gond.
    Mutasd a teljes hozzászólást!
  • A célba érés végén egy többszálú sorfeldolgozóba kell rakni a feladatokat. Annyi szálból szabad csak állnia a feldolgozónak, ahány processzormag van.
    Mutasd a teljes hozzászólást!
  • Akkor megoldhatod úgy, hogy a beérkező vonatokat egy külön FIFO listába rakod, majd a listát kezded feldolgozni egy, vagy néhány külön szálon. Így a fő szálad mindig real-time marad, a megérkezett ám feldolgozatlan vonatok meg lehetnek pl. "kirakodás alatt" státuszban.
    Vagy feldolgozás alatt, vagy hasmenése van az állomásfőnöknek, vagy mittomén.
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd