MURAL - Maynooth University Research Archive Library

    Parallel and sequential optical computing

    Woods, Damien and Naughton, Thomas J. (2008) Parallel and sequential optical computing. Lecture Notes in Computer Science, 5172. pp. 70-86. ISSN 0302-9743

    [img] Download (213kB)

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We present a number of computational complexity results for an optical model of computation called the continuous space machine. We also describe an implementation for an optical computing algorithm that can be easily defined within the model. Our optical model is designed to model a wide class of optical computers, such as matrix vector multipliers and pattern recognition architectures. It is known that the model solves intractable PSPACE problems in polynomial time, and NC problems in polylogarithmic time. Both of these results use large spatial resolution (number of pixels). Here we look at what happens when we have constant spatial resolution. It turns out that we obtain similar results by exploiting other resources, such as dynamic range and amplitude resolution. However, with certain other restrictions we essentially have a sequential device. Thus we are exploring the border between parallel and sequential computation in optical computing. We describe an optical architecture for the unordered search problem of finding a one in a list of zeros. We argue that our algorithm scales well, and is relatively straightforward to implement. This problem is easily parallelisable and is from the class NC. We go on to argue that the optical computing community should focus their attention on problems within P (and especially NC), rather than developing systems for tackling intractable problems.

    Item Type: Article
    Additional Information: Preprint version of original article. The original publication is available at (DOI: 10.1007/978-3-540-85673-3_6). DW acknowledges support from Junta de Andalucıa grant TIC-581. TN acknowledges support from a Marie Curie Fellowship through the European Commission Framework Programme 6.
    Keywords: Parallel; sequential; optical computing; optical computing algorithm;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 2821
    Identification Number:
    Depositing User: CS Editor
    Date Deposited: 09 Nov 2011 15:29
    Journal or Publication Title: Lecture Notes in Computer Science
    Publisher: Springer Verlag
    Refereed: No
    Funders: Junta de Andalucıa, European Commission
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads