[GPGPU] Efficient parallel algoritme voor DVD seek simulatie

[.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 ]

[armageddon_2k1]

Dus je hebt wat aan het topic gehad?
Hosanna!

[.oisyn]

Zowaar

[HMS]

Ik zat te denken om hier een simulated annealing stochastic optimization algoritme voor te gebruiken, maar vannacht kwam ik er niet echt uit wat nou precies de bedoeling was.

Was het een goede permutatie van resources vinden waarvoor de cost minimaal is, of is de volgorde van batches van belang? Daarnaast heb je het in de post met testdata over groups, ik nam aan dat een group een batch was .

Ach ja, je hebt het opgelost lijkt me. Maar ik had gewoon zin om even te puzzelen, maar als je niet snapt wat de bedoeling is wordt het lastig

[.oisyn]

Een group is wat men hier resources noemt. Ik noem het groups omdat het in werkelijkheid groepen van resources zijn die altijd met elkaar worden in- en uitgeladen, dus het heeft niet zoveel zin om die individueel te behandelen.

En het doel is een volgorde van groups/resources te bepalen waarvoor de kosten minimaal zijn. De volgorde van batches is niet van belang.

[ Voor 23% gewijzigd door .oisyn op 20-11-2012 13:33 ]

[Verwijderd]

Soultaker schreef op maandag 19 november 2012 @ 23:54:
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.

Wanneer is ik de resources sorteer met de volgende functie:

code:

    return (a->batches.size() * X + a->size)
            >
           (b->batches.size() * X + b->size);

Waar X = 9472 kom direct op een score van 821886. Dat is uiteengezet in de volgende grafiek. Horizontaal = X, vertcaal = de fitness.

(grafiek wijkt een paar duizend punten af vanwege een programmeerfout)

Tevens heb ik mijn iteratiealgoritme de avond laten draaien. Daar is uitgekomen:

De verticale as weergeeft de fitness. Verticaal de tijd (lineair, de schaal is niet interessant). In totaal zijn er 148280 remove/insert operaties geweest. Weinig verrassende resultaten.

.oisyn schreef op dinsdag 20 november 2012 @ 10:29:
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,

Waarom 5, en geen hele batch?

[.oisyn]

Natte vingerwerk. Hoe groter het aantal resources dat je weghaalt, hoe langer het duurt voor je weer bij een totaaloplossing bent. Ik kan deze instelling nu on the fly aanpassen terwijl het algoritme runt, hele grote aantallen lijken geen positief effect te hebben in termen van daling/tijd. Aantallen onder de 20 lijken vooralsnog een beter resultaat te geven. Het valt me wel op dat als hij in een lokaal minimum lijkt te hangen met een bepaald aantal, dat het aanpassen van dat aantal 'm er meestal wel uittrekt (of het aantal nou groter of kleiner wordt gemaakt). Ik denk dat ik het dus ga randomisen.

Teller staat hier overigens momenteel op 736.999.

De volgende stap is meerdere oplossingen bijhouden en daarmee doorrekenen. Is makkelijk te parallelliseren en verbreedt de search.

[Verwijderd]

Maak een learning algoritme voor de hoeveelheid te herplaatsen resources

[Soultaker]

Learning algorithms zijn stom; je kan toch zelf wel een zinnige heuristiek verzinnen?

... en zo herhaalt het topic zich weer.

[.oisyn]

Ach, zolang het maar op de GPU kan

736.303
Dat is de laatste 9.999 iteraties (verder gaat m'n console window niet terug ) niet veranderd.

[ Voor 65% gewijzigd door .oisyn op 21-11-2012 00:51 ]

[.oisyn]

Als ik steeds de 10 oplossingen bijhoudt, daarmee wat probeer te verwisselen (geeft 10 oude + 10 nieuwe) en die sorteer en dan de 10 beste selecteer (identieke oplossingen niet meegenomen), dan kom ik wel weg van dat lokale minimum van 736.303. Plus het is lekker makkelijk parallelliseerbaar zo . Daarnaast hoef ik minder elementen per keer eruit te halen omdat je minder snel een foute keuze kunt maken waarvan je nooit meer wegkomt (omdat er altijd wel een andere oplossing is waarbij die keuze niet gemaakt is), tenzij het dode spoor meer dan 10 niveaus diep is.

[Bolukan]

Is er een top 5 met de beste fitness en de gehanteerde methodiek te plaatsen?

736.303 .oisyn: GA
821.886 Darkstone: batch-size gesorteerd
852.375 Soultaker: sorteren
3.724.445 testbestand: zonder optimalisatie

[ Voor 11% gewijzigd door Bolukan op 21-11-2012 07:24 ]

[Verwijderd]

.oisyn gebruikt een aanpassing op mijn algoritme voor het testen van de fitness. Mijn gedeeltelijke fitness was 12x sneller dan die van .oisyn (topicstart, algo #2), en de aanpassing van .oisyn (geen sort meer nodig) maakt hem nog 10x zo snel. Die ben ik nu ook aan het implementeren.

Soultaker en ik gebruiken dezelfde 'verbetermethode' (random element verwijderen en weer inserren), en .oisyn verwijdert er gewoon X tegelijk, het GA wordt niet meer gebruikt.

[.oisyn]

Mijn gedeeltelijke fitness was 12x sneller dan die van .oisyn

Beetje flauw om het zo te stellen, het algo in de topicstart is een ad hoc fitnesscalculatie gegeven louter een permutatie van resources, en is ook niet ontworpen om snel te zijn bij meerdere tests van minieme aanpassingen. Het is niet zo dat jouw algo in het algemene geval ook 12x sneller is . Mijn "aanpassing" borduurt overigens niet voort op jouw implementatie (die ik op dat moment nog niet gezien had), en in weze kan ik de delta bepalen tussen het origineel en een willekeurige insertion plek, ipv alleen 2 aangrenzende insertionplekken

[ Voor 25% gewijzigd door .oisyn op 21-11-2012 09:03 ]

[Verwijderd]

Als je het zo bekijkt klopt dat wel, ja.

[.oisyn]

Na een nacht rekenen staat ie op 728.922. Zo nu en dan vindt ie wel wat beters, maar de rek is er duidelijk uit en het loont niet echt meer om 'm zo lang door te laten gaan voor zo'n minimale verbetering.

[Bolukan]

Moet je ook geen rekening houden met de frequentie dat batches worden opgevraagd?

[.oisyn]

.oisyn in "[GPGPU] Efficient parallel algoritme voor DVD seek simulatie"

Elke batch in de data wordt 1x opgevraagd. Sommige batches zijn identiek, als je daar rekening mee houdt dan hoef je minder te berekenen, maar het is niet zo dat een batch staat voor een lijst resources die op willekeurige momenten kan worden opgevraagd door de game. Een batch is gewoon een specifieke situatie. Als je die situatie meerdere keren creëert (bijv. door in de game de hele tijd heen en weer te gaan lopen), dan wordt een batch wel meerdere keren opgevraagd, maar hij blijft gelinkt aan 1 specifieke situatie.

[ Voor 72% gewijzigd door .oisyn op 21-11-2012 10:43 ]

[armageddon_2k1]

Jouw data is gegenereerd door een complete play-through, right? In feite optimaliseer je dus voor n = 1, maar dat hoef ik je ook niet te vertellen.

Ik ben benieuwd hoe je zeker gaat weten/afdekken dat je methode ook voor meerdere spelers en playthroughs efficient gaat zijn. Of is dat inherent aan de opbouw van de game?

[.oisyn]

Afwijkende playthroughs zouden geen groot probleem moeten vormen. De bulk van de batches blijft identiek.

[Waster]

Als ik het goed begrijp gebruik je nu toch een hillclimbing algoritme? Of heb je manieren om uit een lokaal minimum te komen?

Zou het mogelijk zijn om je oplossing te visualiseren zodat je een gevoel hebt van hoe goed je oplossing nu is? Dan kun je misschien inschatten hoeveel verbetering er nog mogelijk is.

[Soultaker]

Verwijderd schreef op woensdag 21 november 2012 @ 08:36:
Soultaker en ik gebruiken dezelfde 'verbetermethode' (random element verwijderen en weer inserten)

Mijn verbetermethode was oorspronkelijk net iets anders: ik swapte twee random elementen. Dat convergeerde minder snel.

Wel herhaalde ik de hele insertion routine een aantal keer, waardoor ik al lager begon (~820,000 ipv ~850,000 ofzoiets) en dan leek fase twee ook wat lager uit te komen (of dat was toeval). Dat is zo'n beetje enige truc die ik verzonnen had die ondertussen niet door anderen sneller en beter geïmplementeerd is, geloof ik.

Misschien dat het nuttig is om op subsequences een rotatie uit te voeren (bijvoorbeeld door random i < j < k te pakken, en dan v = v[0:i) + [j:k) + [i:j) + [k:N) te construeren) — dat is equivalent aan een subsequence extracten en dan elders weer inserten, zonder dat je je vastlegd op de lengte ervan. Maar het is nog wel lastig om dat efficiënt te implementeren, denk ik.

Waster schreef op woensdag 21 november 2012 @ 14:14:
Zou het mogelijk zijn om je oplossing te visualiseren zodat je een gevoel hebt van hoe goed je oplossing nu is? Dan kun je misschien inschatten hoeveel verbetering er nog mogelijk is.

Darkstone had wel wat grafiekjes gepost maar het lijkt er op dat verschillende heuristieken naar verschillende waarden convergeren. Ik denk niet dat je uit het feit dat de ene techniek een bepaalde plateau laat zien zomaar kunt concluderen dat er geen andere techniek is die een stuk lager uitkomt.

[ Voor 12% gewijzigd door Soultaker op 21-11-2012 17:02 ]

[Bolukan]

Heb je niet nog een paar spellen te optimaliseren? Ik zie een programming contest mogelijkheid.

[Verwijderd]

Waster schreef op woensdag 21 november 2012 @ 14:14:
Als ik het goed begrijp gebruik je nu toch een hillclimbing algoritme? Of heb je manieren om uit een lokaal minimum te komen?

.oisyn onthoud de 10 laatste waarden zodat hij uit het lokale minimum komt tenzij dat pad meer dan 10 diep is.

Zou het mogelijk zijn om je oplossing te visualiseren zodat je een gevoel hebt van hoe goed je oplossing nu is? Dan kun je misschien inschatten hoeveel verbetering er nog mogelijk is.

De fitness is gewoon 'een score' waar je weinig waarde aan moet hechten. Je kan er betekenis aan hangen als je het optimum kan inden, maar dat is N! = 10¹⁷⁴³⁹ mogelijkheden om te bruteforcen. Misschien is het mogelijk een simpele heuristiek te maken, maar hoe je dat gaat doen, geen idee.

[Waster]

Verwijderd schreef op woensdag 21 november 2012 @ 19:12:
[...]
.oisyn onthoud de 10 laatste waarden zodat hij uit het lokale minimum komt tenzij dat pad meer dan 10 diep is.

Ah, was dat het idee van de laatste 10 waarden onthouden
Het lijkt een beetje op tabu search. Als oisyn toch die kant opgaat zou hij een tabu search algoritme ook nog kunnen proberen. Heb je daar al naar gekeken?

[Verwijderd]

Hoe wil je tabu search gebruiken als de branching factor vanaf een willekeurige state praktisch oneindig is?

[Soultaker]

Ik interpreteerde 't meer als simulated annealing waarbij je verwisselingen die de score verhogen helemaal nooit toestaat.

[Verwijderd]

Dat doe ik sowieso niet. Wat .oisyn exact doet weet ik niet.

[.oisyn]

't is feitelijk gewoon stochastiche hill climbing waarbij je meerdere kandidaat-oplossingen bijhoudt. Oplossingen die slechter worden laat ik in principe gewoon toe, alleen is er een maximum aan aantal oplossingen en ik houd alleen de N beste bij. Oplossingen die zo slecht worden dat ze buiten die N vallen verdwijnen dus. De vorige oplossing bewaar ik overigens ook, en volgt hetzelfde criterium (als de Nste oplossing beter wordt dan is er dus geen plek meer voor de oude permutatie).

Verder gebruik ik een mechanisme om de boel af en toe wat door elkaar te schudden als er al een tijdje geen betere oplossing is gevonden, simpelweg door alle oplossingen behalve de beste weg te gooien. Hierdoor is er weer ruimte voor veel slechtere oplossingen. Zo blijft hij momenteel bijvoorbeeld al een tijdje hangen op 725844. De andere gevonden oplossingen liggen daar naar vervloop van tijd meestal vlak achter:
725844-725845-725846-725847-725848-725849-725850-725851
Een rijtje dat perfect oploopt dus. Gaat dat 100 iteraties zo door dan gooi ik alles behalve de 725844 weg, waardoor het na een paar iteraties uitgroeit naar een minder "perfect" rijtje van
725844-725919-725994-726148-726448-726668-726817-726818
Die oplossingen zijn essentieel anders en vormen vaak de basis van verdere progress.

Overigens krijg je alleen maar slechtere oplossingen als je meer dan 1 element verwijdert en weer toevoegt, want anders zal je altijd een minstens zo goede oplossing vinden (namelijk de plek waar ie stond)

[Soultaker]

.oisyn schreef op donderdag 22 november 2012 @ 00:55:
Overigens krijg je alleen maar slechtere oplossingen als je meer dan 1 element verwijdert en weer toevoegt, want anders zal je altijd een minstens zo goede oplossing vinden (namelijk de plek waar ie stond)

Dit volg ik niet

[.oisyn]

Nou ja het is maar hoe je het aanpakt natuurlijk, maar feitelijk hadden we denk ik allemaal wel een routine die, gegeven een bepaalde permutatie en een enkel in te voegen element, de efficientste plek van dat element ging bepalen. Als je die routine herhaaldelijk aanroept, waarbij je steeds een willekeurig element eruit verwijderd en weer terug stopt, dan vindt die routine óf een betere plek, óf de plek waar ie al stond. Hij zal nooit een slechtere plek vinden.

Als je definieert dat de oude plek niet gecontroleerd moet worden of niet valide is, dan kun je natuurlijk wel een slechter resultaat krijgen.