t******0
发帖数: 629 | 1 小弟最近写东西。想找一些公认的term或者名词来准确表达我的设计。
实现的算法方是N^2的复杂度,即a1,a2,a3..ai...a100，每一个ai需要和与全部这100个
数相乘。所以总共有100x100次乘法运算。
总共算下来，如果只用一个乘法器，一共要10000个周期。
（1）已有的大部分同样领域的VLSI文章：
它们号称有parallel computing，实现方法是用100个乘法器并行地算出每个ai和100数
相乘的乘积，那么只需要100周期就能全部完成。
（2）我们的设计是这样的：
也要号称有parallel computing, 实现方法是事先把100个数分成5个小的数据集，对于
每一个小的数据集用一个乘法器来实现ai与此集中全部20个数相乘，由于这5个乘法器
是并行执行的，所以总共需要20个周期就可以。
这里我没写错，的确是20个周期，而且总共的计算量是20x20x5次乘法，不需要10000次
了。数学算法比较难解释，但是最后需要的结果，以上两种方法的确是一样的，这是我
们这个邪门算法的bonus。
回到正题，VLSI实现中，
（1）是一个Core，这种设计依靠这个core内部的并行乘法器陈列来实现parallelsim，
没有用到这种邪门算法的bonus。
（2）是5个Core，这种设计依靠这种邪门算法的bonus来实现parallelism，每个Core里
有一个乘法器（其实多个也行）。
感觉上，（2）采用的并行计算level比（1）高，但是我找不出一个合理的term来形容
。都叫parallelism，但是我感觉:
（2）叫做algorithm-level parallel 或者 Core-level parallel;（硬件上有并行，
但主要优势在这种算法的bonus上）
(1) 叫做ALU-level parallel 或者 Multiplier-level parallel；（硬件上有并行，
只是加速原算法的一部分，没有利用bonus）
请问没有什么名词来指代区分以上（1）和（2）两种并行技术呢？
我查过Data Parallelsim，Task Parallelism, Thread Parallelsim这些概念，结果发
现很难对上号，也很难直接解释以上区别。 |
k**********g
发帖数: 989 | 2
Is it a variation of the Karatsuba algorithm?
http://en.wikipedia.org/wiki/Karatsuba_algorithm
【在 t******0 的大作中提到】
: 小弟最近写东西。想找一些公认的term或者名词来准确表达我的设计。
: 实现的算法方是N^2的复杂度,即a1,a2,a3..ai...a100，每一个ai需要和与全部这100个
: 数相乘。所以总共有100x100次乘法运算。
: 总共算下来，如果只用一个乘法器，一共要10000个周期。
: （1）已有的大部分同样领域的VLSI文章：
: 它们号称有parallel computing，实现方法是用100个乘法器并行地算出每个ai和100数
: 相乘的乘积，那么只需要100周期就能全部完成。
: （2）我们的设计是这样的：
: 也要号称有parallel computing, 实现方法是事先把100个数分成5个小的数据集，对于
: 每一个小的数据集用一个乘法器来实现ai与此集中全部20个数相乘，由于这5个乘法器
|
t******0
发帖数: 629 | 3 多谢大侠回复。
是machine learning的一种算法，也是QP问题 ：）
其实意思很简单：
（1）一种并行就是一堆乘法器一起计算；
（2）一种是在数据上就分割成小块独立的QP问题，divide-and-conquer，用到了顶层
算法的优势。
如果来用parallelism说事的话，用什么术语能准确地区分（1）和（2）呢？
（1）可以说成是divide-and-conquer吗？
【在 k**********g 的大作中提到】
:
: Is it a variation of the Karatsuba algorithm?
: http://en.wikipedia.org/wiki/Karatsuba_algorithm
|
h*******o
发帖数: 778 | 4 如果还是要做100 x 100次乘法, 楼主第二种算法要5 × 100个乘法器, 要不然不make
sense.
【在 t******0 的大作中提到】
: 小弟最近写东西。想找一些公认的term或者名词来准确表达我的设计。
: 实现的算法方是N^2的复杂度,即a1,a2,a3..ai...a100，每一个ai需要和与全部这100个
: 数相乘。所以总共有100x100次乘法运算。
: 总共算下来，如果只用一个乘法器，一共要10000个周期。
: （1）已有的大部分同样领域的VLSI文章：
: 它们号称有parallel computing，实现方法是用100个乘法器并行地算出每个ai和100数
: 相乘的乘积，那么只需要100周期就能全部完成。
: （2）我们的设计是这样的：
: 也要号称有parallel computing, 实现方法是事先把100个数分成5个小的数据集，对于
: 每一个小的数据集用一个乘法器来实现ai与此集中全部20个数相乘，由于这5个乘法器
|
t******0
发帖数: 629 | 5 谢谢回复。
您的concern我明白，可是具体算法解释起来太麻烦。100X100不是最终的目的。
最终的目的就是找出一条逼近曲线，而我的第二种方法也能达到效果（好像又说远了。
。。）
总而言之，我的第二种方法是用到了一些数学上的特性bonus，从而不用再100x100次乘
法了。
我主要想强调的是，第二种方法输入数据集的根本划分，从而divide and conquer不同
的子问题。（利用的顶层算法的一些magic）
而第一种方法，仍然用的是原来的一个完整数据集，很直观，没有任何magic，就是纯
用100个乘法器并行加速。
make
【在 h*******o 的大作中提到】
: 如果还是要做100 x 100次乘法, 楼主第二种算法要5 × 100个乘法器, 要不然不make
: sense.
|
h*******o
发帖数: 778 | 6 I think it is still data-level parallelism since the same task is working on
different group of data-set. You can say you have proposed a new algorithm
easy for parallel processing by exploiting data-level parallelism.
【在 t******0 的大作中提到】
: 谢谢回复。
: 您的concern我明白，可是具体算法解释起来太麻烦。100X100不是最终的目的。
: 最终的目的就是找出一条逼近曲线，而我的第二种方法也能达到效果（好像又说远了。
: 。。）
: 总而言之，我的第二种方法是用到了一些数学上的特性bonus，从而不用再100x100次乘
: 法了。
: 我主要想强调的是，第二种方法输入数据集的根本划分，从而divide and conquer不同
: 的子问题。（利用的顶层算法的一些magic）
: 而第一种方法，仍然用的是原来的一个完整数据集，很直观，没有任何magic，就是纯
: 用100个乘法器并行加速。
|
l****n
发帖数: 36 | 7 I know someone using the same method accelerating the Montgomery
Multiplication in FPGAs. It is data-level parallelism. |
