Abstract-I detta dokument arbetar vi på parallellisering av den inneboende serie Dijkstra algoritm på moderna multicore plattformar. Dijkstra algoritm är en girig algoritm som beräknar Single Source Shortest Paths för grafer med icke-negativa kanter och är baserad på iterativ extraktion av noder från en prioriterad kö. Denna egenskap begränsar den explicita parallellismen av algoritmen och varje försök att utnyttja den återstående parallellismen resulterar i betydande nedgångar på grund av synkronisering overheads. För att hantera dessa problem använder vi konceptet Helper Threads (HT) för att extrahera parallellism på ett icke-traditionellt mode och Transactional Memory (TM) för att effektivt orkestrera de samtidiga trådarnas åtkomst till delade datastrukturer. Resultaten visar att det föreslagna genomförandet kan leda till högre prestanda (upp till 1,84 för 14 trådar), vilket tyder på att de två paradigmerna skulle kunna kombineras på ett effektivt sätt.
I REF-hjälptrådning ingår i Dijkstras algoritm och i kombination med Transaktionsminne för att påskynda parallell körning.
Employing Transactional Memory and Helper Threads to Speedup Dijkstra's Algorithm
{'venue': '2009 International Conference on Parallel Processing', 'journal': '2009 International Conference on Parallel Processing', 'mag_field_of_study': ['Computer Science']}