CPU-intensive oppgaver som kan deles opp

[smetho]

Hei.

 

Jeg sitter for tiden med en masteroppgave der jeg skal utvikle en desktop grid-applikasjon. Poenget med denne er å ta CPU-intensive oppgaver og fordele disse ut til andre maskiner i et peer-to-peer nettverk. Hoveddelen av oppgaven trenger jeg ikke å ta her, men med delen som jeg har nevnt så lurer jeg på om noen kan hjelpe meg med følgende:

 

Jeg trenger tips/råd om CPU-intensive oppgaver jeg kan dele opp (altså parallelliserbare oppgaver) som jeg kan kjøre på dette systemet. De mindre delene skal, når de er utført, kunne settes sammen til å utgjøre det endelige resultatet. Oppgavene må ikke være så små at de kan gjøres på en vanlig maskin på 1-2-3, men heller ikke så store som de vi finner i SETI@home, Folding@Home Climatepredicting.net osv. Nettverket skal være såkallt 'short-lived'. Jeg ser for meg oppgaver som blir ferdige på < 1 time (ca), dog det er ikke såå nøye hvor lang tid det tar.

 

Jobben som utføres trenger ikke være noe nyttig. Faktisk vil jeg foretrekke "enkle" oppgaver som er lette og programmere. Noe nummer-"krønsjing" vil fungere fint (bare holde CPUen i arbeid en periode) Jeg skal kun simulere "virkelig" arbeid, jeg skal ikke løse en gitt oppgave. Det er nemlig ikke denne delen her som er fokuset på oppgaven (og nei, det er heller ikke juks å få hjelp til den ).

 

Noen som har noen tips, eventuelt noen kjekke linker de vil dele med meg?

 

På forhånd takk for hjelpen!

[Zethyr]

Kan jo eventuelt bare finne noen hinsides presise tall for sinus-funksjoner, pi, eller liknende .. ?

 

Finn et en fem-seks irrasjonelle tall som du lager et regnestykke med og finner en lur måte å forkorte svaret på. F.eks. summen av hvert 40 siffer i svaret

 

Eller måtte det være noe nyttig bruksområde?

 

Eventuelt en weathercalc-light. Da kan du sikkert få låne noe rådata et steds fra også.

[Legion]

en 'dårlig' primtallsgenerator hvor subset av mengden deles ut til nodene og resultatet flettes tilbake til den opprinnelige mengden.

Endret 21. november 2005 av Legion

[smetho]

Trenger som sagt ikke være noe nyttig bruksområdet

 

Ja, tenker kanskje noen slike regnestykker, men jeg vet ikke hva. Ikke er matte min sterke side heller, men kan jo gjøre "enkle" beregninger, men mange av dem f.eks. Det er noe slikt fiffig jeg ser etter Ser kanskje for meg å sende et eller flere tall ut til hver maskin som jobber med disse. Resultatene som kommer tilbake kan så settes sammen til å bli det endelige resultatet. Skjønner? Jeg er bare ELENDIG til å komme på slike ting

 

Selvsagt ville en virkelig versjon av applikasjonen gjøre noe litt mer fornuftig

[dayslepr]

behøver du å vite hva oppgaven (og sub-oppgavene) skal være på forhånd da?

 

lager du noe som er generisk så kan du sette inn koden (subklasse f.eks.) som løser den spesifike oppgaven, og den kode-biten som løser sub-oppgavene siden .. dette er jo i seg selv en hel masse jobb - så kommer du kanskje på noen oppgaver du kan løse v.h.a. den siden

 

du kan jo lage en ting som finner den lengste veien igjennom et nettverk (jeg nevnte dette i en tidligere tråd her) .. når det er flere mulige veier å gå, så deles oppgaven i tilsvarende flere deler til andre maskiner og de går hver sin vei og rapporterer tilbake til "hovednoden" hvilke av dem som når lengst ... eller om de støter på flere kryss ... ellernoesånntnoe ... kan så klart være at dette er toskete og vil kreve mer resurser; men det går i hvertfall an å paralellisere

 

tenk på ting som fungerer, eller kan fungere paralellt i virkeligheten .. korteste vei igjennom en laberint blir nesten den samme som over ..

 

er det et krav at den må crunche tall? .. den kan jo simulere et enkelt spill-brett med et par spillere (paralellt) på, med noen enkle regler .. i simuleringer av ting i virkeligheten er det i grunn masse som foregår paralellt - men her kan det også være mer å passe på; synkronisering blir viktigere .. rekkefølge er ikke lenger irrelevant .. jeg vet ikke

[mar]

Korteste sti i en dynamisk vektet graf er et problem som er lett å implementere, veldig enkelt å paralellisere og ganske tidkrevende (for store grafer).

 

En annen mulighet er jo å kryptere en tekst for så knekke krypteringen. Bare ikke bruk så alt for god kryptering, blir jo aldri ferdig da.

 

Edit: Er det problemer med komunikasjon mellom nodene du er ute etter? I så fall kan du feks gjøre enkle simuleringer av energiforplantning i en flate eller et 3 dimensjonalt objekt.

Endret 21. november 2005 av mar

[Zethyr]

Se hvor fort du kan bruteforce en passe lang md5-hashet streng. Jeg vet ikke helt hva du har til rådighet av datakraft, men med 2*29+10 (store og små bokstaver + tall) tegn til rådighet vil vel en 10-12 tegn +- være bra? md5-algoritmen er ganske enkel, og finnes ute på nett på mange steder. For å ikke bare kopiere gamle saker, kan du jo bruke f.eks. en dobbelt-hashet streng, altså md5-hashen av md5-hashen av en streng.

Her kommer en del an på hvor godt du kan disponere og fordele oppgaver mellom nodene mest effektivt, og noe kommer an på hvor effektivt du skriver selve brute-force-kodesnutten.

Endret 22. november 2005 av Zethyr

[MailMan13]

Hva med et av de klassiske optimeringsproblemene da? Travelling salesman, multiconstraint knapsack, set covering osv... skulle være kurrant å dele opp løsningsrommet og la hver klient få sitt subproblem i hvlike som helst av de. Det ligger optimering i lufta her (NP problemer). Disse problemene krever ikke mye mattekunnskaper for å forstå dem, men de er likevel umulig å løse deterministisk så mye datakraft er alltid en god idè.

 

Å gjøre noe som skalerer over tid er alltid bedre enn brute-force som uansett datakraft bare er mulig for små instanser, det er ihvertfall min mening.

 

Hvis du lager noe som beregner noe fancy på store grafer (traversal set, vertex cover, største clique eller noe sånt kult noe) så kan jo jeg bruke det i master-oppgaven min, men da må du være ferdig snart

Endret 26. november 2005 av MailMan13