openpower/sv/test_preduce.py

   1 # source code of yield-based parallel reduction schedule:
   2 # https://git.libre-soc.org/?p=libreriscv.git;a=blob;f=openpower/sv/preduce.py;hb=HEAD
   3 from preduce import preduce_y
   4 from copy import copy
   5
   6 def preduce(vl, vec, pred):
   7     vec = copy(vec)
   8     step = 1
   9     print(" start", step, pred, vec)
  10     while step < vl:
  11         step *= 2
  12         for i in range(0, vl, step):
  13             other = i + step // 2
  14             other_pred = other < vl and pred[other]
  15             if pred[i] and other_pred:
  16                 vec[i] += vec[other]
  17             elif other_pred:
  18                 vec[i] = vec[other]
  19         print("   row", step, pred, vec)
  20     return vec
  21
  22
  23 def preducei(vl, vec, pred):
  24     vec = copy(vec)
  25     step = 1
  26     ix = list(range(vl)) # indices move rather than copy data
  27     print(" start", step, pred, vec)
  28     while step < vl:
  29         step *= 2
  30         for i in range(0, vl, step):
  31             other = i + step // 2
  32             ci = ix[i]
  33             oi = ix[other] if other < vl else None
  34             other_pred = other < vl and pred[oi]
  35             if pred[ci] and other_pred:
  36                 vec[ci] += vec[oi]
  37             elif other_pred:
  38                 ix[i] = oi # leave data in-place, copy index instead
  39         print("   row", step, pred, vec, ix)
  40     return vec
  41
  42
  43
  44 if __name__ == '__main__':
  45     vec = [1, 2, 3, 4, 9, 5, 6]
  46     prd = [0, 1, 1, 1, 0, 0, 1]
  47     print (vec)
  48     res = preduce(len(vec), vec, prd)
  49     print (res)
  50     res2 = preducei(len(vec), vec, prd)
  51     print (res2)
  52     print ()
  53     preduce_y(len(vec), vec, prd)
  54     print (vec)
  55     print ()
  56     assert vec == res2
  57
  58     vec = [1, 2, 3, 4, 9, 5, 6]
  59     prd = [1, 0, 0, 1, 1, 0, 1]
  60     print (vec)
  61     res = preduce(len(vec), vec, prd)
  62     print (res)
  63     res2 = preducei(len(vec), vec, prd)
  64     print (res2)
  65     print ()
  66     preduce_y(len(vec), vec, prd)
  67     print (vec)
  68     print ()
  69     assert vec == res2
  70
  71     vec = [1, 2, 3, 4, 9, 5, 6, 8]
  72     prd = [0, 0, 0, 0, 1, 1, 1, 1]
  73     print (vec)
  74     res = preduce(len(vec), vec, prd)
  75     print (res)
  76     res2 = preducei(len(vec), vec, prd)
  77     print (res2)
  78     print ()
  79     preduce_y(len(vec), vec, prd)
  80     print (vec)
  81     print ()
  82     assert vec == res2
  83
  84     vec = [1, 2, 3, 4, 9, 5, 6, 8]
  85     prd = [0, 1, 0, 0, 0, 1, 0, 1]
  86     print (vec)
  87     res = preduce(len(vec), vec, prd)
  88     print (res)
  89     res2 = preducei(len(vec), vec, prd)
  90     print (res2)
  91     print ()
  92     preduce_y(len(vec), vec, prd)
  93     print (vec)
  94     print ()
  95     assert vec == res2
  96
  97     vec = [1, 2, 3, 4, 9, 5, 6]
  98     prd = [1, 0, 1, 1, 0, 0, 1]
  99     print (vec)
 100     res = preduce(len(vec), vec, prd)
 101     print (res)
 102     res2 = preducei(len(vec), vec, prd)
 103     print (res2)
 104     print ()
 105     preduce_y(len(vec), vec, prd)
 106     print (vec)
 107     print ()
 108     assert vec == res2
 109
 110     vec = [1, 2, 3, 4, 9, 5, 6]
 111     prd = [1, 1, 1, 1, 1, 1, 1]
 112     print (vec)
 113     res = preduce(len(vec), vec, prd)
 114     print (res)
 115     res2 = preducei(len(vec), vec, prd)
 116     print (res2)
 117     print ()
 118     preduce_y(len(vec), vec, prd)
 119     print (vec)
 120     print ()
 121     assert vec == res2
 122