| Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing | |
| Richard M. Karp; Rayamond E. Miller | |
| 1966 | |
| 发表期刊 | SIAM Journal on Applied Mathematics
 |
| 卷号 | 14期号:6页码:1390-1411 |
| 摘要 | 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. |
| 收录类别 | 其他 |
| 合作性质 | 其它 |
| 语种 | 英语 |
| 内容类型 | 期刊论文 |
| URI标识 | http://ir.iscas.ac.cn/handle/311060/1294 |
| 专题 | 中国科学院软件研究所 |
| 推荐引用方式 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. |
| 条目包含的文件 | ||||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
| bj01129201.pdf（1549KB） | 开放获取 | 使用许可 | 请求全文 | |||
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论