Mapping and scheduling of concurrent communication traffic in multicomputer networks.
dc.contributor.author | Tsai, Bingrung | en_US |
dc.contributor.advisor | Shin, Kang G. | en_US |
dc.date.accessioned | 2014-02-24T16:19:59Z | |
dc.date.available | 2014-02-24T16:19:59Z | |
dc.date.issued | 1994 | en_US |
dc.identifier.other | (UMI)AAI9501052 | en_US |
dc.identifier.uri | http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:9501052 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/104214 | |
dc.description.abstract | In a multicomputer network, each task is decomposed into modules which are then executed by a number of processing nodes. During the execution, bursty concurrent communication traffic among processor nodes can lead to network congestion and become a bottleneck. Our goal is to improve the system communication performance in such a situation using on-line traffic flow-control mechanisms, and develop task mapping strategies with sufficient task behavior information prior to the execution. Flow-control mechanisms include message routing algorithms, message scheduling policies, and in the case of virtual channel networks, time-division multiplexing methods. For on-line applications, we propose low-complexity distributed mechanisms to be implemented on each node. Using simulations, we show that effective mechanisms can improve network performance significantly. Without proper flow-control mechanisms, adding communication resources such as links and buffers can actually degrade the network performance. Also, under heavy concurrent traffic, a low-complexity routing algorithm, when combined with a good message scheduling policy, can outperform a much more complex routing algorithm and achieve near-optimal performance. Before their execution, if the task communication behavior can be predicted (with a certain degree of accuracy), task modules can be mapped to processor nodes strategically to exploit their communication locality and thus improve the run-time performance. However, due to the complex interactions among these modules, the performance objective can be very difficult to formulate, making direct optimization impossible. Thus, we propose simple cost functions so that when mappings are optimized with respect to these functions, the actual performance objectives are also optimized. For this purpose, various heuristic algorithms are developed and tested through analytical modeling and simulations. Several cost functions are studied and a few of them found to be very effective when used with appropriate algorithms. For binary hypercubes, we also extend our study to the problem of mapping concurrently communicating subcubes. We show that the optimization process can be simplified and existing algorithms can be easily adapted for this application. | en_US |
dc.format.extent | 139 p. | en_US |
dc.subject | Computer Science | en_US |
dc.title | Mapping and scheduling of concurrent communication traffic in multicomputer networks. | en_US |
dc.type | Thesis | en_US |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Computer Science and Engineering | en_US |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/104214/1/9501052.pdf | |
dc.description.filedescription | Description of 9501052.pdf : Restricted to UM users only. | en_US |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.