Abstract
Implementation issues such as synchronization, implementation of abstract data types, and scheduling of processes are usually not addressed in the formal derivation of parallel programs. We seek to redress the situation by considering these issues in the context of developing an efficient implementation of an actual parallel program. The computational problem that we proceed by developingan algorithm in Unity and investigating the issues that arise in producing an efficient C implementation of the resulting algorithm. Along the way, we develop some theorems about program refinements, and illustrate the usefulness of the theorems in the context of refining the original Unity program.
Similar content being viewed by others
References
K. M. Chandy and J. Misra,Parallel Program Design: A Foundation, Reading, Massachusetts: Addison-Wesley (1988).
K. M. Chandy and J. Misra, An Example of Stepwise Refinement of Distributed Programs: Quiescence Detection,ACM Transactions on Programming Languages and Systems,8(3):326–343 (July1986).
E. W. Dijkstra,A Discipline of Programming, Englewood Cliffs, New Jersey: Prentice-Hall (1976).
D. Gries,The Science of Programming, New York: Springer-Verlag (1981).
C. B. Jones,Systematic Software Development Using VDM, Englewood Cliffs, New Jersey: Prentice-Hall (1986).
N. Lynch and M. R. Tuttle, Hierarchical Correctness Proofs for Distributed Algorithms,Proc. Sixth Annual ACM Symposium on the Principles of Distributed Computing, pp. 137–151 (1987).
R. Butler, T. Butler, I. Foster, N. Karonis, R. Olson, N. Pflunger, M. Pric, and S. Tuecke, Generating Alignments of Genetic Sequences, Technical Report ANL/MCS-TM-132, Mathematics and Computer Science Division, Argonne National Laboratories (June 1989).
C. A. R. Hoare, An Axiomatic Basis for Computer Programming,Communications of the ACM,12:576–580 (1969).
R. Milner, Calculi for Synchrony and Asynchrony,Theoretical Computer Science,25:267–310 (1983).
D. Gries and J. A. Prins, A New Notion of Encapsulation,Proc. Symp. Language issues in Programming Environments, SIGPLAN,20:131–139 (1985).
C. A. R. Hoare, Proofs of Correctness of Data Representations,Acta Informatica,1(4):271–281 (1972).
J. M. Morris, Laws of Data Refinement,Acta Informatica,26(4):287–308 (1989).
Singh, A. K., On Strengthening the Guard, Notes on Unity Vol. 7 (June 1989).
J. C. Browne, M. Azam, and S. Sobek, CODE: A Unified Approach to Parallel Programming,IEEE Software, pp. 10–17 (July 1989).
Author information
Authors and Affiliations
Additional information
Work supported in part by ONR Grants N00014-86-K-0763 and N00014-87-K-0510 while the author was at The University of Texas at Austin.
Rights and permissions
About this article
Cite this article
Singh, A.K., Overbeek, R. Derivation of efficient parallel programs: An example from genetic sequence analysis. Int J Parallel Prog 18, 447–484 (1989). https://doi.org/10.1007/BF01381718
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01381718