{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88981"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88981","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Communication avoiding parallel algorithms for amorphous problems","abstract":"Parallelizing large sized problem in parallel systems has always been a challenge for programmer. This difficulty is caused by the complexity of the existing systems as well as the target problems. This is becoming a greater issue as the data sizes are constantly growing and as a result, larger parallel systems are required. Graph algorithms, machine learning problems and bio-informatics methods are among the many ever-growing problems. These group of problems are amorphous, meaning that memory accesses are unpredictable and the application usually has a poor locality. Therefore, synchronizations in these problems are specially costly since all-to-all communications are required and delivering an efficient parallel algorithm becomes more challenging. Another difficulty with these problems is that the amount of parallelism in them is limited which naturally makes them hard to parallelize. This is due to complicated data-dependences among the data elements in the algorithm. Writing parallel algorithms for these problems, on the other hand, are specially difficult since an amorphous problem can be expressed in several dramatically different ways. This is because of complex data dependences which are statically unknown and therefore, many unique parallel approaches exist for a single problem. Consequently, programming each single approach requires starting from scratch which is time consuming. This thesis introduces several ways to avoid costly communications in amorphous problems by compromising from the computation. This means that we can increase the total amount of work done by the processors to avoid synchronizations in an algorithm. This is specially effective in large clusters since there is a massive computing power with very costly communications. These approaches, clearly, have a trade off between computation and communication and in this thesis, we study these trade offs as well. Also, we propose a new language to express the proposed algorithms to overcome the programming difficulty of the problems by providing tunable parameters for performance.","abstract_html":"Parallelizing large sized problem in parallel systems has always been a challenge for programmer. This difficulty is caused by the complexity of the existing systems as well as the target problems. This is becoming a greater issue as the data sizes are constantly growing and as a result, larger parallel systems are required. Graph algorithms, machine learning problems and bio-informatics methods are among the many ever-growing problems. These group of problems are amorphous, meaning that memory accesses are unpredictable and the application usually has a poor locality. Therefore, synchronizations in these problems are specially costly since all-to-all communications are required and delivering an efficient parallel algorithm becomes more challenging. Another difficulty with these problems is that the amount of parallelism in them is limited which naturally makes them hard to parallelize. This is due to complicated data-dependences among the data elements in the algorithm. Writing parallel algorithms for these problems, on the other hand, are specially difficult since an amorphous problem can be expressed in several dramatically different ways. This is because of complex data dependences which are statically unknown and therefore, many unique parallel approaches exist for a single problem. Consequently, programming each single approach requires starting from scratch which is time consuming. This thesis introduces several ways to avoid costly communications in amorphous problems by compromising from the computation. This means that we can increase the total amount of work done by the processors to avoid synchronizations in an algorithm. This is specially effective in large clusters since there is a massive computing power with very costly communications. These approaches, clearly, have a trade off between computation and communication and in this thesis, we study these trade offs as well. Also, we propose a new language to express the proposed algorithms to overcome the programming difficulty of the problems by providing tunable parameters for performance.","abstract_has_math":false,"creators":["Maleki, Saeed"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Padua, David","Garzaran, Maria J.","Kale, Laxmikant","Pingali, Keshav","Musuvathi, Madanlal"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-03-02T19:33:34Z","date_published":"2016-03-02T19:33:34Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Amorphous","Symbolic","Parallel","Communication Avoiding","Linear Algebra","Tropical Semi-Ring","Single-Source Shortest Path","Dynamic Programming","Longest Common Subsequence","Smith-Waterman","Needleman-Wunsch","Viterbi Decoder","Parallel Notations"],"languages":["en"],"rights":["Copyright 2015 Saeed Maleki"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88981","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, David","Garzaran, Maria J.","Kale, Laxmikant","Pingali, Keshav","Musuvathi, Madanlal"]},{"key":"dc:creator","label":"Author","values":["Maleki, Saeed"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-03-02T19:33:34Z","2015-11-10","2015-12"]},{"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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Amorphous","Symbolic","Parallel","Communication Avoiding","Linear Algebra","Tropical Semi-Ring","Single-Source Shortest Path","Dynamic Programming","Longest Common Subsequence","Smith-Waterman","Needleman-Wunsch","Viterbi Decoder","Parallel Notations"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Saeed Maleki"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88981"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Parallelizing large sized problem in parallel systems has always been a challenge for programmer. This difficulty is caused by the complexity of the existing systems as well as the target problems. This is becoming a greater issue as the data sizes are constantly growing and as a result, larger parallel systems are required. Graph algorithms, machine learning problems and bio-informatics methods are among the many ever-growing problems. These group of problems are amorphous, meaning that memory accesses are unpredictable and the application usually has a poor locality. Therefore, synchronizations in these problems are specially costly since all-to-all communications are required and delivering an efficient parallel algorithm becomes more challenging. Another difficulty with these problems is that the amount of parallelism in them is limited which naturally makes them hard to parallelize. This is due to complicated data-dependences among the data elements in the algorithm. Writing parallel algorithms for these problems, on the other hand, are specially difficult since an amorphous problem can be expressed in several dramatically different ways. This is because of complex data dependences which are statically unknown and therefore, many unique parallel approaches exist for a single problem. Consequently, programming each single approach requires starting from scratch which is time consuming. This thesis introduces several ways to avoid costly communications in amorphous problems by compromising from the computation. This means that we can increase the total amount of work done by the processors to avoid synchronizations in an algorithm. This is specially effective in large clusters since there is a massive computing power with very costly communications. These approaches, clearly, have a trade off between computation and communication and in this thesis, we study these trade offs as well. Also, we propose a new language to express the proposed algorithms to overcome the programming difficulty of the problems by providing tunable parameters for performance.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Saeed Maleki, accepted the attached license on 2015-11-05 at 14:32.","The student, Saeed Maleki, submitted this Dissertation for approval on 2015-11-05 at 14:42.","This Dissertation was approved for publication on 2015-11-10 at 14:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8761 on 2016-03-02 at 12:49:56","Made available in DSpace on 2016-03-02T19:33:34Z (GMT). No. of bitstreams: 2 MALEKI-DISSERTATION-2015.pdf: 4576470 bytes, checksum: 209faeb55f524bc86520bf05b01b176c (MD5) LICENSE.txt: 4209 bytes, checksum: bc997039c51b62c08c83b9b68d014d08 (MD5) Previous issue date: 2015-11-10"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Communication avoiding parallel algorithms for amorphous problems"]}]}],"canonical_facts":{"dc:contributor":["Padua, David","Garzaran, Maria J.","Kale, Laxmikant","Pingali, Keshav","Musuvathi, Madanlal"],"dc:creator":["Maleki, Saeed"],"dc:date":["2016-03-02T19:33:34Z","2015-11-10","2015-12"],"dc:description":["Parallelizing large sized problem in parallel systems has always been a challenge for programmer. This difficulty is caused by the complexity of the existing systems as well as the target problems. This is becoming a greater issue as the data sizes are constantly growing and as a result, larger parallel systems are required. Graph algorithms, machine learning problems and bio-informatics methods are among the many ever-growing problems. These group of problems are amorphous, meaning that memory accesses are unpredictable and the application usually has a poor locality. Therefore, synchronizations in these problems are specially costly since all-to-all communications are required and delivering an efficient parallel algorithm becomes more challenging. Another difficulty with these problems is that the amount of parallelism in them is limited which naturally makes them hard to parallelize. This is due to complicated data-dependences among the data elements in the algorithm. Writing parallel algorithms for these problems, on the other hand, are specially difficult since an amorphous problem can be expressed in several dramatically different ways. This is because of complex data dependences which are statically unknown and therefore, many unique parallel approaches exist for a single problem. Consequently, programming each single approach requires starting from scratch which is time consuming. This thesis introduces several ways to avoid costly communications in amorphous problems by compromising from the computation. This means that we can increase the total amount of work done by the processors to avoid synchronizations in an algorithm. This is specially effective in large clusters since there is a massive computing power with very costly communications. These approaches, clearly, have a trade off between computation and communication and in this thesis, we study these trade offs as well. Also, we propose a new language to express the proposed algorithms to overcome the programming difficulty of the problems by providing tunable parameters for performance.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Saeed Maleki, accepted the attached license on 2015-11-05 at 14:32.","The student, Saeed Maleki, submitted this Dissertation for approval on 2015-11-05 at 14:42.","This Dissertation was approved for publication on 2015-11-10 at 14:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8761 on 2016-03-02 at 12:49:56","Made available in DSpace on 2016-03-02T19:33:34Z (GMT). No. of bitstreams: 2 MALEKI-DISSERTATION-2015.pdf: 4576470 bytes, checksum: 209faeb55f524bc86520bf05b01b176c (MD5) LICENSE.txt: 4209 bytes, checksum: bc997039c51b62c08c83b9b68d014d08 (MD5) Previous issue date: 2015-11-10"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88981"],"dc:language":["en"],"dc:rights":["Copyright 2015 Saeed Maleki"],"dc:subject":["Amorphous","Symbolic","Parallel","Communication Avoiding","Linear Algebra","Tropical Semi-Ring","Single-Source Shortest Path","Dynamic Programming","Longest Common Subsequence","Smith-Waterman","Needleman-Wunsch","Viterbi Decoder","Parallel Notations"],"dc:title":["Communication avoiding parallel algorithms for amorphous problems"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}