allokering

Projektet "resursteori för mikroprocessor" ger en bild av hur beräkningstiden beror av ett antal parametrar. I stort sett kan man sammanfatta den som:

  • varje beräkning är en nod, som relaterar till andra beräkningar. En riktad graf uppstår. För denna grafen placeras beräkningar på processorer och vertex över kommunikationslänkar.
  • Latenstiden för ett problem är ungefär lika med längsta totala tiden från roten till något löv.
  • För en länk mostvarar latenstiden tiden för kommunikation. Normalt är latenstiden för beräkningar försumbar i förhållande till kommunikationstiden.
  • Ordningen på beräkningar har knappast någon betydelse.

Bästa allokeringsmekanismen är den som ser till att tiden för beräkna från löv till rot är mindre än ett visst värde för alla grenar och att detta är så lågt som möjligt.

Fördröjningstiden för en länk beror av att länken är högt belastad. Det gäller därför att fördela lasten på länkarna.

Placeringen kan i stort sett liknas med att placera komponenter och göra ledningsdragning kortaste vägen på mönsterkort. Detta problem har ingen bästa lösning ty det NP-komplett. Däremot finns det goda lösningar.

Ovanstående problem gäller för en uppsättning indata så att de ger exakt en graf med visst innehåll. Vid andra indata så ändras grafen. I vissa fall som i signalbehandlingsproblem har grafen samma struktur men olika innehåll och som vid kompilering har grafen helt annan struktur och innehåll.

Allokeringen måste därför göras sådan att alternativa placeringar för de ändrade delgraferna även de ger upphov till kort latenstid.

Förmodligen är en randombaserad placering av delgrafer lämplig.

Placering kan göras vid ladddning av datorn eller run-time. För att utröna hur det senare skall kunna göras så måste en kostnadsfunktion användas.

  • Det är mycket sannolikt att de mätare som finns för dessa ger värden med mycket brus. Frågan är då hur brus påverkar placeringen.
  • Då omtimeringen sker run-time, så mäts ju på redan utförda delar av en graf. Hur påverkar det lämplig allokering för den framtida beräkningen?

Olika optimeringsmekanismer studeras. Främst studeras simulated annealing.

english

nästa >