From 44a13479195a591b436d28efada8953b3cff36ba Mon Sep 17 00:00:00 2001 From: Eric Kunze Date: Thu, 12 Aug 2021 11:01:14 -0700 Subject: Add FFT operators to MI/MT profiles Adds FFT2D for complex->complex FFT Adds RFFT2D for real->complex FFT Change-Id: Id50f96b8f66f17c3020767c002f0c1f41a76d62e Signed-off-by: Eric Kunze --- Makefile | 10 +- chapters/pseudocode.adoc | 12 ++ chapters/tensor_ops.adoc | 112 +++++++++++++++++ figures/forward_fft2d.svg | 312 ++++++++++++++++++++++++++++++++++++++++++++++ figures/inverse_fft2d.svg | 306 +++++++++++++++++++++++++++++++++++++++++++++ tools/dictionary.dic | 6 + tools/get_descriptions.py | 3 + tosa_spec.adoc | 1 + 8 files changed, 760 insertions(+), 2 deletions(-) create mode 100644 figures/forward_fft2d.svg create mode 100644 figures/inverse_fft2d.svg diff --git a/Makefile b/Makefile index cbbbe6a..b7cd640 100644 --- a/Makefile +++ b/Makefile @@ -22,23 +22,29 @@ COMMON_ARGS= -a revnumber="$(TOSAREVISION)" SPECSRC := tosa_spec.adoc ADOCFILES = $(wildcard chapters/[A-Za-z]*.adoc) SPECFILES = $(ADOCFILES) tosa.css +FIGURES = $(wildcard figures/*.svg) .DELETE_ON_ERROR: -.PHONY: all html pdf clean spell +.PHONY: all html pdf clean spell copy_html_figures all: spell html pdf -html: $(HTMLDIR)/tosa_spec.html +html: copy_html_figures $(HTMLDIR)/tosa_spec.html pdf: $(PDFDIR)/tosa_spec.pdf clean: $(RM) $(HTMLDIR)/tosa_spec.html + rm -rf $(HTMLDIR)/figures $(RM) $(PDFDIR)/tosa_spec.pdf spell: out/spell.txt +copy_html_figures: $(FIGURES) + $(MKDIR) -p $(HTMLDIR)/figures + cp $(FIGURES) $(HTMLDIR)/figures + .PRECIOUS: out/spell.txt out/spell.txt: $(ADOCFILES) FORCE @echo Running spell check diff --git a/chapters/pseudocode.adoc b/chapters/pseudocode.adoc index d22d180..993c6e7 100644 --- a/chapters/pseudocode.adoc +++ b/chapters/pseudocode.adoc @@ -212,4 +212,16 @@ int32_t tensor_size(int32_t input[]) { } return size; } + +float_t pi() + returns value of pi + +float_t sin(angle) + return sine of angle given in radians + +float_t cos(angle) + return cosine of angle given in radians + +bool power_of_two(int32_t value) + return true if value is a power of two, false otherwise ---- diff --git a/chapters/tensor_ops.adoc b/chapters/tensor_ops.adoc index 47768d4..b3f6f5a 100644 --- a/chapters/tensor_ops.adoc +++ b/chapters/tensor_ops.adoc @@ -333,6 +333,70 @@ for_each(0 <= n(input_real, [N,H,W], [n,iy,ix]); + in_out_t val_imag = tensor_read(input_imag, [N,H,W], [n,iy,ix]); + float_t a = sign_val * 2 * pi() * ((iy * oy) / H + (ix * ox) / W); + sum_real += val_real * cos(a) + val_imag * sin(a); + sum_imag += -val_real * sin(a) + val_imag * cos(a); + } + tensor_write(output_real, [N,H,W], [n,oy,ox], sum_real); + tensor_write(output_imag, [N,H,W], [n,oy,ox], sum_imag); +} +---- + +*Supported Data Types:* + +|=== +|Profile|Mode|in_out_t +|MI,MT|floating-point|float +|=== + ==== FULLY_CONNECTED Performs a fully connected network. @@ -479,6 +543,54 @@ for_each(0 <= n < N, 0 <= oy < H, 0 <= ox < W, 0 <= c < C ) { |MI, MT|floating-point|float_t |=== +==== RFFT2D + +Performs a batched 2D real-valued Fast Fourier Transform over the input where the input tensor consists of real values producing complex valued output. +The complex output values will be split into the output_real and output_imag tensor arguments. +RFFT2D takes advantage of Hermitian symmetry to only calculate the first half of the output. +Imaginary values with locations h=0,H/2 or w=0,W/2 are zero. + +image::forward_fft2d.svg["forward FFT definition", align="center"] + +*Arguments:* + +|=== +|Argument|Type|Name|Shape|Description + +|Input|in_out_t*|input|[N,H,W]|Real input. H,W must be powers of two. +|Output|in_out_t*|output_real|[N,H/2 + 1,W/2 + 1]|Real part of the complex output +|Output|in_out_t*|output_imag|[N,H/2 + 1,W/2 + 1]|Imaginary part of the complex output. +|=== + +*Operation Function* + +[source,c++] +---- +ERROR_IF(!power_of_two(H)); +ERROR_IF(!power_of_two(W)); + +for_each(0 <= n < N, 0 <= oy < H/2 + 1, 0 <= ox < W/2 + 1) { + in_out_t sum_real = 0.0; + in_out_t sum_imag = 0.0; + for_each(0 <= iy < H, 0 <= ix < W) { + in_out_t val_real = tensor_read(input_real, [N,H,W], [n,iy,ix]); + float_t a = 2 * pi() * ((iy * oy) / H + (ix * ox) / W); + sum_real += val_real * cos(a); + sum_imag += -val_real * sin(a); + } + tensor_write(output_real, [N,H,W], [n,oy,ox], sum_real); + tensor_write(output_imag, [N,H,W], [n,oy,ox], sum_imag); +} +---- + +*Supported Data Types:* + +|=== +|Profile|Mode|in_out_t +|MI,MT|floating-point|float +|=== + + ==== TRANSPOSE_CONV2D Performs a 2D transposed convolution over the given tensor input, using the weights tensor. diff --git a/figures/forward_fft2d.svg b/figures/forward_fft2d.svg new file mode 100644 index 0000000..e012656 --- /dev/null +++ b/figures/forward_fft2d.svg @@ -0,0 +1,312 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/figures/inverse_fft2d.svg b/figures/inverse_fft2d.svg new file mode 100644 index 0000000..59a9f26 --- /dev/null +++ b/figures/inverse_fft2d.svg @@ -0,0 +1,306 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tools/dictionary.dic b/tools/dictionary.dic index 94ef782..29be61e 100644 --- a/tools/dictionary.dic +++ b/tools/dictionary.dic @@ -20,10 +20,14 @@ CPUs denormalizing DEPTHWISE Elementwise +FFT +fft foreach Fulbourn GPUs Hadamard +Hermitian +imag INTDIV licence Licence @@ -49,12 +53,14 @@ README Rescale RESCALE rescaled +RFFT RSQRT sigmoid Sigmoid SIGMOID SIMD subtensor +svg tanh TANH TensorFlow diff --git a/tools/get_descriptions.py b/tools/get_descriptions.py index 3f2ee05..beded87 100755 --- a/tools/get_descriptions.py +++ b/tools/get_descriptions.py @@ -49,5 +49,8 @@ for name in args.filenames: # not useful there if re.match(r'[\[\*]', text): in_description = False + # skip comments + elif re.match(r'\w*\/\/', text): + continue else: print(text) diff --git a/tosa_spec.adoc b/tosa_spec.adoc index 130d98e..1b4eecd 100644 --- a/tosa_spec.adoc +++ b/tosa_spec.adoc @@ -12,6 +12,7 @@ :toc: left :toclevels: 3 :source-highliter: coderay +:imagesdir: figures include::chapters/tosa_license.adoc[] -- cgit v1.2.1