Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Altera C2H – Bygg din egen kryptoaccelerator » Kryptoblog

Altera C2H – Bygg din egen kryptoaccelerator

October 24th, 2006 by Joachim Strömbergson Leave a reply »

I förra veckan var jag på en workshop för att lära mig använda verktyget C2H från Altera. C2H skall utläsas C to Hardware, alltså ett verktyg för att (automagiskt) konvertera C-kod till hårdvara. Hårdvara i form av digitala logikblock, register, minnen och ledningar.

Att generera hårdvara direkt från en programvarubeskrivning, eller annan högnivåbeskrivning är inte helt nytt – det har varit en kommande teknik i flera decenier – något som i stort sett alltid varit nästan här. När jag gjorde mitt examensarbete på Ericsson 1997 var det faktiskt precis det jag arbetade med. (J. Strömbergson, P. Wikman. Sömlös konstruktion av rekonfigurerbar hårdvara. Luleå tekniska universitet. LTU 1997:338.)

I det läget handlade det om att utifrån en beteendemodell skapad i ett signalbehandlingsverktyg automatiskt generera hårdvaruacceleratorer. När systemets huvudprocessor (En DSP från Texas Instruments) anropade motsvarande C-funktion, laddades motsvarande accelerator in i en till processorn kopplad FPGA (en Xilinx 4xxx – det var länge sedan) varvid funktionen utfördes med hög prestanda.

Detta fungerade faktiskt hyggligt, men själva högnivåsyntesen var en väldigt omständig och allt annat än automatisk process där verktygen krävde mycket stöd och handkraft för att generera något vettigt. Verktyget vi då använde var från det svenska företaget Synthesia, ett företag som sedemera köptes upp av Cadence. Deras verktyg integrerades med Cadence systemkonstruktionsverktyg SPW, och lades därefter ned.

Jag har sedan dess periodiskt tittat på verktyg och metoder för högnivåsyntes och hårdvarukonstruktion från en C-beskrivning. Jag tycker att man kan ana att det skett en klar förändring. Till det bättre. Jag skulle vilja hävda att det är två saker som gör att vi nu ser praktiskt användbar HW-syntes från C-kod:

  1. Verktygen har mognat och är nu industrianpassade. När jag gjorde mitt exjobb och då läste mycket av litteraturen på området var det uppenbart att mycket tid ägnades åt att skapa algoritmer för att optimera schemaläggning av operationer, göra resursdelningar och optimera den genererade hårdvaran. Detta gjorde verktygen komplexa och sega. Alteras C2H-verktyg gör inga försök till resursdelning alls, utan då får du som konstruktör skriva din kod så att det sker. Vidare är schemaläggningen uppenbarligen inte den mest fantastiska. Och det är ok. Jag tror att Altera (och andra leverantörer) insett att det är bättre med en fungerande och hygglig konstruktion som möter tidplanen, än en optimerad lösning som blir försenad.

  2. Moores lag. Vi får hela tiden mer och mer resurser tillgängliga. Bortsett från extremt kostnadskänsliga applikationer (mobiltelefoner för konsumenter), alternativt extrem prestanda (processorer för gamers) är det få som kan utnyttja all logik, alla ledningar och minnen som i dag får plats på en krets. Att då göra slut på 30% mer resurser, men kapa utvecklingstiden ordentligt börjar bli en acceptabel kompromiss.

Det är alltså klart bättre med ett halvkorkat, men snabbt och användarvänligt verktyg än ett avancerat verktyg som genererar nästan lika bra hårdvara som de bästa konstruktörer kan få fram för hand, men som kräver nästan lika mycket resurser och tid som en handkodad konstruktion.

(Altera, som lever på att sälja FPGA-kretsar ser naturligtvis att folk köper fler och större FPGAer, tycker säkerligen att (1) och (2) bara är positivt).

Altera har gett sig själva några genvägar som förenklar C2H. Dom utgår helt enkelt ifrån att din konstruktion innehåller (minst) en processor, mer specifikt deras mjuka processor Nios II kopplad till kommunikationsstruktur Avalon. Programvaran som skall accelereras förväntas från början köra på processorn. Den accelerator som sedan genereras kopplas in som en periferienhet i Avalon och Altera kan då generera headerfiler och programstöd som behövs för att över Avalon använda periferienheten utan att applikationskoden påverkas. Så här ser alltså det tänkta systemet ut:

Att programkoden i sig inte behöver ändras för att anropa acceleratorn är en viktig poäng och visar att det är programkoden som är i fokus. C2H är över huvud taget i första hand riktad mot programvaruutvecklare, inte mot hårdvaruutvecklare. Detta ser man inte minst av det faktum att C2H körs inifrån Alteras IDE (baserad på Eclipse) för Nios II. Det du som konstruktör behöver göra för att accelerera din funktion är att markera funktionsnamnet, högerklicka för att få upp menyn och sedan välja Accelerate with the Nios II C2H Compiler:

Vad har då detta med IT-säkerhet att göra? Jo, jag testade naturligtvis att köra igenom en kryptofunktion för att se om det verkligen var så enkelt som Altera hävdade, och om det blev någon prestandaförbättring. Funktionen jag testade att generera i hårdvara var generatorfunktionen i strömkryptot RC4:


    u_8 rc4_genkey(u_8* ip, u_8* jp)
    {

    u_8 si, sj, sk;

    // Update the pointers and read state values
    // using the pointers. The i pointer scans the
    // state memory and the j pointer jumps
    // randomly.
    ip = (ip + 1) % 256;
    si = state_mem[ip];
    jp = (jp + si) % 256;

    // Read out the new key value using the state
    // values as index.
    sk = state_mem[((si + sj) % 256)];

    // Update the state_mem by swapping the
    // ip and jp values.
    state_mem[ip] = sj;
    state_mem[jp] = ip;

    // Finally return the new key value.
    return sk;
    }


    (Nej, just den här koden är inte kompilerad, utan skriven för att visa funktionen i RC4.)

    Jag kan direkt säga att det här antagligen inte var den bästa koden att accelerera. En bättre kod hade antagligen varit en del av AES, SHA-1 eller annan kod med mycket databehandling och många iterationer. Men algoritmen för RC4 kan jag utantill och även en algoritm jag implementerat flera gånger, såväl i program som i digital hårdvara.

    Men den accelerator som genererades var mer än dubbelt så snabb som den rena programvaruimplementationen. Latenstiden, dvs tiden i antal klockcykler för att generera nästa rc4-nyckel var 12 cykler. Beroende på vilken typ av minne man använder för tillståndsminnet (state_mem) har den optimala implementationen, eller mer korrekt den bästa implementationen jag byggt, en latenstid på tre cykler. Används ett mer normalt minnesmakro för sitt tillståndsminne hamnar den handbyggda lösningen på fyra till sex cykler.

    Som mest ligger den genererade implementationen alltså en faktor fyra, men mer troligt en faktor två till tre efter den handbyggda implementationen. Och då har jag inte hjälpt generatorn på något sätt. Vad som hände när jag provkörde var att generatorn placerade såväl tillståndsminnet som pekarna i och j i det externa minnet. Hade jag sett till att dom var lokala för funktionen hade dom hamat i för acceleratorn register och minnen och då hade troligen fyra till sex cykler försvunnit från latenstiden.

    Storleksmässigt var den genererade konstruktionen större än den hade behövt vara. Bland annat genererades tre stycken adderare, när det skulle räcka med en adderare, men som jag skrev innan så gör väsentligen inte C2H några försök att hitta resurser att dela. Och skall man vara ärlig så är tre stycken åttabitars adderare inte speciellt mycket logik, speciellt inte i en FPGA där adderare implementeras väldigt effektivt.

    Implementationstiden låg på ungefär 15 minuter, och då räknar jag inte in tiden för att skriva C-koden och debugga den från syntaxfel, vilket tog ungefär lika lång tid. En någorlunda optimerad handbyggd implementation i Verilog eller SystemVerilog fixar inte jag på mycket under en dag, speciellt inte om man dessutom skall bygga testbänkar, skriva testfall och debugga.

    Sammanfattningsvis fick jag alltså fram en konstruktion som var fyra gånger långsammare och ungefär tre gånger större än en manuell konstruktion. Men potentiellt borde jag med några enkla ändringar i min C-kod kunnat komma fram till en konstruktion som varit ungefär två gånger långsammare än den manuella konstruktionen. Och totala utvecklingstiden hade troligen stannat på en timme istäkket för (minst) en dag. Inte illa.

    Verifiering är en viktig del i all utveckling av hårdvara. I fallet med C2H får man lita på att verktyget genererar rätt. Å andra sidan är det enkelt att samköra programvaruversionen och hårdvaruversionen av funktionen och jämföra resultatet. Använder du din funktion på ett sätt som täcker in hela funktionsymden och får samma resultat från båda versionerna bör du kunna lita på att C2H gjort rätt.

    En viktig poäng med verktyg som C2H är att du kan vänta med att bestämma vad du skall accelerera i hårdvara. Metodiken bli nu att se till att den önskade funktionaliteten fungerar korrekt. Sedan kör du profilering och får reda på var du faktiskt har prestandaproblem. Du genererar då acceleratorer för dessa och kör om profileringen. Eftersom manuell utveckling tar lång tid sker beslut om vad som skall accelereras långt innan det går att göra profilering. Och som många andra har upptäckt är det svårt att i förväg gissa var flaskhalsarna i ett system verkligen finns. Vid manuell utveckling riskerar du alltså att accelerera fel funktion.

    C2H är nu inte ensam på marknaden, utan det finns flera andra produkter för hårdvarusyntes av C-kod, exempelvis:

    1. Celoxica. Använder en variant på C kallad Handel-C som har språkmässigt stöd för att beskriva parallella beteenden och synkroniseringar. Verkar fungera bra, men ställer större krav på dig som konstruktör.

    2. Mentor Graphics Catapult-C. Att döma av pressreleaser har både Ericsson och Nokia använt detta verktyg för att bygga hårdvara som sitter i deras mobilplattformar. Detta tyder på att Catapult-C kan leverera bra resultat (I en ASIC för mobiltelefoner finns det inte kostnadsmässiga möjligheter att slösa med resurser). Dock har jag förstått att det krävs ordentliga styrfiler, ibland lika stora som C-koden för att få önskat resultat från Catapult-C.

    3. Mitrionics. Lundaföretaget har utvecklat egna verktyg för att generera hårdvara till sina FPGA-baserade acceleratorkort. Konceptet påminner mycket om C2H, men riktar sig mot applikationsacceleration av tekniska beräkningar som körs på en server eller till och med en superdator.

    Jag tror att C2H är rätt väg att gå. Tack vare de faktorer jag tidigare räknat upp tror jag att utveckling av hårdvarublock för FPGA och ASIC kommer att automatiseras. Detta, tillsammans med ökad outsourcing av rena konstruktionsjobb exempelvis till Kina eller Indien, innebär att marknaden för denna typ av jobb kommer att marginaliseras. Min bedömning är att det nog inte kommer att finnas många jobb för blockkonstruktion för ASIC och FPGA i Sverige om tio år.

    Ja det kommer alltid att finnas applikationer som av olika skäl kommer att kräva (och har råd med) manuell konstruktion, men det kommer att vara en krympande marknad. Ja, till viss del tycker jag att detta är en tråkig utveckling – Jag jobbar med FPGA- och ASIC-kontruktion och tycker fortfarande att det är spännande att arbeta fram en bra arkitektur och snygg implementationer som möter applikationskraven.

    Men det går inte att vare sig blunda för eller motarbeta utvecklingen. Istället måste vi som konstruktörer inse att det är dags att lyfta oss i håret. Vi skall inte bara trycka på knappen till C2H, men även skriva koden och den kravspecifikation som är indata till hur koden ser ut och knapptryckandet utförs.

    Jag hoppas få möjlighet att testa C2H ordentligt senare i höst, och då köra igenom flera olika kryptografiska primitiver. Det vore intressant att se hur bra det går att få utan att lägga ett stort antal timmar på att hjälpa verktyget.

    Är du nyfiken på C2H rekommenderar jag att du tittar närmare på Alteras webbsida för C2H.

    No related posts.

    Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

2 comments

  1. Kristina Kristoffersson says:

    Hej!

    Imponerande. Tänk om den hade varit på Englska så hade jag kunnat visa upp det för Altera

    Kristina

  2. Joachim says:

    Det skulle ju iofs gå att ordna. 😉

Leave a Reply

You must be logged in to post a comment.