{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72903"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72903","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization by runtime specialization for sparse matrix-vector multiplication","abstract":"Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this thesis we explore the potential for obtaining speed-ups for sparse matrix-dense vector multipli- cation using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving run-time specialization with parallelization, comparing them to methods that do not (including Intel’s MKL library). For this work, our focus is the evaluation of the parallel speed-ups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments run on four different machines with 88 matrices from the Matrix Market and Florida collections, among others. In 348 of those 352 cases, the specialized code runs faster than any version without specialization. In the worst case, the specialized code is 7 percent slower than the Intel’s MKL library. If we only use specialization, the average speedup with respect to Intel’s MKL library ranges from 1.416x to 1.470x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.","abstract_html":"Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this thesis we explore the potential for obtaining speed-ups for sparse matrix-dense vector multipli- cation using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving run-time specialization with parallelization, comparing them to methods that do not (including Intel’s MKL library). For this work, our focus is the evaluation of the parallel speed-ups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments run on four different machines with 88 matrices from the Matrix Market and Florida collections, among others. In 348 of those 352 cases, the specialized code runs faster than any version without specialization. In the worst case, the specialized code is 7 percent slower than the Intel’s MKL library. If we only use specialization, the average speedup with respect to Intel’s MKL library ranges from 1.416x to 1.470x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.","abstract_has_math":false,"creators":["Xu, Danqing"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Garzaran, Maria J."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-21T19:49:20Z","date_published":"2015-01-21T19:49:20Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Computer Science","Parallel Programming","Program Optimization","Code generation","Runtime Specialization","Programming Languages"],"languages":["en"],"rights":["Copyright 2014 Danqing Xu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/72903","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garzaran, Maria J."]},{"key":"dc:creator","label":"Author","values":["Xu, Danqing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-21T19:49:20Z","2014-12","2015-01-21"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["Computer Science","Parallel Programming","Program Optimization","Code generation","Runtime Specialization","Programming Languages"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Danqing Xu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72903"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this thesis we explore the potential for obtaining speed-ups for sparse matrix-dense vector multipli- cation using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving run-time specialization with parallelization, comparing them to methods that do not (including Intel’s MKL library). For this work, our focus is the evaluation of the parallel speed-ups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments run on four different machines with 88 matrices from the Matrix Market and Florida collections, among others. In 348 of those 352 cases, the specialized code runs faster than any version without specialization. In the worst case, the specialized code is 7 percent slower than the Intel’s MKL library. If we only use specialization, the average speedup with respect to Intel’s MKL library ranges from 1.416x to 1.470x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-11-05T15:26:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Xu_Danqing.pdf: 835944 bytes, checksum: 57b887c6270944218c49288fc501c222 (MD5)","Made available in DSpace on 2015-01-21T19:49:20Z (GMT). No. of bitstreams: 1 Danqing_Xu.pdf: 835944 bytes, checksum: 57b887c6270944218c49288fc501c222 (MD5)"]},{"key":"dc:title","label":"Title","values":["Optimization by runtime specialization for sparse matrix-vector multiplication"]}]}],"canonical_facts":{"dc:contributor":["Garzaran, Maria J."],"dc:creator":["Xu, Danqing"],"dc:date":["2015-01-21T19:49:20Z","2014-12","2015-01-21"],"dc:description":["Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this thesis we explore the potential for obtaining speed-ups for sparse matrix-dense vector multipli- cation using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving run-time specialization with parallelization, comparing them to methods that do not (including Intel’s MKL library). For this work, our focus is the evaluation of the parallel speed-ups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments run on four different machines with 88 matrices from the Matrix Market and Florida collections, among others. In 348 of those 352 cases, the specialized code runs faster than any version without specialization. In the worst case, the specialized code is 7 percent slower than the Intel’s MKL library. If we only use specialization, the average speedup with respect to Intel’s MKL library ranges from 1.416x to 1.470x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-11-05T15:26:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Xu_Danqing.pdf: 835944 bytes, checksum: 57b887c6270944218c49288fc501c222 (MD5)","Made available in DSpace on 2015-01-21T19:49:20Z (GMT). No. of bitstreams: 1 Danqing_Xu.pdf: 835944 bytes, checksum: 57b887c6270944218c49288fc501c222 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/72903"],"dc:language":["en"],"dc:rights":["Copyright 2014 Danqing Xu"],"dc:subject":["Computer Science","Parallel Programming","Program Optimization","Code generation","Runtime Specialization","Programming Languages"],"dc:title":["Optimization by runtime specialization for sparse matrix-vector multiplication"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}