Add random_walk microbenchmark

A heavily rewritten version of mc2spin as written by Namhoon.

3 files changed, 557 insertions, 4 deletions

diff --git a/dis/original/Makefile b/dis/original/Makefile
index 7ff5e2a..9f7286d 100755
--- a/dis/original/Makefile
+++ b/dis/original/Makefile
@@ -1,12 +1,12 @@
 LIBLITMUS ?= /media/speedy/litmus/liblitmus
 CC ?= gcc
-CFLAGS = -pthread -O2 -g -I../../baseline/source
+override CFLAGS += -pthread -O2 -ggdb3 -I../../baseline/source
 LDFLAGS = -lrt -lm
 COMMON = ../../baseline/source/extra.h
 
 # Handle cases where we're also profiling with the MMDC on the i.MX6Q
 ifneq ($(shell grep "define MMDC 1" ../../baseline/source/extra.h),)
-»···COMMON += /media/speedy/litmus/tools/mmdc/mmdc.c
+        COMMON += /media/speedy/litmus/tools/mmdc/mmdc.c
 endif
 
 # Include all the LITMUS^RT headers if we're using it
@@ -16,11 +16,11 @@ ifneq ($(shell grep "define LITMUS 1" ../../baseline/source/extra.h),)
 endif
 
 
-all: field matrix neighborhood pointer transitive update
+all: field matrix neighborhood pointer transitive update random_walk
 
 .PHONY: clean
 clean:
-        rm field matrix neighborhood pointer transitive update
+        rm field matrix neighborhood pointer transitive update random_walk
 
 field: ${COMMON} ./Field/field.c
         $(CC) $(CFLAGS) $^ -o $@ $(LDFLAGS)
@@ -34,3 +34,5 @@ transitive: ${COMMON} ./Transitive/transitive.c
         $(CC) $(CFLAGS) $^ -o $@ $(LDFLAGS)
 update: ${COMMON} ./Update/update.c
         $(CC) $(CFLAGS) $^ -o $@ $(LDFLAGS)
+random_walk: ${COMMON} random_walk.c
+        $(CC) $(CFLAGS) $^ -o $@ $(LDFLAGS)
diff --git a/dis/original/inputs/random_walk/in1 b/dis/original/inputs/random_walk/in1
new file mode 100644
index 0000000..a50f416
--- /dev/null
+++ b/dis/original/inputs/random_walk/in1
@@ -0,0 +1 @@
+0 5 0
diff --git a/dis/original/random_walk.c b/dis/original/random_walk.c
new file mode 100644
index 0000000..9f907bb
--- /dev/null
+++ b/dis/original/random_walk.c
@@ -0,0 +1,550 @@
+#include <sys/time.h>
+#include <sys/mman.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <time.h>
+#include <string.h>
+#include <inttypes.h>
+#include <assert.h>
+#include <limits.h>
+#include <fcntl.h>
+#include <errno.h>
+/*
+#include "litmus.h"
+#include "common.h"
+*/
+/* CPU time consumed so far in seconds */
+double cputime(void)
+{
+        struct timespec ts;
+        int err;
+        err = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+        if (err != 0)
+                perror("clock_gettime");
+        return (ts.tv_sec + 1E-9 * ts.tv_nsec);
+}
+
+/* wall-clock time in seconds */
+double wctime(void)
+{
+        struct timeval tv;
+        gettimeofday(&tv, NULL);
+        return (tv.tv_sec + 1E-6 * tv.tv_usec);
+}
+
+void bail_out(const char* msg)
+{
+        perror(msg);
+        exit(-1 * errno);
+}
+
+#include "extra.h"
+
+#define PAGE_SIZE (4096)
+#define CACHELINE_SIZE 64
+#define INTS_IN_CACHELINE (CACHELINE_SIZE/sizeof(int))
+#define CACHELINES_IN_1KB (1024 / sizeof(cacheline_t))
+#define INTS_IN_1KB (1024 / sizeof(int))
+
+typedef struct cacheline
+{
+        int line[INTS_IN_CACHELINE];
+} __attribute__((aligned(CACHELINE_SIZE))) cacheline_t;
+
+static volatile cacheline_t* arena = NULL;
+
+#define UNCACHE_DEV "/dev/litmus/uncache"
+#define FAKE_DEV "/dev/litmus/fakedev0"
+
+static cacheline_t* alloc_arena(size_t size, int use_huge_pages, int use_uncache_pages)
+{
+        int flags = MAP_PRIVATE | MAP_POPULATE;
+        cacheline_t* arena = NULL;
+        int fd;
+
+        if(use_huge_pages)
+                flags |= MAP_HUGETLB;
+
+        if(use_uncache_pages == 1) {
+                fd = open(UNCACHE_DEV, O_RDWR|O_SYNC);
+                if (fd == -1)
+                        bail_out("Failed to open uncache device. Are you running the LITMUS^RT kernel?");
+        } else if (use_uncache_pages == 2) {
+                fd = open(FAKE_DEV, O_RDWR|O_SYNC);
+                if (fd == -1)
+                        bail_out("Failed to open fake device. Are you running the LITMUS^RT kernel?");
+        } else {
+                fd = -1;
+                flags |= MAP_ANONYMOUS;
+        }
+
+        arena = (cacheline_t*)mmap(0, size, PROT_READ | PROT_WRITE, flags, fd, 0);
+        
+        if(use_uncache_pages)
+                close(fd);
+
+        assert(arena);
+
+        return arena;
+}
+
+static void dealloc_arena(cacheline_t* arena, size_t size)
+{
+                int ret = munmap((void*)arena, size);
+        if(ret != 0)
+                bail_out("munmap() error");
+}
+
+static int randrange(int min, int max)
+{
+    // Range is [min, max)
+    assert(max - min - 1 <= RAND_MAX);
+    return rand() % (max - min) + min;
+    //return (rand() % (max - min + 1)) + min;
+    /* generate a random number on the range [min, max) w/o skew */
+    /*int limit = max - min;
+    int devisor = RAND_MAX/limit;
+    int retval;
+
+    do {
+            retval = rand() / devisor;
+    } while(retval == limit);
+    retval += min;
+
+    return retval;*/
+}
+
+static void init_arena(volatile cacheline_t* arena, size_t size)
+{
+    int i;
+    size_t num_arena_elem = size / sizeof(cacheline_t);
+
+    /* Generate a cycle among the cache lines using Sattolo's algorithm.
+       Every int in the cache line points to the same cache line.
+       Note: Sequential walk doesn't care about these values. */
+    for (i = 0; i < num_arena_elem; i++) {
+            int j;
+            for(j = 0; j < INTS_IN_CACHELINE; j++)
+                    arena[i].line[j] = i;
+            arena[i].line[1] = 0;
+    }
+    /*while(1 < i--) {
+            int j = randrange(0, i);
+            cacheline_t temp = arena[j];
+            arena[j] = arena[i];
+            arena[i] = temp;
+    }*/
+    for (int j = 0; j < num_arena_elem-1; j++) {
+        int k = randrange(j+1, num_arena_elem);
+        cacheline_t temp = arena[j];
+        arena[j] = arena[k];
+        arena[k] = temp;
+    }
+}
+
+/* Random walk around the arena in cacheline-sized chunks.
+   Cacheline-sized chucks ensures the same utilization of each
+   hit line as sequential read. (Otherwise, our utilization
+   would only be 1/INTS_IN_CACHELINE.) */
+static int random_walk(volatile cacheline_t *mem, int wss, int write_cycle)
+{
+        /* a random cycle among the cache lines was set up by init_arena(). */
+        int sum, i, next;
+