BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260522T150122Z
LOCATION:D172
DTSTART;TZID=America/Chicago:20181112T105500
DTEND;TZID=America/Chicago:20181112T112000
UID:submissions.supercomputing.org_SC18_sess168_ws_ia101@linklings.com
SUMMARY:A Fast and Simple Approach to Merge and Merge Sorting Using Wide V
 ector Instructions
DESCRIPTION:Alex Watkins and Oded Green (Georgia Institute of Technology)\
 n\nMerging and sorting algorithms are the backbone of many modern computer
  applications. As such, efficient implementations are desired. Recent arch
 itectural advancements in CPUs (Central Processing Units), such as wider a
 nd more powerful vector instructions, allow for algorithmic improvements. 
 This paper presents a new approach to merge sort using vector instructions
 . Traditional approaches to vectorized sorting typically utilize a bitonic
  sorting network (Batcher's Algorithm) which adds significant overhead. Ou
 r approach eliminates the overhead from this approach. We start with a bra
 nch-avoiding merge algorithm and then use the Merge Path algorithm to spli
 t up merging between the different SIMD lanes. Testing demonstrates that t
 he algorithm not only surpasses the SIMD based bitonic counterpart, but th
 at it is over 2.94X faster than a traditional merge, merging over 300M key
 s per second in one thread and over 16B keys per second in parallel.  Our 
 new sort reaches is over 5X faster than quicksort and 2X faster than Intel
 's IPP library sort, sorting over 5.3M keys per second for a single proces
 sor and in parallel over 500M keys per second and a speedup of over 2X fro
 m a traditional merge sort.\n\nTag: Architectures, Data Analytics, Graph A
 lgorithms\n\nRegistration Category: Workshop Reg Pass\n\nSession Chairs: V
 ito Giovanni Castellana (Pacific Northwest National Laboratory (PNNL)), Jo
 hn Feo (Pacific Northwest National Laboratory (PNNL)), and Antonino Tumeo 
 (Pacific Northwest National Laboratory (PNNL))\n\n
END:VEVENT
END:VCALENDAR