Techniques for the design of communicating processes
Pages 67 - 74
Abstract
These last few years have seen the development of many parallel architectures. Among them, Distributed Memory Parallel Computers seem to be very promizing. The programmation of these machines requires to design processes to be mapped on the nodes, communicating by message passing along the links of the architecture. The aim of this paper is to give a contribution for a rationalized design of such programs, by defining refinement techniques.
References
[1]
{Apt 80} K. R. Apt, N. Francez, W. P. De Roever: A proof system for communicating sequential processes; ACM, Toplas 2, 3 (1980), pp. 359--385.
[2]
{Back 88} R. J. Back: A calculus of Refinements for Program Derivations; Acta Informatica 25, p. 593--624, 1988.
[3]
{Back 89} R. J. Back, K. Sere: Stepwise refinement of actions systems; LNCS 375, p. 115--138, 1989.
[4]
{Chandy 88} K. M. Chandy, J. Misra: Parallel Program Design: a Foundation; Prentice Hall, 1988.
[5]
{Clauss 88} P. Clauss, G. R. Perrin: Synthesis of process arrays; CONPAR'88, Manchester, 1988.
[6]
{Delosme 85} J. M. Delosme, I. C. F. Ipsen: An illustration of a methodology for the construction of efficient systolic architectures in VLSI; Snd Inter. Symposium on VLSI technology systems and applications, 1985.
[7]
{Dijkstra 76} E. W. Dijkstra: A discipline of programming; Prentice-Hall, Englewood Cliffs, 1976.
[8]
{Gribomont 89} P. E. Gribomont: Stepwise refinement and concurrency: the finite-state case; Research Report, Philips, Brussels, 1989.
[9]
{Gribomont 90} P. E. Gribomont: Development of concurrent systems by incremental transformation; Research Report, Philips, Brussels, 1990.
[10]
{Hoare 78} C. A. R. Hoare: Communicating Sequential Processes; Com. ACM Vol. 21, No. 8, 1978.
[11]
{Karp 67} R. M. Karp, R. E. Miller, S. Winograd: The organization of computations for uniform recurrence equations; J. of ACM, 14, 3, 1967.
[12]
{Knapp 90} E. Knapp: An exercise in the formal derivation of parallel programs: Maximum flows in graphs; ACM Transactions on Programming Languages and Systems, Vol.12, No. 2, p. 203--223, Avril 1990.
[13]
{Kung 79} H. T. Kung: The structure of parallel algorithms; Advances in Computer, 15, 1, 1979.
[14]
{Mongenet 87} C. Mongenet, G. R. Perrin: Synthesis of systolic arrays for inductive problems; Conf. PARLE, Eindhoven, LNCS 259, 1987.
[15]
{Morgan 89} C. C. Morgan: Types and invariants in the refinement calculus; LNCS 375, p. 363--378, 1989.
[16]
{Morris 87} J. M. Morris: A theorical basis for stepwise refinement and the programming calculus; Science of Computer Programming, 9 (3), p. 298--306, December 1987.
[17]
{Perrin 89} G. R. Perrin, P. Clauss, S. Damy: Mapping programs on regular Distibuted Architectures; Hypercube an Distributed Computers, Elsevier Sc. Pub., 1989.
[18]
{Quinton 88} P. Quinton: Mapping recurrences on parallel architectures; Third Inter. Conf. on Supercomputing, Boston, 1988.
[19]
{Thalhofer 89} K. Thalhofer: RGL A Specification Language Based on Recurrence Equations; Research Report, Univ. of Erlangen-Nürmberg, 1989.
[20]
{Wirth 71} N. Wirth. Program Development by Stepwise Refinement; Com. ACM Vol. 14, No. 4, 1971.
- Techniques for the design of communicating processes
Recommendations
Filter Promotion Transformation Strategies for Deriving Efficient Programs from Z Specifications
ICFEM '00: Proceedings of the 3rd IEEE International Conference on Formal Engineering MethodsIn recent years, there have been growing interests in systematic methods for refining Z specifications into programs. In this paper, we consider a transformational programming strategy known as filter promotion and examine its use for refining a class ...
A state-based approach to communicating processes
Communicating processes, which may exhibit nondeterministic behaviour, are specified as state-transition systems. Equivalence and refinement relations are defined in terms of the failures model of processes. Downward and upward simulation are considered ...
Proving safety and liveness of communicating processes with examples
PODC '82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computingA method is proposed for reasoning about safety and liveness properties of message passing networks. The method is hierarchical and is based upon combining the specifications of component processes to obtain the specification of a network. The inference ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 1991
257 pages
ISBN:0818623209
- General Chair:
- Jean-Pierre Finance,
- Program Chairs:
- Carlo Ghezzi,
- Gruia-Catalin Roman
Sponsors
- SIGSOFT: ACM Special Interest Group on Software Engineering
- IEEE-CS\DATC: IEEE Computer Society
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 25 October 1991
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 110Total Downloads
- Downloads (Last 12 months)20
- Downloads (Last 6 weeks)2
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in