[Libre-soc-dev] DCT/FFT augmentations

[Hendrik Boom]

On Fri, Jul 02, 2021 at 11:27:33PM +0100, Luke Kenneth Casson Leighton wrote:
> On 7/2/21, Hendrik Boom <hendrik at topoi.pooq.com> wrote:
> 
> > Just a note:  interpreting + as 'or', and * as 'and',
> > operating on Boolean matrices,
> > and having result, X, and Y be the exact same matrix,
> > updated while being used,
> > gives the traditional Warshall transitive-closure
> > algorithm, if the loops are nested exactly in thie order.
> 
> nice.
> 
> we'd need a triple boolean logic
> instruction to do it... oh wait! the ternary instruction!
> 
> this can handle 3 operands in with all possible permutations of all
> possible boolean logic combinations between 3 operands.
> 
> > And probably a truckload of read-write conflicts.
> 
> the priority is i j on the result as inner loops, so it's ok.

Rearranging and inserting a branch,

    for k in range(len(Y)):       # ydim2                                     
        for i in range(len(X)):              # ydim1                          
           if X[i][k]
              for j in range(len(Y[0])):        # xdim2                          
                 result[i][j] += Y[k][j]

we arrive at a formulation that allows collapsing the boolean
array into 64-bit words in the j-direction.  I suspect this
is also a speed-up, but one that doesn't mesh well with 
collapsing multiple loops into a single instruction.

-- hendrik
 

> 
> read is fine, it's writes that you have to be careful about.
> 
> my other favourite one is GF(2^N) equivalent of mul-and-add.
> 
> this is how Rijndael MixColumns can be done in its original
> mathematical form, with GF(2^8)
> 
> i'll make a note about the Warshall algorithm.
> 
> thank you Hendrik.
> 
> l.
> 
> _______________________________________________
> Libre-soc-dev mailing list
> Libre-soc-dev at lists.libre-soc.org
> http://lists.libre-soc.org/mailman/listinfo/libre-soc-dev