[Libre-soc-bugs] [Bug 238] POWER Compressed Formal Standard writeup

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=238

--- Comment #139 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Jacob Lifshay from comment #138)
> (In reply to Alexandre Oliva from comment #137)
> > what that arrangement does is to avoid having to work out the dependencies
> > in full, and avoid cascading dependencies.  it trades working out and
> > optimizing the actual dependencies, possibly simplified by O(n) cascading,
> > for O(2^n) parallel-precomputing gates, followed by O(log n) selection and
> > aggregation.
> 
> Please read the code again, you will find that the total gate count is O(N +
> N * log N) == O(N * log N), with O(log N) circuit depth.

phase 1: predecode O(N) gates, O(1) depth

phase 2: prefix-sum O(N * log N) gates, O(log N) depth

phase 3: not included in example but should be O(N * log N) gate count, O(log
N) depth

-- 
You are receiving this mail because:
You are on the CC list for the bug.