Evoluerende chipontwerpen met distributed computing

In een artikel van New Scientist wordt geschreven over een nieuw distributed systeem dat electronische schakelingen ontwerpt. De manier waarop dit gebeurt is opmerkelijk: evolutie. Cliënts brengen willekeurige veranderingen aan in een basisontwerp, waarna een simulator bepaalt of de gemuteerde versie van de chip levensvatbaar zou zijn. De stukken die goed (of in ieder geval beter) blijken te werken dan het origineel worden na een tijdje teruggestuurd naar een centrale server, die vervolgens een aantal andere cliënts bevrucht met de verbeterde bouwstenen. Door de cliënts in een aantal gescheiden groepen in te delen wordt voorkomen dat ze de oplossing allemaal in dezelfde richting gaan zoeken, met het risico om vast te komen zitten.

Miguel Garvie, de Britse student die het systeem heeft ontworpen, zegt dat de resultaten veelbelovend zijn. Uit het systeem zouden na vijf dagen al chips zijn komen rollen die twee keer zo snel waren als het origineel. Nadeel is nog wel dat ze wel 50% groter kunnen worden tijdens alle mutaties, maar het programma aanpassen om zich aan standaard afmetingen te houden zou relatief eenvoudig zijn. Hoewel de student niet de eerste is die experimenteert met evoluerende chips, wil hij wel de eerste systeem bouwen dat echt complexe ontwerpen aankan door gebruik te maken van distributed computing:

The best solutions to complex problems often result from the occasional combination of individuals that have evolved in many diverse populations, he says. Single populations can become stuck in an evolutionary niche that is too highly specialised.

Even though the project has already produced some promising results, Garvie admits that it is not yet ready for commercial use. The circuit designs generated do not have a standard die size, for example. "It's still a bit green," he says. But he believes it should be relatively simple to refine the process.

Reacties (37)

Dat is eigenlijk een logische ontwikkeling.
Bij mij op school heb ik het vak AI gehad waar dit principe ook werd behandeld.
Alleen deden wij dit met het "traveling salesman" probleem. Waarbij je de kortste route moet vinden met behulp van deze methode.

Wat je dus doet is het principe van natuurlijke selectie gebruiken om zo tot een beter resultaat te komen. Wat je doet is willekeurig dingen aanpassen (muteren) en vervolgens bekijken of dit beter is. En dan vervolgens met deze verbeteringen verder gaan om zo nog een beter resultaat te krijgen.

Dit principe is normaal in de natuur (vandaar dat het in dit stuk ook evolutie wordt genoemd). In de natuur is het dus dat de sterkste van een groep zich mag voortplanten, waardoor je een betere en sterkere soort krijgen (bijv dat een bacterie resistent wordt tegen peniciline)

Maar de natuur is ook niet altijd even efficiënt. Kijk maar eens naar een kolonne mieren die om een takje heenlopen, haal het takje weg en de kolonne blijft doorleuk het oude pad volgen....

Het "mierenprincipe" is een van natuurs meest efficiente systemen. Elke mier laat op zijn pad een feromoon achter. Hoe meer mieren het pad volgen des te sterker het geurpad. Op die manier is heuristiek supereenvoudig maar zeer efficient ingericht.

het takje weghaal idee, lijkt mischien een fout. Maar in de werkelijkheid is dat niet zo heel erg. En na verloop van tijd zullen er best wel mieren de 'shotcut' nemen en gaat het hele spel van voren af aan.

Het eerste artikel over evoluerende hardware stond al in 1997 in de NewScientist van Adrian Thomson. Zie ook hier: http://www.newscientist.com/hottopics/ai/primordial.jsp
Vooral het feit dat het uitschakelen van bepaalde cellen die geen functie lijken te hebben, toch een invloed op het totale systeem heeft, is bizar...

Dit is HET DPC project natuurlijk. Gebruik je computer voor computer research.

Als er commercieel aan verdiend gaat worden zal dit geen DPC project gaan worden.
Wel klopt het dat dit project duizend maal nuttiger is dan RC5 of ECC2.
(niet vergeten dat er een heleboel projecten duizend maal nuttiger zijn dan deze 2 laatst genoemde en waar DPC al wel aan meedoet trouwens; zoek ze hier maar uit: http://gathering.tweakers.net/forum/list_topics/5 )

Inderdaad zijn RC5 en ECC2 niet erg nuttig, t gaat domweg om geld en om ff iets te testen.... Ik moet wel zeggen dat die test wellicht een basis kan zijn voor betere beveiligingen....

Verder is het efficienter maken van chips ook nog steeds minder nuttig dan onderzoek naar kanker...

Verder is het efficienter maken van chips ook nog steeds minder nuttig dan onderzoek naar kanker...

Kun je dat misschien even onderbouwen? Je stelt het hier als een onweerlegbaar feit, terwijl ik mij goed kan voorstellen dat mensen het er niet mee eens zijn.

Verder is het efficienter maken van chips ook nog steeds minder nuttig dan onderzoek naar kanker...

Wat een onzin. Het is helemaal niet ondenkbaar dat niet een mens met een geneesmiddel voor kanker komt maar een computer. Het is misschien wel waarscheinlijker.

Deze vorm van vooruitgangsfobe redenatie valt in dezelfde sfeer als de zinloze protesten tegen genmanupilatie en klonen c.q. DNA manupilatie.

JE KUNT VOORUITGANG NIET BLOKKEREN OF TEGENHOUDEN.

offtopic:
deze tekst zal wel weer tot flame gebombardeerd worden

etisch op korte termijn wel, maar op langere termijn is het efficienter maken toch echt beter:

- betere computers kunnen meer/sneller simulaties draaien (betere onderzoeksmiddelen voor kankeronderzoek
- efficientere chips verbruiken minder energie (broeikas -> huidkanker
- efficienter grondmiddelen verbruik zorgt voor minder vervuiling (toxische prikkelingen zorgen voor verhoogd kankerrisico).
- heuristische technieken kunnen efficienter/anderszins op zoek gaan naar oplossingen voor kanker.

Einstein (ruwweg gequote): "computers bevatten een enorme rekenkracht, maar missen creativiteit. De mens mag dan wel slecht rekenaar zijn, zijn creativiteit is prima compensatie. Breng deze 2 samen en het perfecte kennismiddel is gevonden". Kortom: dit is nu weer een stapje dichterbij - en dus ook dichterbij alle problemen die een wetenschappelijke/kennisoplossing benodigen.

Zo'n soort systemen zou ik niet graag willen gebruiken. De kans dat het systeem niet (helemaal) voldoet is natuurlijk ontzettend groot. En hoe bepaal je of een ontwerp goed genoeg is om op de markt in te zetten?

Uiteraard zijn er wel toepassingen te bedenken waarvoor dit een goede methode zou zijn. Denk aan toepassingen waar exactheid van minder belang is, zoals geluid- of beeldherkenning, of video (de)compressie.

Overigens lijkt dit wel veel op de manier waarop een of ander bedrijf in Amerika software maakt --> Gedistribueerd het ontwerp aanpassen en het beste houden

Je test een processor ook niet op *alles*. Daarom kan het prima voorkomen dat ontwerpfouten pas een jaar na de introductie van een processor ontdekt worden (Intel, Sun).
Als je aan kunt tonen dat je ontwerp voldoet aan de van te voren gestelde criteria, is dat goed genoeg.
Deze ontwerpen hoeven overigens niks af te doen aan exactheid. Dat ze andere ontwikkelmethoden hebben gebruikt hoeft niet per definitie te betekenen dat ze minder nauwkeurig zijn. Het is eerder dat deze circuits slimmer omgaan met de aanwezige bouwstenen dan een menselijke ontwerper zou doen.

Bovendien worden de chips van tegenwoordig ook grotendeels door programma's ontworpen en gecontroleerd. Een ontwerper moet alleen bepaalde keuzes maken die nu door een programma gemaakt worden. De controlle werd eerst door een cluster gedaan, nu doet jou pc het.

http://www.cogs.susx.ac.uk/users/mmg20/contrcpu.htm

Hier kun je de client downen

Running....

ziet er wel leuk uit dat Java maar volgens mij kan je beter een Native C of C++ programma bouwen (Sneller)

Ik zie nog wel wat problemen...

De chip moet natuurlijk testbaar zijn (krijgen we met het vak digitaal systeem ontwerp). Als er overbodige hardware in een chip zit blijkt het dat zo chip meestal niet volledig testbaar is. Er zullen dan vaak extra pinnen moeten worden toegevoegd.

Een chip als deze moet dan waarschijnlijk op al zijn functies en op alle ingangsvariablen worden gecontroleerd. Dit soort tests noemen we niet voor niets uitputtende tests en zop deze manier testen is onbetaalbaar en kost extreem veel tijd (we praten dan over maanden of jaren).

Het is dus veel te duur om volledige chips op deze manier te verkrijgen of een van de parameters moet dit bevatten. Het is wel goed mogelijk om onderedelen uit de chip te gebruiken voor toekomstige chips.

Alles bij elkaar juich ik dit project geweldig toe !!!!

Goed nieuws, nog een project voor DPC misschien

Ik weet wel dat ik er als een van eerste mee ga doen. Als dit gaat zorgen voor de eerste open source chips dan zie hier nog wel een goude toekomst in. Tot nu toe was het produceren van chips nog niet echt duur, maar het ontwerpen wel. Nu de ontwerpkoste overboord worden gegooid, en dadelijk iedereen deze chip zou kunnen gaan bakken, kunnen we wel heel goedkope chips verwachten.
Ik zie alleen het probleem aankomen met compatibaliteit. Als dit systeem de eerste heeft gevonden en dit is aangeboden aan het publiek (er dus ook een OS enzo). Dan moet de volgende versie die er uit rolt wel compatible zijn met de vorige, of ie daar rekening mee zal gaan houden betwijfel ik. Wat dus een acceptatie van het publiek weer tegen zal gaan werken. Immers zullen de OS proggers het op een gegeven moment toch wel op moeten geven verwacht ik. Tenzij het systeem ook een compiler maakt voor de proc

EDIT:
Hier is al iemand die een linkje heeft gevonden naar de webpagina waar het progje al te downen is. In zoverre ik het begrijp gaat het er niet echt om complete cpu's te generen maar meer om bepaalde circuits te optimaliseren, zoals adders of fpu's. Op die pagina kun je ook een linkje vinden naar de dingen die ze al ondervonden hebben. Dus ze publiceren wel degelijk hun ondervindingen. Voorbeeld.
Wat is de wetenschap toch mooi he.

Nu de ontwerpkoste overboord worden gegooid, en dadelijk iedereen deze chip zou kunnen gaan bakken, kunnen we wel heel goedkope chips verwachten.

Iedereen? Ik denk niet dat de maker van deze software het uiteindelijke ontwerp zo maar even op straat gooit zodat iedereen het kan gebruiken. Ik denk dat als het uiteindelijke ontwerp goed genoeg is, of als er bijzondere technieken gevonden zijn, dat hij dan eerst langs een paar fabrikanten gaat om te kijken of die intresse hebben.

Pas als dat niet gaat zal hij misschien het ontwerp vrijlaten.

Maar ook al doet hij dat vanaf het begin, het is niet goedkoop om een chip te laten fabriceren. Ten eerste moet er een productielijn worden ingericht bij bijvoorbeeld UMC en voordat dat gebeurd moet er wel genoeg vraag naar zijn. Dan nog zijn de kosten redelijk hoog, want het opzetten moet ook terug verdiend worden.

Als dat allemaal gelukt is moet er waarschijnlijk nog een chipset ontworpen worden, want ik denk niet dat het ontwerp meteen op een s478 of een socket A kan worden geprikt, dus daarvoor komen ook weer extra kosten die betaald moeten worden.

En als dat allemaal gelukt is, is de vraag welke architectuur het is geworden, als het x86 of PowerPC is zal het geen probleem zijn om een OS te vinden, maar wanneer dat niet het geval is en er moet een OS (bijvoorbeeld Linux) worden aangepast gaat dat ook een tijd duren.

Al met al zie ik dus niet gebeuren dat het ontwerp straks gewoon vrij wordt gegeven en dat wij als consument zo even een CPU kunnen laten bakken. Ik zie eerder Intel, AMD of IBM met het uiteindelijke ontwerp aan de haal gaan als het goed genoeg is.

edit:

Als ze een bestaand ontwerp willen laten evolueren zullen ze toch eerst de blauwdrukken moeten hebben, en die geven Intel, AMD en de rest echt niet af.

Ik denk eerder dat (als het goed werkt) hij het verkoopt aan intel / amd / etc of bij 1 van deze bedrijven in dienst gaat (lijkt me wel dat ze hem graag willen inhuren)

Aangezien het een student is die het ontwikkeld heeft betreft het waarschijnlijk een project voor de universiteit. Dit betekent dat de universiteit ook eigenaar is van het ontwerp en eventueel daaruit voortvloeiende patenten. Als deze het met de wereld wil delen (wat sommige universiteiten echt doen) is dat mogenlijk.

ZO een groot probleem moet dat toch niet zijn? B.V. In linux heb je toch ook gewoon een CPU selectie in je kernel zitten, en windows ondersteunt ook meerdere CPU's. Echter het groote (en belangrijke) verschil zit hem in het feit dat beide CPU's 386 compatible zijn en je gemakelijk een OS kan installen. Dit word wat lastiger als je een nieuwe kernel ergens op moet zetten zonder dat je het systeem direct kan booten (bootcd oid kan natuurlijk wel weer)

Je kan hem gewoon compatible maken.
Om te bepalen of een volgende generatie sterker is dan de vorige, moet je een aantal parameters meegeven (hoe moet je anders testen of de mutatie beter is). Een van de parameters kan zijn dat het ontwerp moet voldoen aan x86 standaard, of dat hij PPC is.
Zo kan je ook een evolutie kunnen laten plaatsvinden die niets doet aan de features, maar alleen aan de energieconsumptie. Dus dat je een nieuwe chip maakt die exact hetzelfde doet als een Pentium 4 met HT, maar 50% minder stroom verbruikt, of dat je minder pinnetjes wil, of dat je 2x zoveel kracht wil op een kleinere die met maximaal hetzelfde stroomverbruikt.
De mogelijkheden zijn eigenlijk eindeloos op dit punt.

Misschien is het ook is tijd om af te stappen van het constante backwards compatible ontwerpen van chips. Denk je eens in wat een vooruitgang er geboekt wordt als een keer de hele structuur grondig herzien wordt, in plaats van te zorgen dat bijvoorbeeld spellen als tetris of digger voor de 8086 nog gedraaid kunnen worden.

Eens in de zoveel tijd iets compleets nieuws ontwerpen, met het risico van oncompatibiliteit lijkt me niet ongezond voor de technologische ontwikkelingen op computergebied.

Op zich heb je wel gelijk, maar er zit altijd een commercieel belang bij het ontwikkelen van nieuwe technologie inbegrepen.
En als het aan de consument ligt willen ze niet in een keer alles overboord gooien om vervolgens alles opnieuw aan te moeten schaffen. Daarbij komt als je een nieuw type proc ontwikkeld, is er geen software daarvoor op de markt, wat ook weer een vereiste is om geaccepteerd te worden.
Kijk maar naar de Itanium, het heeft Intel veel moeite gekost om deze op de markt te krijgen en nog zijn er lang niet zoveel toepassings gebieden als er momenteel voor de x86 is. Voor de consument is deze proc al helemaal niet geschikt (even afgezien van de prijzen).
De Opteron zal wat dat betreft een vele malen makkelijkere introductie krijgen aangezien je geen nieuwe software hoeft te kopen om met deze proc aan de gang te kunnen.

Realiseer je je wel de prijs van die 'open source' chips?

Universiteiten kunnen 'gratis' nog wel een paar honderd chips per jaar bakken.

Maar als je een beetje hooggeclockte (zeg 133Mhz) chip wil bakken dan betaal je ladingen met geld. Echt ladingen.

In een open source chip zou mijn enige voorstel zijn om indien er een werkende chip is, om dan op 1 chip zoveel mogelijk cpu's te bakken.

Dus een CMP chip met heel veel chips op 1 chip.

Dus niet 2 of 4 of 8. Maar echt *heel* veel. Elk natuurlijk wel met een superkleine L1 cache, een iets grotere L2 cache en een gezamenlijke L3 cache.

Dan kan zo'n chip zelfs al is hij heel laag geclockt tenminste nog wat presteren voor *bepaalde* applicaties.

Echter als je voor een groot publiek deze chip wil drukken. Houdt rekening met prijzen van rond de 5000 euro per chip.

MVG

Zoals bij veel producten in de pc industrie overstijgen de R&D kosten vaak de productie kosten.
Het eerste wat Intel en AMD dus doen is deze R&D koste terug verdienen en vervolgens de prijzen omlaag schroeven tot een zo laag mogelijk niveau (productie kosten + een beetje winst), als ik dan in de pricewatch zie dan een 1700+ maar 54 eurotjes kost.
Tuurlijk heb je nog wel opstart kosten, zoals het maken van de templates ed. Dus een introductie prijs van 200 a 300 euro mag je toch wel verwachten. Maar bijna niet hebben van R&D geeft je iig een grote voorsprong op de concurentie.

Waar kunnen we "intekenen"

Wat is hier nu eigenlijk nieuw aan? Genetische algorithmen bestaan al meer dan 10 jaar, gedistribueerde systemen nog langer, en simulaties van chipontwerpen ook. Is de combinatie dan zo origineel?

Het concept GA bestaat al langer dan 10 jaar, zeg maar grofweg zo'n jaartje of dertig (zoek maar eens op John Holland, 1973). In de afgelopen 30 jaar zijn er ook al heel veel mensen geweest die bovenstaand idee geopperd hebben in een of andere vorm. GA's worden al heel erg lang toegepast bij ontwerp van allerlei zaken, van vliegtuigvleugels tot netwerken. Chip design (en evolvable systems is het algemeen) is al veer eerder geopperd (kijk maar eens bij de Evolutionary Electronics group in Sussex - http://www.cogs.susx.ac.uk/users/adrianth/ade.html).

Dus nee, niet nieuw, wel leuk, en weer een leuke opsteker voor evolutionary algorithms, die de afgelopen jaren een beetje weggezakt zijn qua belangstelling.

Maar denk je dat het toeval is dat bij dezelfde universiteit een student dit idee weer wat verder uitwerkt?
Het feit dat de universiteit dit via de NewScientist laat uitkomen geeft wel aan dat dit een nieuwe ontwikkeling is.

Welke grappenmaker heeft dit sprookje geschreven?

Een verandering plegen in een chip is vrij ingrijpend. Ten eerste moet het natuurlijk in een hardware language als verilog gebeuren.

Ten tweede is het zo dat het verifieren van een complexe chip wel een paar jaar systeemtijd kan kosten van een enorme supercomputer.

Dus als elke hacker wat wijzigingen in het ontwerp aanbrengt, met name als het complexer wordt, dan zit men met het bovenstaande probleem.

Daarnaast is het doel wel erg hoog gesteld. "de grootste priemgetallen berekenen".

Dus die chip moet ook nog eens gaan concurreren met 's werelds grootste supercomputers die vele teraflops leveren?

Ik krijg de indruk dat degene die dit project 'gestart' is niet goed begrijpt wat een chip ontwerpen is.

Die 'enorme' verbeteringen waren vast mogelijk omdat het superknullig ontworpen was.

Verder moeten we realistisch zijn dat zo'n chip als deze natuurlijk nooit zal gaan concurreren met commerciele chips als die we voor 100 euro in de winkel kunnen kopen.

De belangrijkste snelheidswinst van processors zit hem in het hoger clocken van processors. Teneinde processors hoger te kunnen clocken dienen de meest briljante ontwerpers ter wereld werkelijk enorme moeite te doen om de chip beter te ontwerpen.

Daardoor kunnen ze die dan een factor 2 tot 3 hoger clocken dan een 'standaard' ontwerp.

Factor 2 tot 3 is zoals we begrijpen een enorm verschil.

Het is het verschil tussen een P3 op 800Mhz en een P4 op 3Ghz, of een K7 op 700Mhz versus een K7 op 2.25Ghz

Een volledig generatie verschil kortom.

In plaats van een chip te ontwerpen is het natuurlijk ook mogelijk om een electronische schakeling te ontwerpen. Zoals sommigen zullen weten is het zo dat de Cray supercomputers niet echte chips zijn maar electronische schakelingen.

Het nadeel is de enorme prijs en power consumptie.

Een enkele Cray processor vreet ongeveer 150 kilowatt.

Dat is dus 150000 watt voor een ENKELE processor geclockt op 'maar' 1 Ghz.

Dat is dan een vector processor.

De kosten van een multiprocessor Cray machine een aantal jaar geleden was vrij prijzig. Rond de enige tientallen miljoenen dollars.

Dus het realisme gehalte van dit project is heel erg ver te zoeken hoe mooi het de linux figuren en studenten misschien ook in de oren moge klinken.

Overigens die krijgen hun electronische schakelingen nooit op 1 Ghz geclockt.

Realiseer u goed dat gigantische fabrikanten zelfs processors als de 30 watt vretende MIPS nog maar slechts op 800Mhz hebben weten te clocken.

En die 800Mhz MIPS processor komt pas uit in 2004 op zijn vroegst

Ten tweede is het zo dat het verifieren van een complexe chip wel een paar jaar systeemtijd kan kosten van een enorme supercomputer.

Dit is ontzettend overdreven. Het kost veel kracht om een chip te verifieren ja, maar echt geen "paar jaar". Als dat zo zou zijn dan zou de industrie nooit zo snel en zo vaak nieuwe of verbeterde chips uit kunnen brengen als nu het geval is. Het ontwerpen van een nieuwe chip van de grond af kan misschien wel een paar jaar kosten, maar puur de verficatie van een licht aangepast ontwerp echt bij lange na niet, en dat is precies wat deze software in hoog tempo kan doen: wijzigingen in kleine bouwstenen aanbrengen en testen. Deze software gaat echt niet de complete chip 40.000 keer opnieuw van de grond af ontwerpen, maar vele kleine verbeteringen maken natuurlijk samen wel één grote.

Daarnaast is het doel wel erg hoog gesteld. "de grootste priemgetallen berekenen".

Dus die chip moet ook nog eens gaan concurreren met 's werelds grootste supercomputers die vele teraflops leveren?

Geen idee waar je dit vandaan haalt, maar het is onzin. In het artikel staat dat distributed computing bijvoorbeeld ook gebruikt wordt om priemgetallen te zoeken. Dat wil dus niet zeggen dat "die chip" (welke chip eigenlijk? het gaat helemaal niet over één chip) priemgetallen moet gaan zoeken.

Ik krijg de indruk dat degene die dit project 'gestart' is niet goed begrijpt wat een chip ontwerpen is.

En ik krijg het idee dat jij helemaal niet weet waar dit project over gaat. Niemand heeft het over pc-processors of supercomputerchips gehad, en toch blijf je daar maar over doorpraten. Nee, deze software is inderdaad (nog) niet geschikt om een volwaardige processor van 50 of 100 miljoen transistors te bouwen of fundamenteel te verbeteren, maar dat wordt ook nergens beweerd. Dat betekent echter niet dat het concept niet werkt, niet kan werken en dat degene die die software gemaakt heeft maar een sukkel is die sprookjes vertelt.

Het feit dat chips tegenwoordig zo complex worden pleit mijns inziens juist voor dit soort brute force oplossingen, in plaats van er tegen. Het wordt namelijk steeds moeilijker, als het op dit moment al niet onmogelijk is, om een (serie) algoritmes op te stellen die voor iedere chip meteen het optimale ontwerp oplevert. Dan kun je wel met de hand verder gaan tweaken, maar dat kost veel meer tijd dan 'gewoon' een batterij computers neerzetten die zelf aan het basisontwerp gaan knutselen en doormiddel van 'evolutie' bepalen op welke punten deze nog verbeterd kan worden.

Kleine toevoeging:

En pc cpu is vaak in delen opgedeeld, welke dus apart kunnen worden bekeken en geoptimaliseerd, waardoor het bij complexe cpu's toch wat realistischer is.
En je kan het controleren van een cpu ook laten doen door de clients, want er zullen meerdere tests gedaan worden, waardoor je dat ook distributed kan doen.
Dus zo onrealistisch is het niet.
Maar een bedrijf als intel zal het wel niet snel doen, omdat ze erg gevoelige informatie de wereld rond sturen.

Linkje naar z'n website:
http://www.cogs.susx.ac.uk/users/mmg20/contrcpu.htm

edit:

Net te laat

Ze moeten gewoon de broncode van dit distributed systeem vrijgeven. Het is natuurlijk leuk om de chips openscource te maken. Maar het zou veel beter werken om een hele communty mee te laten bouwen aan het programma. Dan is de kans groot dat openscource cpuŽs realiteit worden.