Performance evaluation of shared memory multiprocessing architectures /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1991.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Abstract: | With the availability of shared memory multiprocessors in today's market comes a growing need for performance evaluation of such systems. The conventional motheds for performance evaluation of multiprocessing architectures have been mostly based on simulation and measurements which can be very inefficient due to their inflexibility and large time/resource consumption. In this dissertation, we propose computationally efficient and accurate analytical models to predict performance of shared memory multiprocessing architectures with respect to various applications or algorithms. In particular, we evaluate the performance of task graphs when executed on a multiprocessing system. Due to the large complexity of analyzing the task graphs in their complete generality, we propose a set of formulations to characterize and transform arbitrary task graphs into simple and highly structured ones, called level-oriented graphs. With these characterization and transformation of task graphs, performance analysis can be simplified significantly. Approximate analytical models based on queueing networks are developed to analyze performance of shared memory multiprocessing architectures based on shared-buses and multistage interconnection networks (MINs). The proposed techniques relate the notions of variations of parallelism and average parallelism that are inherent in any parallel algorithm to the queueing network model of an architecture. The approaches are based on a decomposition that transforms an arbitrary task graph into a layered graph, analyzes each layer separately, and combines the results in a weighted manner. The technique captures the effect of dynamic changes of parallelism while significantly simplifying the otherwise complicated analysis. The problem of internal concurrency due to data dependencies, the main cause of complexity in analysis, is resolved indirectly by analyzing maximum and minimum dependencies among tasks. The proposed models have been shown to be more effective and efficient than the previous models. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Computer Science." |
| Physical Description: | xiv, 193 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |