An Algorithmic Evaluation of Optical Interconnection Networks

光互连网络的算法评估

• 批准号: 9912395
• 负责人: Sartaj Sahni
• 金额: $ 28.5万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9912395&HistoricalAwards=false
• 关键词: Algorithmic; Evaluation; Optical; Interconnection; Networks

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.

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