Institutional Repository
| Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing | |
| Richard M. Karp; Rayamond E. Miller | |
| 1966 | |
| Source | SIAM Journal on Applied Mathematics
 |
| Volume | 14Issue:6Pages:1390-1411 |
| English Abstract | This paper gives a graph-theoretic model for the description and analysis of parallel computations. Within the model, computation steps correspond to nodes of a graph, and dependency between computation steps is represented by branches with which queues of data are associated. First, it is shown that each such computation graph$G$represents a unique computation, determined independently of operation times. Next, methods of determining whether such a computation terminates and of finding the number of performances of each computation step are developed. The maximal strongly connected subgraphs of $G$ and the loops within these subgraphs play aooutnal role in this analysis. For example, use is made of the result that either every computation step within a strongly connected snbgroph of $G$ is performed an infinite number of times, or none is. Finally, necessary and sufficient conditions for the lengths of data queues to remain bounded are derived. |
| Indexed Type | 其他 |
| Cooperation Status | 其它 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/1294 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Richard M. Karp,Rayamond E. Miller. Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing[J]. SIAM Journal on Applied Mathematics,1966,14(6):1390-1411. |
| APA | Richard M. Karp,&Rayamond E. Miller.(1966).Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing.SIAM Journal on Applied Mathematics,14(6),1390-1411. |
| MLA | Richard M. Karp,et al."Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing".SIAM Journal on Applied Mathematics 14.6(1966):1390-1411. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| bj01129201.pdf（1549KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment