首页> 外文会议> >A period-processor-time-minimal schedule for cubical mesh algorithms
【24h】

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

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

获取原文

摘要

The paper, using a direct acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n /spl times/ n /spl times/ n 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 3n - 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 [3n/sup 2//4] 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 3n/2 steps. This lower bound is shown to be exact by 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/ n/2 /spl times/ 3 mesh.
机译:该论文使用一种算法的直接非循环图(dag)模型,研究了针对n / spl times / n / spl times / n有向网格的优先级受限多处理器调度。该三次网格是基本的,代表了正方形矩阵乘积的标准算法以及许多其他算法。它的完成至少需要3n-2个多处理器步骤。使用最少处理器的最小时间多处理器调度称为最小处理器时间。对于三次网格,此类计划至少需要[3n / sup 2 // 4]个处理器。在这样的调度中,具有最小周期(即,最大吞吐量)的调度被称为周期处理器时间最小调度。三次网格的任何处理器时间最小调度的周期至少为3n / 2步。通过针对n的6的倍数构造一个周期处理器时间最小的多处理器计划,可以证明此下界是正确的,该时间表可以在拓扑为环形连接的n / 2 / spl times /的脉动阵列上实现n / 2 / spl次/ 3目。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号