عنوان

Performance modeling of parallel computations in resource-constrained systems

شماره

TLpq303720533

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Performance modeling of parallel computations in resource-constrained systems

نام عام مواد

[Thesis]

نام نخستين پديدآور

M. Ghodsi

نام ساير پديدآوران

K. Kant

نام ناشر، پخش کننده و غيره

The Pennsylvania State University

تاریخ نشرو بخش و غیره

1989

نام خاص و کميت اثر

140

جزئيات پايان نامه و نوع درجه آن

Ph.D.

کسي که مدرک را اعطا کرده

The Pennsylvania State University

امتياز متن

1989

متن يادداشت

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

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y