On performance prediction of parallel computations with precedent constraints
| Autor: | Satish K. Tripathi, De-Ron Liang |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
Queueing theory
Computational Theory and Mathematics Series (mathematics) Parallel processing (DSP implementation) Computational complexity theory Hardware and Architecture Computer science Computation Signal Processing Structure (category theory) Performance prediction Parallel computing Time complexity |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 11:491-508 |
| ISSN: | 1045-9219 |
| DOI: | 10.1109/71.852402 |
| Popis: | 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(C/sup 2/N/sup 2/K) and the space complexity is O(C/sup 2/N/sup 2/K), 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|