resursteori

Traditionell syntes av processorsystem har gått från singelprocessorer till multiprocessorer. Egenskaperna har ärvts. Mekanismen bakom exekvering har varit mycket enkel och baserat sig på Turingmaskinen. Multiprocessorernas mekanism har baserat sig på olika arkitekturer såsom gemensamt minne eller meddelandeöverföringar. Inga egentliga teorier har satts upp för resursanvändningen, ty de inger en omfattande komplexitet. I stället har många experiment utförts.

Det har arbetats med modeller för parallell exekvering. Eager har en teori för kommunicerande processer där grafens storlek är konstant. Man har även visat att process allokeringen är viktig och att den inte kan vara fix.

Denna rapport skall presentera

  • att det under vissa förutsättningar är möjligt att exekvera godtyckliga program på generella godtyckligt små/stora multiprocessorer. Processorena behöver inte vara anpassade för programmen och omvänt
  • en modell där latenstiden och använd minnesvolym kan beräknas för ett generellt exekverande program. Modellen använder tre uppsättningar av parametrar, som beskriver programmet, multiprocessorarkitekturen och dess hastighet.
  • med modellen kan multiprocessorer optimeras. Det kan bl a påvisas att granulariten för processorer i vissa fall är avgörande för prestanda.

I denna skrift skall en generell teori för exekvering presenteras. Den baserar sig egentligen enbart på de absolut grundläggande exekveringsegenskaperna lagring, transport och beräkning. Teorin utgår ifrån att en mängd sådana resurser används och är därför väsenskilt från de traditionella sekvensiella mekanismerna.

Teorin är generell och kan användas för flertalet olika semantiker såsom imperativa och deklarativa samt sådana med indeterminism. Av den anledningen kan teorin användas för konventionella multiprocessorer och nya.

I teorin finns ett antal allokerings- (eller mappnings-) funktioner. Dessa är specifika för olika arkitekturer. I denna skrift har mycket generella sådana använts. Dessa baserar sig på slumpvis allokering. Mer specifika algoritmerna kan införas och då kan de slumpvisa användas som referens.

Teorin för imperativ semantik är rakfram, men kan i de minsta detaljerna vara svår att implementera. För att lösa detta kan implementeringen basera sig på beräkningsenheter, som är större än de minsta uttrycken. Granulariteten växer då och motsvarar då ungefär objekt i en objektorienterad semantik. För deklarativ semantik kan även de minsta detaljerna analyseras.

Teorin ställer upp ett antal matematiska uttryck för att modellera exekveringen. Modellen presenterar beräkningsfrekvens (motsvarar hastighet), belastning på processorer och länkar, samt minnesvolymer. Med hjälp av dessa kan arkitekturer optimeras då implementeringar av enheter är kända. I en efterföljande skrift kommer en sådan optimering att presenteras.

Teorin utgör basen för datorkonceptet rp8601 i sin ursprungliga utformning.

english

rapport

nästa >