Re: [riscv-xbitmanip] Abridged summary of riscv-xbitmanip@googlegroups.com - 1 update in 1 topic

[Allen Baum]

My major concern for free and bit gather/scatter was prior art/ IP issues. 

We need to have that very clearly documented if we are going to include them (E.g. the prior art must be > 20 years old and clearly applicable). I found some references to "private email" on the web, but that isn't good enough.

-Allen

On Apr 9, 2018, at 12:35 PM, riscv-x...@googlegroups.com wrote:

riscv-x...@googlegroups.com

Google Groups

Today's topic summary
View all topics

• Update: XBitmanip Draft Spec on GitHub - 1 Update

Update: XBitmanip Draft Spec on GitHub

Clifford Wolf <cliffor...@gmail.com>: Apr 08 10:46AM -0700 Hi,   a big update:   The current version of the draft spec can now be found on github: https://github.com/cliffordwolf/xbitmanip   I've cleaned it up a lot, removed the bits relating to the ...more

Back to top

You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to riscv-xbitman...@googlegroups.com.

[Clifford Wolf]

Hi,

On Tuesday, April 10, 2018 at 12:42:53 AM UTC+2, Allen Baum wrote:

My major concern for free and bit gather/scatter was prior art/ IP issues. 

We need to have that very clearly documented if we are going to include them (E.g. the prior art must be > 20 years old and clearly applicable). I found some references to "private email" on the web, but that isn't good enough.

First: I absolutely agree, however, I am not a patent lawyer, so I'm not really qualified to do that (or, better said, since I'm not a patent lawyer my conclusions are not worth much here).

That being said, I think there are in fact three different questions: (1) The bext/bdep instructions per se, (2) using butterfly circuits to implement them, and (3) using a GRPR circuit to configure the butterfly circuits.

I don't think that bext/bdep per se are even patentable. (At least I'm pretty sure they would not be under European patent law). They are not a technical solution, they are a problem statement. It would be like patenting "flying car". You can't. You can only patent the mechanism that makes your car fly, i.e. the solution to the question "how can we make a car fly". Similarly the description of what the bext/bdep instruction does is trivial. The only thing that might be protected by a patent could be a concrete method for implementing those instructions.

I have a few reference implementations on https://github.com/cliffordwolf/bextdep. Not all of them are even using butterfly circuits. The ones that do use a GRPR circuit to configure them.

Re the use of butterfly circuits: Gauss used butterflies in what is now essentially known as Cooley-Tukey Radix-2 FFT in the early 19th century. I don't know when butterflies were first used for bit permutations, but this must also be around for ages now. So using butterflies to implement bext/bdep should not be an issue and there must be plenty of prior art around.

Lastly there is the GRPR circuit. This might be the only problem because I think the original invention of them is from around 2004 (Hilewitz). But there are two things noteworthy about them:

First you don't really need the GRPR circuit for small butterflies. In those cases you can also produce the control signal using a brute-force search that results in a truth table and then just run logic synthesis on that truth table. I've made some experiments along those lines last year and the results were looking promising. The "sequential" implementations in my collection of implementations use such smaller butterflies and thus you don't really need to construct a GRPR circuit to control those butterflies.

And second, I did search for patents on the GRPR circuit last year and all I could find was a patent from Hilewitz. But it was filed even *after* his 2006 paper was published. And arguably the 2004 paper already contains everything one needs to implement bext/bdep using butterflies and GRPR, but the 2006 paper obviously contains all the required information. Since he published that work in the ASAP'06 Proceedings before filing a patent I don't see how that patent could be enforceable. (My guess would be that not he filed that patent but his university did. At least the whole thing looks like that to me.)

So that is where we are right now. Maybe it would be a good idea to simply contact Hilewitz and ask his opinion?

regards,

 - clifford