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, 0 insertions, 813 deletions
diff --git a/test/ccured_olden/bisort/.cvsignore b/test/ccured_olden/bisort/.cvsignore deleted file mode 100644 index 14e4fb3b..00000000 --- a/test/ccured_olden/bisort/.cvsignore +++ /dev/null @@ -1,25 +0,0 @@ -*.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 deleted file mode 100644 index 6bd4f26b..00000000 --- a/test/ccured_olden/bisort/CVS/Entries +++ /dev/null @@ -1,12 +0,0 @@ -/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 deleted file mode 100644 index 08d61689..00000000 --- a/test/ccured_olden/bisort/CVS/Repository +++ /dev/null @@ -1 +0,0 @@ -cil/test/olden/bisort diff --git a/test/ccured_olden/bisort/CVS/Root b/test/ccured_olden/bisort/CVS/Root deleted file mode 100644 index 35f411e9..00000000 --- a/test/ccured_olden/bisort/CVS/Root +++ /dev/null @@ -1 +0,0 @@ -/home/cvs-repository diff --git a/test/ccured_olden/bisort/HOWTO b/test/ccured_olden/bisort/HOWTO deleted file mode 100644 index 170ad73c..00000000 --- a/test/ccured_olden/bisort/HOWTO +++ /dev/null @@ -1 +0,0 @@ -250000 0
\ No newline at end of file diff --git a/test/ccured_olden/bisort/Makefile b/test/ccured_olden/bisort/Makefile deleted file mode 100644 index b030ced2..00000000 --- a/test/ccured_olden/bisort/Makefile +++ /dev/null @@ -1,67 +0,0 @@ -# /* 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 deleted file mode 100644 index 7b12c4bb..00000000 --- a/test/ccured_olden/bisort/README +++ /dev/null @@ -1,22 +0,0 @@ -/* 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 deleted file mode 100644 index 12591026..00000000 --- a/test/ccured_olden/bisort/args.c +++ /dev/null @@ -1,32 +0,0 @@ -/* 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 deleted file mode 100644 index 72ff8611..00000000 --- a/test/ccured_olden/bisort/bitonic.c +++ /dev/null @@ -1,267 +0,0 @@ -/* 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 deleted file mode 100644 index c1b81c6d..00000000 --- a/test/ccured_olden/bisort/node.h +++ /dev/null @@ -1,18 +0,0 @@ -/* 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 deleted file mode 100644 index eadb80aa..00000000 --- a/test/ccured_olden/bisort/proc.h +++ /dev/null @@ -1,25 +0,0 @@ -/* 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 deleted file mode 100644 index 43d3f9db..00000000 --- a/test/ccured_olden/bisort/ssplain.c +++ /dev/null @@ -1,69 +0,0 @@ -#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 deleted file mode 100644 index 54f3a3ed..00000000 --- a/test/ccured_olden/bisort/ssplain.h +++ /dev/null @@ -1,128 +0,0 @@ -#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 deleted file mode 100644 index e1e98749..00000000 --- a/test/ccured_olden/bisort/swap.c +++ /dev/null @@ -1,145 +0,0 @@ -/* 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); -} - |