{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23746"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23746","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Interconnection networks and data prefetching for large-scale multiprocessors: Design and performance","abstract":"Increasing computing power demands higher memory performance than ever before, and memory access becomes a more serious bottleneck in high-performance computer systems. Therefore, reducing memory access latency or hiding the latency is crucial to achieving high performance. In shared memory multiprocessor systems, where memory access must traverse interconnection networks, the system performance and costs are directly affected by interconnection networks. Latency hiding techniques such as data prefetching affect interconnection network and memory performance by demanding more bandwidth. This dissertation studies interconnection networks and data prefetching.","abstract_html":"Increasing computing power demands higher memory performance than ever before, and memory access becomes a more serious bottleneck in high-performance computer systems. Therefore, reducing memory access latency or hiding the latency is crucial to achieving high performance. In shared memory multiprocessor systems, where memory access must traverse interconnection networks, the system performance and costs are directly affected by interconnection networks. Latency hiding techniques such as data prefetching affect interconnection network and memory performance by demanding more bandwidth. This dissertation studies interconnection networks and data prefetching.","abstract_has_math":false,"creators":["Kim, Sun-il"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Veidenbaum, Alexander V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:25:32Z","date_published":"2011-05-07T14:25:32Z","updated_at":"2026-07-22T22:25:22Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Kim, Sunil"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624392","(UMI)AAI9624392"],"render_values":[{"text":"AAI9624392","href":null,"code":true},{"text":"(UMI)AAI9624392","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23746","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Veidenbaum, Alexander V."]},{"key":"dc:creator","label":"Author","values":["Kim, Sun-il"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:25:32Z","10000-01-01","1995"]},{"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":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Kim, Sunil"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624392","(UMI)AAI9624392","http://hdl.handle.net/2142/23746"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Increasing computing power demands higher memory performance than ever before, and memory access becomes a more serious bottleneck in high-performance computer systems. Therefore, reducing memory access latency or hiding the latency is crucial to achieving high performance. In shared memory multiprocessor systems, where memory access must traverse interconnection networks, the system performance and costs are directly affected by interconnection networks. Latency hiding techniques such as data prefetching affect interconnection network and memory performance by demanding more bandwidth. This dissertation studies interconnection networks and data prefetching.","We establish a theoretical framework for routing in shuffle-exchange networks and develop an algorithm for shortest path routing in single stage shuffle-exchange networks. Single stage shuffle-exchange networks are attractive because of their relatively low cost and shorter average internode distance as compared to multistage shuffle-exchange networks. The theoretical framework and routing algorithm allow network size to be any multiple of the switch size. We evaluate the effect of shortest path routing on memory system performance.","Three different network topologies are evaluated by varying system size, switch size and channel width under various design constraints. These networks are multistage and single stage shuffle-exchange networks and multidimensional torus networks. By employing detailed trace-driven simulations of an entire system, we conduct an extensive comparative study of these interconnection networks in terms of performance and cost. In general, multistage shuffle-exchange networks are the best network topology when cost is not the main limiting factor. Otherwise, single stage shuffle-exchange networks are the best network topology when cost is a main limiting factor. Multidimensional torus networks were seriously limited by their long average internode distance.","We investigate the effect of data prefetching on interconnection networks and vice versa. When data prefetching is effective, the performance difference caused by different networks tends to be reduced. The high memory bandwidth demand of prefetching requires that the number of outstanding requests be controlled to effectively utilize network and memory bandwidth. Finally, we develop and evaluate a prefetching scheme that enables stride-directed prefetching at the second-level of a memory hierarchy and outside a processor chip. Using the prefetching scheme, we compare three different second-level memory organizations: traditional caches, prefetching without a cache, and prefetching with a small cache. Prefetching with a small cache shows strong potential to be an efficient second-level memory organization.","Made available in DSpace on 2011-05-07T14:25:32Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624392.pdf: 6717523 bytes, checksum: be75b29a450079812442cd483c618cee (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:06:34Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:58-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Interconnection networks and data prefetching for large-scale multiprocessors: Design and performance"]}]}],"canonical_facts":{"dc:contributor":["Veidenbaum, Alexander V."],"dc:creator":["Kim, Sun-il"],"dc:date":["2011-05-07T14:25:32Z","10000-01-01","1995"],"dc:description":["Increasing computing power demands higher memory performance than ever before, and memory access becomes a more serious bottleneck in high-performance computer systems. Therefore, reducing memory access latency or hiding the latency is crucial to achieving high performance. In shared memory multiprocessor systems, where memory access must traverse interconnection networks, the system performance and costs are directly affected by interconnection networks. Latency hiding techniques such as data prefetching affect interconnection network and memory performance by demanding more bandwidth. This dissertation studies interconnection networks and data prefetching.","We establish a theoretical framework for routing in shuffle-exchange networks and develop an algorithm for shortest path routing in single stage shuffle-exchange networks. Single stage shuffle-exchange networks are attractive because of their relatively low cost and shorter average internode distance as compared to multistage shuffle-exchange networks. The theoretical framework and routing algorithm allow network size to be any multiple of the switch size. We evaluate the effect of shortest path routing on memory system performance.","Three different network topologies are evaluated by varying system size, switch size and channel width under various design constraints. These networks are multistage and single stage shuffle-exchange networks and multidimensional torus networks. By employing detailed trace-driven simulations of an entire system, we conduct an extensive comparative study of these interconnection networks in terms of performance and cost. In general, multistage shuffle-exchange networks are the best network topology when cost is not the main limiting factor. Otherwise, single stage shuffle-exchange networks are the best network topology when cost is a main limiting factor. Multidimensional torus networks were seriously limited by their long average internode distance.","We investigate the effect of data prefetching on interconnection networks and vice versa. When data prefetching is effective, the performance difference caused by different networks tends to be reduced. The high memory bandwidth demand of prefetching requires that the number of outstanding requests be controlled to effectively utilize network and memory bandwidth. Finally, we develop and evaluate a prefetching scheme that enables stride-directed prefetching at the second-level of a memory hierarchy and outside a processor chip. Using the prefetching scheme, we compare three different second-level memory organizations: traditional caches, prefetching without a cache, and prefetching with a small cache. Prefetching with a small cache shows strong potential to be an efficient second-level memory organization.","Made available in DSpace on 2011-05-07T14:25:32Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624392.pdf: 6717523 bytes, checksum: be75b29a450079812442cd483c618cee (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:06:34Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:58-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9624392","(UMI)AAI9624392","http://hdl.handle.net/2142/23746"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Kim, Sunil"],"dc:subject":["Computer Science"],"dc:title":["Interconnection networks and data prefetching for large-scale multiprocessors: Design and performance"],"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:25:22Z"}