• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >The mesh with hybrid buses: an efficient parallel architecture for digital geometry
【24h】

The mesh with hybrid buses: an efficient parallel architecture for digital geometry

机译：带混合总线的网格：用于数字几何的高效并行架构

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The first main contribution of this work is to propose an efficient VLSI architecture obtained by augmenting the Mesh with Multiple Broadcasting (MMB) with precharged 1-bit row and column buses. The new architecture, which we call Mesh with Hybrid Buses (MHB for short), is realizable in VLSI with no increase in the area or the wiring complexity of the MMB chip. Our second main contribution is to show that the MHB is extremely well-suited for solving an entire slew of digital geometry tasks. The MHB is not a reconfigurable architecture. Yet, quite remarkably, for a large number of fundamental digital geometry tasks, the MHB offers a level of performance previously attained only by reconfigurable architectures. Specifically, with a digital image pretiled onto a MHB of size /spl radic/spl times//spl radic one pixel per processor, we show that the problems of computing the convex hull of the image, computing the diameter and the width of the image, deciding whether a set of digital points is a digital line, computing the maximum distance between two images, deciding whether two images are linearly separable, computing several moments and low-level descriptors of the image, including the perimeter, area, center, and median row of its convex hull, can be solved in O(log n) time. By contrast, the fastest possible algorithms for the problems above on the MMB run in /spl Theta/(n/sup 1/6/) time. Finally, we go on to show that, with minor changes, our algorithms can be implemented to run within cost-optimality on a MHB of size /spl radic/log n/spl times//spl radic/log n.
机译：这项工作的第一个主要贡献是提出一种有效的VLSI体系结构，该体系结构是通过使用预充电的1位行和列总线扩展多播网（MMB）来获得的。这种新的架构，我们称为混合总线网格（Mesh with Hybrid Bus，简称MHB），可以在VLSI中实现，而不会增加MMB芯片的面积或布线复杂性。我们的第二个主要贡献是表明MHB非常适合解决整个数字几何任务。 MHB不是可重新配置的体系结构。然而，非常值得注意的是，对于大量基本的数字几何任务，MHB提供了以前只能通过可重新配置的架构才能达到的性能水平。具体而言，将数字图像预倾斜到大小为/ spl radic / n / spl times // spl radic / n每个处理器一个像素的MHB上，我们发现存在计算图像凸包，计算直径和尺寸的问题。图像的宽度，确定一组数字点是否为数字线，计算两个图像之间的最大距离，确定两个图像是否可线性分离，计算图像的多个矩和低级描述符，包括周长，面积，其中心和凸包的中间行可以在O（log n）时间内求解。相比之下，MMB上上述问题的最快可能算法以/ spl Theta /（n / sup 1/6 /）时间运行。最后，我们继续说明，只需稍作更改，我们的算法就可以实现在成本最优的MHB上运行，其大小为/ spl radic / n / log n / spl times // spl radic / n / log n。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号