From 33c6002a778b26ebf7c409d0ceeda17d11d3db73 Mon Sep 17 00:00:00 2001 From: programmerjake Date: Fri, 1 May 2020 01:40:37 +0100 Subject: [PATCH] add prefix sum --- 3d_gpu/architecture/alternative-design-idea.mdwn | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/3d_gpu/architecture/alternative-design-idea.mdwn b/3d_gpu/architecture/alternative-design-idea.mdwn index 0b755f32f..f20f33ac8 100644 --- a/3d_gpu/architecture/alternative-design-idea.mdwn +++ b/3d_gpu/architecture/alternative-design-idea.mdwn @@ -1 +1,13 @@ # TODO(programmerjake) + +Some ideas: + +## Abstract Prefix-sum Class + +We should build a generic class for implementing algorithms that are based on a [parallel Prefix-sum](https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_2:_Work-efficient) except that, instead of numeric addition, any associative binary operator can be used (the operator and the set of possible values makes a mathematical [Semigroup](https://en.wikipedia.org/wiki/Semigroup)). + +Notably, there are algorithms that implement a parallel prefix-sum as a circuit that has a gate depth of O(log N) and has O(N) or O(N*log N) gates. + +Nearly all carry look-ahead circuits are based on that structure, by having the abstract binary operator be a single-bit carry propagation calculation. + +This will allow us to easily implement things like find-first-set-bit, population count, find-second-set-bit, etc., all of which are useful in implementing a load-store unit (as well as arithmetic/logical operations and other scheduling tasks). -- 2.30.2