4 multithreaded architectures and the sort benchmark

Multithreaded Architectures and The Sort BenchmarkPhil GarciaHank KorthDept. of Computer Science and EngineeringLehigh UniversityAbout our Sort Benchmark• Based on the benchmark proposed in Ameasure of transaction processing power(Anonymous et al).• Sorts 100 byte records containing 10 byte keys.• Modified to run in main-memory.• Modified to sort 250MB of records (instead of 100MB).Results• 2-way SMT can result in speedups of over 60%.• SMT can tolerate cache misses.• Gains increase as the processor/memory gap widens.• The order of threads’ actions significantly affects speed.• Merge sort can be more efficient thanselection trees.Test Platform• Xeon dual 3.0GHz.Debian GNU/Linux– 2-way SMT Kernel 2.6.6– 512KB L2 cachegcc v3.3Optimized for test – 1MB L3 cache.architecture.– 2GB of RAM– 533MHz Bus• Pentium 4 2.8GHz– 2-way SMT– 2GB of RAM– 1MB L2 cache– 800 MHz BusAlgorithm DesignBased on Alphasort (Nyberg et al.)For Each SetExtract (key, pointer) pairsQuicksort on keysMergesort 2 sets at a time until doneFinal merge materializes output.209,286104,04851,73025,71812,7826,3563,1641,56878439219698Single Threaded Breakdown141210Total8Mergesort6Quicksort420Set Size (Bytes)Xeon single processorBillionsMergesort vs.Selection Tree• Selection tree requires large memory footprint.– Results in many cache misses per traversal.• Mergesort has a smaller overall runtime (for larger sorts)• Mergesort is ...