• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >A period-processor-time-minimal schedule for cubical mesh algorithms
【24h】

A period-processor-time-minimal schedule for cubical mesh algorithms

机译：三次网格算法的周期处理器时间最小调度

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

摘要

Using a directed acyclic graph (dag) model of algorithms, we investigate precedence-constrained multiprocessor schedules for the n/spl times/spl times directed mesh. This cubical mesh is fundamental, representing the standard algorithm for square matrix product, as well as many other algorithms. Its completion requires at least 3/sup n/spl minus/2/ multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the cubical mesh, such a schedule requires at least /spl lsqb/3n/sup 2//4/spl rsqb/ processors. Among such schedules, one with the minimum period (i.e., maximum throughput) is referred to as a period-processor-time-minimal schedule. The period of any processor-time-minimal schedule for the cubical mesh is at least 3/sup n/2/ steps. This lower bound is shown to be exact by constructing, for n a multiple of 6, a period-processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a toroidally connected n/2/spl times/2/spl times/3 mesh.
机译：使用算法的有向无环图（dag）模型，我们研究了n / spl次/ n / spl次/ n有向网格的优先级受限的多处理器调度。该三次网格是基本的，代表了正方形矩阵乘积的标准算法以及许多其他算法。它的完成至少需要3 / sup n / spl减/ 2 /多处理器步骤。使用最少处理器的最小时间多处理器调度称为最小处理器时间。对于立方网格，此类计划至少需要/ spl lsqb / 3n / sup 2 // 4 / spl rsqb /处理器。在这些调度中，具有最小周期（即，最大吞吐量）的调度被称为周期处理器时间最小调度。三次网格的任何处理器时间最小调度的周期至少为3 / sup / 2。通过为6的倍数构造一个周期处理器时间最小的多处理器调度程序，可以证明此下界是准确的，该周期可以在一个拓扑为n / 2 / spl times / n /的脉动阵列上实现2 / spl次/ 3目。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号