عنوان

Performance modeling of parallel computations in resource-constrained systems

Number

TLpq303720533

.Language of Text, Soundtrack etc

انگلیسی

Title Proper

Performance modeling of parallel computations in resource-constrained systems

General Material Designation

[Thesis]

First Statement of Responsibility

M. Ghodsi

Subsequent Statement of Responsibility

K. Kant

Name of Publisher, Distributor, etc.

The Pennsylvania State University

Date of Publication, Distribution, etc.

1989

Specific Material Designation and Extent of Item

140

Dissertation or thesis details and type of degree

Ph.D.

Body granting the degree

The Pennsylvania State University

Text preceding or following the note

1989

Text of Note

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.

Applied sciences

Computer science

K. Kant

M. Ghodsi

Electronic name

p

[Thesis]

276903

a

Y