[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Generalized methods for algorithm development on optical systems

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

A number of recent studies have revealed that the Optical Transpose Interconnection Systems (or OTIS) are promising candidates for future high-performance parallel computers. In this paper, we present and evaluate two general methods for algorithm development on the OTIS. The proposed methods are general in the sense that no specific factor network or problem domain is assumed. The proposed methods allow efficient mapping of a wide class of algorithms into the OTIS. These methods are based on grids and pipelines as popular structures that support a vast body of parallel applications including linear algebra, divide-and-conquer type of algorithms, sorting, and FFT computation. Timing models for measuring the performance of the proposed methods are also provided. Through these models, the performance of various algorithms on the OTIS are evaluated and compared with their counterparts on conventional electronic interconnection systems. This study confirms the viability of the OTIS as an attractive alternative for large-scale parallel architectures. Finally, we show how the proposed methods can be used to design parallel algorithms for linear algebra on the OTIS.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Marsden G, Marchand P, Harvey P, Esener S (1993) Optical transpose interconnection system architec- ture. Optics Letters 18(13):1083–1085

    Article  Google Scholar 

  2. Yayla G, Marchand P, Esener S (1998) Speed and energy analysis of digital interconnections: Comparison of on-chip, off-chip, and free-space technologies. Applied Optics 37(2):205–227

    Article  Google Scholar 

  3. Wang C, Sahni S (1998) Basic operations on the OTIS-mesh optoelectronic computer. IEEE Transactions on Parallel and Distributed Systems 9(12):1226–1236

    Article  Google Scholar 

  4. Sahni S, Wang C (1998) BPC permutations on the OTIS-hypercube optoelectronic computer. Informatica 22:263–269

    MATH  Google Scholar 

  5. Sahni S, Wang C (1997) BPC permutations on the OTIS-mesh optoelectronic computer. In: Proceedings of the IEEE Conference on Massively Parallel Programming Using Optical Interconnect pp. 130–135

  6. Krishnamoorthy A, Marchand P, Kiamilev F, Esener S (1992) Grain-size considerations for optoelectronic multistage interconnection networks. Applied Optics 31(26):5480–5507

    Article  Google Scholar 

  7. Hendrick W, Kibar O, Marchand P, Fan C, Blerkom D, McCormick F, Cokgor I, Hansen M, Esener S (1995) Modeling and optimization of the optical transpose interconnection system. In Optoelectronic Technology Center, Program Review, Cornell University

  8. Sahni S (1999) Models and algorithms for optical and optoelectronic parallel computers. In: Proceedings of the International Symposium on Parallel Algorithms and Networks. IEEE Computer Society Press, pp. 2–7

  9. Al-Ayyoub A, Day K (1998) Block-cyclic matrix triangulation on the Cartesian product on star graphs. Journal of Computers and Mathematics with Applications, 36(5):113–126

    Article  MATH  MathSciNet  Google Scholar 

  10. Zane F, Marchand P, Paturi R, Esener S (2000) Scalable network architectures using the optical transpose interconnection system (OTIS). Journal of Parallel and Distributed Computing 60(5):521–538

    Article  MATH  Google Scholar 

  11. Angelacci M, Colajanni M (1993) Unifying and optimizing parallel linear algebra algorithms. IEEE Transactions Parallel and Distributed Systems 4(12):1382–1397

    Article  Google Scholar 

  12. Cappelo P (1985) A mesh automaton for solving dense linear systems. In: Proceedings of the International Conference on Parallel Processing pp. 418–425

  13. Guo Z, Melhem R, Hall R, Chiarulli D, Levitan S (1991) Pipelined communications in optically interconnected arrays. Journal of Parallel and Distributed Computing 12:269–282

    Article  Google Scholar 

  14. Szymanski T (1992) The complexity of FFT and related Butterfly algorithms on meshes and hypermeshes. In Proceedings of the International Conference on Parallel Processing vol. III: pp. 77–81

  15. Johnsson S, Ho C (1989). Optimum broadcasting and personalized communication in hypercubes. IEEE Transactions on Computers 38(9):1249–1267

    Article  MathSciNet  Google Scholar 

  16. Angelacci M, Colajanni M (1994) Subcube matrix decomposition: A unifying view of LU factorization on multicomputers. Parallel Computing 20(2):257–270

    Article  Google Scholar 

  17. Wang C, Sahni S (2000) Image processing on the OTIS-mesh optoelectronic computer. IEEE Transactions on Parallel and Distributed Systems 11(2):97–109

    Article  MATH  Google Scholar 

  18. Wang C, Sahni S (1999) Matrix multiplication on the OTIS-mesh optoelectronic computer. In: Proceedings of the 6th IEEE International Conference on Parallel Interconnects pp. 131–138

  19. Dally W (1990) Performance analysis of the k-ary n-cubes interconnection networks. IEEE Transactions on Computers 39(6):775–785

    Article  Google Scholar 

  20. Awwad AM, Al-Ayyoub A, Day K, Ould-Khaoua M (2000) Generalized methods for algorithm development on optical systems. In: Proceedings of the 2000 Arab Conference on Information Technology (ACIT’2000), Zarka Private University, Jordan, October 31st–November 2nd, pp. 111–118

Download references

Author information

Authors and Affiliations

  1. Faculty of Computer Studies, Arab Open University, P.O. Box 84901, Riyadh, 11681, Saudi Arabia

    A. Al-Ayyoub

  2. Department of Computer Science, Zarqa Private University, P.O. Box 2000, Zarqa, 13110, Jordan

    A. Awwad

  3. Department of Computer Science, Sultan Qaboos University, Muscat, 123, Oman

    K. Day

  4. Department of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK

    M. Ould-Khaoua

Authors
  1. A. Al-Ayyoub
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Awwad
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. K. Day
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. M. Ould-Khaoua
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Al-Ayyoub, A., Awwad, A., Day, K. et al. Generalized methods for algorithm development on optical systems. J Supercomput 38, 111–125 (2006). https://doi.org/10.1007/s11227-006-7447-6

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-006-7447-6

Keywords

Search

Navigation