On performance prediction of parallel computations with precedent constraints

De Ron Liang, Satish K. Tripathi

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


Performance analysis of concurrent executions in parallel systems has been recognized as a challenging problem. The aim of this research is to study approximate but efficient solution techniques for this problem. We model the structure of a parallel machine and the structure of the jobs executing on such a system. We investigate rich classes of jobs, which can be expressed by series, parallel-and, parallel-or, and probabilistic-fork. We propose an efficient performance prediction method for these classes of jobs running on a parallel environment which is modeled by a standard queueing network model. The proposed prediction method is computationally efficient, it has polynomial complexity in both time and space. The time complexity is O(C2N2K) and the space complexity is O(C2N2K), where C is the number of job classes in the system, the number of tasks in each job class is O(N), and K is the number of service centers in the queueing model. The accuracy of the approximate solution is validated via simulation.

Original languageEnglish
Pages (from-to)491-508
Number of pages18
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number5
StatePublished - May 2000


Dive into the research topics of 'On performance prediction of parallel computations with precedent constraints'. Together they form a unique fingerprint.

Cite this