[GPGPU] Efficient parallel algoritme voor DVD seek simulatie

[.oisyn]

Achtergrond
Ik ben momenteel bezig met het optimaliseren van de volgorde van alle resources op een DVD om zo de laadtijden van een specifieke game (waar ik verder weinig over kan zeggen) te verkleinen. Hiervoor heb ik een genetisch algoritme ontwikkeld dat, gegeven alle resources en een resource access log van een volledige playthrough van de game, een zo efficient mogelijke indeling probeert te zoeken. Dit algoritme werkt verder prima en is al in productie. Het nadeel is echter dat het een aantal dagen moet draaien op een Core i7 met 8 threads voordat het een beetje een acceptabele oplossing aandraagt (na ongeveer ~30 miljoen generaties met een snelheid van ~160 generaties per seconde). Ik hoop dit proces te kunnen versnellen door gebruik te maken van een GPGPU implementatie. Gegeven de aard van hardware- en software architectuur op hedendaagse PC's is het helaas van belang dat de gehele implementatie naar de GPU verplaatst wordt - de latency waarbij de GPU-output weer op de CPU uit te lezen is is simpelweg te hoog (3 tot 5ms) om voor een hybride CPU/GPU oplossing te gaan.

Op zich heb ik elke stap van het genetische algoritme nu geïmplementeerd op de GPU (middels DirectX11 compute shaders): het sorteren van de oplossingen op basis van fitness level, genetische cross over, mutatie en fitness evaluation.

Echter, die laatste stap krijg ik gewoonweg niet snel genoeg. Ik heb al tal van aanpakken geprobeerd. Sommigen zijn nauwelijks sneller dan de CPU, en de rest is vele malen langzamer.

Probleem
Goed, die fitness evaluatie is feitelijk gewoon een simulatie van het lezen van alle resources, gegeven de total volgorde van die resources op disc. Zo'n simulatie bestaat uit een aantal "batches". Elke batch bestaat uit een set resources die voor die batch ingelezen moet worden. Een resource kan in meerdere batches voorkomen. De game weet waar elke resource op disc staat en zal zelf de moeite nemen om ze te sorteren voor het inlezen, zodat de kop altijd van voor naar achter over de disc verplaatst wordt en er zo min mogelijk wordt geseekt. De volgorde van resources binnen een batch is dus niet van belang voor het berekenen van de fitness. Hoe ver de resources op disc uit elkaar staan natuurlijk wel. Als fitness voor een oplossing bereken ik de totale seek tijd die nodig voor alle batches.


Wellicht is het handig om even te beginnen met een voorbeeld. Stel er zijn 8 even grote resources (1 t/m 8), en 3 batches (A, B en C). De batches bestaan uit:
A: { 1, 2, 6, 8 }
B: { 2, 3, 4, 5 }
C: { 1, 7, 8 }

En we definieren de kosten van een seek als simpelweg het aantal tussenliggende resources.
Voor de volgorde: { 1, 2, 3, 4, 5, 6, 7, 8 }
Dan kost:
A: 0 (van 1 naar 2) + 3 (van 2 naar 6) + 1 (van 6 naar 8) = 4
B: 0 + 0 + 0 = 0
C: 5 + 0 = 5
Totale kosten: 4 + 0 + 5 = 9

Voor de volgorde: { 1, 3, 5, 7, 2, 4, 8, 6 }
A: 3 (van 1 naar 2) + 1 (van 2 naar 8) + 0 (van 8 naar 6) = 4
B: 0 + 2 + 0 = 2
C: 2 + 3 = 5
Totale kosten: 4 + 2 + 5 = 11

Voor de volgorde: { 3, 4, 5, 2, 1, 6, 8, 7 }
A: 0 + 0 + 0 = 0
B: 0 + 0 + 0 = 0
C: 1 + 0 = 1
Totale kosten: 0 + 0 + 1 = 1

De laatste oplossing is in wat deze gevallen betreft het efficientst.

Bij bovenstaande berekeningen ben ik steeds uitgegaan van de batches. Zou je het probleem serieel willen tacklen, dan is dat niet hele efficiente benadering van het probleem. Omdat de volgorde van de resources op disc niet overeenkomt met de volgorde van resources in een batch, moet je eerst per batch alle resources sorteren op basis van de gevonden oplossing, zodat je daarna per batch van voor naar achter kunt lopen door de resources in de batch. In pseudocode:

code:

foreach (b in batches)
{
    resources = sort b.resources using global resource order;
    foreach (adjacent pair p in resources)
        totalcost += cost(p.fromoffset, p.tooffset);
}

Oftewel, een verwachte looptijd van O(b∙r∙log r), met b het aantal batches en r het gemiddede aantal resources per batch.

Een efficientere benadering is door lineair door de resources op disc heen te lopen en voor elke batch bij te houden waar de laatste leespositie was.

code:

int lastread[batches.size] = { 0 };
foreach (r in resources)
{
    foreach (b in r.batches)
    {
        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset;
    }    
}

Verwachte looptijd O(r∙b) met r het aantal resources en b het gemiddelde aantal batches per resource. Dit is de methode die ik ook voor de CPU implementatie gebruik.

Praktijk
In de realiteit hebben we het over ~5000 resources, ~1000 batches, 1 tot 400 resources per batch en waarbij elke resource in 1 tot 100 batches voorkomt. Deze resources zijn in werkelijkheid overigens groepen van resources die gegarandeerd altijd tegelijkertijd in worden gelezen. Zo zou je in bovenstaand voorbeeld de resources { 3, 4, 5 } en { 1, 8 } bij elkaar kunnen stoppen, omdat die nooit los van elkaar worden ingelezen. Een dergelijke reductie is bij die 5000 "resources" dus niet meer mogelijk (in werkelijkheid zijn het 100.000 resources).

Verder bestaat de populatie van m'n GA uit 100 oplossingen die allemaal moeten worden doorgerekend. Beide bovenstaande oplossingen krijg ik niet snel op de GPU.

De sorteer-oplossing is belabberd, een parallel bitonic sort van 100 (populatie) * 1000 (batches) arrays van 400 elementen (resources per batch) is gewoon niet echt snel te doen.

De lineaire oplossing is lastig te parallelliseren. Je kan niet in een shader even doodleuk 5000 elementen aflopen. Je kunt het wel opdelen en iedere thread een deel laten doen, waarna je daarna nog even de losse eindjes aan elkaar knoopt. Dit was de efficientste oplossing die ik tot nu toe gevonden heb, maar is langzamer dan de CPU.

Een andere oplossing die ik vond was door een oplossing te converteren naar een array van 5000 kolommen (de resources) bij 1000 rijen (de batches) waarbij elk element bestaat uit 2 ints: een from-read en een to-read. Daarna werden de kolommen recursief gereduceerd zodat je een 1x1000 matrix overhoudt met kosten per batch, die je vervolgens kunt opsommen om op het totaal te komen. Op zich aardig, maar gezien het feit dat je dat 100 keer moet doen (voor elke oplossing in de populatie) wordt de GPU daar ook niet echt vrolijk van.

Een van de algoritmes zou daarentegen wel weer prima werken als het probleemgebied op een of andere manier verkleind kan worden. Zo had ik bedacht om batches kleiner dan 4 resources eruit te filteren en die op de sort-methode te doen (max 4 elementen sorteren kan natuurlijk spotgoedkoop). Het werd er echter totaal niet sneller op - voornamelijk omdat elke GPU thread de prijs betaald voor elke branch die de andere GPU thread neemt op dezelfde execution unit. Oftewel, als 1 thread een for-loop doet over 100 batches in een resources, dan doen 31 andere threads dat ook ookal hoeven zij maar 1 batch per resource af te handelen.

Heeft iemand anders eventueel nog een geniale oplossing?

[frG]

Waarom is de CPU een beperkende factor in deze? Is het niet zo dat zo een simulatie maar '1 keer' gedraaid hoeft te worden bij het einde van het ontwikkelingstraject?

Of is de tijd er gewoon niet om er b.v 2-3 dagen op te wachten?

[ Voor 16% gewijzigd door frG op 14-11-2012 10:56 ]

[Verwijderd]

Codewoord: genetisch algoritme.

[.oisyn]

Aangezien dit overigens mijn eerste ervaring met compute shaders is, is het wellicht ook handig om mijn tot nu toe snelste oplossing te posten. Misschien doe ik wel iets wat gewoon enorm inefficient is

C: HLSL

cbuffer Constants0 : register(b0)
{
    int cPopSize;               // population size (100)
    int cNumGroups;             // total number of resource groups
    int cNumBatches;            // total number of batches
};

struct EvalData
{
    int firstRead;  // first read offset for a batch in a thread
    int lastRead;   // last read offset for a batch in a thread
};

typedef StructuredBuffer<int> IntBufferIn;
typedef RWStructuredBuffer<float> FloatBufferOut;
typedef RWStructuredBuffer<EvalData> EvalDataOut;

#define EVAL_WIDTH 128

groupshared float s_threadTotal[EVAL_WIDTH];        // calculated totals per thread

[numthreads(EVAL_WIDTH, 1, 1)]
void Evaluate(
    int3 id : SV_DispatchThreadID,
    IntBufferIn orderDataIn : register(t0),         // permutation of resource group indices
    IntBufferIn groupOffsets : register(t1),        // offset of each resource group on disc
    IntBufferIn groupBatches : register(t2),        // (constant) buffer containing all batches per group
    FloatBufferOut costOut : register(u0),          // result is written here
    EvalDataOut tmpData : register(u1))             // auxillary buffer for patching up per thread states
{
    int idx = id.x;
    int chromoIdx = id.y;                           // index of the current chromosome (0..99)
    int chromoOffset = chromoIdx * cNumGroups;      // offset of the chromosome in the order/offset buffers

    int todo = (uint)(cNumGroups + EVAL_WIDTH - 1) / EVAL_WIDTH;    // number of groups to process per thread
    int tmpDataOffset = chromoIdx * cNumBatches * EVAL_WIDTH + idx; // thread index in the auxillary buffer

    int lastReads[1300];    // last read offset per thread
    float totalCost = 0;

    int pos = idx * todo;
    todo = min(todo, cNumGroups - pos);
    int offset = pos > 0 ? groupOffsets[chromoOffset + pos - 1] : 0;
    
    // process groups
    for (int i = 0; i < todo; i++, pos++)
    {
        if (pos >= cNumGroups)
            break;
        int group = orderDataIn[chromoOffset + pos] & 0xffff;   // get current group (bottom 16 bits)
        int batchOffset = group << 6;                           // offset of this group in the groupBatches buffer (64 entries per group)
        int sizeAndNum = groupBatches[batchOffset++];           // group disc size and number of batches stored in first int
        int size = sizeAndNum & 0xfffff800;
        int num = sizeAndNum & 0x7ff;
        int nextOffset = offset + size;

        // process batches
        for (int b = 0; b < num; b += 2)
        {
            int batches = groupBatches[batchOffset++];          // batches are stored in pairs per int
            
            // first batch, bottom 16 bits
            int b0 = batches & 0xffff;
            if (lastReads[b0])  // a resource in this batch has already been read, calculate seek cost
                totalCost += Cost(lastReads[b0], offset);       
            else                // otherwise, store the first read in the aux buffer
                tmpData[tmpDataOffset + b0 * EVAL_WIDTH].firstRead = offset;
                
            // update last batch read in local and aux buffer
            lastReads[b0] = nextOffset;
            tmpData[tmpDataOffset + b0 * EVAL_WIDTH].lastRead = nextOffset;

            if (b+1 < num)
            {
                // second batch, upper 16 bits
                int b1 = batches >> 16;
                if (lastReads[b1])  // a resource in this batch has already been read, calculate seek cost
                    totalCost += Cost(lastReads[b1], offset);
                else                // otherwise, store the first read in the aux buffer
                    tmpData[tmpDataOffset + b1 * EVAL_WIDTH].firstRead = offset;

                // update last batch read in local and aux buffer
                lastReads[b1] = nextOffset;
                tmpData[tmpDataOffset + b1 * EVAL_WIDTH].lastRead = nextOffset;
            }
        }

        offset = nextOffset;
    }

    // make sure all threads are done writing to aux buffer
    DeviceMemoryBarrierWithGroupSync();
    
    // patch up loose ends. Each thread in threadgroup picks up a number of batches
    int numBatches = (uint)(cNumBatches + EVAL_WIDTH - 1) / EVAL_WIDTH; // number of batches per thread
    pos = idx * numBatches;
    int batchTodo = min(numBatches, cNumBatches - pos);
    tmpDataOffset = tmpDataOffset - idx + pos * EVAL_WIDTH;     // position in aux buffer

    // walk over batches
    for (int b = 0; b < batchTodo; b++, pos++)
    {
        int lastRead = 0;
        
        // walk over EVAL_WIDTH number of loose ends
        for (int i = 0; i < EVAL_WIDTH; i++, tmpDataOffset++)
        {
            EvalData d = tmpData[tmpDataOffset];
            if (d.firstRead)
            {   // a thread had reads for this batch
                if (lastRead)   // there was an earlier read, calculate cost
                    totalCost += Cost(lastRead, d.firstRead);
                lastRead = d.lastRead;
            }
        }
    }

    // store total calculated cost by this thread in shared memory and synchronize
    s_threadTotal[idx] = totalCost;
    GroupMemoryBarrierWithGroupSync();
    
    // first thread in threadgroup will sum all results
    if (idx != 0)
        return;

    for (int t = 1; t < EVAL_WIDTH; t++)
        totalCost += s_threadTotal[t];

    // store result
    costOut[chromoIdx] = totalCost;
}

Met dit algoritme haal ik op een Radeon HD 5870 ongeveer 100 generaties per seconde. Ter vergelijking, de CPU implementatie op een Core i7 doet er 160 per seconde. Er ligt hier nog wel een ongebruikte HD 6970 ergens maar dat is geneuzel in de marge, ik hoop toch echt richting de 1000 generaties per seconde of meer te kunnen gaan.

[ Voor 15% gewijzigd door .oisyn op 14-11-2012 11:33 ]

[.oisyn]

frG schreef op woensdag 14 november 2012 @ 10:54:
Waarom is de CPU een beperkende factor in deze? Is het niet zo dat zo een simulatie maar '1 keer' gedraaid hoeft te worden bij het einde van het ontwikkelingstraject?

Als dat inderdaad het geval is dan had je gelijk, je laat 'm gewoon 1x aan het eind crunchen en dan neem je die paar dagen voor lief.

Maar tegen het einde van het ontwikkeltraject wordt er continu getest, terwijl er hier en daar ook nog content wordt aangepast. Je wil voor het testen wel efficiente disc layouts produceren, en daarom is het onhandig dat je daar een aantal dagen op moet wachten.

[D-Raven]

Heb het doorgelezen, ben fanatiek aan de slag gegaan, kwam toen tot de conclusie dat de ideeen die ik had, eigenlijk hetzelfde waren als de dingen die jij al geprobeerd had, en dacht toen..

ok, im out

Maar vanuitgaande dat je shader optimaal is zit de grootste kans voor verbetering (helemaal gezien de orde van performance verbetering waarnaar je opzoek bent) denk ik in een versimpeling van je problem domain, maar hoe je dit gaat doen..

[Zoijar]

D-Raven schreef op woensdag 14 november 2012 @ 11:40:
Heb het doorgelezen, ben fanatiek aan de slag gegaan, kwam toen tot de conclusie dat de ideeen die ik had, eigenlijk hetzelfde waren als de dingen die jij al geprobeerd had, en dacht toen..

ok, im out

Same here, van 9 tot 12

Grootste probleem is volgens mij dat je load niet gebalanceerd is, zoals je zelf ook aan het einde stelt. Elk thread block moet wachten op de langzaamste thread die dan waarschijnlijk 100 batches moet doen.

Oplossing hiervoor is je data niet opdelen in [solution, resource] maar in [solution, resource, batch]. Dan kan een thread dus of een deel van de batches van een resource doen, of meerdere resources, afhankelijk van de gecombineerde grootte. Echter... ik heb geen idee hoe je dat voor elkaar krijgt met die shared buffer 'lastread' als alles doorelkaar tegelijk gaat lezen en schrijven. Misschien die buffer op de een of andere manier opsplitsen dat het elkaar niet in de weg loopt... (ik moet even kijken hoe je dat nu doet)

Dat sorteren is sowieso theoretisch al een stuk langzamer, dus ik denk dat je dat nooit sneller krijgt dan je CPU lineair (?)

[H!GHGuY]

Je probleemdomein kun je misschien verkleinen door clusters van resources te zoeken die vaak samen of minstens kort op elkaar gebruikt worden. Die voeg je dan samen tot nieuwe resources. Door dit proces enkele malen te herhalen kun je mss al een heel eind komen.

Misschien kun je zo zelfs tot een verdeel-en-heers methode komen?

[Infinitive]

.oisyn schreef op woensdag 14 november 2012 @ 11:27:
[...]
Maar tegen het einde van het ontwikkeltraject wordt er continu getest, terwijl er hier en daar ook nog content wordt aangepast. Je wil voor het testen wel efficiente disc layouts produceren, en daarom is het onhandig dat je daar een aantal dagen op moet wachten.

Ik vraag me af hoe incrementeel je het proces kan maken, en of je in de aanloop en gedurende het testen al oplossingen kan genereren die je dan als initiele populatie voor de volgende ronde kan gebruiken.

Ik realiseer me dat je dan te maken hebt met veranderingen aan resources en batches, en ik weet niet of je vorige uitkomsten eenvoudig aangepast kunnen worden om nieuwe oplossingen te vormen. Als de veranderingen relatief klein zijn, dan zou je verwachten dat het kwalitatief dan ook goede oplossingen zouden zijn en het proces sneller convergeert - hoewel je mogelijk je zoekruimte ook inperkt...

[BNieuwenhuizen]

Als ik het goed begrijp komt de seek tijd tussen twee resources uit op de beginpositie van de laatste resource min de eindpostie van de eerste resource.

Dan kunnen we kijken naar een batch met de resources 1 t/m n, al gesorteerd op basis van hun plek op de schijf. Dus resource 1 heeft de laagste offset en resource n de hoogste.

Dan is de seektijd tussen resource i en i + 1 gelijk aan

offset_i+1 - offset_i - size_i

Als de som hiervan nemen voor alle seektijden krijgen we

offset_n - offset₁ - A

waar A de som is van de de groottes van alle resource behalve de laatste. Er valt namelijk heel wat tegen elkaar weg qua offsets. Die A is heel vervelend, dus we definieren een B die de som is van alle groottes van resources in de batch. Dan krijgen we


offset_n + size_n- offset₁ - B

Omdat we de resources achter elkaar hebben gezet volgt dat de resource met grootste offset ook het laatste eind heeft en dus de maximale offset + size heeft. Aangezien B alleen afhangt van de batch kunnen we daar een constante per batch van maken.

Merk nu op dat de volgorde van de resources in de batch niet echt uitmaakt, alleen waar de eerste en laatste staan.

Dan kunnen we arrays maken van resource id naar offset en size, waarbij de eerste afhankelijk is van je permutatie en de tweede niet.

C++:

unsigned costs = 0;

for(const auto& batch : batches) {
  unsigned begin = 0xffffffff;
  unsigned end = 0;

  for(auto resource : batch.resources) {
    begin = min(begin, offsets[resource]);
    end = max(end, offsets[resource] + sizes[resource]);
  }

  costs += end - begin - batch.B;
}

Dit lijkt me veel beter te paralleliseren over oplossingen, aangezien je branches geheel onafhankelijk zijn van je permutatie. Je hebt echter wel gather loads nodig om dit met SIMD te parallelliseren, wat je met SSE niet hebt.

Ik heb het idee dat grafische kaarten hier misschien wel beter overweg kunnen, alleen heb ik geen openCL implementatie hier die op de GPU draait om het te testen.

Ik heb even kort een benchmark gedraaid tussen dit algoritme en het oude algoritme met een random dataset en het lijkt iets sneller te zijn. Ik heb echter totaal geen parallellisatie gedaan en ook niet al je optimalisaties uit je GPGPU implementatie overgenomen:

C++:

unsigned newScore() {
  unsigned costs = 0;

  for(const auto& batch : batches) {
    unsigned begin = 0xffffffff;
    unsigned end = 0;

    for(auto resource : batch.resources) {
      begin = min(begin, offsets[resource]);
      end = max(end, offsets[resource] + sizes[resource]);
    }

    costs += end - begin - batch.totalsize;
  }
  return costs;
}

unsigned oldScore() {
  vector<bool> batchRead(batches.size(), false);
  vector<unsigned> lastRead(batches.size(), 0);
  unsigned costs = 0;

  for(unsigned i = 0; i < N; ++i) {
    unsigned r = perm[i];

    for(auto m : membership[r]) {
      if(batchRead[m])
        costs += offsets[r] - lastRead[m];
      else
        batchRead[m] = true;

      lastRead[m] = offsets[r] + sizes[r];
    }
  }

  return costs;
}

Deze methode is echter niet zo flexibel als je een andere kostenfunctie wil gebruiken.

[.oisyn]

Bedankt voor je post! Ik heb in dezelfde richting zitten denken. Het probleem is echter dat mijn kostenfunctie een polynoom is in vorm van:

cost(a,b) = |a-b| <= M ? 0 : C + |a-b|/X

Oftewel, als a en b dicht genoeg bij elkaar liggen dan kost het niets, en anders heb je te maken met vaste startkosten in de vorm van C. Het is mij zelf niet gelukt om die C in jouw suggestie te verwerken, en heb het idee al in een vrij vroeg stadium afgedaan.

Maar nu ik er nog eens over nadenk is het wellicht toch te doen. Als we even valsspelen en M hierboven gelijk stellen aan 1, dan geldt C alleen voor resources die niet direct na elkaar staan. Gegeven een willekeurig paar resources zou ik een tabel kunnen maken hoe vaak ze met z'n tweeën in batches voorkomen. Als ik er vervolgens vanuit ga dat C áltijd van toepassing is dan is het terug te brengen naar jouw oplossing, plus een globale constante (namelijk alle C's van alle aanliggende resource-paren in alle batches ongeacht de offsets van die resource-paren). Vervolgens kan ik met een enkele pass over de daadwerkelijke permutatie en de genoemde opzoektabel de kosten voor aaneenliggende paren aftrekken van de globale C om zo te komen tot permutatie-afhankelijke kosten.

M is in werkelijkheid 32kB en resources zijn altijd veelvouden 2kB, dus ik denk niet dat het een té vertekenend beeld geeft van de werkelijkheid als ik stel dat M=1. Overigens zou ik wel per resource verder kunnen kijken dan alleen de aanliggende totdat de grens van 32kB gepasseerd wordt, maar ik denk dat te duur wordt.

Desalniettemin, interessant! Hier ga ik mee aan de slag.

[pedorus]

Ik denk eigenlijk dat het hier al fout gegaan is bij de 2e zin uit de TS Iedereen die iets met evolutionary algorithms doet kan je vertellen dat je ze NIET moet gebruiken, tenzij er geen betere oplossingen beschikbaar zijn. Als je ze dan toch moet gebruiken, dan werkt een gespecialiseerd algoritme beter dan een generiek algoritme, maar ik zie hier daar niets over.

Dan heb je zo'n algoritme dat te traag werkt, en wil je deze versnellen. Het lijkt mij dat (geautomatiseerde) parameter tuning, parallellisatie over meerdere machines, en/ of toevoegen van probleemspecifieke algoritmes daar een aangewezen oplossing voor zijn. Vanwaar de keuze voor de GPU? Het aantal van 100 per generatie lijkt me bijvoorbeeld wat aan de lage kant daarvoor als ik even snel in de literatuur zoek, de verwachte versnelling voor dat soort aantallen is zelfs negatief als ik zo kijk (maar dat zijn problemen waar de evaluatiefunctie minder tijd in beslag neemt, bijv. paper A en paper B). Voor daadwerkelijke problemen wordt dan een versnelling van een factor ~5-10 gevonden, gewoon 10 machines bij [cloud service] inhuren lijkt me makkelijker.

Als het trouwens gaat om resources van <=32kB, waarom zou je die dan niet meerdere keren op de disc kunnen zetten? Verder dacht ik gezien de 3 voorbeelden in TS ook aan simpelweg batchtime=max(positie per benodigde resource)-min(positie per benodigde resource) als benadering (in het begin) te gebruiken. Die constanten kun je natuurlijk weglaten als het alleen gaat om relatieve scores. Verder kun je (afhankelijk van de genetische operaties) misschien stukjes evaluatie niet opnieuw doen, evaluatie opgeven als het waarschijnlijk toch niet interessant is, later verbeterde evaluatie doen, e.d.

Verder doe ik (nog) niets met GPU's, dat is toch jouw gebied? Wat ik me zo kan voorstellen is dat op een GPU algoritmes die de problemen 'uitvergroten' beter zouden werken, bijvoorbeeld alle resources als pixels van 2KB maken (dus dupliceren), een of andere fill per batch en daar de verspreiding van berekenen, dat soort dingen.

Gezien de nieuwheid van dit werk kun je trouwens waarschijnlijk wel een universiteit vinden die enkele maanden tijd aan dit probleem wil besteden, en met subsidie een projectje wil opstarten.

Overigens: op een moderne pc past een hele DVD toch gewoon in werkgeheugen?

[Soultaker]

Ik vind genetische algoritmen stom en dus neig ik naar pedorus' suggestie om gewoon een deterministisch algoritme te ontwikkelen, maar dat zeg ik zonder precies te weten hoe goed de oplossingen die je nu vindt al zijn (lijkt me dat je in een paar dagen op een vette bak ver moet kunnen komen).

Als je andere aanpakken wil zien, zou ik zeggen: maak er een programming contest van. Zet wat representatieve data online en een Python scriptje ofzo waarmee de fitness van een oplossing geëvalueerd kan worden, en kijk of iemand betere oplossingen kan genereren dan jij.

[.oisyn]

pedorus schreef op woensdag 14 november 2012 @ 16:20:
Ik denk eigenlijk dat het hier al fout gegaan is bij de 2e zin uit de TS

Ik denk dat jij niet goed op de hoogte bent van de staat van het project .

Ik heb verschillende deterministische algoritmes geprobeerd. Sommigen werken vrij aardig, maar komen niet zo ver als m'n GA implementatie (die uitgaat van een eerste populatie geproduceerd door zo'n ander algoritme). Ik zeg niet dat het niet beter kan, maar wel dat m'n GA zo goed bleek te werken dat ik daar geen tijd meer aan ga spenderen zo kort voor de deadline van het project. De gehele GPU approach is overigens vooral een personal interest die ik thuis uitwerk, ter lering ende vermaeck

Als je ze dan toch moet gebruiken, dan werkt een gespecialiseerd algoritme beter dan een generiek algoritme, maar ik zie hier daar niets over.

Omdat dat niet relevant is voor de probleemstelling in de topic, namelijk fitness evaluation. Crossover en mutation zijn gewoon geinstrumenteerd op basis van wat parameters, en zijn dus niet compleet random.

Vanwaar de keuze voor de GPU?

Probeersel. Verschillende GA's zijn middels een GPU behoorlijk versneld. Mijn ervaring met GPGPU was voorheen nihiel dus het leek me wel een leuk project om dat eens bij te veizelen

Het aantal van 100 per generatie lijkt me bijvoorbeeld wat aan de lage kant daarvoor als ik even snel in de literatuur zoek

Grappig, bij mijn zoektocht bleek dat de populatie nou juist niet te groot moest zijn. Uiteraard heb ik verschillende parameters getest, een grotere populatie geeft geen betere progress in termen van tijd.

Voor daadwerkelijke problemen wordt dan een versnelling van een factor ~5-10 gevonden, gewoon 10 machines bij [cloud service] inhuren lijkt me makkelijker.

En daar is mijn populatie dan wel weer te klein voor , dan worden de latencies simpelweg te groot. Of je moet denken aan meerdere subpopulaties waartussen je dan gaat crossbreeden.

Als het trouwens gaat om resources van <=32kB, waarom zou je die dan niet meerdere keren op de disc kunnen zetten?

Ten eerste zijn bij lange na niet alle resources <=32kB, maar het is weldegelijk een optie die we in ons achterhoofd houden. Het probleem is echter dat de runtime daar op dit moment niet geschikt voor is.

Verder doe ik (nog) niets met GPU's, dat is toch jouw gebied? Wat ik me zo kan voorstellen is dat op een GPU algoritmes die de problemen 'uitvergroten' beter zouden werken, bijvoorbeeld alle resources als pixels van 2KB maken (dus dupliceren), een of andere fill per batch en daar de verspreiding van berekenen, dat soort dingen.

GPGPU heeft weinig met klassieke GPU problemen te maken. Pixels renderen doe je in een pixelshader, niet in een compute shader. Staar je niet teveel blind op dat eerste paper, dat is 5 jaar oud en gaat over shader model 3 videokaarten. De techniek is inmiddels een heel stuk verder. Neemt niet weg dat je nog weldegelijk texture units kunt gebruiken voor lineair interpolation van data, maar ze kunnen ook gewoon arbitrair geheugen lezen en schrijven.

Overigens: op een moderne pc past een hele DVD toch gewoon in werkgeheugen?

Newsflash: er zijn meer platformen dan PC, alwaar het sowieso geen issue is want je installeert toch naar harddisk

[ Voor 18% gewijzigd door .oisyn op 14-11-2012 17:24 ]

[.oisyn]

Soultaker schreef op woensdag 14 november 2012 @ 16:51:
Ik vind genetische algoritmen stom

Voor dit project was ik het altijd geheel met je eens

[armageddon_2k1]

.oisyn schreef op woensdag 14 november 2012 @ 17:25:
[...]

Voor dit project was ik het altijd geheel met je eens

Ik ben benieuwd naar jullie beweegredenen daarachter en heb daar even een ander topic voor geopend

[.oisyn]

Daar mag best een linkje bij hoor
Genetische algoritmes versus deterministische algoritmes

[PrisonerOfPain]

Waar zitten je bottlenecks? Ben je data bound? Hoe zien je data flow en layouts er uit? Op het moment is je algoritme enorm divergent, heb je daar al wat aan proberen te doen? Hoe zien je profiles er uit?

[.oisyn]

Weet jij een goede profiler? Pix kan niets met compute shaders en de tool van AMD is nogal spartaans (ik haakte af omdat ik UAC uit moest zetten )

[edeboeck]

OPGELET: dummy-modus!

Omdat ik niet thuis ben in dit domein, kan het ongelofelijk stom zijn wat ik hier neerpen, maar stel dat er een kleine kans is dat TS ermee geholpen is, wil ik wel een shot wagen: kan je iets opschieten met het afhuren van rekenkracht in cloud/datacenter of is dat in dit geval geen optie omdat je beperkt bent (lijkt te zijn) tot 1 CPU/GPU?

[PrisonerOfPain]

.oisyn schreef op woensdag 14 november 2012 @ 20:12:
Weet jij een goede profiler? Pix kan niets met compute shaders en de tool van AMD is nogal spartaans (ik haakte af omdat ik UAC uit moest zetten )

UAC uitzetten it is, I guess. Tenzij je er een NV kaart in wil zetten.

Verder heb ik 't er even met een kennis over gehad (heeft hier geen account ) die mij wees op regel 38. Al die data komt in global mem te staan omdat je over je local mem spilled. Nu zit je op 400-600 cycles per access op al je local variables, in het slechtste geval.

Verder kreeg ik te horen dat DeviceMemoryBarrierWithGroupSync belachelijk duur was. En dat je register file zo niet gefreed worden, hij stelde voor om er aparte jobs van te maken zodat je meer threads/core zou kunnen gebruiken.

Als je de DMBWGS weg zou werken zou je volgens hem ook 1 iteratie van je todo loop per thread kunnen runnen om de boel meer parallel te doen.

[ Voor 7% gewijzigd door PrisonerOfPain op 14-11-2012 21:01 ]

[Verwijderd]

Volgens mij is je process-batches ding hopeloos gecompliceerd. Je gebruikt een lijst, en vervolgens ga je een heel triviaal zoekalgoritme gebruiken (een loop over alle elementen). O( b * r ) dus. Terwijl het gewoon in O(1) kan een indirection table Geen idee hoe het heet, maar die term gebruik ik. Het resultaat, O( b * r ). Waar b het gemiddelde aantal objecten in een batch is in plaats van het totaal aantal batches. Ik heb een snelle python implementatie gebakt:

Python:

class Disk:
    def __init__(self, size):
        self.data = range(size)

    @property 
    def disk(self):
        return self.data

    def setDisk(self, newDisk):
        print newDisk;
        for i in range(len(newDisk)):
            self.data[newDisk[i]] = i
        print self.disk

class Simulation:
    def __init__(self):

        self.batches = {
        "B1": [1, 2, 6, 8],
        "B2": [2, 3, 4, 5],
        "B3": [1, 7, 8]
        }

    def simulate(self, disk):
        score = 0;

        for batch in self.batches:
            first = 999999
            last = -999999

            nextBatch = self.batches[batch]
            for resource in nextBatch:
                first = min(first, disk.disk[resource])
                last = max(last, disk.disk[resource])
            diff = last - first - len(nextBatch) + 1
            print "diff in batch", batch, "=", diff
            score = score + diff;
        return score;
        
d = Disk(9)
s = Simulation()

d.setDisk([0, 1, 2, 3, 4, 5, 6, 7, 8])
print s.simulate(d)

d.setDisk([0, 1, 3, 5, 7, 2, 4, 8, 6])
print s.simulate(d)

d.setDisk([0, 3, 4, 5, 2, 1, 6, 8, 7])
print s.simulate(d)

Het algoritme spreekt voor zich. Ik heb een tabel, Disk, waarvan Disk.disk[index] verwijst naar de positie waar index zich bevind. In Disk.setDisk wordt de vertaalslag gemaakt van een normale tabel naar de indirection table (aangezien jij in de topicstart een normale tabel aanlevert) Voor de rest zijn regel 35, en 37 van belang.

code:

[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
diff in batch B1 = 4
diff in batch B2 = 0
diff in batch B3 = 5
9
[0, 1, 3, 5, 7, 2, 4, 8, 6]
[0, 1, 5, 2, 6, 3, 8, 4, 7]
diff in batch B1 = 4
diff in batch B2 = 1
diff in batch B3 = 4
9
[0, 3, 4, 5, 2, 1, 6, 8, 7]
[0, 5, 4, 1, 2, 3, 6, 8, 7]
diff in batch B1 = 0
diff in batch B2 = 0
diff in batch B3 = 1
1

Dat wijkt af van je voorbeeld ja, maar je voorbeeld is fout
Batch B: { 2, 3, 4, 5 }
met Disk { 1, 3, 5, 7, 2, 4, 8, 6 }
levert een distance op van 1, in tegenstelling tot de 2 die in de startpost staat.

Het probleem hiermee, of althans in mijn implementatie, is dat je er geen rekening mee houd dat de grootte van de resources kan variëren. Maar dat is op te lossen met een indirection table. Men neme de volgende indirection table:

{0, 1, 2}

Stel: resource '1' is '2 eenheden' groot. Resultaat:

[0, 1, 3]

ofwel:
resource 0 staat op offset 0 op de disk
resource 1 staat op offset 1 op de disk
resource 2 staat op offset 3 op de disk
Simulation.simulate doet de rest.

Maar dat process (van het muteren van de indirection table zodat je ook de groote van de resources erbij rekent) is toch hartstikke traag? Dat zou best kunnen, geen idee. Maar misschien kan je dat ook versnellen met een heap of een 2-way indirection table of whatever. Of misschien is dat process wel heel goed te parraelliseren?

[.oisyn]

misschien moet je de topic even goed lezen, want je oplossing was al geopperd en ik heb uitgelegd waarom dat niet voldoet (m'n cost function is ingewikkelder dan alleen totale afstand).

[Verwijderd]

.oisyn schreef op woensdag 14 november 2012 @ 21:09:
(m'n cost function is ingewikkelder dan alleen totale afstand).

Dat is met de indirection table approach volgens mij ook te tackelen. Regel 34 en 35 vervangen door score += cost(lastSeen, [disk.disk[resource]) oid.

Maar ik zie dat ik inderdaad slecht gelezen heb, je 2e psuedo code is praktisch mijn python implementatie met de verbetering die in de vorige alinea heb gesuggereerd, alhoewel ik een wat andere naamgeving gebruik. Wat waarschijnlijk de bron is van verwarring.

[ytterx]

Mogelijk een dom antwoord, maar alle variabelen die je gebruikt worden aangemaakt in de for lussen. kan je deze er eens uit halen (er boven zetten (en dan al helemaal die een aantal for loopjes diep))? Dan hoeft er volgens mij niet steeds opnieuw geheugen worden geadresseerd.

[ Voor 14% gewijzigd door ytterx op 14-11-2012 21:55 ]

[PrisonerOfPain]

ytterx schreef op woensdag 14 november 2012 @ 21:54:
Mogelijk een dom antwoord, maar alle variabelen die je gebruikt worden aangemaakt in de for lussen. kan je deze er eens uit halen (er boven zetten (en dan al helemaal die een aantal for loopjes diep))? Dan hoeft er volgens mij niet steeds opnieuw geheugen worden geadresseerd.

Die komen op de GPU toch allemaal in hetzelfde register file te staan, een probleem dat 'ie heeft is z'n 1300 elementen grootte array (zie vorige post).

[.oisyn]

Verwijderd schreef op woensdag 14 november 2012 @ 21:31:

Dat is met de indirection table approach volgens mij ook te tackelen. Regel 34 en 35 vervangen door score += cost(lastSeen, [disk.disk[resource]) oid.

Ik zie niet helemaal in hoe. Het probleem is dat je de resources in een willekeurige volgorde behandelt. Maar resources die binnen M bytes van elkaar liggen hebben 0 seek tiijd, en bij meer dan M krijg je al meteen een vaste kostenpost van C. Je kunt de totale afstand wel bepalen op jouw manier, maar je weet dan niet hoeveel keer je die C erbij op moet tellen en hoe vaak je onder M bleef.

Maar ik zie dat ik inderdaad slecht gelezen heb, je 2e psuedo code is praktisch mijn python implementatie met de verbetering die in de vorige alinea heb gesuggereerd, alhoewel ik een wat andere naamgeving gebruik. Wat waarschijnlijk de bron is van verwarring.

Volgens mij niet hoor , jij loopt eerst over de batches en dan over de resources binnen een batch. Dat is wat BNieuwenhuizen ook voorstelt.

ytterx schreef op woensdag 14 november 2012 @ 21:54:
Mogelijk een dom antwoord, maar alle variabelen die je gebruikt worden aangemaakt in de for lussen. kan je deze er eens uit halen (er boven zetten (en dan al helemaal die een aantal for loopjes diep))? Dan hoeft er volgens mij niet steeds opnieuw geheugen worden geadresseerd.

Een GPU heeft geen stack, alleen registers. En die kunnen niet dynamisch worden gealloceerd, dus een shader bepaalt van tevoren hoeveel registers hij gebruikt (en de compiler is slim genoeg om de lokale variabelen efficient te koppelen aan vrije registers) . Overigens zal een CPU compiler typisch ook geen code produceren die de hele tijd de gereserveerde ruimte op de stack vergroot en verkleint, dus het is sowieso een non-issue.

@PoP: ik heb je post gezien hoor, reageren erop vergt echter iets meer tijd dan deze korte antwoordjes

[ Voor 7% gewijzigd door .oisyn op 14-11-2012 22:09 ]

[.oisyn]

PrisonerOfPain schreef op woensdag 14 november 2012 @ 20:53:
[...]


UAC uitzetten it is, I guess. Tenzij je er een NV kaart in wil zetten.

Haha, that's rich

Al die data komt in global mem te staan omdat je over je local mem spilled. Nu zit je op 400-600 cycles per access op al je local variables, in het slechtste geval.

Ja, dat vreesde ik al. De compiler waarschuwde er al voor. Ik kon alleen geen harde cijfers vinden van registergrootte. NV docs hebben het over een apart soort "local memory" in CUDA tot wel 512kB per thread, maar DirectCompute levert niet iets dergelijks. Al las ik ook wel weer dat dat dan "slow memory" zou zijn. Komt in de praktijk dan gewoon neer op een read/write buffer?

Verder kreeg ik te horen dat DeviceMemoryBarrierWithGroupSync belachelijk duur was.

Duurder dan gewoon een extra Dispatch van een nieuwe job, waarbij volgens mij ook de garantie wordt gegeven dat de vorige klaar is?

En dat je register file zo niet gefreed worden, hij stelde voor om er aparte jobs van te maken zodat je meer threads/core zou kunnen gebruiken.

Mja, het probleem is dat dat zo goed als niet te doen is. Je hebt toch een lokale state nodig voor alle batches, want je weet niet wat je per groep aan gaat treffen. En zoals ik in de TS ook al zei, ik heb een dergelijke aanpak wel geprobeerd, met als resultaat dat je vervolgens een 5000x1000 array "recursief" gaat lopen processen totdat je een 1x1000 array van kosten over hebt. De performance was enorm belabberd. Vooral ook omdat die matrix voor een groot gedeelte leeg is en de meeste threads dus uit hun neus staan te eten, terwijl je er wel 5000x1000x100 launcht. Ik heb overigens verder niet gepoogd om gewoon wat meer data per thread af te laten handelen, da's misschien ook nog wel een optie.

[PrisonerOfPain]

.oisyn schreef op woensdag 14 november 2012 @ 22:21:
[...]

Haha, that's rich

Je moet wat, hehe

[...]

Ja, dat vreesde ik al. De compiler waarschuwde er al voor. Ik kon alleen geen harde cijfers vinden van registergrootte. NV docs hebben het over een apart soort "local memory" in CUDA tot wel 512kB per thread, maar DirectCompute levert niet iets dergelijks. Al las ik ook wel weer dat dat dan "slow memory" zou zijn. Komt in de praktijk dan gewoon neer op een read/write buffer?

Die verschilt ook per manufacturer / GPU volgens mij, normaal worden je register in 'shared memory' (fast mem) gezet alleen arrays niet en als je veel registers gebruikt dus ook niet. Dan gaat 't naar 'global memory' (slow). Dit is allemaal CUDA maar die limieten zijn harde GPU limieten, kortom daar heeft DC ook mee te maken.

Duurder dan gewoon een extra Dispatch van een nieuwe job, waarbij volgens mij ook de garantie wordt gegeven dat de vorige klaar is?

Het voordeel is dat je dan je threads anders in kunt delen en je geheugen voor registers opnieuw gebruikt kan worden; als dat niet te doen is is 't zo. De call kost volgens mij niet heel veel in verhouding tot 't kicken van een nieuwe kernel (geen idee eigenlijk), het is gewoon een lock op global mem. De array zit mij meer dwars, die is groot & duur en je accessed 'm vaak.

[ Voor 24% gewijzigd door PrisonerOfPain op 14-11-2012 22:33 ]

[Verwijderd]

.oisyn schreef op woensdag 14 november 2012 @ 22:08:
Ik zie niet helemaal in hoe. Het probleem is dat je de resources in een willekeurige volgorde behandelt. Maar resources die binnen M bytes van elkaar liggen hebben 0 seek tiijd, en bij meer dan M krijg je al meteen een vaste kostenpost van C. Je kunt de totale afstand wel bepalen op jouw manier, maar je weet dan niet hoeveel keer je die C erbij op moet tellen en hoe vaak je onder M bleef.

Maar kan je de totale seektijd van de batch dan niet detineren als de totale offset, minus de totale groote van alle objecten in de batch batch, minus de groote van het laatste object van de batch?

De totale groote van de batch is een constante. En het laatste object in de batch vinden is vrij triviaal.

Wat je daarmee niet kan doen is de seektijd 1 + 1 zwaarder wegen dan seektijd 2 + 0. Ik weet niet in hoeverre dat voor jou een probleem is.

En nog even een ander idee. Wat als je nu een populatie genereert waarvan de grootte hetzelfde is als het aantal shaders op je grafische kaart. Eventueel minus een klein aantal. Zou dat de efficiëntie ten goede komen? Met 'mijn aanpak' heb je natuurlijk het voordeel dat de looptijd (zo goed als) een constante is en niet afhankelijk van de de volgorde op je disk. Ik heb je GPGPU code niet nauwkeurig bestudeerd, maar het lijkt erop alsof de snelheid voor een deel afhankelijk is van het probleem wat de shader krijgt aangeleverd.

[.oisyn]

Goddomme die AMD GPUPerfStudio is ook een teringzooitje zeg. Werkt voor geen meter. De links in de client startup page werken niet, als je de help opent kan ie geen enkele help pagina vinden, en ook als je connect naar de server doet ie niets. Ik zal 'm eens opnieuw downloaden en extracten.

.edit: nee, nog steeds niet. Het lijkt erop alsof de interne browser gewoon compleet niet werkt ofzo.

.edit2: als ik IIS uit zet en dat ding gewoon op poort 80 laat draaien dan lijkt ie wel iets te doen, maar nu hangt ie. Waarschijnlijk omdat de hele app geen frames produceert maar alleen maar compute shaders dispatcht.

.edit3: dat de interne help niets laat zien komt omdat de default zip extractor zo'n "unsafe" vlaggetje aanzet, waardoor elke help pagina silently failed

.edit4: idd, je moet idd een swap chain hebben en Present() aanroepen. http://devgurus.amd.com/thread/129652

[ Voor 53% gewijzigd door .oisyn op 14-11-2012 23:36 ]

[Ellos]

Ik zal sowieso een ander kaart regelen.
Of die 6970 gebruiken. dat is dan tenminste al VLIW4.

Dit betekent dat 4 instructies per keer gecombineerd tot 1 instructie tijdens compilatie alvorens hij dus in principe als 1 instructie berekend wordt.

Een 5870 maakt nog gebruik van VLIW5 wat erg goed is voor graphics omdat je daar veel herhalende instructie rijen heb die vervolgens in een keer gedraait worden, shaders bijvoorbeeld.

Probleem is dat t voor gpu computing eigenlijk meestal een drama is.

Omdat jij opereert op basis van vorige resultaten profiteer jij totaal niet van VLIW5 zoals bijvoorbeeld een SHA1/2 gpu implementatie dat wel doet.
zoek maar eens op hoe een 5870 het doet ten opzichte van een gtx580 in iets als bitmining (Hashes bruteforcen dus). een 6870 bijvoorbeeld, met VLIW4, doet het dus beter dan een 580 maar weer slechter dan een 5870

Mijn suggestie voor een kaartkeuze
GCN van AMD doet t beter dan GK104 wat gemaakt was voor de gamekant.
Daarmee valt de 6xx serie af, dan kan je nog beter een Fermi kaart pakken.
Wat dus momenteel het beste presteert is een 7970, en om het bedrag nog enigszins leuk te houden zou ik een mooie 7950 kiezen die je nu al voor ~€280.

Dit is dus absoluut niet iets om zomaar weg te zetten als geneuk in de marge.

Meer info over VLIW en SIMD
http://www.anandtech.com/...-architects-for-compute/3

Een V7900 is gebaseerd op Cayman VLIW4 dus alles wat daarna komt is GCN, leuk verschil toch?
http://www.tomshardware.c...00-benchmark,3265-20.html

Mijn post wbt je algoritme bespaar ik tot (vermoed ik) morgen, nadat ik er even goed naar gekeken heb of er mogelijk slimmere opties zijn, nu ben ik moe en ga ik dus naar bed.

-Ellos out

[Verwijderd]

anandtech heeft DX11 compute shader benchmarks voor een respectabel aantal kaarten.

[.oisyn]

Verwijderd schreef op woensdag 14 november 2012 @ 22:46:
[...]

Maar kan je de totale seektijd van de batch dan niet detineren als de totale offset, minus de totale groote van alle objecten in de batch batch, minus de groote van het laatste object van de batch?

De totale groote van de batch is een constante. En het laatste object in de batch vinden is vrij triviaal.

Wat je daarmee niet kan doen is de seektijd 1 + 1 zwaarder wegen dan seektijd 2 + 0. Ik weet niet in hoeverre dat voor jou een probleem is.

Dat is dus wel een probleem, omdat bij de 1 + 1 situatie er 2C bijgetelt moet worden, terwijl dat in de 2+0 situatie maar 1C is.

Stel we definieren Cost(a,b) als: b-a > 1 ? 10 + b-a : 0
En we hebben een batch B met resources { 1, 2, 3 }
En twee permutaties van resources { 1, 4, 2, 5, 3 } en { 1, 2, 4, 5, 3 }. Met jouw methode kan hier nooit een verschil in zitten. Maar met bovenstaande costfunctie zijn de resultaten resp. 22 en 12.

[.oisyn]

Verwijderd schreef op woensdag 14 november 2012 @ 23:43:
anandtech heeft DX11 compute shader benchmarks voor een respectabel aantal kaarten.

En ook @Ellos

Interessant, ik zal AMD eens pingen . Vorige keer hadden ze ons ook ongeveer 10 HD6970's cadeau gedaan

[ Voor 55% gewijzigd door .oisyn op 15-11-2012 00:38 ]

[Ellos]

't is Ellos

Ik blijf erbij dat een Souther Islands (GCN) kaart beter zal presteren dan een Kepler (GK104) kaart zal doen. Kepler is nooit gemaakt voor gpgpu, daarom is de chip ook zo zuinig. Kepler zet wel mooie resultaten neer in games, daar is het voor gemaakt, Kepler was oorspronkelijk bedoeld voor de 660TI en lager mijn vermoedens waarom dit nooit gebeurd is komen later aan bod.

DirectX11 Compute shader is een totaal achterlijke maatstaaf om totale gpgpu capaciteit aan te meten.
Logisch ook eigenlijk... om goeie resultaten in games neer te zetten moet shader computing goed zijn. Het hele shader gebied van Kepler is zeer goed geoptimaliseerd, het gaat mogelijk zelfs via specifieke paden in de chip, SSE style .

GK110 wordt pas interessant omdat dit DE chip van nvidia is die eigenlijk al uit had moeten zijn als directe competitie van de 7970.
Kepler gaf gelukkig al voldoende performance in games om de 7970 bij te benen of zelfs af te troeven. Dit of nvidia had gerekend op veel hogere performance van de 7000 serie, de geruchten waren er in ieder geval wel naar.

GK110 is kepler + fermi compute power (uiteraard dan 1 of 2 generaties sneller)
Dus een lean en mean chip, ten opzichte van fermi, die zowel goeie prestaties in games als in gpgpu neerzet, dit zal waarschijnlijk betekenen dat GK110 ongeveer net zo groot zal zijn als SI (southern islands) mits ze geen dieshrink doen.
Hiermee is ook meteen het huidige voordeel verdwenen wat kepler wel heeft (voor de gamende markt), namelijk een zeer kleine die en de voordelen in energie verbruik en warmte opwekking die daarmee gepaard gaan.

Eigenlijk zijn t ook best wel verschillende beestjes, gpgpu en graphics, t zal ook nog wel enkele gpu generaties duren voordat ze hier een mooi compromis in zullen vinden, ofwel door verbeteringen van de huidige SIMD process ofwel via een afsplitsing van game gpu's en gpgpu's (zoals bijvoorbeeld al te zien is in Xeon Phi)

Hier nog wat mooie benches en info om mijn woorden kracht bij te staan
http://www.anandtech.com/...geforce-gtx-680-review/17
http://www.anandtech.com/...k10-gk110-based-tesla-k20

EDIT: toch nog weer wat toegevoegd en veranderd.

[ Voor 26% gewijzigd door Ellos op 15-11-2012 00:34 . Reden: structuur verbeterd, bedtijd!!! ]

[Verwijderd]

Even iets anders

.oisyn schreef op woensdag 14 november 2012 @ 14:53:
cost(a,b) = |a-b| <= M ? 0 : C + |a-b|/X

Zie je de volgende situatie niet over het hoofd?

situatie 1:
resource 1 = offset 30KB
resource 2 = offset 32KB
ofwel: 2 sectoren.

situatie 2:
resource 1 = offset 32KB
resource 2 = offset 34KB
ofwel: 1 sector.

Overigens niet gehinderd door enige kennis van optische media, maar volgens mij is situatie 2 te prefereren ondanks dat de offset tussen de resources exact hetzelfde is.

Ellos schreef op donderdag 15 november 2012 @ 00:18:
DirectX11 Compute shader is een totaal achterlijke maatstaaf om totale gpgpu capaciteit aan te meten omdat shader computing goed moet zijn wil je snelle resultaten in games neerzetten.
Logisch ook eigenlijk het hele shader gebied van Kepler is zeer goed geoptimaliseerd. en gaat mogelijk zelfs over specifieke paden in de chip.

Dat ben ik met je eens. Maar ik haalde het aan omdat:

.oisyn schreef op woensdag 14 november 2012 @ 02:27:
geïmplementeerd op de GPU (middels DirectX11 compute shaders):

[ Voor 9% gewijzigd door Verwijderd op 15-11-2012 00:32 ]

[.oisyn]

Verwijderd schreef op donderdag 15 november 2012 @ 00:32:
Zie je de volgende situatie niet over het hoofd?

situatie 1:
resource 1 = offset 30KB
resource 2 = offset 32KB
ofwel: 2 sectoren.

situatie 2:
resource 1 = offset 32KB
resource 2 = offset 34KB
ofwel: 1 sector.

Sector size is 2k.

[Ellos]

Ik had door waarom je het deed.
Maar om de verwarring bij onze trouwe lezers niet te vergroten heb ik even verklaard dat er bij gpgpu dus niet alleen daarnaar gekeken moet worden, misschien zou iemand aan de hand van die bench wel voor een gtx680 voor zijn gpgpu werk kiezen en dat zou zonde zijn.

Mogelijk is directx 11 compute shader ook niet de beste manier om dit aan te pakken en blijkt OpenCL veel beter te presteren.

Meer hierover van mij hoor je morgen, ik blijf weer plakken merk ik

[ Voor 3% gewijzigd door Ellos op 15-11-2012 00:46 ]

[roeny]

First of all, zeer interessant topic! lekker parralellolizable

Ik zou persoonlijk voor een kepler/fermi gaan
Kepler is een stuk 'dommer' dan fermi en is daardoor makelijker te programeren, heeft meer onchip geheugen en een boel nieuwe instructies die leuk zijn voor Compute.
Omdat ze er veel hardware uit gesloopt hebben hebben ze er 4 keer zoveel SM's in gepropt zonder je transistor count veel te verhogen, meer SM's = meer threads = lower memory latency.

Disclaimer : Ik heb alleen ervaring met openCL voor AMD, heb nog nooit DirectCompute gebruikt
Dingen die ik op AMD(opencl) tegen nem gekomen waar ik met Nvidia(cuda) nog geen last van heb gehad.
1) Ja, AMD is sneller.. maar hun drivers zijn zo ontzettend brak dat je die performance levels voor compute vaak niet haalt.
2) Het is een stuk moeilijker om voor te programmeren omdat je performance vaak voor geen goede reden in elkaar stort ( waarschijnlijk een compiler issue ), ook zijn er geen (degelijke) profilers
3) Je kunt niets heen of terug naar RAM kopieren tijdens het draaien van een kernel.
4) Page locked CPU memory benaderen vanaf je GPU werkt soms, wat het vrij onbruikbaar maakt .
5) de Tahiti opencl compiler kan geen complexe code compile die texture lookups gebruikt. dit gaat redelijk willekeurig mis, zeer frustrerend. het kan zijn dat dit inmiddels gefixed is.

[Zoijar]

roeny schreef op donderdag 15 november 2012 @ 13:19:
Ik zou persoonlijk voor een kepler/fermi gaan

Ik denk dat hij beter eerst kan gaan voor het uberhaupt sneller krijgen op een GPU dan de CPU CPUs zijn ook niet zo langzaam, intel is ook niet gek, en niet alles draait magisch een factor 10 sneller op een GPU. Dat gaat alleen als je je probleem zo kan opschrijven dat het optimaal werkt op die hardware.

(Zo deden wij dingen ook vaak juist op de CPU, via het netwerk, omdat je dan de hele afdeling aan desktop computers in kon zetten in het weekend. Tientallen quad cores verslaan de meeste GPUs Hele simpele manier: schrijf job files naar een shared netwerk locatie, iedereen mag daar een file locken en een result file wegschrijven, lees results files terug. Schaalbare dynamische cluster )

[ Voor 29% gewijzigd door Zoijar op 15-11-2012 14:37 ]

[pedorus]

PrisonerOfPain schreef op woensdag 14 november 2012 @ 20:53:
Verder heb ik 't er even met een kennis over gehad (heeft hier geen account ) die mij wees op regel 38. Al die data komt in global mem te staan omdat je over je local mem spilled. Nu zit je op 400-600 cycles per access op al je local variables, in het slechtste geval.

Als ik het opzoek heeft zo'n 5870 32 kb local geheugen, en een 7970 64 kb (opzoekfouten daar gelaten). Wellicht dat er nog een factortje 4 aan capaciteit verloren gaat vanwege alignment, dan nog zou dat toch moeten passen (1300*4*4=~21kb)? Random access op groupBatches lijkt me eerder een probleem.

[.oisyn]

Ik kan het nergens terugvinden op die pagina's. Wellicht ben je in de war met thread group shared memory?

[pedorus]

Ik heb het uit een document wat naar dit document verwees, en vond het in een van de plaatjes. Ik zie het ook in deze presentatie, slide 5: http://www.microway.com/p...erformance_Comparison.pdf . Of is dit iets dat je nog door 16 thread processors zou moeten delen?

[ Voor 15% gewijzigd door pedorus op 15-11-2012 15:51 ]

[.oisyn]

Het is idd geen thread group gedeeld geheugen in de zin dat iedere thread binnen de thread group naar dat geheugen kan schrijven, maar het is wel gedeeld geheugen in de zin dat iedere SIMD unit totaal 32kB aan lokaal geheugen heeft waar de 16 threads van de SIMD uit alloceren. Oftewel, als 1 thread 32kB opeet dan zal op die SIMD unit maar 1 thread draaien.

[ Voor 9% gewijzigd door .oisyn op 15-11-2012 16:07 ]

[PrisonerOfPain]

@.oisyn: roeny was de kennis van een paar posts geleden.

pedorus schreef op donderdag 15 november 2012 @ 15:47:
Ik heb het uit een document wat naar dit document verwees, en vond het in een van de plaatjes. Ik zie het ook in deze presentatie, slide 5: http://www.microway.com/p...erformance_Comparison.pdf . Of is dit iets dat je nog door 16 thread processors zou moeten delen?

In NV termen werkt het zo, je krijgt dus 16/48kb shared memory per streaming multiprocessor. Dat is een apparaat bestaande uit N streaming processors. Een streaming multiprocessor krijgt 1 instructie tegelijk en laat die N keer uitvoeren (met verschillende data) op z'n streaming processors. Dit is hoe SIMT (Single Instruction Multiple Thread) werkt.

Als je naar die Fermi core krijgt zie je dat 'ie dus 16 SMs heeft en 32 SPs, kortom die 16 of 48kb moet je nog delen door 32 voor optimaal gebruik. Dan houd je dus ongeveer 0.5kb/1.5kb over voor al je registers en scratch data.

Die ATi kaart zit wat anders in elkaar kwa terminologie en mem/cpu verhoudingen maar de architecture is hetzelfde. Die evergreens hebben 20 SMs met ieder 16 SPs en 32kb per SM, dus 2kb per thread.

Kortom, die int array van 1300 (5200 bytes / thread) elementen past nooit in je snelle geheugen en moet dus in je trage mem gestopt worden. Nu is het volgens mij zo dat je niet al je lanes hoeft te gebruiken dus zou je d'r in deze situatie optimaal gebruik van te kunnen maken door er 3 per SM te draaien.

[ Voor 7% gewijzigd door PrisonerOfPain op 15-11-2012 18:15 ]

[ArtyShock]

Hmm. Interessant probleem dit. Iets in mij probeert toch nog een enigszins deterministische oplossing te vinden zonder alle permutaties te hoeven bruteforcen. Ik blijf nog even denken.

Wat ik me nog afvraag... Niet om je probleemdomein te vergroten hoor, maar heeft het in de praktijk nog nut om de batches te prioriteren? Bijvoorbeeld op basis van batch-grootte? Geen idee hoe die batches gebruikt worden in de praktijk, maar ik kan me voorstellen dat het voor een kleine batch minder interessant is om te optimaliseren dan voor een grote batch. Omgekeerd is het misschien handig om een batch die veel meer wordt ingelezen dan een andere batch een hogere wegingsfactor te geven.

Is bovenstaande een overweging geweest bij het indelen van je algoritme, of is dat in de praktijk niet nuttig genoeg?

[.oisyn]

Batches zijn redelijk uniek voor die specifieke situatie en komen zelden meerdere keren voor. Je hebt er wel een paar die meerdere keren voorkomen, maar dan hoogstens een keer of 6. Het is voor het totale getalletje wellicht leuk, maar het heeft niet zo heel veel zin om iets dat 4x voorkomt in de totale doorlooptijd van de gehele game beter te gaan optimizen dan iets dat 2x voorkomt.

Wel zijn er kritieke batches met een hogere prioriteit. Deze zijn gevlagd tijdens het testen omdat de content gewoonweg niet snel genoeg binnenkwam.

Overigens, aan alle mensen die lopen te hameren op deterministische algoritmes: allemaal heel leuk enzo, maar de topic ging over het probleem van het evalueren van de fitness. Wat voor soort heuristic search je ook toepast, je zal hoe dan ook die fitness moeten evalueren, en het doel van deze topic is het sneller krijgen van die evaluatiestap, waar veruit 90% van de gespendeerde tijd in gaat zitten. Staar je dus niet blind op het feit dat ik een keer de term GA heb laten vallen.

[ Voor 30% gewijzigd door .oisyn op 17-11-2012 01:30 ]

[Verwijderd]

Maar bij een DA kan je 'misschien' de fitness stap sneller maken door niet de fitness zelf te berekenen, maar slechts een deel daarvan.

Stel je verwisselt resource X en Y van plaats. Dan hoef je alleen de batches waar X of Y gebruikt worden opnieuw te berekenen. Misschien kan je iets vergelijkbaars toepassen op je GA.

[.oisyn]

Verwisseling is een zo goed als zinloze mutatie. Je zal voornamelijk zitten schuiven met deelpermutaties. En dat heeft invloed op alle batches die resources hebben waarvan de onderlinge afstand verandert. In de praktijk is al die interne bookkeeping een grotere kostenpost dan het relatief simpele proces van een volledige evaluatie.

Maar natuurlijk, als je makkelijk een incremental update kunt doen dan is dat altijd aan te raden. Maar dat geldt voor de GA net zo goed.

[Soultaker]

.oisyn schreef op zaterdag 17 november 2012 @ 01:24:
Overigens, aan alle mensen die lopen te hameren op deterministische algoritmes: allemaal heel leuk enzo, maar de topic ging over het probleem van het evalueren van de fitness. Wat voor soort heuristic search je ook toepast, je zal hoe dan ook die fitness moeten evalueren [..]

Dat is helemaal niet gezegd; ik kan me bijvoorbeeld allerlei greedy algoritmen voorstellen waarbij het evalueren van fitness helemaal geen bottleneck vormt.

Je mag je natuurlijk best beperken tot het evalueren van fitness op een GPGPU omdat je je nu eenmaal op die aanpak vastgelegd hebt (het is jouw topic, tenslotte, en dat is het concrete probleem wat je op wil lossen) maar dat zegt niet dat alle andere mogelijke benaderingen bij voorbaat kansloos zijn.

Je kunt anderen moeilijk kwalijk nemen dat ze niet bij voorbaat van de superioriteit van genetische algoritmen overtuigd zijn; eerlijk gezegd heb je alleen je reputatie op GoT om die aanname te ondersteunen, want overtuigende data heb ik niet gezien.

[.oisyn]

maar dat zegt niet dat alle andere mogelijke benaderingen bij voorbaat kansloos zijn.

Dat heb je mij niet horen zeggen.

Je kunt anderen moeilijk kwalijk nemen dat ze niet bij voorbaat van de superioriteit van genetische algoritmen overtuigd zijn

En ook dát heb je mij niet horen zeggen. Het punt dat ik duidelijk probeer te maken is dat het probleem dat ik op wil lossen an sich weinig te maken heeft met het GA, en allerminst inherent gekoppeld is eraan terwijl iedereen dat wel zo behandelt. Goed, dat je niet in alle gevallen de fitness function nodig hebt, soit.

Dat is helemaal niet gezegd; ik kan me bijvoorbeeld allerlei greedy algoritmen voorstellen waarbij het evalueren van fitness helemaal geen bottleneck vormt.

Bij all means, doe een poging zou ik zeggen

[ Voor 9% gewijzigd door .oisyn op 17-11-2012 04:09 ]

[Soultaker]

Zoals ik eerder zei: als je wil dat mensen andere benaderingen proberen, kun je het beste wat representatieve testdata online zetten, samen met een scriptje om de fitness van de oplossing te bepalen, en de fitness die jouw huidige oplossing bereikt.

Dan kunnen er twee dingen gebeuren: ofwel iemand komt op de proppen met een slim algoritme dat beter werkt dan jouw genetische algoritme (en dan kun je zijn aanpak emuleren) of men komt erachter dat jouw huidige aanpak eigenlijk wel heel goed werkt (ook niet onwaarschijnlijk, lijkt me) en dan is men in ieder geval overtuigd van de noodzaak om de fitness evaluatie te optimaliseren (of je daar dan nog meer zinnige suggesties voor krijgt is een tweede natuurlijk, aangezien ik vermoed dat weinigen ervaring hebben met programmeren voor GPGPU's, maar het lijkt me sowieso nuttig om te weten of je op de goede weg zit).

Ik denk niet dat veel mensen zin hebben om alternatieve aanpakken uit te werken zonder de relevante scenarios te kennen.

[KopjeThee]

OK, het is nog vroeg, dus neem mij iets minder kwalijk als ik onzin verkoop. Maar iets in de trant van:

1. We maken een afstandsmatrix tussen alle resources door:
   1. Initieel alle afstanden (bijvoorbeeld) op het aantal batches te zetten.
   2. De afstand tussen 2 resources te verlagen met het aantal batches waarin ze gemeenschappelijk zitten. Dit is voor een paar duizend resources/batches prima te doen.
2. We doen een travelling salesman oplossing over de resources. Hier zijn redelijk efficiënte benaderingen voor, zeker als het maar om een paar duizend punten gaat (meest simpel te implementeren misschien een 2-opt).

Dat representeert niet helemaal je kosten functie, maar zou wel eens aardig in de buurt kunnen komen in een fractie van de tijd. Desnoods gebruik je het resultaat als initiële vulling voor je populatie in je GA (de gevonden route doorknippen op een paar punten met hoge afstand, geeft je wat individuen), dan kan je allicht met veel minder generaties toe.

[ Voor 6% gewijzigd door KopjeThee op 17-11-2012 09:09 ]

[pedorus]

PrisonerOfPain schreef op donderdag 15 november 2012 @ 18:12:
Kortom, die int array van 1300 (5200 bytes / thread) elementen past nooit in je snelle geheugen en moet dus in je trage mem gestopt worden. Nu is het volgens mij zo dat je niet al je lanes hoeft te gebruiken dus zou je d'r in deze situatie optimaal gebruik van te kunnen maken door er 3 per SM te draaien.

Interessant! Nu is de vraag natuurlijk hoe je dat zo kan instellen, en of dit beter zal werken. In hoeverre lopen threads exact tegelijkertijd en kunnen ze dit geheugen delen? Ik kan me zo voorstellen dat de opsplitsing in 128 threads nu niet handig is gedaan. Nu is het vooral een workaround als ik het goed begrijp om het maximum aantal instructies per shader niet te overschrijden. Handiger zou zijn om de opsplitsing (ook) over batches-loop (for(b)) te doen als je het geheugen mag delen en de boel exact tegelijkertijd loopt. Per SIMD-unit reken je 1 instantie door, 100 instanties is prima deelbaar door 20, dus dit gaat al goed.

[Verwijderd]

Als ik zijn code goed begrijp doet hij dat al. Hij verdeelt zijn fitness algoritme in stukken van 64 batches per stuk. (dus 1000 batches -> ~16 brokken).

Je kan het verder iets optimaliseren door de batches te sorteren, zodat in elk brok van 64 *ongeveer* evenveel resources zitten zodat elke thread evenveel werk doet. Maar ik neem aan dat hij dat al doet.

[pedorus]

Verwijderd schreef op zaterdag 17 november 2012 @ 12:22:
Als ik zijn code goed begrijp doet hij dat al. Hij verdeelt zijn fitness algoritme in stukken van 64 batches per stuk. (dus 1000 batches -> ~16 brokken).

De opsplitsing is nu over de 5000 resources. Die worden in 128 blokjes werk opgedeeld, waardoor je die array van 1300 nodig hebt per blokje werk, wat te veel is. Binnen 1 resources zijn er 64 batches mogelijk waarin deze gebruikt worden. Als je daarover zou verdelen, zou je misschien die array kunnen delen.

Je kan het verder iets optimaliseren door de batches te sorteren, zodat in elk brok van 64 *ongeveer* evenveel resources zitten zodat elke thread evenveel werk doet. Maar ik neem aan dat hij dat al doet.

Als de instructieset voor alle 16 threads in hetzelfde tempo wordt afgelopen, dan maakt dit weinig uit. Ik baseer me op http://s08.idav.ucdavis.edu/fatahalian-gpu-architecture.pdf pagina 25.

[Verwijderd]

pedorus schreef op zaterdag 17 november 2012 @ 13:04:
De opsplitsing is nu over de 5000 resources. Die worden in 128 blokjes werk opgedeeld, waardoor je die array van 1300 nodig hebt per blokje werk, wat te veel is.

Waarom is dat te veel? Als ik in alle shaders van een bepaalde core dezelfde array van 5000 elementen hebt, dan past dat toch prima in de 64/48/16kb die je per 'core' hebt? Of werkt dat niet op die manier?

[pedorus]

Het probleem is dat je met het behandelen van 5000 resources waarschijnlijk over de maximale grootte van de instructieset per shader gaat. Er zijn in die instructieset namelijk geen loops mogelijk als ik het goed begrijp.

Als je die 1300 bedoelt, dan zit je met het probleem dat 1300 ints * 4 bytes * 16 threads met zo'n array niet in de 32 kb per SIMD-unit (waarop 16 threads draaien) passen. Of zie ook de uitleg van PrisonerOfPain in "[GPGPU] Efficient parallel algoritme voor DVD seek simulatie"

[.oisyn]

Er zijn we loops mogelijk, het punt is dat iedere thread op een SM dezelfde set instructies uitvoert. Als A dus vaker loopt dan B dan staat B voor de iteraties die ie niet neemt uit z'n neus te eten. Instructielimiet is overigens zo goed als nonexistent.

Die array van 1300 is de interne state van 1 thread - een last read offset per batch. Aangezien ik 1200 nogwat batches heb heb ik de array 1300 groot gemaakt. Hij loopt over een gelimiteerd aantal resources, maar wel over alle batches per resource. Hij kan dus potentieel elke batch tegenkomen.

Je kan wel zeggen dat elke thread maar een X aantal batches per resource mag doen, maar dat betekent niet dat die array kleiner kan. Wat wel kan is dat iedere thread alleen de batches Xm tot Xn doet, maar dan staat het meerendeel niets te doen (gemiddeld heeft een batch iets van 150 resources, dus verdeeld over 5000 resources is de kans dat een batch in een resource vertegenwoordigd is slechts 150/5000 = 3%)

[Verwijderd]

Maar wat als je het omdraait: elke thread loopt over alle resources. Maar als de thread de batches van die resource opvraagt, dan krijgt hij slechts een deel van de batches terug.

van:

code:

int lastread[batches.size] = { 0 };
foreach (r in resources)
{
    foreach (b in r.batches)
    {
        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset;
    }    
}

naar:

code:

int lastread[batches.size] = { 0 };
foreach (r in resources)
{
    foreach (b in r.batches(van, tot))
    {
        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset;
    }    
}

Als je het intern organiseert als een array van 5000x1300bit reken je af met het probleem van stall's ten koste van een hogere big-O.

[pedorus]

Als de instructielimiet en/of het gebrek aan loops niet de reden is, vanwaar dan deze zin: "Je kan niet in een shader even doodleuk 5000 elementen aflopen."? Even afgezien van het geheugenprobleem zou je dan 1 thread/werkeenheid per instantie kunnen doen.

Ik bedoelde niet dat iedere thread een range aan batches doet, want dat is waarschijnlijk langzamer dan de oplossing met 3 threads (de theads lopen tegelijkertijd). Ik bedoelde dat het wellicht toegestaan zou zijn om de state te delen met 16 threads (groupshared) als iedere thread 4 batches uit groupbatches zou kunnen afhandelen, omdat je weet dat de threads exact tegelijkertijd afgehandeld worden, en er toch geen overlappingen voorkomen binnen die 64 batches/resource.

[.oisyn]

Dat was wat ongelukkig verwoord. Maar meer kortere threads geeft een veel beter granularity wat scheduling betreft.

Dat ze hetzelfde doen is alleen binnen 1 SM he, en bovendien geen keiharde garantie. Je zal ze dan per group moeten synchroniseren

[.oisyn]

Verwijderd schreef op zaterdag 17 november 2012 @ 14:58:
Als je het intern organiseert als een array van 5000x1300bit reken je af met het probleem van stall's ten koste van een hogere big-O.

Ik heb dit in het begin eens geprobeerd, maar het was een van de slechter performande oplossingen, waarschijnlijk omdat zoveel threads niets te doen hebben.

Soultaker schreef op zaterdag 17 november 2012 @ 04:17:
Zoals ik eerder zei: als je wil dat mensen andere benaderingen proberen, kun je het beste wat representatieve testdata online zetten, samen met een scriptje om de fitness van de oplossing te bepalen, en de fitness die jouw huidige oplossing bereikt.

Voor de geïnteresseerden: http://oisyn.nl/testdata.txt
Op elke regel staan een aantal ints gescheiden door komma's. Elke regel stelt een group voor, de eerste int is de grootte van de group, de rest van de ints zijn de batches waarin die group voorkomt.

De totale kosten van een oplossing definiëren we als:

code:

int cost(int fromOffset, int toOffset)
{
    int d = toOffset - fromOffset;
    return d > 32768 ? 75 + d / 34761904 : 0;
}

int lastread[batches.size] = { 0 };
foreach (r in resources)
{
    foreach (b in r.batches)
    {
        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset + r.size;
    }    
}

Zou je de groepen in testdata.txt gewoon van voor naar achter zetten dan zou je uit moeten komen op een totale waarde van 3.687.599.

[ Voor 61% gewijzigd door .oisyn op 18-11-2012 00:16 ]

[Verwijderd]

code:

        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset;

Zou je daar niet eerder dit van maken?

code:

        if (lastread[b])
            totalcost += cost(lastread[b], r.offset);
        lastread[b] = r.offset + r.size;

(regel 3)

Stel dat je een hele lange resource en een korte resource hebt. Deze staan exact achter elkaar. Volgens jouw algo is de volgorde van belang, maar dat lijkt mij niet. Je wilt alleen de loze ruimte tussen de resources meten.

[.oisyn]

Klopt, foutje

[ Voor 72% gewijzigd door .oisyn op 18-11-2012 00:17 ]

[Caelorum]

Heb je toch nog wat uit het topic gehaald

[.oisyn]

Euh nee, het was een foutje in mijn post, niet in mijn daadwerkelijke algo (zoals je aan mijn shader code kunt zien)

[Soultaker]

Als ik met onderstaande code test:

Python:

#!/usr/bin/env python3

resources = [ [ int(i) for i in line.rstrip(',\n').split(',') ]
              for line in open('testdata.txt') ]

def cost(fromOffset, toOffset):
    d = toOffset - fromOffset
    return 75 + d // 34761904 if d > 32768 else 0

lastread = {}
totalcost = 0
offset = 0
for r in resources:
    size = r[0]
    for b in r[1:]:
        if b in lastread:
            totalcost += cost(lastread[b], offset)
        lastread[b] = offset + size
    offset += size
print(totalcost)

... dan is totalcost 3737856.002814118 (of 3724445 als ik op regel 7 integer division gebruik). Da's dus net iets te hoog.

Weet je zeker dat die 3687599 klopt voor deze invoer? Of doe ik ergens iets verkeerd?

[pedorus]

.oisyn schreef op zaterdag 17 november 2012 @ 17:33:
Dat ze hetzelfde doen is alleen binnen 1 SM he, en bovendien geen keiharde garantie. Je zal ze dan per group moeten synchroniseren

Het lijkt erop dat DirectCompute niet direct ondersteuning hiervoor heeft, zoals AMD/Nvidia dat wel hebben met Warp/Wavefront: http://forum.beyond3d.com/archive/index.php/t-55751.html Toch zou je kunnen proberen om 100 (populatie) threadgroups van 16 threads die dit doen te maken, al dan niet nog eens opgesplitst zoals je nu al doet. Misschien dat de drivers in dit geval zelfs kunnen detecteren dat een DeviceMemoryBarrierWithGroupSync niet daadwerkelijk nodig is.

Over de evaluatiefunctie: hou je er geen rekening mee dat data aan de binnenkant van de dvd lezen met een andere snelheid gaat dan aan de buitenkant, en met een prioriteit per batch (bjjv. op basis van hoe vaak je een bepaalde batch nodig hebt en/of hoe vervelend de laadtijd van deze batch is in de gameplay)?

[Verwijderd]

Bij mij klopt de uitvoer ook niet: ik kom eveneens op 3724445 met cost() als integer. In mijn eigen python implementatie.

pedorus schreef op zondag 18 november 2012 @ 00:48:
Over de evaluatiefunctie: hou je er geen rekening mee dat data aan de binnenkant van de dvd lezen met een andere snelheid gaat dan aan de buitenkant, en met een prioriteit per batch (bjjv. op basis van hoe vaak je een bepaalde batch nodig hebt en/of hoe vervelend de laadtijd van deze batch is in de gameplay)?

Daar had ik ook al aan gedacht. Maar dan moet je ook rekening houden met de verschillende laagjes van DVD's.

[ Voor 14% gewijzigd door Verwijderd op 18-11-2012 01:11 ]

[.oisyn]

Euh ja dat klopt ook, het moet idd 3724445 zijn. Ik had per ongeluk al een soort van optimilisatiestap gedaan en daarna pas naar de waarde gekeken

pedorus schreef op zondag 18 november 2012 @ 00:48:
Over de evaluatiefunctie: hou je er geen rekening mee dat data aan de binnenkant van de dvd lezen met een andere snelheid gaat dan aan de buitenkant, en met een prioriteit per batch (bjjv. op basis van hoe vaak je een bepaalde batch nodig hebt en/of hoe vervelend de laadtijd van deze batch is in de gameplay)?

Jawel, dat doe ik wel, en ik hou ook rekening met layer switching, maar ik dacht laat ik de boel ietwat simpel houden.

[ Voor 64% gewijzigd door .oisyn op 18-11-2012 02:22 ]

[Neverwinterx]

Vraagje: waarom is het eigenlijk nodig in de eerste versie van je fitness evaluatie algoritme om eerst de resources in de batch te sorteren? Liggen de batches en de resources daarin niet vast in het begin (i.e. de playthrough van de game die je simuleert) en zijn de individuen in je populatie niet gewoon de volgorde van de resources? Dan moet je toch gewoon maar 1 keer in het begin van het G.A. die resources in de batches sorteren en daarna nooit meer (dus niet in elke fitness evaluatie voor elk individu in elke generatie)? Of simuleer je met meerdere mogelijke playthroughs die op verschillende manier batches/resources laden? Of versta ik de individuen verkeerd en behoort hoe een batch eruit ziet tot het individu?

Niet gerelateerd aan de fitness:
Ik vind ook dat je een zeer kleine populatie hebt en erg veel generaties. Hier wat lectuur en hier.

Gebruik je trouwens elitist selection?

[ Voor 3% gewijzigd door Neverwinterx op 18-11-2012 14:28 ]

[Verwijderd]

De volgorde van de resources van de batch zijn van belang, je wilt namelijk de ruimte tussen de resources meten. Om dat voor elkaar te krijgen op de manier die .oisyn wil moeten de resources langskomen in de volgorde dat ze op de disk staan. Zie ook .oisyn in "[GPGPU] Efficient parallel algoritme voor DVD seek simulatie".

Dan zijn er dus 2 mogelijkheden: je loopt door de disk heen (want de disk is gesorteerd), of je loopt door de batches heen, en sorteert die.

(of je pakt het anders aan en maakt een cost() berekening waarbij de volgorde niet belangrijk is, maar dat is suboptimaal).

---

Als je je algoritme laat draaien op de testdata, wat voor fitness komt daar dan uit? Dan kan ik een inschatting maken hoe goed mijn probeersels zijn.

Na 2 uur rekenen print mijn houtje-toutje algoritme 932710

[ Voor 14% gewijzigd door Verwijderd op 18-11-2012 19:07 ]

[.oisyn]

Netjes. Ik heb nog geen cijfers van deze data. Wat doe je ongeveer?

[Verwijderd]

Ik begin met een lege resource pool. Dan pak ik resource R (het eerste resource uit jouw bestandje). R probeer ik op alle mogelijk posities in de resource pool te inserten, na elke insert bereken ik de fitness. Als ik alle mogelijke posities heb geprobeerd plaats in R op de meest optimale plek (de positie met de laagste fitness).

Daarna bestaat de resource pool uit 1 resource. En herhaal ik het geheel weer. Ik moet het nog even optimaliseren zodat het wat sneller gaat (veel insert en delete operaties uitvoeren op een vector = geen succes) zodat ik misschien meerdere passes eroverheen kan maken binnen een acceptabele tijd. En zoals ik al eerder vermeldde kan het evalueren van de fitness veel sneller als slechts een beperkt deel van de data verandert.

Om een idee te krijgen van de snelheid van mijn bak: ik doe ongeveer 1300 fitness berekeningen op de test data per seconde. Jij doet er volgens mij 10.000 (100 generaties x 100 populaties per seconde).

Ik verwacht er niet al te veel van, maar het is leuk om te proberen.

[ Voor 12% gewijzigd door Verwijderd op 18-11-2012 20:25 ]

[.oisyn]

Je zou een linked list kunnen gebruiken. Of een iets aangepaste evaluatiefunctie met als extra parameter een additionele resource op een bepaalde plek. Dan hoef je tijdens het vinden van de beste plek niet de fysieke lijst aan te passen, dat doe je dan pas als je de definitieve plek weet.

[Verwijderd]

Ik heb het even getest: een list is een seconde per minuut sneller dan een vector, omdat de evaluatiefunctie verreweg het meeste tijd in neemt. Die roep ik al 501500x aan als ik bij 1000 resources stop. Even denken hoe ik het sneller kan maken.

[ Voor 9% gewijzigd door Verwijderd op 18-11-2012 20:34 ]

[.oisyn]

Ik zou het proberen op de GPU te doen

Wat je evt nog zou kunnen doen is plekken negeren die niet naast een willekeurige resource staan die in één van de batches zit waar de te plaatsen resource ook in zit.

En/of een incrementele evaluatie.

[ Voor 76% gewijzigd door .oisyn op 18-11-2012 20:56 ]

[Verwijderd]

Misschien doe ik dat wel, maar dan moet ik het eerst het algoritme op de CPU goed werkend hebben (en ik betwijfel of mijn antieke radeon 4570m sneller is dan een 2.4Ghz C2D...)

.oisyn schreef op zondag 18 november 2012 @ 20:46:
En/of een incrementele evaluatie.

Dat is wat ik nu aan het testen ben. Jouw eerste algoritme uit TS, maar dan alleen de batches die ook daadwerkelijk interessant zijn.

[ Voor 44% gewijzigd door Verwijderd op 18-11-2012 21:22 ]

[Soultaker]

Verwijderd schreef op zondag 18 november 2012 @ 20:17:
Ik begin met een lege resource pool. Dan pak ik resource R (het eerste resource uit jouw bestandje). R probeer ik op alle mogelijk posities in de resource pool te inserten, na elke insert bereken ik de fitness. Als ik alle mogelijke posities heb geprobeerd plaats in R op de meest optimale plek (de positie met de laagste fitness).

Dit was ook mijn eerste aanpak en ik kom op bijna exact dezelfde oplossing uit (932522 exact) al snap ik niet wat je hierna probeert te doen.

De kern van mijn code is simpelweg dit:

C++:

static vector<int> optimize(const Problem &prob, vector<int> perm)
{
    vector<int> opt;
    for(int i = 0; i < perm.size(); ++i)
    {
        vector<int> best, next = opt;
        next.push_back(perm[i]);
        int best_value = evaluate(prob, next);
        best = next;
        for (int j = i; j > 0; --j)
        {
            swap(next[j], next[j - 1]);
            int value = evaluate(prob, next);
            if (value < best_value)
            {
                best_value = value;
                best = next;
            }
        }
        opt = best;
    }
    return opt;
}

Dit duurt wat lang maar is (denk ik) nog wel sneller te maken. Los daarvan kan ik me voorstellen dat de volgorde waarin je resources probeert te inserten mogelijk van invloed is op de kwaliteit van de oplossing. Misschien moet ik daar eens mee gaan spelen.

Maar ik ben ook wel benieuwd wat .oisyn's fancy genetic algorithm op deze data doet, om te zien of dit enigzins in de juiste ballpark zit of niet.

[Verwijderd]

Soultaker schreef op zondag 18 november 2012 @ 21:30:
Dit was ook mijn eerste aanpak en ik kom op bijna exact dezelfde oplossing uit (935522 exact) al snap ik niet wat je hierna probeert te doen.

Ik probeer de fitness functie te versnellen door domeinspecifieke kennis toe te voegen. Als je resources A en B verwisselt dan weet je zeker dat de fitness van de batches die niet in A of B voorkomen niet zijn veranderd.

[Soultaker]

Dat geldt alleen als ze direct tegen elkaar aanliggen, of dezelfde grootte hebben.

[Verwijderd]

Dat geldt, inderdaad alleen als ze direct tegen elkaar aanliggen, maar dat is ook het enige soort swap wat mijn algoritme uitvoert.

Maar goed dat je het even zegt, ik had het nog niet op die manier bekeken.

---

De nieuwe aanpak is erg succesvol.

bij 1000 elementen duurt het algoritme:
54 seconden met volledige fitness evaluatie. Fitness = 241089
47 seconden met gedeeltelijke fitness evaluatie Fitness = 246210

bij ~5300 elementen duurt het algoritme:
2 uur seconden met volledige fitness evaluatie. Fitness = 932710
22 minuten met gedeeltelijke fitness evaluatie. Fitness = 948883

De fitness is wel iets minder, ik heb wel een vermoedden waar de fout zit.

[ Voor 79% gewijzigd door Verwijderd op 18-11-2012 22:22 ]

[Soultaker]

Nice, ik ga ook zo'n soort optimalisatie proberen, maar ik vermoed dat ik op ongeveer hetzefde uitkom als jij.

edit: Blegh, ik kom er even niet uit. Later verder. Mijn laaste poging resulteerde trouwens in een score van 867,121 in iets minder dan een uur (op een vrij snelle machine).

[ Voor 46% gewijzigd door Soultaker op 19-11-2012 00:03 ]

[Verwijderd]

Ik krijg nu dezelfde resultaten met de gedeeltelijke en volledige fitness evaluatie. Daarnaast heb ik een simpel loopje gemaakt die de oplossing tracht te verbeteren. Die laat ik de rest van de avond draaien.

Verder zijn er nog flink wat versnellingspunten mogelijk: STL sort heeft O(n * (log n)²) complexiteit. Wat natuurlijk extreem brak is om iets te sorteren wat 99% van de tijd al gesorteerd is.

Verder vraag ik me ook heel erg af waar .oisyn's gekke algoritme op uitkomt met de testdata.

Overigens zie ik het voordeel van een evolutionair algoritme wel in: je parraliseert het in een handomdraai. Een DA is een stuk lastiger te splitsen over de gewenste thread of 8. Laat staat een GPU...

---

Na een uur of 4 draaien prijkt de score plusminus 801000. Het lijkt erop dat ik bijna op een lokaal minimum zit. Hij heeft 44890 iteraties gemaakt (8 volledige passes van element verwijderen en weer op de ideale plek insecten). Is dat wat je bedoelde met 'iteraties verwisselen is een tamelijk zinloze mutatie'?

[ Voor 18% gewijzigd door Verwijderd op 19-11-2012 08:02 ]

[Neverwinterx]

Verwijderd schreef op zondag 18 november 2012 @ 17:13:
De volgorde van de resources van de batch zijn van belang, je wilt namelijk de ruimte tussen de resources meten. Om dat voor elkaar te krijgen op de manier die .oisyn wil moeten de resources langskomen in de volgorde dat ze op de disk staan. Zie ook .oisyn in "[GPGPU] Efficient parallel algoritme voor DVD seek simulatie".

Dan zijn er dus 2 mogelijkheden: je loopt door de disk heen (want de disk is gesorteerd), of je loopt door de batches heen, en sorteert die.

---

Uiteraard. Mijn vraag was waarom het nodig is om dat in elke fitness evaluatie te doen? Ik dacht in zijn uitleg te lezen dat de batches en de resources daarin vastliggen het begin en niet veranderen daarna, enkel de globale resource order verandert.
Dan doe je de sortering eenmaal in de initialisatie en dan zou je enkel dit moeten parallelliseren voor de fitness evaluatie:

code:

foreach (b in batches)
{
    foreach (adjacent pair p in b.resources)
        totalcost += cost(p.fromoffset, p.tooffset);
}

Dat is ook O(b * r ) en dat lijkt me wat vlotter parallelliseerbaar dan de tweede versie.

[Verwijderd]

Hij gebruikt een evolutionair algoritme. Hij pakt en bepaalde state, maakt daar 100 variaties op, en kiest daarna de beste state om nog 100 variaties op te maken. Enzovoorts.

Met een variatie wordt er bedoeld dat de resources volgorde een beetje wordt gehusseld. Het kost relatief veel tijd om de resources opnieuw te sorteren.

.oisyn: welk sorteeralgoritme gebruikte je bij algoritme #1? Ik heb zojuist een speedup van 2x gerealiseerd door het gebruik van bubblesort in plaats van STL sort. Afhankelijk van het type mutatie dat je uitvoert is het misschien mogelijk met een vergelijkbare optimalisatie te komen.

[ Voor 68% gewijzigd door Verwijderd op 19-11-2012 20:25 ]

[HMS]

Heeft iemand hier al een stochastic optimalisation algorithm op los gelaten, a la TSP? Of is er een hele goede reden om dat niet te doen ?

[Soultaker]

@HMS: werk dat idee eerst maar eens uit. (Is een genetic algorithm niet al een soort van stochastische optimalisatie?)

@Darkstone: wil jij je code delen? Ik ben te lui om zelf dingen te verzinnen maar misschien dat ik aan je bestaande code nog wat verbeteren (en sowieso vind ik het wel leuk om te zien hoe je 't nu precies aangepakt hebt).

[Verwijderd]

Kern van het algoritme is:

code:

void mostEfficientPlacement(list<Resource* >& resources, Resource* r)
{

}

Deze functie probeert r op de meest positie, en berekent ook wat die positie is. Hoe werkt dat? Ik Insert r aan het begin van de lijst resources. Daarna:

code:

for(list<Resource*>::iterator resourceIterator = resources.begin();
        resourceIterator != resources.end();
        resourceIterator++)
{
    if (index != 0) {
        // swap element resourceIterator en resourceIterator-1 en bereken fitness
    }

    if (index == 0)
    {
        bestIterator = resourceIterator;
        bestFitness = fitness;
    } 
    else if (fitness <= bestFitness)
    {
        bestIterator = resourceIterator;
        bestFitness = fitness;
        }
    index++
}

Kortom. Ik loop over alle elementen en verwissel elementen zodanig dat 'r' zich door de lijst beweegt.

De truuk is natuurlijk hoe je de resources swapt en fitness correct berekent. We defineren de volgende kosten:
A: de fitness van de resource (*resourceIterator) vóór het swappen van de resources.
B: de fitness van de resource (*resourceIterator - 1) vóór het swappen van de resources.
C: de fitness van de resource (*resourceIterator) na het swappen van de resources.
D: de fitness van de resource (*resourceIterator - 1) na het swappen van de resources.

fitness = fitness - A - B + C + D;

B is altijd hetzelfde als C de iteratie ervoor. Daarom hoeven we slechts 3 keer per swap de fitness van de resources te berekenen. De fitness van een resource wordt gedefineerd door de som van de fitness van alle batches

code:

for(b in r.batches)
{
    sort(b.resources)
    lastseen = 0;
    for (r in b.resources)
    {
        if (lastseen)
            totalcost += cost(lastseen, r.offset)
        lastseen = r.offset + r.size;
    }
}
return totalCost

Volgens valgrind neemt deze code 99.1% van de tijd in beslag, en het lezen van testdata.txt 0.86%. Ik zie nog 2 verbeterpunten aan dit algoritme: resourceFitness herschrijven in assembly, en de resource plaatsen op een random positie in plaats van simpelweg de eerste.

Verder heb ik een continuousIteration methode. Die kiest random een element uit, verwijdert die uit de lijst, en plaatst die weer opnieuw in de lijst met de mostEfficientPlacement() methode. Daar valt ook nog het een en ander aan te verbeteren (te veel om op te noemen). Maar ik ben eerst data aan het verzamelen hoe het huidige verbeterprocess performt. Het volledig opbouwen van de ~5300 resources kost 11 minuten op dit moment.

Geef me een paar minuten, dan gooi ik het project op git.
https://bitbucket.org/sdessens/xbox-dvd-optimizer/overview

[Soultaker]

Nice. Een hele makkelijke verbetering is om de resources voor de eerste fase te sorteren op grootte (van groot naar klein); dan zit je fitness al direct rond de 852375 in plaats van 935190. Of het veel effect heeft op de kwaliteit van de eindoplossing weet ik niet.

Ik zag dat je eerst tien keer je insertion-algoritme uitvoerde, maar dat later had uitgecomment. Waarom? Dat leverde mij nog wel een paar procent verbetering op (maar ik weet niet zeker of 't ook een betere investering van de tijd is dan simpelweg overgaan naar de tweede fase).

[Verwijderd]

Soultaker schreef op maandag 19 november 2012 @ 23:54:
Ik zag dat je eerst tien keer je insertion-algoritme uitvoerde, maar dat later had uitgecomment. Waarom? Dat leverde mij nog wel een paar procent verbetering op (maar ik weet niet zeker of 't ook een betere investering van de tijd is dan simpelweg overgaan naar de tweede fase).

Dat was een benchmark dingetje. Om mijn verbeteringen te testen draai ik niet de volledige data, maar 10x over een beperkt subset van 1000 resources.

[Soultaker]

Oh ja, slecht gelezen door mij.

[.oisyn]

Weer een berichtje van mij . Ik had gehoopt er vandaag wat mee bezig te zijn op kantoor maar er kwamen andere dringendere zaken tussendoor , maar heb ondertussen wel de tijd gehad om dingen eens in mijn hoofd uiteen te zetten.

Anyway, ik had wat getallen beloofd. Vergeet niet dat mijn GA pas daadwerkelijk begon nádat er een deterministisch algo overheen was gegaan, zoals ik in een van de eerste posts in deze draad al zei - deze opmerking lijkt een beetje ondergesneeuwd te zijn. Dit algoritme lag niet zo heel erg ver van jullie oplossing vandaan (een greedy algo dat in plaats van groepen de batches bij elkaar voegt, en ondertussen wat slims probeert te doen met de resources binnen die batches om de seektijden te minimaliseren). Dit algo was echter takketraag en ik zag niet echt een manier om het sneller te maken, plus het feit dat het snel op een lokaal minimum bleef hangen. Vandaar dat ik op dat moment ben overgestapt op een GA die door z'n randomheid weliswaar een stuk minder deterministisch was maar wel veel sneller oplossingen probeerde.

De initiele start van de GA met deze data lag rond de 850.000, na een dagje rekenen zat het rond de 750.000. Die hebben jullie tot op heden dus nog niet gebeat , maar daar staat tegenover dat ik ook nog geen computing times van 24+ uur zie .

Máár, geïnspireerd door jullie discussie ben ik weer eens gaan nadenken om verbeteringen aan te brengen aan het deterministische startup deel. Jullie hadden aangetoond dat gewoon groepen bij elkaar stoppen ook best een goed uitgangspositie vormt, maar waarvan de code wel een stuk simpeler is. En omdat de code veel simpeler werd, leek het me ook een stuk makkelijker om de kosten incrementeel te updaten terwijl je aan het proberen bent.

Ik heb dus vanavond het een en ander uit zitten werken, en ben op een oplossing gekomen die binnen een minuut de volledige set bij elkaar graait (en heb daarbij vergelijkbare conclusies gevonden als Soultaker, zoals sorteren op grootte, maar bijvoorbeeld ook de batches sorteren op aantal groepen en daar dan overheen lopen en alle groepen pakken die je nog niet hebt gehad), en daarna incrementeel gewoon steeds een willekeurig element verwijderen en die op de meest efficiente plek weer terugzetten. Na een 10 minuten looptijd duikt hij onder de 800.000, maar progress is daarna wel heel langzaam. Na totaal 20 minuten staat de teller momenteel op 792.940. Dit alles is overigens nog op een enkele core (van een C2Q @ 3GHz)

Maar goed, dit is slechts een eerste implementatie. Door steeds maar 1 resource te verplaatsen blijf je natuurlijk al snel in een lokaal minimum hangen, je zult er meerdere tegelijk moeten doen om daar overheen te komen. Ik wil jullie in ieder geval even bedanken voor de hint in deze richting, die ik in eerste instantie had afgeschreven door een brakke implementatie van mijn kant.

Mijn incrementele methode werkt door voor iedere batch een lijst bij te houden welke resources hij allemaal aandoet, en wat de kosten zijn tussen die resources. Vervolgens loop ik voor een te inserten resource van voor naar achter over de al gevormde permutatie, waarbij ik voor elke batch bijhoud waar ik momenteel zit in de batch. Voor batches waar de huidige resource niet inzit hoef je alleen te updaten als je resource uit die batch passeert (omdat de afstand tussen de vorige en de huidige dan kleiner wordt, en die tussen de huidige en de volgende groter). Voor batches waar je resource wel inzit moet je updaten voor elke iteratie, door de link A-B op te splitsen in A-X-B, met A en B de al bestaande resources en X de te inserten resource. Dan heb je niet eens een sort nodig.

En ik hoop dat jullie ook slim genoeg waren om batches met 1 resource te negeren, en batches die meerdere keren voorkomen samen te voegen. Uiteindelijk kom ik op 808 verschillende relevante batches, ipv de 1226 (dacht ik) van het origineel

.edit: 789710 inmiddels na 30 minuten.

[ Voor 4% gewijzigd door .oisyn op 20-11-2012 00:34 ]

[.oisyn]

Verwijderd schreef op maandag 19 november 2012 @ 01:56:
Verder zijn er nog flink wat versnellingspunten mogelijk: STL sort heeft O(n * (log n)²) complexiteit. Wat natuurlijk extreem brak is om iets te sorteren wat 99% van de tijd al gesorteerd is.

Welke STL is dat? Ik kan me wel herinneren dat Dinkumware's implemetatie (die in VC++) efficienter is dan die van GCC.

Overigens zie ik het voordeel van een evolutionair algoritme wel in: je parraliseert het in een handomdraai. Een DA is een stuk lastiger te splitsen over de gewenste thread of 8. Laat staat een GPU...

Snelheid van mogelijkheden uitproberen was inderdaad het grootste argument voor een GA.

(8 volledige passes van element verwijderen en weer op de ideale plek insecten).

Wat bedoel je precies? Ga je 8 keer de permutatie helemaal opnieuw opbouwen? Op basis van een random volgorde oid? Nadat ik de set compleet heb haal ik gewoon steeds 1 willekeurig element weg en die voeg ik dan opnieuw toe.

Is dat wat je bedoelde met 'iteraties verwisselen is een tamelijk zinloze mutatie'?

Nee ik bedoelde een swap(r1, r2) als mutatie op zich is over het algemeen vrij nutteloos, daar wordt de oplossing zo goed als nooit beter van. Dit staat uiteraard los van het feit dat je een combinatie van meerdere swaps natuurlijk wel kunt gebruiken om elementen te verplaatsen.

[Verwijderd]

.oisyn schreef op dinsdag 20 november 2012 @ 00:49:
[...]

Welke STL is dat? Ik kan me wel herinneren dat Dinkumware's implemetatie (die in VC++) efficienter is dan die van GCC.

Wikipedia beweert dat, ik heb het niet zelf getest.

Wat bedoel je precies? Ga je 8 keer de permutatie helemaal opnieuw opbouwen? Op basis van een random volgorde oid? Nadat ik de set compleet heb haal ik gewoon 1 willekeurig element weg en die voeg ik dan opnieuw toe.

8 x 5300 = ~45000 maal een element verwijderen en opnieuw plaatsen.
Maar ik versprak mezelf lelijk, want er staat eigenlijk wat anders dan ik bedoel.


Ik had overigens nooit gedacht dat het ook zonder sort kon, en dat die oplossing te veel overhead zou hebben. Maar dat valt dus best mee.

[Soultaker]

.oisyn schreef op dinsdag 20 november 2012 @ 00:27:
En ik hoop dat jullie ook slim genoeg waren om batches met 1 resource te negeren

Ik had de bipartiete graaf die je krijgt door batches met resources te verbinden zelfs opgesplitst in connected components, maar dat leverde niet veel op aangezien je een grote component met 5000+ resources overhoudt.

en batches die meerdere keren voorkomen samen te voegen.

Hoe bedoel je dit precies? Dat lijkt me geen permissible optimalisatie tenzij je een weging toevoegt aan de batches om te compenseren.

[.oisyn]

Soultaker schreef op dinsdag 20 november 2012 @ 01:21:
[...]

Ik had de bipartiete graaf die je krijgt door batches met resources te verbinden zelfs opgesplitst in connected components, maar dat leverde niet veel op aangezien je een grote component met 5000+ resources overhoudt.

Klopt, daarvoor zijn ze allemaal teveel met elkaar verbonden

Hoe bedoel je dit precies? Dat lijkt me geen permissible optimalisatie tenzij je een weging toevoegt aan de batches om te compenseren.

Uiteraard, maar het scheelt evaluaties. Zo is het maximaal aantal batches per resource zonder de optimalisatie gelijk aan 107, maar na optimalisatie slechts 69. En zeker met mijn implementatie, waarbij hij per iteratie over alle N batches heenwandelt scheelt het zo'n 30%.

[.oisyn]

Wow. Ik heb 'm een hele nacht laten lopen, waarbij hij elke keer 5 random elementen uit de oplossing haalde en die opnieuw ging inserten, en de score stond op 777.807 met een gigantisch trage progress. Dit heb ik zojuist iets aangepast door niet 5 random elementen te doen maar een rijtje van 5 elementen achter elkaar, en die in omgekeerde volgorde weer inserten. De score zakte binnen 5 minuten in naar 769.563 en daalt nog steeds in een relatief rap tempo. Ik denk dat ik een vervanger voor m'n GA heb gevonden

.edit: 766.400 na 10 minuten.

[ Voor 3% gewijzigd door .oisyn op 20-11-2012 10:32 ]