|
" Performance modeling of parallel computations in resource-constrained systems "
M. Ghodsi
K. Kant
| Document Type
|
:
|
Latin Dissertation
|
| Language of Document
|
:
|
English
|
| Record Number
|
:
|
1112488
|
| Doc. No
|
:
|
TLpq303720533
|
| Main Entry
|
:
|
K. Kant
|
|
|
:
|
M. Ghodsi
|
| Title & Author
|
:
|
Performance modeling of parallel computations in resource-constrained systems\ M. GhodsiK. Kant
|
| College
|
:
|
The Pennsylvania State University
|
| Date
|
:
|
1989
|
| student score
|
:
|
1989
|
| Degree
|
:
|
Ph.D.
|
| Page No
|
:
|
140
|
| Abstract
|
:
|
In this research, we study several problems related to the modeling and performance analysis of parallel computations. First, we investigate the properties of a new task graph model, called the generalized task graphs, which can represent the nondeterminism involved in the parallel search algorithms. In parallel search, several possible solutions to a problem are carried out concurrently, with the intention of having only one successful result. The general task graphs are prone to problems such as deadlock, unboundedness, and unsafeness. We define the notion of well-formedness of task graphs by viewing them as high level Petri nets and provide necessary and sufficient conditions under which a generalized task graph is well formed. Next, we propose a new approximate iterative algorithm to predict the performance of a resource constrained queueing network, running a number of statistically identical jobs with internal concurrency. The jobs are assumed to be instances of an arbitrary task graph. The queueing network includes a limited number of identical passive resources. A task must acquire one unit of the passive resources before receiving service. Detailed experimental results are presented which show that the algorithm converges quite fast and is reasonably accurate. In the final part of this dissertation, we present an exact solution technique for analyzing the performance of parallel search algorithms implemented on multiprocessor systems. A job, representing a parallel search, arrives at a station with usdMusd identical servers from a Poisson source. After some initial computation, the job spawns usdKusd statistically identical subtasks. All these subtasks can be executed independently in parallel, but only one of them is required to finish for the entire job to complete. We show that, for any usdKusd and usdMusd, if the service times of the initial task and the subtasks are exponentially distributed with equal rates, the processor utilization is independent of usdKusd while the job response time decreases with usdKusd.
|
| Subject
|
:
|
Applied sciences
|
|
|
:
|
Computer science
|
| |