Help us understand the problem. What is going on with this article?

unroll と最適化

More than 1 year has passed since last update.

for 文の unroll 意外と使い勝手がある。マクロの代用みたいに使える。common lisp で(あるいは scheme で)マクロの強力さを実感してはいたが、unroll といった限られた形のマクロ展開(と呼んでおこう)が多くの場所で適用可能とは思っていなかった。勿論、その分、回路は大きくなるのだが。

どんな時に有益なのだろうか?

python
for i in unroll(range(8)):
    __h[i] = _h[i]

例えば、上のようなリスト(配列)のコピー。現在の Polyphony はリストの長さによってレジスタを使うか BRAM を使うかを切り分けている。マクロという観点から言うとリスト自身が FF へのマクロと言えるかもしれない。その場合、ここの FF へのアクセスを同時に行えるためunroll することで一気に(最良の場合は 1 clock で)値をコピーすることが出来る。

リストが BRAM である場合は unroll は効かないので、この場合はpipelined (パイプライン化の指示) を使うことになるだろう。

別の例を考える。リストにある数値をすべて足すような場合。Polyphony はどこまで最適化してくれるのだろう?

sum0.py
from polyphony import unroll, pipelined

def sum0(data):
    sum = [0] * 16
    for i in unroll(range(8)):
        sum[i] = data[i] + data[i+8]

    for i in unroll(range(4)):
        sum[i] += sum[i+4]

    for i in unroll(range(2)):
        sum[i] += sum[i+2]

    return sum[0] + sum[1]


import polyphony
from polyphony import testbench

@testbench
def test():
    rv = sum0([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
    print(rv)

test()

まずはなんとなく、自分で最適化もどきを考えてみた。結果は 90 clock(データを準備する時間も入っている)。unroll しないバージョンとそう大差ない。ならば、全部自分で unroll でどうなるかみてみる。

def sum2(data):
    sum01 = data[0] + data[1]
    sum23 = data[2] + data[3]
    sum45 = data[4] + data[5]
    sum67 = data[6] + data[7]
    sum89 = data[8] + data[9]
    sumAB = data[10] + data[11]
    sumCD = data[12] + data[13]
    sumEF = data[14] + data[15]

    sum0123 = sum01 + sum23
    sum4567 = sum45 + sum67
    sum89AB = sum89 + sumAB
    sumCDEF = sumCD + sumEF

    sum0_7 = sum0123 + sum4567
    sum8_F = sum89AB + sumCDEF

    return sum0_7 + sum8_F

これだと 50 clock。しかし、こんなソースは書きたくない。書いてる途中に何度も間違えた。

def sum1(data):
    sum = 0
    for i in unroll(range(16)):
        sum += data[i]

    return sum

開発バージョンの polyphony では上のようなスマートな記述方法が取れる。50 clock。最適化はコンパイラに任せよう。参考までに書くと、コンパイラとしてもっと最適化できることはわかっていて、実験的にではあるが、19 clock まで縮めることができた。データを用意するのに 17 clock かかっているので、関数自体は 2 clock で結果を出すことが出来るという試算だ(もちろん全部FFに載せてという前提)。

現時点で Polyphony の最適化はコンパイラ的にかなりいい線はいっているが吐き出すコードは RTL としてはまだまだあまいところはある。しかし、今後の成長に期待が出来る結果が出始めていることも確かだ。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away