[test-suite] Add Interpolation kernels Using Benchmark Library

[proton]

Summary

This patch adds Interpolation kernels in MicroBenchmarks/ImageProcessing directory
It contains the implementation of bicubic and bilinear interpolation (sources mentioned in corresponding kernel files)
Since there was no license mentioned in either of reference, I have not added any license (but still mentioned them in corresponding kernel files).

Runtime: (Using O3 flag)

Benchmark	Time	CPU	Iterations
BENCHMARK_BICUBIC_INTERPOLATION/16	75 us	75 us	9085
BENCHMARK_BICUBIC_INTERPOLATION/32	379 us	379 us	1877
BENCHMARK_BICUBIC_INTERPOLATION/64	1654 us	1654 us	419
BENCHMARK_BICUBIC_INTERPOLATION/128	6987 us	6988 us	97
BENCHMARK_BICUBIC_INTERPOLATION/256	28686 us	28688 us	24
BENCHMARK_BILINEAR_INTERPOLATION/16	18 us	18 us	39513
BENCHMARK_BILINEAR_INTERPOLATION/32	74 us	74 us	9368
BENCHMARK_BILINEAR_INTERPOLATION/64	294 us	294 us	2352
BENCHMARK_BILINEAR_INTERPOLATION/128	1191 us	1191 us	571
BENCHMARK_BILINEAR_INTERPOLATION/256	4969 us	4969 us	127

Runtime with and without Polly is same

[Meinersbur]

LGTM

test-suite/trunk/MicroBenchmarks/ImageProcessing/CMakeLists.txt

 add_subdirectory(Dither)
 add_subdirectory(AnisotropicDiffusion)
+add_subdirectory(Interpolation)
 add_subdirectory(Blur)

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/CMakeLists.txt

+set(IMAGEPROC_UTILS MicroBenchmarks/ImageProcessing/utils)
+list(APPEND CPPFLAGS -I ${CMAKE_SOURCE_DIR}/${IMAGEPROC_UTILS} -std=c++11)
+
+llvm_test_verify("${CMAKE_SOURCE_DIR}/HashProgramOutput.sh ${CMAKE_CURRENT_BINARY_DIR}/bicubicOutput.txt")
+llvm_test_verify("${FPCMP} ${CMAKE_CURRENT_BINARY_DIR}/bicubicOutput.txt ${CMAKE_CURRENT_SOURCE_DIR}/bicubic.reference_output")
+
+llvm_test_verify("${CMAKE_SOURCE_DIR}/HashProgramOutput.sh ${CMAKE_CURRENT_BINARY_DIR}/bilinearOutput.txt")
+llvm_test_verify("${FPCMP} ${CMAKE_CURRENT_BINARY_DIR}/bilinearOutput.txt ${CMAKE_CURRENT_SOURCE_DIR}/bilinear.reference_output")
+
+llvm_test_run(WORKDIR ${CMAKE_CURRENT_BINARY_DIR})
+llvm_test_executable(Interpolation bicubicKernel.c bilinearKernel.c main.cpp ../utils/ImageHelper.cpp ../utils/glibc_compat_rand.c)
+
+target_link_libraries(Interpolation benchmark)

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/bicubic.reference_output

+289aae9408984be189aa2c8dfec4cdc7

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/bicubicKernel.c

+/** This is a modified version of serial/bicubicInterpolation.cpp of
+ * https://github.com/srijanmishra/parallel-bicubic-interpolation
+ *
+ * Modified by
+ * Pankaj Kukreja (github.com/proton0001)
+ * Indian Institute of Technology Hyderabad
+ */
+#include "interpolation.h"
+void bicubicKernel(int height, int width, int inputImage[HEIGHT][WIDTH],
+                   int outputImage[ZOOM * height][ZOOM * width]) {
+  int f = ZOOM;
+  int newheight = f * height;
+  int newwidth = f * width;
+  double arr[4][4];
+  for (int i = 0; i < newheight - 3 * f; i++) {
+    for (int j = 0; j < newwidth - 3 * f; j++) {
+      // for row offset
+      for (int l = 0; l < 4; l++) {
+        // for column offset
+        for (int k = 0; k < 4; k++) {
+          arr[l][k] = inputImage[i / f + l][j / f + k];
+        }
+      }
+      double x = (double)(i % f) / f;
+      double y = (double)(j % f) / f;
+      double arr2[4];
+      arr2[0] = arr[0][1] + 0.5 * y *
+                                (arr[0][2] - arr[0][0] +
+                                 y * (2.0 * arr[0][0] - 5.0 * arr[0][1] +
+                                      4.0 * arr[0][2] - arr[0][3] +
+                                      y * (3.0 * (arr[0][1] - arr[0][2]) +
+                                           arr[0][3] - arr[0][0])));
+      arr2[1] = arr[1][1] + 0.5 * y *
+                                (arr[1][2] - arr[1][0] +
+                                 y * (2.0 * arr[1][0] - 5.0 * arr[1][1] +
+                                      4.0 * arr[1][2] - arr[1][3] +
+                                      y * (3.0 * (arr[1][1] - arr[1][2]) +
+                                           arr[1][3] - arr[1][0])));
+      arr2[2] = arr[2][1] + 0.5 * y *
+                                (arr[2][2] - arr[2][0] +
+                                 y * (2.0 * arr[2][0] - 5.0 * arr[2][1] +
+                                      4.0 * arr[2][2] - arr[2][3] +
+                                      y * (3.0 * (arr[2][1] - arr[2][2]) +
+                                           arr[2][3] - arr[2][0])));
+      arr2[3] = arr[3][1] + 0.5 * y *
+                                (arr[3][2] - arr[3][0] +
+                                 y * (2.0 * arr[3][0] - 5.0 * arr[3][1] +
+                                      4.0 * arr[3][2] - arr[3][3] +
+                                      y * (3.0 * (arr[3][1] - arr[3][2]) +
+                                           arr[3][3] - arr[3][0])));
+      outputImage[i][j] =
+          arr2[1] +
+          0.5 * x *
+              (arr2[2] - arr2[0] +
+               x * (2.0 * arr2[0] - 5.0 * arr2[1] + 4.0 * arr2[2] - arr2[3] +
+                    x * (3.0 * (arr2[1] - arr2[2]) + arr2[3] - arr2[0])));
+    }
+  }
+}

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/bilinear.reference_output

+9ab422ac2cb253fdd6687fa1cd009006

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/bilinearKernel.c

+/**
+  Source: github ->
+  https://github.com/yglukhov/bicubic-interpolation-image-processing/blob/master/libimage.c
+
+  Modifications by
+  Pankaj Kukreja (github.com/proton0001)
+  Indian Institute of Technology Hyderabad
+*/
+#include "interpolation.h"
+
+void bilinearKernel(int height, int width, int inputImage[HEIGHT][WIDTH],
+                    int outputImage[ZOOM * height][ZOOM * width]) {
+  int x, y;
+
+  float x_diff, y_diff;
+  int i, j;
+
+  int newheight = ZOOM * height;
+  int newwidth = ZOOM * width;
+
+  for (i = 0; i < newheight; i++) {
+    for (j = 0; j < newwidth; j++) {
+      x = j / ZOOM;
+      y = i / ZOOM;
+
+      x_diff = ((j / (float)ZOOM) - x);
+      y_diff = ((i / (float)ZOOM) - y);
+      if ((x + 1) < width && (y + 1) < height) {
+        outputImage[i][j] = inputImage[y][x] * (1 - x_diff) * (1 - y_diff) +
+                            inputImage[y][x + 1] * (1 - y_diff) * (x_diff) +
+                            inputImage[y + 1][x] * (y_diff) * (1 - x_diff) +
+                            inputImage[y + 1][x + 1] * (y_diff) * (x_diff);
+      } else if ((x + 1) < width) {
+        outputImage[i][j] = inputImage[y][x] * (1 - x_diff) * (1 - y_diff) +
+                            inputImage[y][x + 1] * (1 - y_diff) * (x_diff);
+      } else {
+        outputImage[i][j] = inputImage[y][x] * (1 - x_diff) * (1 - y_diff);
+      }
+    }
+  }
+}

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/interpolation.h

+/**
+  Pankaj Kukreja
+  github.com/proton0001
+  Indian Institute of Technology Hyderabad
+*/
+#ifndef _INTERPOLATION_H_
+#define _INTERPOLATION_H_
+
+#define HEIGHT 256
+#define WIDTH 256
+
+// 4x zoom
+#define ZOOM 4
+
+#endif /* _INTERPOLATION_H_ */

test-suite/trunk/MicroBenchmarks/ImageProcessing/Interpolation/main.cpp

+/**
+  Pankaj Kukreja
+  github.com/proton0001
+  Indian Institute of Technology Hyderabad
+*/
+#include "ImageHelper.h"
+#include "interpolation.h"
+#include <iostream> // std::cerr
+
+#define BENCHMARK_LIB
+#ifdef BENCHMARK_LIB
+#include "benchmark/benchmark.h"
+#endif
+
+extern "C" void bicubicKernel(int height, int width, int *inpImage,
+                              int *outImage);
+extern "C" void bilinearKernel(int height, int width, int *inpImage,
+                               int *outImage);
+
+int *inputImage;
+int main(int argc, char **argv) {
+#ifdef BENCHMARK_LIB
+  ::benchmark::Initialize(&argc, argv);
+#endif
+
+  const char *bicubicOutputFilename = (const char *)"./bicubicOutput.txt";
+  const char *bilinearOutputFileName = (const char *)"./bilinearOutput.txt";
+
+  inputImage = (int *)malloc(sizeof(int) * (HEIGHT) * (WIDTH));
+
+  if (inputImage == NULL) {
+    std::cerr << "Insufficient memory\n";
+    exit(1);
+  }
+
+  initializeRandomImage(inputImage, HEIGHT, WIDTH);
+
+#ifdef BENCHMARK_LIB
+  ::benchmark::RunSpecifiedBenchmarks();
+#endif
+
+  int outputHeight = ZOOM * HEIGHT;
+  int outputWidth = ZOOM * HEIGHT;
+
+  int *outputImage =
+      (int *)malloc(sizeof(int) * (outputHeight) * (outputWidth));
+
+  if (outputImage == NULL) {
+    std::cerr << "Insufficient memory\n";
+    exit(1);
+  }
+
+  for (int i = 0; i < outputHeight; i++) {
+    for (int j = 0; j < outputWidth; j++) {
+      outputImage[i * outputWidth + j] = 0;
+    }
+  }
+
+  bicubicKernel(HEIGHT, WIDTH, inputImage, outputImage);
+  saveImage(outputImage, bicubicOutputFilename, outputHeight, outputWidth);
+
+  for (int i = 0; i < outputHeight; i++) {
+    for (int j = 0; j < outputWidth; j++) {
+      outputImage[i * outputWidth + j] = 0;
+    }
+  }
+
+  bilinearKernel(HEIGHT, WIDTH, inputImage, outputImage);
+  saveImage(outputImage, bilinearOutputFileName, outputHeight, outputWidth);
+
+  free(inputImage);
+  free(outputImage);
+  return 0;
+}
+
+#ifdef BENCHMARK_LIB
+void BENCHMARK_BICUBIC_INTERPOLATION(benchmark::State &state) {
+  int inputHeight = state.range(0);
+  int inputWidth = state.range(0);
+  int outputHeight = ZOOM * inputHeight;
+  int outputWidth = ZOOM * inputWidth;
+
+  int *outputImage = (int *)malloc(sizeof(int) * outputHeight * outputWidth);
+
+  if (outputImage == NULL) {
+    std::cerr << "Insufficient memory\n";
+    exit(1);
+  }
+  /* This call is to warm up the cache */
+  bicubicKernel(inputHeight, inputWidth, inputImage, outputImage);
+
+  for (auto _ : state) {
+    bicubicKernel(inputHeight, inputWidth, inputImage, outputImage);
+  }
+
+  /* Since we are not passing state.range as 20 this if case will always be
+   * false.
+   * This call is to prevent above function calls from getting optimized out
+   */
+  if (state.range(0) == 20) {
+    saveImage(outputImage, (const char *)"failedCase.txt", outputHeight,
+              outputWidth);
+  }
+
+  free(outputImage);
+}
+BENCHMARK(BENCHMARK_BICUBIC_INTERPOLATION)
+    ->Arg(16)
+    ->Arg(32)
+    ->Arg(64)
+    ->Arg(128)
+    ->Arg(256)
+    ->Unit(benchmark::kMicrosecond);
+
+void BENCHMARK_BILINEAR_INTERPOLATION(benchmark::State &state) {
+  int inputHeight = state.range(0);
+  int inputWidth = state.range(0);
+  int outputHeight = ZOOM * inputHeight;
+  int outputWidth = ZOOM * inputWidth;
+  int *outputImage = (int *)malloc(sizeof(int) * outputHeight * outputWidth);
+
+  if (outputImage == NULL) {
+    std::cerr << "Insufficient memory\n";
+    exit(1);
+  }
+  /* This call is to warm up the cache */
+  bilinearKernel(inputHeight, inputWidth, inputImage, outputImage);
+
+  for (auto _ : state) {
+    bilinearKernel(inputHeight, inputWidth, inputImage, outputImage);
+  }
+
+  /* Since we are not passing state.range as 20 this if case will always be
+   * false.
+   * This call is to prevent above function calls from getting optimized out
+   */
+  if (state.range(0) == 20) {
+    saveImage(outputImage, (const char *)"failedCase.txt", outputHeight,
+              outputWidth);
+  }
+
+  free(outputImage);
+}
+BENCHMARK(BENCHMARK_BILINEAR_INTERPOLATION)
+    ->Arg(16)
+    ->Arg(32)
+    ->Arg(64)
+    ->Arg(128)
+    ->Arg(256)
+    ->Unit(benchmark::kMicrosecond);
+
+#endif
 No newline at end of file