{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23307"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23307","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Performance analysis of multiprocessor interconnection networks using a burst-traffic model","abstract":"This thesis presents the development and use of a performance analysis methodology suitable for use in the evaluation of multiprocessor interconnection networks. The study is grounded in a detailed evaluation of the Cedar multiprocessor. Using characteristics of the behavior exhibited by the benchmarks studied on that system, a burst-traffic model is developed. The performance predictions of the model for adaptive and oblivious virtual-channel routers used in a 2D torus are compared to those of an open-loop random-traffic model, and significant differences are shown to exist.","abstract_html":"This thesis presents the development and use of a performance analysis methodology suitable for use in the evaluation of multiprocessor interconnection networks. The study is grounded in a detailed evaluation of the Cedar multiprocessor. Using characteristics of the behavior exhibited by the benchmarks studied on that system, a burst-traffic model is developed. The performance predictions of the model for adaptive and oblivious virtual-channel routers used in a 2D torus are compared to those of an open-loop random-traffic model, and significant differences are shown to exist.","abstract_has_math":false,"creators":["Turner, Stephen Wilson"],"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:09:31Z","date_published":"2011-05-07T14:09:31Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Turner, Stephen Wilson"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624522","(UMI)AAI9624522"],"render_values":[{"text":"AAI9624522","href":null,"code":true},{"text":"(UMI)AAI9624522","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23307","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":["Turner, Stephen Wilson"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:09:31Z","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":["Engineering, Electronics and Electrical","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 Turner, Stephen Wilson"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624522","(UMI)AAI9624522","http://hdl.handle.net/2142/23307"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis presents the development and use of a performance analysis methodology suitable for use in the evaluation of multiprocessor interconnection networks. The study is grounded in a detailed evaluation of the Cedar multiprocessor. Using characteristics of the behavior exhibited by the benchmarks studied on that system, a burst-traffic model is developed. The performance predictions of the model for adaptive and oblivious virtual-channel routers used in a 2D torus are compared to those of an open-loop random-traffic model, and significant differences are shown to exist.","The design of a novel adaptive router, the Shunt router, is proposed. Proofs of its freedom from deadlock and livelock are provided, showing its suitability for use in the construction of a shared-memory multiprocessor. The burst traffic model is used to drive simple versions of the Shunt router and compare its performance to those of the virtual-channel routers discussed previously. The Shunt router is shown to provide a suitable base for explorations of alterations to the routing algorithms and size of buffers within the router, due to its simplicity of structure.","The Shunt router is then augmented with a variety of adaptive routing algorithms. The performance of these algorithms, as well as two oblivious routing algorithms, is evaluated. The results show that structure in oblivious routing is important, and several adaptive routing schemes perform equally well. The Shunt router is also used to evaluate the impact of queue sizes on performance, as well as the interaction between queue lengths and adaptivity. Finally, a traffic-throttling network interface is used, with results that show it is primarily useful in cases of limited router buffering.","Analytic performance bounds are developed, and used to place the improvements due to adaptive routing into perspective. These bounds are derived from considerations of the systems topology and the structure of the burst-traffic model. Minimum latency, bisection-width, and a complex mean value analysis model are developed, and each is shown to have utility in different areas of performance prediction and comparison. Given the context of the performance bounds, the adaptive routers are shown to achieve a significant percentage of the potential performance improvement.","Made available in DSpace on 2011-05-07T14:09:31Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624522.pdf: 6603130 bytes, checksum: 4a09262d7d4ce8f9d772881d2252cbf1 (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:03:35Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:30:19-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":["Performance analysis of multiprocessor interconnection networks using a burst-traffic model"]}]}],"canonical_facts":{"dc:contributor":["Veidenbaum, Alexander V."],"dc:creator":["Turner, Stephen Wilson"],"dc:date":["2011-05-07T14:09:31Z","10000-01-01","1995"],"dc:description":["This thesis presents the development and use of a performance analysis methodology suitable for use in the evaluation of multiprocessor interconnection networks. The study is grounded in a detailed evaluation of the Cedar multiprocessor. Using characteristics of the behavior exhibited by the benchmarks studied on that system, a burst-traffic model is developed. The performance predictions of the model for adaptive and oblivious virtual-channel routers used in a 2D torus are compared to those of an open-loop random-traffic model, and significant differences are shown to exist.","The design of a novel adaptive router, the Shunt router, is proposed. Proofs of its freedom from deadlock and livelock are provided, showing its suitability for use in the construction of a shared-memory multiprocessor. The burst traffic model is used to drive simple versions of the Shunt router and compare its performance to those of the virtual-channel routers discussed previously. The Shunt router is shown to provide a suitable base for explorations of alterations to the routing algorithms and size of buffers within the router, due to its simplicity of structure.","The Shunt router is then augmented with a variety of adaptive routing algorithms. The performance of these algorithms, as well as two oblivious routing algorithms, is evaluated. The results show that structure in oblivious routing is important, and several adaptive routing schemes perform equally well. The Shunt router is also used to evaluate the impact of queue sizes on performance, as well as the interaction between queue lengths and adaptivity. Finally, a traffic-throttling network interface is used, with results that show it is primarily useful in cases of limited router buffering.","Analytic performance bounds are developed, and used to place the improvements due to adaptive routing into perspective. These bounds are derived from considerations of the systems topology and the structure of the burst-traffic model. Minimum latency, bisection-width, and a complex mean value analysis model are developed, and each is shown to have utility in different areas of performance prediction and comparison. Given the context of the performance bounds, the adaptive routers are shown to achieve a significant percentage of the potential performance improvement.","Made available in DSpace on 2011-05-07T14:09:31Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624522.pdf: 6603130 bytes, checksum: 4a09262d7d4ce8f9d772881d2252cbf1 (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:03:35Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:30:19-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":["AAI9624522","(UMI)AAI9624522","http://hdl.handle.net/2142/23307"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Turner, Stephen Wilson"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Performance analysis of multiprocessor interconnection networks using a burst-traffic model"],"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:21Z"}