[GPGPU] Efficient parallel algoritme voor DVD seek simulatie

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