矩阵乘法的并行算法分析王前本章目录乘法器设计矩阵乘法单处理机矩阵乘法器二维方阵矩阵乘法器乘法器设计1、性能级设计 4位数字乘法器。2、结构级
设计乘法器设计方案1：空间迭代分析：方案1通过完全空间意义上的迭代，实现4位二进制数相乘的迭代网络。特点：速度快、硬件复杂Ba8B
a4Ba2Ba1Ba8Ba4Ba2Ba1Ba8Ba4Ba2Ba1Ba8Ba4Ba2Ba100000000b1b4b3b2P1P2P
4P8P16P32P64P128方案2：时间迭代－部分积左移累加算法乘法器设计方案2：时间迭代－部分积左移累加算法A7 A6
A5 A4 A3 A2 A1 A0M7 M6 M5 M4 M3 M2 M1 M0Q7 Q6 Q5 Q
4可控全加器控制器左移命令右移命令乘数寄存器Q累加寄存器A被乘数寄存器M加命令乘法器设计矩阵乘法一个 m×p 阶的A矩阵与一个p×
n阶的B矩阵相乘得到一个m×n阶的C矩阵（即C=AB）积矩阵C的第i行第j列元素等于矩阵A的第i行向量与矩阵B的第j列向量的内积。
Horner递推形式表示矩阵乘法举例：一个4×4阶的A矩阵与一个4×4阶的B矩阵相乘实现算法 ：单处理机矩阵乘法器2. 二维方阵
结构矩阵乘法器单处理机矩阵乘法器b1x至b4x表示矩阵B的第x列的所有元素；c1x至c4x表示积矩阵C的第x列所有元素同时输出；矩
阵A四行的对应元素同时与B的某列的一个元素相乘。举例：矩阵乘法器单处理机矩阵乘法器的仿真结果二维方阵结构矩阵乘法器VLSI并行结构
特点心动阵列二维方阵结构矩阵乘法器VLSI并行结构特点属于阵列式结构以互连网络为中心是一组由相同的、简单的、规整的计算单元（PE）
连接而成的；计算单元之间的通信应保持局部性可广泛采用流水线技术提高吞吐量心动阵列(Systolic array)由一组简单、重复P
E构成，每个PE执行固定简单操作。每个PE只与相邻的PE有规则连接。除了极少数边界PE外，所有内部PE的构造都是一样的。进入/输出
阵列的数据必须在边界PE进入/输出阵列。心动阵列图中存储器的作用有点象心脏，心脏收缩把血液压入循环系统，经过处理又回到心脏。Sys
tolic在英文里是心脏有节奏地收缩的意思。在心动阵列中，数据从计算机的存储器中有节奏地流出并“压”入阵列，经过许多连成流水线的P
E，沿途得到连续的有效处理。 它把算法中蕴含的操作并行性用由具有同样逻辑功能的PE通过简单的、规则的通讯几何局部地互连起来的阵列来
实现。这样的阵列除了连接几何形状有所变化外，在阵列内，无论输入数据流或结果数据流的速度与方向都有所变化，这是传统的流水线结构所没有
的。在功能上，一个这样的阵列相当于软件中一个含有循环语句的过程。 心动阵列心动阵列可以解决一大类基本计算问题，其中包括绝大部分的矩
阵运算、数字信号与图象处理的计算及许多非数值计算问题。不同的算法有不同阵列结构，同一个算法也可有许多不同的阵列来实现。 局部互连的
约束却使阵列的连接结构为数不多。通常有一维线性、二维正方形、二维六角形、树状、三角状等连接方式 心动阵列心动阵列实质上是一种线性时
间阵列。数据在阵列内的相邻PE之间的运动，时时、处处都用相同的时间单位。因此，任何算法若能在抽象代数空间中找到一种线性表示，就至少
存在着一种心动阵列来实现它。例如，离散傅立叶变换（DFT）的表示是线性的。它的数据运动具有局部性，所以很容易找到其心动阵列实现。
心动阵列免除了形成数据流所需的控制开销。阵列内PE间的局部连接方式，使得阵列中负载均匀、连线极短、最大限度的减少了系统内部的通讯延
时，提高PE的利用率。心动阵列局限通用性差，不同算法不同阵列一个阵列通常只适用于大小确定的问题。解决途径可编程、可重构的PE多个阵
列组合成一个系统心动阵列VLSI设计三个阶段应用问题的表达抽象为数学模型，选择适当的算法并描述它算法到阵列的映射由算法描述到阵列结
构描述硬件实现硬件实现该阵列结构二维方阵结构矩阵乘法器AB=C B和C的元素将分别沿垂直与水平方向自上而下和自左至右有节奏地流动
，A的元素则按它们的原行列顺序存入阵列的相应行列位置上的PE中，每一PE存入矩阵A的一个元素。举例：矩阵乘法器二维方阵矩阵乘法器的仿真结果 |
|
