diff options
Diffstat (limited to 'test/ccured_olden/bisort')
-rw-r--r-- | test/ccured_olden/bisort/.cvsignore | 25 | ||||
-rw-r--r-- | test/ccured_olden/bisort/CVS/Entries | 12 | ||||
-rw-r--r-- | test/ccured_olden/bisort/CVS/Repository | 1 | ||||
-rw-r--r-- | test/ccured_olden/bisort/CVS/Root | 1 | ||||
-rw-r--r-- | test/ccured_olden/bisort/HOWTO | 1 | ||||
-rw-r--r-- | test/ccured_olden/bisort/Makefile | 67 | ||||
-rw-r--r-- | test/ccured_olden/bisort/README | 22 | ||||
-rw-r--r-- | test/ccured_olden/bisort/args.c | 32 | ||||
-rw-r--r-- | test/ccured_olden/bisort/bitonic.c | 267 | ||||
-rw-r--r-- | test/ccured_olden/bisort/node.h | 18 | ||||
-rw-r--r-- | test/ccured_olden/bisort/proc.h | 25 | ||||
-rw-r--r-- | test/ccured_olden/bisort/ssplain.c | 69 | ||||
-rw-r--r-- | test/ccured_olden/bisort/ssplain.h | 128 | ||||
-rw-r--r-- | test/ccured_olden/bisort/swap.c | 145 |
14 files changed, 813 insertions, 0 deletions
diff --git a/test/ccured_olden/bisort/.cvsignore b/test/ccured_olden/bisort/.cvsignore new file mode 100644 index 00000000..14e4fb3b --- /dev/null +++ b/test/ccured_olden/bisort/.cvsignore @@ -0,0 +1,25 @@ +*.o +*.obj +*.exe +*.pdb +*.ilk +*.cpp +*.i +*.s +*.asm +*cil.c +*.rtl +*box.c +*infer.c +*_ppp.c +*.origi +*.stackdump +*_all.c +allcfiles +ope.m +*_comb.c +*cured.c +*.optim.c +changes +*.browser +*optimcured* diff --git a/test/ccured_olden/bisort/CVS/Entries b/test/ccured_olden/bisort/CVS/Entries new file mode 100644 index 00000000..6bd4f26b --- /dev/null +++ b/test/ccured_olden/bisort/CVS/Entries @@ -0,0 +1,12 @@ +/HOWTO/1.1/Thu Jul 5 20:05:08 2001// +/Makefile/1.4/Wed Oct 3 00:09:43 2001// +/README/1.1/Tue Jun 12 16:43:34 2001// +/args.c/1.1/Thu Jul 5 20:05:08 2001// +/bitonic.c/1.3/Wed Oct 3 00:09:43 2001// +/node.h/1.2/Thu Jul 5 20:05:08 2001// +/proc.h/1.1/Tue Jun 12 16:43:34 2001// +/swap.c/1.2/Thu Jul 5 20:05:08 2001// +/ssplain.c/1.4/Fri Nov 9 00:51:25 2001// +/.cvsignore/1.7/Wed Aug 7 01:48:34 2002// +/ssplain.h/1.6/Mon Jan 6 23:28:32 2003// +D diff --git a/test/ccured_olden/bisort/CVS/Repository b/test/ccured_olden/bisort/CVS/Repository new file mode 100644 index 00000000..08d61689 --- /dev/null +++ b/test/ccured_olden/bisort/CVS/Repository @@ -0,0 +1 @@ +cil/test/olden/bisort diff --git a/test/ccured_olden/bisort/CVS/Root b/test/ccured_olden/bisort/CVS/Root new file mode 100644 index 00000000..35f411e9 --- /dev/null +++ b/test/ccured_olden/bisort/CVS/Root @@ -0,0 +1 @@ +/home/cvs-repository diff --git a/test/ccured_olden/bisort/HOWTO b/test/ccured_olden/bisort/HOWTO new file mode 100644 index 00000000..170ad73c --- /dev/null +++ b/test/ccured_olden/bisort/HOWTO @@ -0,0 +1 @@ +250000 0
\ No newline at end of file diff --git a/test/ccured_olden/bisort/Makefile b/test/ccured_olden/bisort/Makefile new file mode 100644 index 00000000..b620fafb --- /dev/null +++ b/test/ccured_olden/bisort/Makefile @@ -0,0 +1,67 @@ +# /* For copyright information, see olden_v1.0/COPYRIGHT */ + +BINARY = bisort.exe +PROGS = bitonic args ssplain + +ifdef _MSVC +CC = cl + +SRC = .c +OBJ = .obj +ASM = .s + +EXTRA_CDEFS = /DI_TIME /DI_SYS_TIME /DULTRIX +CDEFS = /DPLAIN /DSS_PLAIN +OPTFLAGS = /Ox + +LIBS = +LIBPATH = +else +CC = gcc -arch ppc # MacOS X +#CC=gcc # other systems +CCOMP=../../../../ccomp +CCOMPFLAGS=-dump-c + +SRC = .c +OBJ = .o +ASM = .s + +EXTRA_CDEFS = -DI_TIME -DI_SYS_TIME -DULTRIX +CDEFS = -DPLAIN -DSS_PLAIN +OPTFLAGS = -g -Wall -O3 + +LIBS = # MacOS X +# LIBS = -lm +LIBPATH = +endif + +SRCS = $(addsuffix $(SRC),$(PROGS)) +OBJS = $(addsuffix $(OBJ),$(PROGS)) +ASMS = $(addsuffix $(ASM),$(PROGS)) + +#defaulttarget: $(BINARY) + +#$(BINARY): $(OBJS) +# $(CC) $(LDFALGS) $(OPTFLAGS) -o $@ $(OBJS) $(LIBPATH) $(LIBS) + +#$(SRC)$(OBJ): +# $(CC) $(CDEFS) $(EXTRA_CDEFS) $(MY_CDEFS) $(OPTFLAGS) -c $< + +all_s: $(PROGS:%=%.s) + +all: $(PROGS:%=%.compcert) + +all_gcc: $(PROGS:%=%.gcc) + +%.compcert: %.s + $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.compcert $*.s $(LIBS) + +%.s: %.c ../../../../ccomp + $(CCOMP) $(CCOMPFLAGS) $*.c + +%.gcc: %.c + $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.gcc $*.c $(LIBS) + +clean: + rm -f $(BINARY) $(OBJS) $(ASMS) *~ *.light.c *.cil.* + diff --git a/test/ccured_olden/bisort/README b/test/ccured_olden/bisort/README new file mode 100644 index 00000000..7b12c4bb --- /dev/null +++ b/test/ccured_olden/bisort/README @@ -0,0 +1,22 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ +****************** +olden_v1.0/benchmarks/bisort/README +January 3, 1995 +Martin C. Carlisle + +this directory contains the Bitonic Sort benchmark: +G. Bilardi and A. Nicolau. "Adaptive Bitonic Sorting: An optimal +parallel algorithm for shared-memory machines." SIAM J. Comput. +18(2):216-228, 1989. + +as implemented for Olden by Martin C. Carlisle +****************** + +Makefile - "make bisort" makes executable + +args.c - handle command line arguments +bitonic.c - main routines +swap.c - used to swap subtrees +node.h - declarations +code.h - prototypes + diff --git a/test/ccured_olden/bisort/args.c b/test/ccured_olden/bisort/args.c new file mode 100644 index 00000000..12591026 --- /dev/null +++ b/test/ccured_olden/bisort/args.c @@ -0,0 +1,32 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#ifdef SS_PLAIN +#include "ssplain.h" +#endif SS_PLAIN + +int mylog(int num) +{ + int j=0,k=1; + + while(k<num) { k*=2; j++; } + return j; +} + +extern int flag; +int dealwithargs(int argc, char *argv[]) +{ + int size; + + if (argc > 2) + flag = atoi(argv[2]); + else + flag = 0; + + if (argc > 1) + size = atoi(argv[1]); + else + size = 16; + + return size; +} + diff --git a/test/ccured_olden/bisort/bitonic.c b/test/ccured_olden/bisort/bitonic.c new file mode 100644 index 00000000..72ff8611 --- /dev/null +++ b/test/ccured_olden/bisort/bitonic.c @@ -0,0 +1,267 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +/* =================== PROGRAM bitonic===================== */ +/* UP - 0, DOWN - 1 */ + +#include "node.h" /* Node Definition */ +#include "proc.h" /* Procedure Types/Nums */ + +#define CONST_m1 10000 +#define CONST_b 31415821 +#define RANGE 100 + +#ifdef SS_PLAIN +#include "ssplain.h" +#endif SS_PLAIN + +#define put(a) chatting("%d",a) +#define puts(a) chatting(a) + + +int flag=0,foo=0; + +#define NewNode(h,v) \ + \ +{ \ + h = (HANDLE *) malloc(sizeof(struct node)); \ + h->value = v; \ + h->left = NIL; \ + h->right = NIL; \ + }; + + +void InOrder(h) + HANDLE *h; +{ + HANDLE *l, *r; + if ((h != NIL)) + { + l = h->left; + r = h->right; + InOrder(l); + chatting("%d @ 0x%x\n", h->value, (long)h); + InOrder(r); + } +} + +int mult(int p, int q) +{ + int p1, p0, q1, q0; + + p1=p/CONST_m1; p0=p%CONST_m1; + q1=q/CONST_m1; q0=q%CONST_m1; + return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); +} + +int skiprand(int seed, int n) +{ +#ifdef SS_PLAIN + for (; n; n--) seed=mult(seed,CONST_b)+1; +#else SS_PLAIN + for (; n; n--) seed=random(seed); +#endif SS_PLAIN + return seed; +} + +#ifndef SS_PLAIN +int random(int seed) +{ + int tmp; + tmp = (mult(seed,CONST_b)+1); + return tmp; +} +#endif SS_PLAIN + +HANDLE* RandTree(n,seed,level) + int n,seed,level; + +{ + int next_val,my_name; + HANDLE *h; + my_name=foo++; + + if (n > 1) + { +#ifdef SS_PLAIN + seed = mult(seed,CONST_b)+1; +#else SS_PLAIN + seed = random(seed); +#endif SS_PLAIN + next_val=seed % RANGE; + NewNode(h,next_val); + + h->left = RandTree((n/2),seed,level+1); + h->right = RandTree((n/2),skiprand(seed,(n)+1),level+1); + } + else + h = NIL; + return(h); +} + +void SwapVal(l,r) + HANDLE *l, *r; +{ + int temp; + + temp = l->value; /* MISS PROBLEM */ + l->value = r->value; + r->value = temp; +} + +void SwapLeft(l,r) + HANDLE *l, *r; +{ + HANDLE *h; + + h = r->left; + r->left = l->left; + l->left = h; +} + +void SwapRight(l,r) + HANDLE *l, *r; +{ + HANDLE *h; + + h = r->right; + r->right = l->right; /* MISS PROBLEM */ + l->right = h; +} + +int Bimerge(root,spr_val,dir) + HANDLE *root; + int spr_val,dir; +{ + int rightexchange, elementexchange; + HANDLE *pl, *pr; + + /*chatting("enter bimerge %x\n", root);*/ + rightexchange = ((root->value > spr_val) ^ dir); + if (rightexchange) + { + int temp; + temp = root->value; + root->value = spr_val; + spr_val = temp; + } + + pl = root->left; + pr = root->right; + + while (pl != NIL) + { + elementexchange = ((pl->value > /* MISS PROBLEM */pr->value) ^ dir); + if (rightexchange) + { + if (elementexchange) + { + SwapVal(pl,pr); + SwapRight(pl,pr); + pl = pl->left; + pr = pr->left; + } + else + { + pl = pl->right; + pr = pr->right; + } + } + else + { + if (elementexchange) + { + SwapVal(pl,pr); + SwapLeft(pl,pr); + pl = pl->right; + pr = pr->right; + } + else + { + pl = pl->left; + pr = pr->left; /* MISS PROBLEM */ + } + } + } + + if (root->left != NIL) + { + root->value=Bimerge(root->left,root->value,dir); + spr_val=Bimerge(root->right,spr_val,dir); + } + /*chatting("exit bimerge %x\n", root);*/ + return spr_val; +} + +int Bisort(root,spr_val,dir) + HANDLE *root; + int spr_val,dir; +{ + /*chatting("bisort %x\n", root);*/ + if (root->left == NIL) + { + if ((root->value > spr_val) ^ dir) + { + int val; + val = spr_val; + spr_val = root->value; + root->value =val; + } + } + else + { + /* Bisort both halves of the tree and merge */ + root->value=Bisort(root->left,root->value,dir); + spr_val=Bisort(root->right,spr_val,!dir); + spr_val=Bimerge(root,spr_val,dir); + } + /*chatting("exit bisort %x\n", root);*/ + return spr_val; +} + +void main(argc,argv) + int argc; + char *argv[]; + + +{ + HANDLE *h; + int sval; + int n; + + n = dealwithargs(argc,argv); + + chatting("Bisort with %d size\n", n); + h = RandTree(n,12345768,0); +#ifdef SS_PLAIN + sval = (mult(245867,CONST_b)+1) % RANGE; +#else SS_PLAIN + sval = random(245867) % RANGE; +#endif SS_PLAIN + if (flag) { + InOrder(h); + chatting("%d\n",sval); + } + chatting("**************************************\n"); + chatting("BEGINNING BITONIC SORT ALGORITHM HERE\n"); + chatting("**************************************\n"); + + chatting("Sorting forward..."); + sval=Bisort(h,sval,0); + if (flag) { + chatting("Sorted Tree:\n"); + InOrder(h); + chatting("%d\n",sval); + } + chatting("done\n"); + + chatting("sorting backward..."); + sval=Bisort(h,sval,1); + if (flag) { + chatting("Sorted Tree:\n"); + InOrder(h); + chatting("%d\n",sval); + } + chatting("done\n"); + exit(0); +} + diff --git a/test/ccured_olden/bisort/node.h b/test/ccured_olden/bisort/node.h new file mode 100644 index 00000000..c1b81c6d --- /dev/null +++ b/test/ccured_olden/bisort/node.h @@ -0,0 +1,18 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +/* =============== NODE STRUCTURE =================== */ + +struct node { + int value; + struct node *left; + struct node *right; + }; + +typedef struct node HANDLE; + +#define NIL ((HANDLE *) 0) +#ifdef FUTURES +#define makenode(procid) ALLOC(procid,sizeof(struct node)) +#else +#define makenode(procid) mymalloc(sizeof(struct node)) +#endif diff --git a/test/ccured_olden/bisort/proc.h b/test/ccured_olden/bisort/proc.h new file mode 100644 index 00000000..eadb80aa --- /dev/null +++ b/test/ccured_olden/bisort/proc.h @@ -0,0 +1,25 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +/* ========== PROCEDURE TYPES/NUMS ================== */ + + +HANDLE *RandTree(); + +void SwapValue(); +void SwapValLeft(); +void SwapValRight(); +int Bimerge(); +int Bisort(); +#define DD_EXIT 0 + + +/* ================= PROC NAMES ==============*/ + +#ifdef EXTERN + extern char *procnames[]; +#else + static char *procnames[] = + { + "EXIT" + }; +#endif diff --git a/test/ccured_olden/bisort/ssplain.c b/test/ccured_olden/bisort/ssplain.c new file mode 100644 index 00000000..43d3f9db --- /dev/null +++ b/test/ccured_olden/bisort/ssplain.c @@ -0,0 +1,69 @@ +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdarg.h> +#include <limits.h> +#include <stddef.h> +#include "ssplain.h" + +void chatting(char *s, ...) +{ + va_list ap; + va_start(ap,s); + vfprintf(stderr, s, ap); + va_end(ap); +} + + +#ifdef SS_RAND +double drand48() +{ + double d; + d = (double) random() / LONG_MAX; + return d; +} + + +long lrand48() +{ + long l = random(); + return l; +} + +void srand48(long seed) +{ + srand(seed); +} +#endif SS_RAND + + +#ifndef BEFOREBOX +static unsigned long bytes_allocated = 0; +static unsigned long allocations = 0; + +void* +ssplain_malloc(int size) +{ + allocations++; + bytes_allocated+=size; + return malloc(size); +} + +void* +ssplain_calloc(int nelems, int size) +{ + void *p; + allocations++; + bytes_allocated+= nelems * size; + p = calloc(nelems, size); + if(! p) { printf("Allocation failed\n"); exit(3); } + return p; +} + +void +ssplain_alloc_stats() +{ + chatting("Allocation stats: %d bytes allocated in %d allocations\n", + bytes_allocated, allocations); +} +#endif diff --git a/test/ccured_olden/bisort/ssplain.h b/test/ccured_olden/bisort/ssplain.h new file mode 100644 index 00000000..54f3a3ed --- /dev/null +++ b/test/ccured_olden/bisort/ssplain.h @@ -0,0 +1,128 @@ +#ifndef SS_PLAIN_H +#define SS_PLAIN_H + +void * ssplain_malloc(int size); +void * ssplain_calloc(int nelems, int size); +void ssplain_alloc_stats(); + +/* Convert MP shutdown to exit */ +#define __ShutDown(ID) { ssplain_alloc_stats(); exit(ID); } + +/* All these CM-5 things are nops */ +#define CMMD_node_timer_clear(ID) +#define CMMD_node_timer_start(ID) +#define CMMD_node_timer_stop(ID) +#define CMMD_node_timer_elapsed(ID) ((double)0) + +#define CMMD_self_address() 0 + +#define ClearAllStats() + +/* define away the CM-5 allocator */ +#include <stdlib.h> + +#ifndef ALLOC +#define ALLOC(NUM,ESIZE) ssplain_calloc (NUM+1,ESIZE) +#endif ALLOC + +#ifndef mymalloc +#define mymalloc malloc +#endif mymalloc + +/* Get all of these multiprocessing things out of here. */ +/* My id will stay that way */ +#define IDMASK 0xffffffff + +/* Nothing is getting tested */ +#ifndef RETEST +#define RETEST() +#endif RETEST + +#ifndef NOTEST +#define NOTEST() +#endif NOTEST + +/* Everything is local */ +#ifndef local +#define local +#endif local + +#ifndef LOCAL +#define LOCAL(VAL) (VAL) +#endif LOCAL + +#ifndef ISLOCPTR +#define ISLOCPTR(VAL) (1) +#endif ISLOCPTR + +#ifndef MLOCAL +#define MLOCAL(VAL) +#endif MLOCAL + +/* An atomic increment is a normal increment */ +#ifndef ATOMICINC +#define ATOMICINC(PVAL) (*(PVAL) = *(PVAL) + 1) +#endif ATOMICINC + +/* Nothing is migrating anywhere */ +#ifndef MIGRATE +#define MIGRATE(ID) +#endif MIGRATE + +#ifndef MIGRPH +#define MIGRPH() +#endif MIGRPH + +#ifndef UNPHASE +#define UNPHASE() +#endif UNPHASE + +#ifndef PID +#define PID(VAL) (0) +#endif PID + +/* All these functions */ +#pragma ccuredvararg("chatting", printf(1)); +void chatting(char *s, ...); + +/* just define these guys, they are not going to change */ +#define __NumNodes 1 +#define __MyNodeId 0 +#define __NDim 0 + +typedef struct ss_future_cell_int { + int value; +} future_cell_int; + +/* Where are these things for real? */ +#ifdef SS_RAND +long lrand48(); +double drand48(); +void srand48(long seed); +#endif SS_RAND + +#define MOD(V,M) ((V) & ((M) - 1)) +#define INC_MOD(V,M) (V) = MOD((V) + 1, (M)) + +/* Prefetch instructions */ + +/* Use these for 1 lookahead prefetching */ + +#ifdef OVERHEAD_ONLY +#define ASSEMBLE_PREFETCH(ARG) +#define ASSEMBLE_PREFETCH_HEAD(ARG) +#else !OVERHEAD_ONLY + +#define ASSEMBLE_PREFETCH(ARG) \ + asm ("lw $0, %0" : /* no outputs */ : "g" (ARG)) + +/* Use these for infinite lookahead prefetching */ +#define ASSEMBLE_PREFETCH_HEAD(ARG) \ + asm ("lh $0, %0" : /* no outputs */ : "g" (ARG)) + +#endif OVERHEAD_ONLY + +#endif SS_PLAIN_H + + + diff --git a/test/ccured_olden/bisort/swap.c b/test/ccured_olden/bisort/swap.c new file mode 100644 index 00000000..e1e98749 --- /dev/null +++ b/test/ccured_olden/bisort/swap.c @@ -0,0 +1,145 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#define COLLECT_SIZE 256 +#define DFS_SIZE 20 +#include "node.h" + +#ifdef SS_PLAIN +#include "ssplain.h" +#endif SS_PLAIN + + +typedef struct { + int top; + HANDLE *handles[DFS_SIZE]; +} stack; + +#define push(s,v) (s)->handles[++((s)->top)] = v +#define pop(s) (s)->handles[((s)->top)--] +#define stackempty(s) ((s)->top < 0) +void VisitCollect(HANDLE *t, local int *collect) +{ + register int val; + val = t->value; + *collect = val; +} + +void VisitCollectReplace(HANDLE *t, local int *collect) +{ + register int temp = *collect; + register int val = t->value; + *collect = val; + t->value = temp; +} + +void VisitReplace(HANDLE *t, local int *collect) +{ + register int val = *collect; + t->value = val; +} + +void swapDFS(local stack *s, local int collection[], void visit()) +{ + int num=0; + + while (!stackempty(s) && num < COLLECT_SIZE) + { + HANDLE *v = pop(s); + visit(v,&collection[num]); + num++; + if (v->left != NULL) + { + HANDLE *child; + child = v->right; + push(s,child); + child = v->left; + push(s,child); + } + } +} + +void NewSwapSubTree(HANDLE *t1, HANDLE *t2) +{ + local stack c1, r1, s2; + int collection[COLLECT_SIZE]; + + /*chatting("starting swapping\n");*/ + + if (t1!=NULL) + { + c1.top = -1; + r1.top = -1; + s2.top = -1; + push(&c1,t1); + push(&r1,t1); + push(&s2,t2); + while (!stackempty(&c1)) + { + MLOCAL(t1); + swapDFS(&c1,collection,VisitCollect); + MLOCAL(t2); + swapDFS(&s2,collection,VisitCollectReplace); + MLOCAL(t1); + swapDFS(&r1,collection,VisitReplace); + } + } + /*chatting("ending swapping\n");*/ + +} + + +int *Collect(HANDLE *t1, local int collection[]) +{ + register int val; + if (t1==NULL) return collection; + MLOCAL(t1); + val = t1->value; + *collection = val; + collection += 1; + collection = Collect(t1->left,collection); + collection = Collect(t1->right,collection); + return collection; +} + +int *Collect_Replace(HANDLE *t1, local int collection[]) +{ + register int temp,val; + if (t1==NULL) return collection; + MLOCAL(t1); + temp = *collection; + val = t1->value; + *collection = val; + t1->value = temp; + collection += 1; + collection = Collect_Replace(t1->left,collection); + collection = Collect_Replace(t1->right,collection); + return collection; +} + +int *Replace(HANDLE *t1, local int collection[]) +{ + register int val; + if (t1==NULL) return collection; + MLOCAL(t1); + val = *collection; + t1->value = val; + collection +=1; + collection = Replace(t1->left,collection); + collection = Replace(t1->right,collection); + return collection; +} + + +void SwapSubTree(HANDLE *t1, HANDLE *t2) +{ + int collection[COLLECT_SIZE]; + HANDLE *t1loc, *t2loc; + + MLOCAL(t1); + Collect(t1,collection); + MLOCAL(t2); + Collect_Replace(t2,collection); + MLOCAL(t1); + Replace(t1,collection); +} + |