{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/90824"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/90824","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel merge for many-core architectures","abstract":"This thesis proposes a novel GPU implementation for merging two sorted arrays. We consider the problem of merging two arrays A and B into a single array C. Each element in the arrays has a key. An ordering relation denoted by is defined on the keys. Array A and array B have m and n elements, respectively, where m and n do not have to be equal. Both array A and array B are sorted based on the ordering relation. The task is to produce the output array C of size m + n. Array C consists of all the input elements from array A and array B, and is sorted by the ordering relation. We applied several GPU-specific optimizations to a parallel merge algorithm. The optimizations include coordinating the memory access pattern, making full use of the shared memory and reducing the thread divergence. Our implementation achieves up to 10x and 40x speedup on Titan-Z and GTX 980 GPU respectively compared to thrust merge implementation.","abstract_html":"This thesis proposes a novel GPU implementation for merging two sorted arrays. We consider the problem of merging two arrays A and B into a single array C. Each element in the arrays has a key. An ordering relation denoted by is defined on the keys. Array A and array B have m and n elements, respectively, where m and n do not have to be equal. Both array A and array B are sorted based on the ordering relation. The task is to produce the output array C of size m + n. Array C consists of all the input elements from array A and array B, and is sorted by the ordering relation. We applied several GPU-specific optimizations to a parallel merge algorithm. The optimizations include coordinating the memory access pattern, making full use of the shared memory and reducing the thread divergence. Our implementation achieves up to 10x and 40x speedup on Titan-Z and GTX 980 GPU respectively compared to thrust merge implementation.","abstract_has_math":false,"creators":["Lv, Jie"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hwu, Wen-Mei W."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-07-07T20:28:00Z","date_published":"2016-07-07T20:28:00Z","updated_at":"2026-07-22T22:26:34Z","subjects":["Graphics processing unit (GPU)","Parallel Merge"],"languages":["en"],"rights":["Copyright 2016 Jie Lv"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/90824","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hwu, Wen-Mei W."]},{"key":"dc:creator","label":"Author","values":["Lv, Jie"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-07-07T20:28:00Z","2018-07-08T09:15:27Z","2016-04-27","2016-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graphics processing unit (GPU)","Parallel Merge"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Jie Lv"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/90824"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis proposes a novel GPU implementation for merging two sorted arrays. We consider the problem of merging two arrays A and B into a single array C. Each element in the arrays has a key. An ordering relation denoted by is defined on the keys. Array A and array B have m and n elements, respectively, where m and n do not have to be equal. Both array A and array B are sorted based on the ordering relation. The task is to produce the output array C of size m + n. Array C consists of all the input elements from array A and array B, and is sorted by the ordering relation. We applied several GPU-specific optimizations to a parallel merge algorithm. The optimizations include coordinating the memory access pattern, making full use of the shared memory and reducing the thread divergence. Our implementation achieves up to 10x and 40x speedup on Titan-Z and GTX 980 GPU respectively compared to thrust merge implementation.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2018-05-01","The student, Jie Lv, accepted the attached license on 2016-04-25 at 14:33.","The student, Jie Lv, submitted this Thesis for approval on 2016-04-25 at 14:46.","This Thesis was approved for publication on 2016-04-27 at 15:02.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9480 on 2016-07-07 at 13:50:49","Made available in DSpace on 2016-07-07T20:28:00Z (GMT). No. of bitstreams: 2 LV-THESIS-2016.pdf: 1402811 bytes, checksum: a076d56310ec6de319d32e07c43e9729 (MD5) LICENSE.txt: 4203 bytes, checksum: 9d3c401b7dae8f095d017842fdb6e601 (MD5) Previous issue date: 2016-04-27","Embargo set by: Seth Robbins for item 93176 Lift date: 2018-07-07T20:28:14Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 93176 Lift date: 2018-07-07T20:35:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 93176 on 2018-07-08T09:15:27Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Parallel merge for many-core architectures"]}]}],"canonical_facts":{"dc:contributor":["Hwu, Wen-Mei W."],"dc:creator":["Lv, Jie"],"dc:date":["2016-07-07T20:28:00Z","2018-07-08T09:15:27Z","2016-04-27","2016-05"],"dc:description":["This thesis proposes a novel GPU implementation for merging two sorted arrays. We consider the problem of merging two arrays A and B into a single array C. Each element in the arrays has a key. An ordering relation denoted by is defined on the keys. Array A and array B have m and n elements, respectively, where m and n do not have to be equal. Both array A and array B are sorted based on the ordering relation. The task is to produce the output array C of size m + n. Array C consists of all the input elements from array A and array B, and is sorted by the ordering relation. We applied several GPU-specific optimizations to a parallel merge algorithm. The optimizations include coordinating the memory access pattern, making full use of the shared memory and reducing the thread divergence. Our implementation achieves up to 10x and 40x speedup on Titan-Z and GTX 980 GPU respectively compared to thrust merge implementation.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2018-05-01","The student, Jie Lv, accepted the attached license on 2016-04-25 at 14:33.","The student, Jie Lv, submitted this Thesis for approval on 2016-04-25 at 14:46.","This Thesis was approved for publication on 2016-04-27 at 15:02.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9480 on 2016-07-07 at 13:50:49","Made available in DSpace on 2016-07-07T20:28:00Z (GMT). No. of bitstreams: 2 LV-THESIS-2016.pdf: 1402811 bytes, checksum: a076d56310ec6de319d32e07c43e9729 (MD5) LICENSE.txt: 4203 bytes, checksum: 9d3c401b7dae8f095d017842fdb6e601 (MD5) Previous issue date: 2016-04-27","Embargo set by: Seth Robbins for item 93176 Lift date: 2018-07-07T20:28:14Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 93176 Lift date: 2018-07-07T20:35:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 93176 on 2018-07-08T09:15:27Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/90824"],"dc:language":["en"],"dc:rights":["Copyright 2016 Jie Lv"],"dc:subject":["Graphics processing unit (GPU)","Parallel Merge"],"dc:title":["Parallel merge for many-core architectures"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:34Z"}