Vi presenterar en deterministisk sorteringsalgoritm, SPMS (Sample, Partition, and Merge Sort), som blandar partitioneringen av ett provslag med sammanslagning. Sekventiellt, det sorterar n element i O (n log n) tid cache-oblivious med ett optimalt antal cache missar. Den parallella komplexiteten (eller den kritiska vägens längd) hos algoritmen är O(log n · log n), vilket förbättrar på tidigare gränser för optimal cache oöverträffad sortering. Algoritmen har också låga kostnader för falsk delning. När schemaläggningen sker av en arbetsstjälk schemaläggare i en multicore datormiljö med ett globalt delat minne och p-kärnor, var och en med en cache av storlek M organiserad i block av storlek B, kostnaderna för ytterligare cache missar och falska delning missar på grund av detta parallella utförande begränsas av kostnaden för O(S · M/B) och O(S · B) cache missar respektive, där S är antalet stölder som utförs under utförandet. Slutligen är SPMS resurs omedveten om att beroendet av maskinparametrar endast förekommer i analysen av dess prestanda och inte inom själva algoritmen.
Cole och Ramachandran REF presenterade nyligen en ny optimal kombinationssortalgoritm (SPMS) för resursen oöverträffad multicoremodell.
Resource Oblivious Sorting on Multicores
{'venue': 'ACM Transactions on Parallel Computing (TOPC), Vol. 3, No. 4, Article 23, 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}