Skip to main content
SpringerLink
Log in

Derivation of efficient parallel programs: An example from genetic sequence analysis

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K. M. Chandy and J. Misra,Parallel Program Design: A Foundation, Reading, Massachusetts: Addison-Wesley (1988).

    Google Scholar 

  2. 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).

    Article  Google Scholar 

  3. E. W. Dijkstra,A Discipline of Programming, Englewood Cliffs, New Jersey: Prentice-Hall (1976).

    Google Scholar 

  4. D. Gries,The Science of Programming, New York: Springer-Verlag (1981).

    Google Scholar 

  5. C. B. Jones,Systematic Software Development Using VDM, Englewood Cliffs, New Jersey: Prentice-Hall (1986).

    Google Scholar 

  6. 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).

  7. 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).

  8. C. A. R. Hoare, An Axiomatic Basis for Computer Programming,Communications of the ACM,12:576–580 (1969).

    Article  Google Scholar 

  9. R. Milner, Calculi for Synchrony and Asynchrony,Theoretical Computer Science,25:267–310 (1983).

    Article  Google Scholar 

  10. D. Gries and J. A. Prins, A New Notion of Encapsulation,Proc. Symp. Language issues in Programming Environments, SIGPLAN,20:131–139 (1985).

    Google Scholar 

  11. C. A. R. Hoare, Proofs of Correctness of Data Representations,Acta Informatica,1(4):271–281 (1972).

    Article  Google Scholar 

  12. J. M. Morris, Laws of Data Refinement,Acta Informatica,26(4):287–308 (1989).

    Google Scholar 

  13. Singh, A. K., On Strengthening the Guard, Notes on Unity Vol. 7 (June 1989).

  14. J. C. Browne, M. Azam, and S. Sobek, CODE: A Unified Approach to Parallel Programming,IEEE Software, pp. 10–17 (July 1989).

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of California at Santa Barbara, 93106, Santa Barbara, California

    Ambuj K. Singh

  2. Argonne National Laboratory, 60439, Argonne, Illinois

    Ross Overbeek

Authors
  1. Ambuj K. Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ross Overbeek
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01381718

Key Words

Search

Navigation