Parallellism för effektivare datorberäkningar
Inom många forskningsområden, som till exempel högenergifysik, biomedicin, meteorologi och geofysik, utförs operationer som kräver omfattande beräkningar. Här behövs datorsystem med hög beräkningskapacitet. För att uppnå detta används parallella datastrukturer. I ett doktorsarbete på Chalmers har Phuong Ha utvecklat parallella datastrukturer som anpassar sig till belastningen.
För att uppnå höga prestanda räcker det inte med att bara köra mer hårdvara parallellt utan hårdvaran måste också utnyttjas effektivt. Hur väl den parallella hårdvaran kan utnyttjas påverkas avsevärt av om processorerna/processerna kan synkroniseras utan att för mycket parallellism förloras.
För att synkronisera parallella processer används ofta delade/gemensamma datastrukturer. Strukturer som ökar parallellismen genom att tillåta att flera processer använder dem samtidigt kallas parallella datastrukturer. I doktorsarbetet har effektiva parallella datastrukturer och algoritmer för synkronisering i högpresterande parallella datorsystem utvecklats.
Enkla parallella datastrukturer presterar i allmänhet bra i situationer när belastningen är låg, det vill säga när antalet samtidiga operationer är lågt, medan de däremot ofta fungerar sämre när belastningen är hög. Sofistikerade datastrukturer, å andra sidan, har ofta bra prestanda vid hög belastning, men kan vara onödigt resurskrävande när belastningen är låg. För att uppnå hög effektivitet bör parallella datastrukturer kunna anpassa sitt beteende när belastningen i systemet varierar.
– För att möta det behovet har vi utvecklat självjusterande parallella datastrukturer som automatiskt anpassar sin storlek och sina algoritmer efter belastningen i systemet. Det är en ganska svår uppgift eftersom man i de flesta multiprogrammiljöer inte har någon information om hur belastningen kommer att ändra sig i framtiden. För att hantera den här osäkerheten har vi utvecklat icke-blockerande synkroniseringsmetoder och tekniker för online-algoritmer för självjusterande parallella datastrukturer. Vi har också utvecklat en ny optimal online-algoritm som innebär att vi kan bestämma optimala lösningar för fler praktiska problem inom området parallella datastrukturer än som tidigare varit möjligt, säger Phuong Ha.
Avhandlingen “Reactive Concurrent Data Structures and Algorithms for Synchronization” försvaras vid en offentlig disputation på Chalmers den 2 juni 2006 kl. 10.00 i sal EA, Rännvägen 6B, Göteborg.
Kontaktinformation
Mer information:
Phuong Ha, Institutionen för data- och informationsteknik, Chalmers, Göteborg.
Tel: 031-772 1024
E-post: phuong@cs.chalmers.se
Professor Philippas Tsigas, Institutionen för data- och informationsteknik, Chalmers, Göteborg.
Tel: 031-772 5409
E-post: tsigas@cs.chalmers.se