Add FFT benchmark

6 files changed, 278 insertions, 4 deletions

diff --git a/hardinfo2/Makefile.in b/hardinfo2/Makefile.in
index 58423f2a..b8dc28b9 100644
--- a/hardinfo2/Makefile.in
+++ b/hardinfo2/Makefile.in
@@ -9,7 +9,7 @@ CCSLOW = gcc -O0 -g
 OBJECTS = hardinfo.o shell.o util.o iconcache.o loadgraph.o  \
 		menu.o stock.o callbacks.o expr.o report.o binreloc.o \
 		vendor.o socket.o syncmanager.o
-BENCHMARK_OBJECTS = fbench.o sha1.o blowfish.o md5.o nqueens.o
+BENCHMARK_OBJECTS = fbench.o sha1.o blowfish.o md5.o nqueens.o fftbench.o
 
 MODULES = computer.so devices.so benchmark.so network.so
 
diff --git a/hardinfo2/arch/common/fft.h b/hardinfo2/arch/common/fft.h
new file mode 100644
index 00000000..62daa9fe
--- /dev/null
+++ b/hardinfo2/arch/common/fft.h
@@ -0,0 +1,47 @@
+/*
+ *    HardInfo - Displays System Information
+ *    Copyright (C) 2003-2007 Leandro A. F. Pereira <leandro@hardinfo.org>
+ *
+ *    This program is free software; you can redistribute it and/or modify
+ *    it under the terms of the GNU General Public License as published by
+ *    the Free Software Foundation, version 2.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU General Public License for more details.
+ *
+ *    You should have received a copy of the GNU General Public License
+ *    along with this program; if not, write to the Free Software
+ *    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ */
+
+#include <fftbench.h>
+
+static gpointer fft_for(unsigned int start, unsigned int end, void *data, GTimer *timer)
+{
+    unsigned int i;
+    
+    for (i = start; i <= end; i++) { 
+        fft_bench_start();
+    }
+    
+    return NULL;
+}
+
+static void
+benchmark_fft(void)
+{
+    gdouble elapsed = 0;
+    
+    shell_view_set_enabled(FALSE);
+    shell_status_update("Running FFT benchmark...");
+        
+    fft_bench_init();
+    elapsed = benchmark_parallel_for(0, 4, fft_for, NULL);
+    fft_bench_finish();
+    
+    bench_results[BENCHMARK_FFT] = elapsed;
+}
+
+
diff --git a/hardinfo2/benchmark.c b/hardinfo2/benchmark.c
index d03ce531..f115afe5 100644
--- a/hardinfo2/benchmark.c
+++ b/hardinfo2/benchmark.c
@@ -26,6 +26,7 @@
 #include <sys/resource.h>
 
 enum {
+    BENCHMARK_FFT,
     BENCHMARK_FIB,
     BENCHMARK_CRYPTOHASH,
     BENCHMARK_BLOWFISH,
@@ -34,12 +35,14 @@ enum {
     BENCHMARK_N_ENTRIES
 } Entries;
 
+void scan_fft(gboolean reload);
 void scan_raytr(gboolean reload);
 void scan_bfsh(gboolean reload);
 void scan_cryptohash(gboolean reload);
 void scan_fib(gboolean reload);
 void scan_nqueens(gboolean reload);
 
+gchar *callback_fft();
 gchar *callback_raytr();
 gchar *callback_bfsh();
 gchar *callback_fib();
@@ -47,10 +50,11 @@ gchar *callback_cryptohash();
 gchar *callback_nqueens();
 
 static ModuleEntry entries[] = {
-    {"CPU Fibonacci", "nautilus.png", callback_fib, scan_fib},
-    {"CPU CryptoHash", "cryptohash.png", callback_cryptohash, scan_cryptohash},
     {"CPU Blowfish", "blowfish.png", callback_bfsh, scan_bfsh},
+    {"CPU CryptoHash", "cryptohash.png", callback_cryptohash, scan_cryptohash},
+    {"CPU Fibonacci", "nautilus.png", callback_fib, scan_fib},
     {"CPU N-Queens", "nqueens.png", callback_nqueens, scan_nqueens},
+    {"FPU FFT", "fft.png", callback_fft, scan_fft},
     {"FPU Raytracing", "raytrace.png", callback_raytr, scan_raytr},
     {NULL}
 };
@@ -118,7 +122,7 @@ gdouble benchmark_parallel_for(guint start, guint end,
         DEBUG("launching thread %d", 1 + (iter / iter_per_core));
         
         pbt->start    = iter == 0 ? 0 : iter + 1;
-        pbt->end      = iter + iter_per_core;
+        pbt->end      = iter + iter_per_core - 1;
         pbt->data     = callback_data;
         pbt->callback = callback;
         
@@ -222,6 +226,13 @@ static gdouble bench_results[BENCHMARK_N_ENTRIES];
 #include <arch/common/blowfish.h>
 #include <arch/common/raytrace.h>
 #include <arch/common/nqueens.h>
+#include <arch/common/fft.h>
+
+gchar *callback_fft()
+{
+    return benchmark_include_results(bench_results[BENCHMARK_FFT],
+				     "CPU FFT");
+}
 
 gchar *callback_nqueens()
 {
@@ -261,6 +272,13 @@ gchar *callback_fib()
     setpriority(PRIO_PROCESS, 0, old_priority);		\
   } while (0);
 
+void scan_fft(gboolean reload)
+{
+    SCAN_START();
+    RUN_WITH_HIGH_PRIORITY(benchmark_fft);
+    SCAN_END();
+}
+
 void scan_nqueens(gboolean reload)
 {
     SCAN_START();
diff --git a/hardinfo2/fftbench.c b/hardinfo2/fftbench.c
new file mode 100644
index 00000000..597c5693
--- /dev/null
+++ b/hardinfo2/fftbench.c
@@ -0,0 +1,201 @@
+/*
+    fftbench.c
+
+    Written by Scott Robert Ladd (scott@coyotegulch.com)
+    No rights reserved. This is public domain software, for use by anyone.
+
+    A number-crunching benchmark using LUP-decomposition to solve a large
+    linear equation.
+
+    The code herein is design for the purpose of testing computational
+    performance; error handling is minimal.
+    
+    In fact, this is a weak implementation of the FFT; unfortunately, all
+    of my really nifty FFTs are in commercial code, and I haven't had time
+    to write a new FFT routine for this benchmark. I may add a Hartley
+    transform to the seat, too.
+
+    Actual benchmark results can be found at:
+            http://www.coyotegulch.com
+
+    Please do not use this information or algorithm in any way that might
+    upset the balance of the universe or otherwise cause a disturbance in
+    the space-time continuum.
+*/
+
+#include <time.h>
+#include <string.h>
+#include <stdlib.h>
+#include <math.h>
+#include <stdbool.h>
+#include <stdio.h>
+
+// embedded random number generator; ala Park and Miller
+static long seed = 1325;
+static const long IA = 16807;
+static const long IM = 2147483647;
+static const double AM = 4.65661287525E-10;
+static const long IQ = 127773;
+static const long IR = 2836;
+static const long MASK = 123459876;
+
+static double random_double()
+{
+    long k;
+    double result;
+
+    seed ^= MASK;
+    k = seed / IQ;
+    seed = IA * (seed - k * IQ) - IR * k;
+
+    if (seed < 0)
+	seed += IM;
+
+    result = AM * seed;
+    seed ^= MASK;
+
+    return result;
+}
+
+static const int N = 800;
+static const int NM1 = 799;	// N - 1
+static const int NP1 = 801;	// N + 1
+
+static int *lup_decompose(double **a)
+{
+    int i, j, k, k2, t;
+    double p, temp;
+
+    int *perm = (int *) malloc(sizeof(double) * N);
+
+    for (i = 0; i < N; ++i)
+	perm[i] = i;
+
+    for (k = 0; k < NM1; ++k) {
+	p = 0.0;
+
+	for (i = k; i < N; ++i) {
+	    temp = fabs(a[i][k]);
+
+	    if (temp > p) {
+		p = temp;
+		k2 = i;
+	    }
+	}
+
+	// check for invalid a
+	if (p == 0.0)
+	    return NULL;
+
+	// exchange rows
+	t = perm[k];
+	perm[k] = perm[k2];
+	perm[k2] = t;
+
+	for (i = 0; i < N; ++i) {
+	    temp = a[k][i];
+	    a[k][i] = a[k2][i];
+	    a[k2][i] = temp;
+	}
+
+	for (i = k + 1; i < N; ++i) {
+	    a[i][k] /= a[k][k];
+
+	    for (j = k + 1; j < N; ++j)
+		a[i][j] -= a[i][k] * a[k][j];
+	}
+    }
+
+    return perm;
+}
+
+static double *lup_solve(double **a, int *perm, double *b)
+{
+    int i, j, j2;
+    double sum, u;
+
+    double *y = (double *) malloc(sizeof(double) * N);
+    double *x = (double *) malloc(sizeof(double) * N);
+
+    for (i = 0; i < N; ++i) {
+	y[i] = 0.0;
+	x[i] = 0.0;
+    }
+
+    for (i = 0; i < N; ++i) {
+	sum = 0.0;
+	j2 = 0;
+
+	for (j = 1; j <= i; ++j) {
+	    sum += a[i][j2] * y[j2];
+	    ++j2;
+	}
+
+	y[i] = b[perm[i]] - sum;
+    }
+
+    i = NM1;
+
+    while (1) {
+	sum = 0.0;
+	u = a[i][i];
+
+	for (j = i + 1; j < N; ++j)
+	    sum += a[i][j] * x[j];
+
+	x[i] = (y[i] - sum) / u;
+
+	if (i == 0)
+	    break;
+
+	--i;
+    }
+
+    free(y);
+
+    return x;
+}
+
+static double **a, *b, *r;
+static int *p;
+
+void fft_bench_init(void)
+{
+    int i, j;
+
+    // generate test data            
+    a = (double **) malloc(sizeof(double *) * N);
+
+    for (i = 0; i < N; ++i) {
+	a[i] = (double *) malloc(sizeof(double) * N);
+
+	for (j = 0; j < N; ++j)
+	    a[i][j] = random_double();
+    }
+
+    b = (double *) malloc(sizeof(double) * N);
+
+    for (i = 0; i < N; ++i)
+	b[i] = random_double();
+
+}
+
+void fft_bench_start(void)
+{
+    p = lup_decompose(a);
+    r = lup_solve(a, p, b);
+}
+
+void fft_bench_finish(void)
+{
+    int i;
+    
+    // clean up
+    for (i = 0; i < N; ++i)
+	free(a[i]);
+
+    free(a);
+    free(b);
+    free(p);
+    free(r);
+}
diff --git a/hardinfo2/fftbench.h b/hardinfo2/fftbench.h
new file mode 100644
index 00000000..055226e0
--- /dev/null
+++ b/hardinfo2/fftbench.h
@@ -0,0 +1,8 @@
+#ifndef __FFTBENCH_H__ 
+#define __FFTBENCH_H__
+
+void fft_bench_init(void);
+void fft_bench_start(void);
+void fft_bench_finish(void);
+
+#endif /* __FFTBENCH_H__ */
\ No newline at end of file
diff --git a/hardinfo2/pixmaps/fft.png b/hardinfo2/pixmaps/fft.png
new file mode 100644
index 00000000..3a44038c
--- /dev/null
+++ b/hardinfo2/pixmaps/fft.png