Onderzoekers vergelijken GPU en CPU met sorteeralgoritme

Onderzoekers van de University of North Carolina in de Verenigde Staten hebben de snelheid waarmee GPU's en CPU's kunnen sorteren vergeleken. Hiervoor hebben de onderzoekers zelf een sorteeralgoritme voor de GPU geschreven, GPUSort genaamd. Dit algoritme kan 32bits drijvende komma getallen sorteren. Uit de resultaten blijkt dat een PCI Express nVidia GeForce Ultra 6800 Ultra met gemak een 3,2GHz Pentium 4 met 2GB aan geheugen verslaat. Nog indrukwekkender is de snelheid van een PCI Express ATi Radeon X800XT, deze sorteert namelijk twee keer zo snel als de GeForce 6800 Ultra.

Verder hebben de onderzoekers het nieuwe sorteeralgoritme vergeleken met andere algoritmen, Purcel en Kipfer, voor GPU's. Hieruit blijkt dat GPUSort het snelste sorteeralgoritme voor GPU's is, dat op dit moment bestaat. Purcel en Kipfer gebruikten echter de normale pipeline van de GPU om te sorteren. GPUSort maakt echter alleen gebruik van simpele texture mapping instructies. Daarnaast is de toegang tot het videogeheugen in GPUSort geoptimaliseerd. Het lijkt er dus op dat de toepassing van een GPU voor andere zaken dan het renderen van beelden weer een stap dichterbij is gekomen.

Reacties (93)

[Fuzzems]

En wat mag het nu van dit hele sorteer gebeuren zijn ?
kan hier daadwerkelijk iets mee gedaan worden waar gebruikers van computersystemen wat aan hebben ?

[Verwijderd]

Ja natuurlijk slimpie. Nee, dit is puur een experiment hoe je zo efficient mogelijk je tijd kan verdoen d.m.v. nieuwe technologieen.

Nut wordt toch al beschreven in de text:
Het is een onderzoek waarbij GPU's gebruikt worden ipv CPU's. Wat blijkt: een GPU is prima in staat bepaalde berekeningen over te nemen van een CPU en nog veeel sneller ook.

Praktich voorbeeld: Back to front rendering van een octtree. Dat zorgt ervoor dat je bijvoorbeeld alpha blending kan gebruiken in je matrialen en dat alles correct op het scherm verschijnt. Simpel gezegd: Je hebt coole rook achter je missle aan of mooie wolk zand om je rally car heen.

Hoe sneller, hoe meer particles mogelijk in de rook.

[Madrox]

Eigenlijk kan je dat niet met zekerheid zeggen.
Wat met tegenstaat aan dit onderzoek is nogal essentieel; De onderzoekers hebben een programma voor de GPU! gemaakt: GPU-SORT.

Lijkt me zeer aannemelijk dat het programma dus vooral rekening houdt met de GPU-architectuur en niet met de CPU-architectuur. Als je het mij vraagt nogal een gekleurd onderzoek. Vraag me af: hoe zou de GPU het afbrengen met een CPU-SORT programma ?

[demonite]

Wat inderdaad de vraag is, is of de vergelijking tussen een qsort en de GPUSort gaat of tussen de CPU en de GPU.

De GPUsort lijkt de meest optimale sorteermethode voor de GPU in dit geval... Maar was de qsort dat ook voor de CPU ?

[demonite]

@theStickie

Inderdaad zou het niet nuttig zijn om de qsort op een GPU te draaien.. Misschien is dat zelfs helemaal niet mogelijk.

Maar, de GPUSORT is de meest optimale sorteermethode voor de GPU voor dit probleem..
Was de qsort voor de cpu ook de meest optimale ? En ipv seconden hadden ze beter clockcycles kunnen meten.. Wat deed de cpu nog meer op dat moment ?

Zo zijn er nog wel een paar dingen die je je af kunt vragen... Maar opzich is de uitslag niet verwonderlijk. Het is al langer bekend dat de GPU sneller is qua floating point berekeningen dan de CPU

[the_stickie]

Je zou het ook anders kunnen zien: wellicht is juist beiden andere code geven niet eerlijk: beiden hebben immers en totaal andere architectuur

ze hebben dus een programma geschreven voor een bepaalde processor en dat vergeleken met "standaard" programma's voor x86 cpus, die redelijk algemeen als de snelste algoritmes beschouwd worden... Ik dnek niet dat ze de gpu hier echt mee bevoordeeld hebben

[Verwijderd]

Volgens mij snap je de essentie niet. Ze hebben niet dezelfde alogaritmes gebruikt, dit kan immers niet. Een GPU wert anders dan een CPU. Op de CPU hebben ze quicksort gebruikt en op de GPU een zelf bedacht proggie.

[Verwijderd]

De gebruikte algoritmes kunnen wel degelijk identiek zijn (dat verwacht ik eigenlijk ook), de gebruikte (machine)code uiteraard niet...

[martijnvanegdom]

Je moest eens weten wat er allemaal gesorteerd word in Software. Paar kleine voorbeeldjes gericht op de gebruiker..

Stel jij heb een lijst van mp3 in je media programma staan. Dat is het heel fijn om te kunnen daarin. Als je een lijst gesorteerd opslaat kun je er een stuk sneller in zoeken die lijst dan als die lijst ongesorteerd opgeslagen staat..

stel je hebt een lied met een A. Als je de lijst ongesorteerd opgeslagen heb moet je alles langs tot dat je het heb gevonden. Als je gesorteerd opslaat dan zijn er een heel stel goede en minder goede zoekmethoden.

Sorteren gebeurd op heel veel plekken. Vaak leverd het een sneller werkend geheel op. In de informatica zijn er zelf vakgebieden te vinden die zich alleen met sorteren en zoeken bezig houden, zijn vaak erg theoritisch maar soms ook erg praktisch en vaak ook best gaaf

[Luxx]

Is dit eigenlijk niet ietwat vergelijkbaar met het hele CELL gebeuren van IBM/SONY? De "cells" van deze processor zouden ook in dat soort dingen uitzonderlijk snel kunnen zijn, maar wel oh zo moeilijk efficient te gebruiken.
Ik kan me zo voorstellen dat er technisch gezien ook meerdere overeenkomsten zijn.

[Verwijderd]

Correct. De Cell heeft meer weg van een GPU dan een CPU. Het zijn beide DSP's.

Kort samengevat stuur je een stream data er doorheen en vervolgens wordt daar een heel 'dom' stukje code op uitgevoerd. Een super voordeel van deze aanpak is dat de processor vele malen simpler is om te bouwen (goedkoop dus) en dat het process makkelijk te paralleliseren is. Net als op een GPU ben je met 4 SPE cores 2x sneller dan met 2 SPE cores. Ze doen namelijk allemaal hetzelfde tegelijk.

Wat ik me affvraag is hoeveel nut zo'n SPE heeft aangezien het ongeveer dezelfde limitaties heeft als een GPU. Een GPU heeft echter veel meer troeven: snellere memory acccess en een aantal functie die handig zijn voor graphics.

Ik voorspel dat over een paar jaren GPU's helemaal gestandaardiseert zijn net als normale processors. Je kunt ze dan inzetten voor bijvoorbeeld sound of elk ander streamable process. De eerste GPU's waren enorm bepert maar je ziet steeds meer dat GPU's een algemene vorm aannemen. Op een gegeven moment is het niet meer nodig om het aantal instructies zo vaak uit te breiden of nieuwe functies toe te voegen.

[cavey]

nou, als je die gpu's ook nog kan gebruiken voor het quicksorten / z-sorten (ok, gpu sorten) van je objecten..... kan je dat stukje van je 3d engine offloaden naar je gpu en zo nog meer ellende op je scherm toveren

(alleen, KAN je wel meer dingen tegelijkertijd doen met je GPU? dus je CPU helpen met algoritmes EN nog eens 3d shit renderen?) hmmmmmm

[Luuk1983]

Maar de ATI is dus 24-bits, das toch niet eerlijk vergelijken??

[The Condor]

Maar toch is die 2x zo snel als de Geforce 6800, dus zo oneerlijk is het niet , de gpu kan ondanks het 24 bit is dus toch sneller zijn dan z`n 32bits tegenstander.

Het is maar net hoe geoptimaliseerd de core is, want de 7800gfx is ook geloof 2x zo snel als deze geforce
Ondanks dat er niet veel nieuwe features bij zijn gekomen, ze hebben hoofdzakelijk de core geoptimaliseerd.

[catfish]

24bits en 32bits maakt in floating point een gigantisch verschil hoor, het is dus niet meer dan logisch dat de Ati sneller is

[Verwijderd]

Als je een btje assembly ervaring hebt weet je dat het niet uitmaakt of je nou 32 bit of 24 bit gebruikt, de instructies die op die 32 bit of 24 bit getallen werken kunnen niet in minder dan 1 klokcyclus voltooien. Met beide heb je hetzelfde aantal
klokcycli, dus ook dezelfde snelheid, omdat beide getallen op een 256-bit gpu register worden gezet.

[Chatslet]

Ik denk dat de GPU juist 24 bit is en dat het sorteren daarom in stappen gebeurt.

[Verwijderd]

@sse2

Maar je geheugen bandwidth is wel vershillend. Die Ati heeft 25% minder bandwidth nodig. Met betrekking tot de 50% prestatie winst is dit nogal wat.

[Verwijderd]

Als beide kaarten evenveel data ontvangen, dan maakt dat niet meer uit. Het maakt niet uit of je nou 4x3 bytes(24 bits) of 3x4 bytes (32 bits) ontvangt. Je krijgt dezelfde hoeveelheid data binnen. Maar of nou de onderzoekers dezelfde hoeveelheid data voor beide kaarten hebben gebruikt???

[tweakerbee]

32 bits = 4 bytes, vandaar 3 keer 32-bits instructies
24 bits = 3 bytes, waarvoor je dus 4x data moet sturen

Dan heb je in beide gevallen gewoon 12 bytes aan data verwerkt.

[Vastloper]

Onzin die assembly waarin jij denkt is x86 assembly dat is niet te vergelijken met de werking van een gpu. Alle x86 processors zijn 32 bit en daarom maakt het niet uit in x86 assembly nee, maar de gpu van ati is vanaf de basis maar 24 bit. Als je in hardware (dus niet x86 assembly) een 24 bit floating point unit bouwt op dezelfde techniek dan is deze altijd sneller dan een 32 bit floating point unit. Denk bijvoorbeeld maar aand de carry latencies die over het hele bereik moeten propegeren. Oh ja rekenen is ook een vak:

4x3 bytes(24 bits) of 3x4 bytes (32 bits)

Sinds wanneer is 3x4=32?? Dan is het toch echt 4x4 bytes. Als zogenaamde assembly programmeur zou je toch op zijn minst moeten weten hoeveel bytes 32 bit is.

[Luuk1983]

ja of de GPU rekend slechts met 24 bit getallen?

[Verwijderd]

Eigenlijk hadden ze ook een 16bit variant op de 6800 moeten draaien.

[oeLangOetan]

What's the point? de GF6800 werkt intern toch altijd 32 bits. 16bit is alleen handig als opslagformaat.

[Zegato]

Uit de resultaten blijkt dat een PCI Express nVidia GeForce Ultra 6800 Ultra met gemak een 3,2GHz Pentium 4 met 2GB aan geheugen verslaat.

Het is wel een hele leuke vergelijking, GPU's met CPU's vergelijken, maar deze zijn beiden voor een totaal ander doeleinde gebouwd. Deze "test" vind ik dan ook een beetje àla appels met peren vergelijken.

Misschien is het dan wel tof om te laten zien dat een GPU ook andere dingen kan doen dan beelden renderen, maar om dat weer te geven met een vergelijking als deze vind ik een beetje vreemd

[Maurits van Baerle]

Misschien is het juist wel minder appels met peren vergelijken dan we altijd hebben gedacht, zeker tegenwoordig.

Niet voor niets zijn zowel Apple als Microsoft bezig om de GPU (die een groot deel van de tijd toch niets staat te doen) veel meer te betrekken bij gewone OS taken. Apple nu al in Tiger (hoewel het standaard nog niet aan staat, komt met een update binnenkort) en Microsoft in de eerstvolgende Windows-versie (Longhorn).

Zo vreemd is zo'n vergelijking dus eigenlijk niet meer.

[Kevinp]

Maar misschien shut dit ait(of nvidia) wel wakker, en krijgen we er een speler bij op de cpu markt. Kan je een all nvidia systeem kopen(of all ati).

[Zr40]

Kan je een all nvidia systeem kopen(of all ati).

Ik heb anders nog geen ATI harde schijf, nVidia geheugenmodule of Matrox muis gezien

[Verwijderd]

Niet voor niets zijn zowel Apple als Microsoft bezig om de GPU (die een groot deel van de tijd toch niets staat te doen) veel meer te betrekken bij gewone OS taken. Apple nu al in Tiger (hoewel het standaard nog niet aan staat, komt met een update binnenkort) en Microsoft in de eerstvolgende Windows-versie (Longhorn).

Dat heeft niets met dit artikel te maken, in de voorbeelden die je noemt worden de GPU's nog steeds voor redering gebruikt, zij het via het OS. Maar dat heeft niks te maken met "gewone" taken van de CPU overnemen.

[Verwijderd]

Wat is er mis met appels en peren
Natuurlijk zijn ze hetzelfde, beide zijn ze fruit..

Dus als de appels niet snel zijn in de ochtend verkoop, dan zet je de peren in...

en niet meer een appel en een peren kraam, maar een groentenkraam!!

[Verwijderd]

Fruitkraam.

[Mizitras]

Groentenkraam kan ook.
(ja, ik ben serieus)

[Verwijderd]

dat een gpu voor grafische doeleinden ontworpen is en een cpu voor een groot aantal verschillende taken is iedereen welk duidelijk lijkt me..
wil nog niet zeggen dat je ze niet kan vergelijken in snelheid in een sorteer opdracht.
sorteren lijkt voor een mens waarschijnlijk vrij makkelijk , maar voor een binair systeem is dat iets heel anders , zeker als het om een zeer groot aantal te sorteren objecten gaat (ook al zijn het maar getallen).

[4VAlien]

groter dan en kleiner dan zijn toch hele elementaire operaties die dan ook altijd hardwarematig aanwezig zijn (in ieder geval in cpu's) en ik snap niet waarom 'veel' juist een probleem zou zijn. Computers zijn juist goed in het doen van iets simpels, met veel dingen duurt het langer maar ja bij mensen ook.

[TheRock2k4]

Dat klopt jah, maar met sorteren heb je vaak dat als x dingen moet sorteren het n seconden duurt. Moet je 2 keer x dingen sorteren, dan heb je er n^2 seconden voor nodig.... (afhankelijk van je soorteer algoritme natuurlijk)

[Kurgan]

Misschien is het dan wel tof om te laten zien dat een GPU ook andere dingen kan doen dan beelden renderen, maar om dat weer te geven met een vergelijking als deze vind ik een beetje vreemd

-zucht- Dat is nou juist het hele DOEL van deze vergelijking. CPU's en GPU's zijn voor hele verschillende doeleinden gemaakt, en om een beetje duidelijk te maken hoeveel kracht er in een GPU zit als hij op de juiste manier toegepast wordt is deze test gedaan.

Denk je nou eens even in wat er gebeurt als alle taken dynamisch verdeeld kunnen worden over GPU en CPU, zodat elk kan doen waar hij het best in is, en onthoud nu dat een GPU in sommige opzichten sneller is dan een P4 3.2GHz met 2GB geheugen. Lijkt het dan nog steeds zinloos?

[Kurgan]

Klein leermoment voor je, niet iedereen ziet dingen meteen.

Klein leermoment voor je: niet iedereen neemt de moeite om het artikel te lezen voor ze reageren. Het staat er namelijk letterlijk in wat het doel van deze test is: "Onderzoekers van de University of North Carolina in de Verenigde Staten hebben de snelheid waarmee GPU's en CPU's kunnen sorteren vergeleken."

Het hele artikel gaat erover wat GPU's beter kunnen dan CPU's, dus als iemand dan gaat vragen wat het nut ervan is en waarom een GPU met een CPU vergeleken wordt dan vind ik dat wel een zucht waard ja. Het is inderdaad absoluut niet speciaal om dit in een keer te zien...

[Rembert]

Het is wel een hele leuke vergelijking, GPU's met CPU's vergelijken, maar deze zijn beiden voor een totaal ander doeleinde gebouwd. Deze "test" vind ik dan ook een beetje àla appels met peren vergelijken.

Ja, dus? Als je reken-power nodig hebt, dan zoek je die op. Op m'n Apple ][ gebruikte ik de Z80 processor van mijn CP/M kaart ook af en toe. En met de C-64: Daar kon je de processor in de externe floppy drive ook gebruiken. Dat werkte ook. De VIC en de SID eigenlijk nooit geprobeerd. Hmmmz... najah... m'n C-64 tijd ligt ver achter me.
Ik heb ook een 68020 scanner kaart gehad voor de PC (van Omnipage geloof ik). Maar het is me nooit gelukt om die aan te spreken - kheb daarna maar een Amiga freak wijsgemaakt dat de kaart een Amiga emulator bevatte voor op de PC En hij geloofde het ook nog Reden genoeg om m uit de droom te helpen en de kaart kado te doen.

[TD-er]

Vroeger kon je een fractal sneller uit laten rekenen op je Laserjet printer met Postscipt-support dan op de toen verkrijgbare PC's. Het gebeurde dus al veel langer dat CPU's in randapparatuur gebruikt wordt.

De C'T heeft ook eens een geheugentest-programma gemaakt wat in het videogeheugen van de videokaart draaide en zo dus al het geheugen in de PC kon testen.

[Zegato]

Lees jij dan ook even

Misschien is het dan wel tof om te laten zien dat een GPU ook andere dingen kan doen dan beelden renderen, maar om dat weer te geven met een vergelijking als deze vind ik een beetje vreemd

Ga dus alsjeblieft ergens anders trollen.

[foppe-jan]

juist. ik begrijp dat ze het hadden moeten testen op een gpu met dezelfde specs als een cpu dus (even voor de duidelijkheid: die dus nooit gemaakt zullen worden omdat het absoluut niet interessant is)?...
denk je niet dat juist *dat* nooit zou gebeuren, en dit wel, en dat iets wat wel gebeurt eerder aan zal zetten tot innovatie dan iets wat niet gebeurd..

nah ja, je zal wel niet heel sterk zijn in logica

[muksie]

De GPU zal dus in de toekomst niet alleen meer samenwerken met de CPU bij het renderen van beelden maar ook voor andere zaken, zodat je dus eigenlijk twee processors in de computer krijgt die samen voor een snel systeem zorgt dat alles kan.
Dus een processor voor de ene soort taken, zoals uitvoeren van programma's enzo en een processor voor andere taken, zoals onder andere het renderen van beelden.

Maar is het nu ook mogelijk om de goede kanten van de GPU en de goede kanten van de CPU te combineren in een XPU

[Chatslet]

Ik meen dat er op tweakers wel eens eerder berichten hebben gestaan dat een GPU bepaalde niet video gerelateerde taken sneller kon verwerken dan een CPU. Dit bewijst maar weer eens dat een multipurpose processor zoals de x86 bijna nooit optimaal benut wordt. Wat er met deze bevindingen gaan gebeuren lijkt me erg interessant: gaan we op den duur een soort van super computer krijgen met allemaal processoren van verschillende architecturen die allemaal voor andere taken geschikt zijn? In feite is dit nu al het geval met bijvoorbeeld GPU's, moderne geluidskaarten en hard disk controllers waar processoren op zitten die echt geoptimaliseerd zijn voor 1 specifieke taak. Het wachten is nu nog op een programma dat echt iets nuttigs kan doen met de "rekenkracht" van de GPU en dan doel ik niet op spelletjes maar echte complexe rekentaken zoals bijvoorbeeld encoding etc...

[Rey Nemaattori]

Duh, je zegt het zelf: multi purpose, dat betekent tevens dat ie nergens in gespecialiseerd is, en nergens in uitblinkt, maar wel heel veel best goed kan.

Een beetje gpu heeft tegenwoordig over de 200 miljoen transistoren, de FX-57 van amd zit net niet aan de 120 mil geloof ik, nogal een verschil

[fenrir]

tijd voor een koe voor de GPU dus

Alleen maar goed voor DPC

[Reinstein]

idd, zodra de monitoren standby gaan hoeft de GPU niks mee te doen, dan kan hij/zij mooi voor andere dingen gebruikt worden, hoeft niet perse een te zijn, voor het renderen kan het ook heel handig zijn.

[bigfoot1942]

nu ben ik benieuwd tot hoeverre hierbij een AGP videokaart nog ondersteund gaat worden. Ik heb dan wel een x800 Pro (geflashed naar XT PE) en die is toch best wel snel...
Nu weet ik dat AGP niet zoveel upstream heeft, maar is het theoretisch nog mogelijk een AGP kaart hiervoor te kunnen gebruiken of is de upstream bandbreedte hiervoor gewoon sowieso veel te weinig?

Een koetje op mijn GPU lijkt me wel wat

[Chatslet]

Download het programma GPUsort http://gamma.cs.unc.edu/GPUSORT/download.html en probeer het eens zou ik zeggen...

[Capa]

Dat progsel werkt alleen nog maar met NVidia kaartjes

Requires a programmable NVIDIA Graphics Card (NVIDIA GeForceFX series, GeForce 6 series, and GeForce 7 series), latest NVIDIA drivers (7772 or higher), and GLUT libraries.

Note: We will support ATI GPUs in future releases.

[Verwijderd]

Hoe hebben ze dan met een ATI kaart kunnen testen?

Er zijn drie mogelijkheden:
1) Er is alleen ondersteuning voor een klein aantal ATI kaarten.
2) De test is met een nieuwere versie dan 1.0 gedaan.
3) De link wijst helemaal niet naar hetzelfde algoritme dat in de test is gebruikt (Lijkt me vreemd trouwens)

[the_stickie]

of het programma heeft known issues op sommige of meerdere Ati's, en hebben ze die er liever uit voor ze het progsel in het wild laten...

[Verwijderd]

Dit toont weer eens aan dat het nuttig is om gespecialiseerde rekeneenheden in je machine te hebben ipv 1 supersnelle general purpose CPU.

Voor graphics doeleinden is dit al een tijdje duidelijk, maar in alle berichtgevingen rondom de cell werd dit principe toch een beetje in twijfel getrokken. Testen als dit geven duidelijk weer dat het nuttig is om dergelijk eenheden bij specificieke, non-game related tasks, in je systeem te betrekken.

Wat wel een probleem is, is dat het voor developpers moeilijker wordt om dergelijke eenheden effecient te benutten. In het geval van graphics is het duidelijk, maar in het geval van sorts uitvoeren wordt het een stuk moeilijker om te beslissen of je het de CPU laat doen of de GPU of een andere speciale rekeneenheid (zoals in de cell). Natuurlijk kun je ook dit weer abstracten via een API, maar het geheel wordt er niet makkelijker op.

Tevens, zijn GPU's geschikts om rekentaken in een multi-tasking omgeving uit te voeren? Kun je die GPUSort meerdere keren tegelijk hebben draaien? Waarschijnlijk niet, dus zul je een manager laag nodig hebben die de resource GPU gaat beheren. Kortom, er is veel mogelijk, maar zo heel makkelijk in de praktijk is het niet.

[Dala]

nope.. geen multitask.. staat ook op de website:

To ensure maximum performance, a GPUSort object takes up the maximum video memory available on creation. Therefore, in our current implementation, only one GPUSort object is active at any time and more importantly, the object is cleaned when it is no longer required. Ideally you should not need to instantiate more than one object because the same object can be used to sort any number of arrays. Failing to do so may lead to severely degraded performance. It is also possible to add an interface where multiple objects are created with lower memory requirements.

[familyman]

Dit is toch ook waarom veel mensen een audigy oid hebben. of een raidcontroller met logica?

Jammer genoeg betreft dit ook alleen maar logica die op één bepaalde manier te gebruiken is. Toch, We weten het dus al, maar gebruiken het zo beperkt. Dat vind ik nu net het mooie van CELL, gooi de logica er maar in en dan gaan we het proberen.

Zo is het inet ook mooi geworden. De begintijd van inet lijkt ook niet op wat we nu allemaal voor moois zien. Eerst de capaciteit en dan de inhoud.

[Verwijderd]

Een andere moeilijk is overigens de mogelijkheid om een compiler automatisch code voor dergelijke alternatieve rekeneenheden te laten genereren. Dit is zeker een interesante optie: de compiler een stuk code laten analyseren en laten bepalen of dat effecienter execute op de target CPU of op rekeneenheid X, Y, of Z van het target systeem.

In het meest optimale geval zou je willen dat de compiler code voor ALLE soorten rekeneenheden genereerd, met een prefererence rating. Het OS kan dan aan de hand van die rating een beslissing maken:

Code portion A draait meest effecient op unit X
Unit X is nog 2 seconden bezet.
Unit Y heeft 75% effecientie t.o.v. X voor dit probleem, maar is NU beschikbaar.
Huidige taak zal +- 1 seconden duren
conclusie: Nu de Y versie van de code op Y laten executen is het voordeligst.

(overigens is het automatisch bepalen van de executie duur theoretisch onmogelijk, maar het gaat hier om het idee)

[tweakerbee]

Dus je zegt het zelf al: Het is niet handig, omdat je dan moet gaan gokken hoe lang het zal duren voor die ene unit weer vrij is.
Toch wel leuk, als je computer het gewoon op het snelste apparaat uitvoert.

[hondeman]

Oude tijden gaan herleven (zx-81): het beeld even op zwart wanneer het schaakprogramma de volgende zet bedenkt

[H!GHGuY]

uit het grafiekje blijkt dat het sorteren hier niet langer O(lg n) is maar O(n) ?
mooie zaak, maar de toepasbaarheid ervan ?
een GPU is net zo snel omdàt het ook zo specifiek is...

edit: je hebt gelijk... my bad

[Dala]

je bedoeld O(n log n)...
want O(log n) is kleiner als O(n)..

en als ze inderdaad een sort hebben uitgevonden die een orde heeft van n of lager.. dan hadden ze dat ook wel vermeld..

maar voor zover ik wit is het nog niet mogelijk om in < O(n log n)..

wat wel zo is in dit geval, dat het goed geoptimaliseerd is.. waardoor het bij kleinere aantallen een O(n) lijkt..

[Twilight Burn]

Juist bij grote getallen stijgt het log gedeelte van n*log(n) veel minder snel dan het getal gedeelte, en gaat dus lijken op een rechte lijn. Voorbeeld: bij ~8 miljoen is je log(n) 23, en bij ~16 miljoen (verdubbeling dus) is de log(n) 24. En (16*24)/(8*23) =~ 2.09 - wat dus niet veel meer is dan de 2 van een O(n) functie.

[H!GHGuY]

maar voor zover ik wit is het nog niet mogelijk om in < O(n log n)..

idd wegens het feit dat je moet vergelijken...
dat was ons eerste semester Algoritmen & Gegevensstructuren, maar het zit blijkbaar al ver

[jvo]

Sorteren in O(n) is wel mogelijk, namelijk met radix sort. Dit is niet op basis van vergelijkingen. Ik vraag me af of je dit ook op floating point getallen kan toepassen. (Hmm, daar ga ik eens over nadenken...)

[samvanbrussel]

Sorteren (op basis van vergelijken) kan nooit sneller zijn dan O(n lg(n)). Quicksort is O(n lg(n)).

[Verwijderd]

Binsort: O (n)

Alles kan, zolang je maar extra restricties toevoegd.

[Verwijderd]

"32 bits drijvende komma getallen"

babelfish?

[laurensl]

heel erg grote nauwkeurige getallen

-2.147.483.648 tot 2.147.483.647

[Verwijderd]

Ik snap ook wel wat ze bedoelen. n.l. een komma getal met 7 significante cijfers. Echter, het leek mij een beet je een steenkolen vertaling zo van: Yes then are you in the monkey gestayed.

drijvende komma

[Verwijderd]

"32 bits drijvende komma getallen"

babelfish?

32 snappishly floating comma numbers
en als we dan toch bezig zijn
32 la virgule nombres brusquement flottante

[Ruuddie]

Drijvende komma... K vind t ook achterlijk, maar zo wordt Floating Point nou eenmaal vertaald hier

Ik vind zelf 'Centrale Verwerkings Eenheid' (CVE) ipv 'Central Processing Unit' (CPU) véél erger. En ja, dat wordt gebruikt

[bredend]

Gelukkig kan je bij je bureau ook een CPU-houder kopen!

Ben benieuwd hoe je nou eigenlijk moet denken wil je zo'n programma voor een GPU schrijven. Men doet al zo moeilijk over de Cell processor, lijkt me dat een GPU nog meer simultaan kan.

Ben benieuwd wanneer geluidsbewerking via de GPU gaat...


Trouwens, die site van GPUSort lijkt verdacht veel op de site van Macromedia

[Verwijderd]

Ben benieuwd wanneer geluidsbewerking via de GPU gaat...

bestaat al :

http://www.bionicfx.com/

[Olaf van der Spek]

-2.147.483.648 tot 2.147.483.647

Dat is het bereik van een 32-bit signed integer.

[Verwijderd]

Floating point is niet nauwkeurig
Je hebt altijd te maken met underflow /overflow. Nauwkeurige berekeningen zijn een ramp op een computer (beter gezegd, dat kan dat ding gewoon niet)

Daarnaast het bereik.
Een floating point getal is basicly als volgt op gebouwd A * B ^C waarbij B constant is.
Dus 10 is bv 1 * 10^1
100 1 * 10^2
1000 1 * 10^3
0,1 1 * 10 ^-1
enz

Als ik voor A en C 16 bits ruimte neem -32768 tot 32767 en B op 10 zet is mijn bereik
-32768 * 10 ^32767 tot 32767 * 10 ^32767

De nauwkeurigheid is bij deze keuze natuurlijk niet al te best, maar dat valt te verbeteren door B kleiner te maken en meer bits beschikbaar te maken voor A (en dus minder voor C) Met floating point kun je dus nauwkeurigheid opofferen voor bereik. Maar het getal 10,0000001 is bijvoorbeeld met de hierboven gekozen waarden voor A,B en C nooit exact weer te geven.

[Olaf van der Spek]

babelfish?

Floating point numbers. Van de vorm (-)#.######### x 2^(-)####.

[Verwijderd]

http://nl.wikipedia.org/wiki/Drijvendekommagetal