An Algorithmic Evaluation of Optical Interconnection Networks

基于光互连技术的并行架构越来越受欢迎，近年来出现了许多光学计算机。与电子计算机相比，光学计算机已被证明具有优越的互连特性。这些架构提供了构建经济实惠的机器以极高速度运行的潜力。由于某些模型支持流水线数据传输，其他模型具有异构互连拓扑，还有其他模型使用非对称拓扑，因此所提出的光学体系结构的算法开发变得复杂。虽然已经为其中一些模型设计了算法，但这一发展还处于起步阶段。已开发的算法主要用于有限的基本问题集，甚至这种水平的开发也只针对少数提出的体系结构。此外，开发的算法假设体系结构的大小是问题大小的函数。这种假设在实践中显然是无效的。通常，问题的规模将远远大于体系结构的规模。一个重要的问题是，迄今为止开发的光学架构算法是否具有可扩展性。也就是说，它们能否有效地扩展，以解决尺寸远远大于机器尺寸的问题。在这个项目中，已知的有效的光学架构算法的基础将大大扩展。我们将特别关注可扩展算法。从算法的角度进行跨架构性能研究。本研究将在基础数据运算和图像处理领域进行。在过去，各种研究人员对模型进行了可扩展性研究，如PRAM、网格与总线等。但是对光学模型的研究却很少。此外，许多过去的工作（例如，关于带有总线的网格）通过在不同大小的机器上模拟一个大小的机器来研究可伸缩性问题。这些研究的适用性受到限制。在这个项目中，一般的可扩展性问题将被调查，因此算法的可扩展性将直接探索。特别要解决的问题是：当输入的大小任意增加时，算法的加速和效率会发生怎样的变化？感兴趣的问题域是基本的数据操作，如排序、路由、选择等，以及图像处理操作，如聚类、模板匹配、直方图、FFT等。之所以选择这些操作，是因为它们跨越了许多应用程序域。至少三种光学架构，即阵列可重构光总线（AROBs），光转置互连系统（otis）和可分区光无源星（POPS）计算机，将被考虑。在这个项目中开发的算法和算法技术也可以应用于其他架构。

Parallel architectures based on the optical interconnect technology are becoming more and more popular as reflected by the numerous optical computers that have been proposed in recent years. Optical computers have been shown to possess superior interconnect properties compared to their electrical counterparts. These architectures offer the potential of building affordable machines operating at extremely high speeds.The development of algorithms for the proposed optical architectures is complicated by the fact that some models support pipelined data transfer, other models have a heterogeneous interconnect topology, and yet other models use an asymmetric topology. Although algorithms have been designed for some of these models, this development is in its infancy. The developed algorithms are mainly for a limited set of fundamental problems, and even this level of development has been done for only a few of the proposed architectures. Further, the developed algorithms assume that the size of the architecture is a function of the problem size. This assumption is clearly invalid in practice. Typically, the problem size will be much larger than the size of the architecture. An important question is if the optical architecture algorithms that have been developed so far are scalable. That is, can they be efficiently extended to solve problems whose size is considerably larger than the machine size. In this project the base of known efficient algorithms for optical architectures will be significantly expanded. Special attention will be paid to scalable algorithms. A cross-architecture performance study from the algorithms point of view will be performed. This study will be conducted in the domains of fundamental data operations and image processing. Scalability study has been conducted in the past by various researchers on models such as the PRAM, meshes with buses, and so on. But little has been done for the optical models. Also, many of the past works (for example, on meshes with buses) have studied the scalability issue by simulating a machine of one size on a machine of different size. Such studies are restricted in their applicability. In this project the general scalability issue will be investigated and hence the scalability of algorithms will be explored directly. In particular, the following question will be addressed: As the size of the input increases arbitrarily, how do the speedup and efficiency of the algorithm under concern change?The problem domains of interest are fundamental data operations such as sorting, routing, selection, etc. and image processing operations such as clustering, template matching, histogram, FFT, etc. These operations have been chosen since they span a number of application domains. At least three optical architectures, namely, Arrays with Reconfigurable Optical Buses (AROBs), Optical Transpose Interconnection Systems (OTISs), and Partitionable Optical Passive Star (POPS) computers, will be considered. The algorithms and algorithmic techniques to be developed in this project can be expected to be applicable to other architectures as well.