Högpresterande samtidiga prioriterade köer är viktiga för tillämpningar såsom schemaläggning och diskret händelsesimulering. Tyvärr, även de bäst presterande implementationer inte skala förbi ett antal trådar i de enskilda siffrorna. Detta beror på den sekventiella flaskhalsen att komma åt elementen i spetsen av kön för att utföra en Ta bortMin operation. I denna artikel presenterar vi SprayList, en skalbar prioriterad kö med avslappnad beställning semantik. Med utgångspunkt från en icke-blockerande SkipList är den viktigaste innovationen bakom vår design att Ta bortMin-verksamheten undviker en sekventiell flaskhals genom att "spraya" sig själva på SkipList-listans huvud på ett samordnat sätt. Besprutningen genomförs med hjälp av en noggrant utformad slumpmässig gång, så att Ta bortMin returnerar ett element bland de första O(p log 3 p) i listan, med hög sannolikhet, där p är antalet trådar. Vi bevisar att körtiden för en Ta bortMin operation är O(log 3 p), med hög sannolikhet, oberoende av storleken på listan. Våra experiment visar att de avslappnade semantikerna gör det möjligt för datastrukturen att skala för höga trådvärden, jämförbara med en klassisk oordnad SkipList. Dessutom konstaterar vi att för relativt parallella arbetsbelastningar uppväger skalbarhetsvinsterna av avslappning avsevärt det ytterligare arbetet på grund av oordnad körning.
SprayList REF minskar innehållet för att ta bortMin genom att navigera inte till det globala minimum utan till ett element bland O p log 3 p minsta element och ta bort det.
The SprayList: a scalable relaxed priority queue
{'venue': 'PPoPP 2015', 'journal': None, 'mag_field_of_study': ['Computer Science']}