diff options
Diffstat (limited to 'test/ccured_olden/perimeter')
-rw-r--r-- | test/ccured_olden/perimeter/.cvsignore | 32 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/CVS/Entries | 9 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/CVS/Repository | 1 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/CVS/Root | 1 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/Makefile | 99 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/README | 20 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/main.c | 221 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/maketree.c | 120 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/out.orig | 3 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/output | 4 | ||||
-rw-r--r-- | test/ccured_olden/perimeter/perimeter.h | 54 | ||||
-rwxr-xr-x | test/ccured_olden/perimeter/testit | 25 |
12 files changed, 589 insertions, 0 deletions
diff --git a/test/ccured_olden/perimeter/.cvsignore b/test/ccured_olden/perimeter/.cvsignore new file mode 100644 index 00000000..9cd22bfd --- /dev/null +++ b/test/ccured_olden/perimeter/.cvsignore @@ -0,0 +1,32 @@ +*.o +*.obj +*.exe +*.pdb +*.ilk +*.cpp +*.i +*.s +*.asm +*cil.c +*.rtl +*box.c +*infer.c +*_ppp.c +*.origi +*.stackdump +*_all.c +changes.out +perimeter.cil +perimeter.*box +allcfiles +ope.m +ope.m +*cured.c +*.optim.c +*_comb.c +changes +output +out.diff +*.browser +*optimcured* + diff --git a/test/ccured_olden/perimeter/CVS/Entries b/test/ccured_olden/perimeter/CVS/Entries new file mode 100644 index 00000000..4d821ece --- /dev/null +++ b/test/ccured_olden/perimeter/CVS/Entries @@ -0,0 +1,9 @@ +/Makefile/1.3/Sun Jul 8 14:10:47 2001// +/README/1.1/Tue Jun 12 04:17:59 2001// +/main.c/1.1/Tue Jun 12 04:17:59 2001// +/maketree.c/1.1/Tue Jun 12 04:17:59 2001// +/out.orig/1.1/Mon Nov 12 08:08:28 2001// +/testit/1.2/Tue Dec 4 05:07:50 2001// +/.cvsignore/1.14/Wed Aug 7 01:48:13 2002// +/perimeter.h/1.4/Sat Jan 11 20:38:42 2003// +D diff --git a/test/ccured_olden/perimeter/CVS/Repository b/test/ccured_olden/perimeter/CVS/Repository new file mode 100644 index 00000000..63138464 --- /dev/null +++ b/test/ccured_olden/perimeter/CVS/Repository @@ -0,0 +1 @@ +cil/test/olden/perimeter diff --git a/test/ccured_olden/perimeter/CVS/Root b/test/ccured_olden/perimeter/CVS/Root new file mode 100644 index 00000000..35f411e9 --- /dev/null +++ b/test/ccured_olden/perimeter/CVS/Root @@ -0,0 +1 @@ +/home/cvs-repository diff --git a/test/ccured_olden/perimeter/Makefile b/test/ccured_olden/perimeter/Makefile new file mode 100644 index 00000000..47675db0 --- /dev/null +++ b/test/ccured_olden/perimeter/Makefile @@ -0,0 +1,99 @@ +# /* For copyright information, see olden_v1.01/COPYRIGHT */ +.KEEP_STATE: +SRCS = main.c maketree.c + +OLDEN_DIR=/u/ac/carlisle/olden_v1.01 +RCC = $(OLDEN_DIR)/mcc/sparc/backend/mcc +CPP = gcc -E -U__GNUC__ -D_NO_LONGLONG +#CPPFLAGS = -DVERIFY_AFFINITIES +CPPFLAGS = +#LIBFLAGS = "CPPFLAGS=-DPROF" +#LIBFLAGS = "CPPFLAGS=-DVISUALIZE" "VFLAG=-v" +LIBFLAGS = +#PFLAG = -p +PFLAG = +PLIBOBJS = plain.o plain2.o +LIBOBJS = libolden.a +OBJS = $(SRCS:%.c=%.o) args.o +ROBJS = $(SRCS:%.c=%.r.o) args.o +LIBLINK = $(LIBOBJS:%=$(OLDEN_DIR)/runtime/%) +RLIBLINK = $(PLIBOBJS:%=$(OLDEN_DIR)/runtime/%) +INCDIRS = /usr/include $(OLDEN_DIR)/runtime +NODELIBS = +LIBDIRS = + +CC = cc +#sm: CFLAGS = +CFLAGS = -O2 + + +# sm: +PLAIN=1 +all: defaulttarget + +ifdef PLAIN +ifdef _MSVC +EXTOBJ = .obj +OBJOUT = /Fo +EXEOUT = /Fe +CFLAGS = /DPLAIN +CONLY = /c +CC = cl +else +EXTOBJ = .o +OBJOUT = -o +EXEOUT = -o +CFLAGS += -DPLAIN +CONLY = -c +CC = gcc -arch ppc +CCOMP=../../../../ccomp +CCOMPFLAGS=-dump-c + +endif + +OBJS = maketree$(EXTOBJ) main$(EXTOBJ) + +%.obj : %.c + $(CC) $(CONLY) $(CFLAGS) $< $(OBJOUT)$@ + + +defaulttarget: $(OBJS) + $(CC) $(CFLAGS) $(OBJS) $(EXEOUT)perimeter.exe +endif + +perm: $(OBJS) target + /usr/bin/cmmd-ld \ + -comp $(CC) $(OBJS) $(LIBLINK) -v -o /scratch1/carlisle/perm \ + $(LIBDIRS:%=-L%) $(NODELIBS:%=-l%) + +plain: $(ROBJS) target + /usr/bin/cmmd-ld \ + -comp $(CC) $(ROBJS) $(RLIBLINK) -v -o /scratch1/carlisle/plainperm \ + $(LIBDIRS:%=-L%) $(NODELIBS:%=-l%) + +ifndef PLAIN +args.s: args.c + /lib/cpp $(CPPFLAGS) $(INCDIRS:%=-I%) args.c | $(RCC) > args.s +endif + +%.s: %.c + $(CPP) -DFUTURES $(CPPFLAGS) $(INCDIRS:%=-I%) $< | $(RCC) $(PFLAG) -n -m -k > $*.s + + +%.p.s: %.c + /lib/cpp -DPLAIN $(CPPFLAGS) $(INCDIRS:%=-I%) $< | $(RCC) -f > $*.p.s + +%.o: %.s + $(CC) $(CFLAGS) -c $< + + +%.r.o: %.p.s + $(CC) $(CFLAGS) -c $< -o $*.r.o + +target: + cd $(OLDEN_DIR)/runtime; make $(LIBFLAGS) + +clean: + rm -f $(TARGET) $(OBJS) *.exe *.o *.obj *~ .make.state .nse_depinfo *.s *.light.c + + diff --git a/test/ccured_olden/perimeter/README b/test/ccured_olden/perimeter/README new file mode 100644 index 00000000..c8f557c9 --- /dev/null +++ b/test/ccured_olden/perimeter/README @@ -0,0 +1,20 @@ +/* For copyright information, see olden_v1.01/COPYRIGHT */ +********************** +olden_v1.01/benchmarks/perimeter/README +June 1996 +Martin C. Carlisle + +this directory contains the Perimeter benchmark: + +H. Samet. "Computing Perimeters of Regions in Images Represented by Quad- +Trees". IEEE Trans. on Pattern Analysis and Machine Intelligence +PAMI-3(6), Nov. 1981 + +as implemented for Olden by Martin C. Carlisle +********************** + +Makefile - use "make perm" to create executable + +args.c - process command line args +main.c,perimeter.h - main routines +maketree.c - creates random quad-tree diff --git a/test/ccured_olden/perimeter/main.c b/test/ccured_olden/perimeter/main.c new file mode 100644 index 00000000..ff58925a --- /dev/null +++ b/test/ccured_olden/perimeter/main.c @@ -0,0 +1,221 @@ +#include "perimeter.h" +#ifdef MIGRONLY +#define BLAH MIGRPH() +#else +#define BLAH +#endif + +#ifdef VERIFY_AFFINITIES +#include "affinity.h" +CHECK4(QuadTree,nw,ne,sw,se,tree) +#endif + +static int adj(Direction d, ChildType ct) +{ + BLAH; + switch (d) + { + case north: + return ((ct==northeast) || (ct==northwest)); + case south: + return ((ct==southeast) || (ct==southwest)); + case east: + return ((ct==northeast) || (ct==southeast)); + case west: + return ((ct==southwest) || (ct==northwest)); + } +} + +static ChildType reflect(Direction d, ChildType ct) +{ + BLAH; + if ((d==west) || (d==east)) + { + switch(ct) + { + case northwest: + return northeast; + case northeast: + return northwest; + case southeast: + return southwest; + case southwest: + return southeast; + } + } + switch(ct) + { + case northwest: + return southwest; + case northeast: + return southeast; + case southeast: + return northeast; + case southwest: + return northwest; + } +} + +int CountTree(QuadTree tree) +{ + QuadTree nw,ne,sw,se; + + BLAH; + nw = tree->nw; ne = tree->ne; sw = tree->sw; se = tree->se; + if (nw==NULL && ne==NULL && sw==NULL && se==NULL) + return 1; + else + return CountTree(nw) + CountTree(ne) + CountTree(sw) + + CountTree(se); +} + +static QuadTree child(QuadTree tree, ChildType ct) +{ + BLAH; + switch(ct) + { + case northeast: + return tree->ne; + case northwest: + return tree->nw; + case southeast: + return tree->se; + case southwest: + return tree->sw; + } +} + +static QuadTree gtequal_adj_neighbor(QuadTree tree, Direction d) +{ + QuadTree q,parent; + ChildType ct; + + BLAH; + parent=tree->parent; + ct=tree->childtype; + if ((parent!=NULL) && adj(d,ct)) + q=gtequal_adj_neighbor(parent,d); + else q=parent; + if (q && q->color==grey) { + return child(q,reflect(d,ct)); + } + else return q; +} + +static int sum_adjacent(QuadTree p, ChildType q1, ChildType q2, int size) +{ + BLAH; + if (p->color==grey) + { + return sum_adjacent(child(p,q1),q1,q2,size/2) + + sum_adjacent(child(p,q2),q1,q2,size/2); + } + else if (p->color==white) + { + return size; + } + else return 0; +} + +int perimeter(QuadTree tree, int size) +{ + int retval = 0; + QuadTree neighbor; + + BLAH; + if (tree->color==grey) + { + QuadTree child; +#ifdef FUTURES + future_cell_int fc_sw,fc_se,fc_ne; +#endif + +#ifndef FUTURES + child = tree->sw; + retval += perimeter(child,size/2); + child = tree->se; + retval += perimeter(child,size/2); + child = tree->ne; + retval += perimeter(child,size/2); + child = tree->nw; + retval += perimeter(child,size/2); +#else + child = tree->sw; + FUTURE(child,size/2,perimeter,&fc_sw); + child = tree->se; + FUTURE(child,size/2,perimeter,&fc_se); + child = tree->ne; + FUTURE(child,size/2,perimeter,&fc_ne); + child = tree->nw; + retval = perimeter(child,size/2); + TOUCH(&fc_sw); + TOUCH(&fc_se); + TOUCH(&fc_ne); + retval += fc_sw.value + fc_se.value + fc_ne.value; +#endif + } + else if (tree->color==black) + { + /* North */ + neighbor=gtequal_adj_neighbor(tree,north); + if ((neighbor==NULL) || (neighbor->color==white)) retval+=size; + else if (neighbor->color==grey) + retval+=sum_adjacent(neighbor,southeast,southwest,size); + /* East */ + neighbor=gtequal_adj_neighbor(tree,east); + if ((neighbor==NULL) || (neighbor->color==white)) retval+=size; + else if (neighbor->color==grey) + retval+=sum_adjacent(neighbor,southwest,northwest,size); + /* South */ + neighbor=gtequal_adj_neighbor(tree,south); + if ((neighbor==NULL) || (neighbor->color==white)) retval+=size; + else if (neighbor->color==grey) + retval+=sum_adjacent(neighbor,northwest,northeast,size); + /* West */ + neighbor=gtequal_adj_neighbor(tree,west); + if ((neighbor==NULL) || (neighbor->color==white)) retval+=size; + else if (neighbor->color==grey) + retval+=sum_adjacent(neighbor,northeast,southeast,size); + } + return retval; +} + +#ifdef PLAIN +double wallclock; +int __NumNodes; +#endif + +int main() +{ + QuadTree tree; + int count; + int level; + int i; + + BLAH; + level = 12; + __NumNodes = 1; + + chatting("Perimeter with %d levels on %d processors\n",level,__NumNodes); + tree=MakeTree(2048,0,0,0,__NumNodes-1,NULL,southeast,level); +#ifdef VERIFY_AFFINITIES + Docheck_tree(tree); +#endif + count=CountTree(tree); + chatting("# of leaves is %d\n",count); + + + timer_start(0); + for(i=0;i<100;i++) { + count=perimeter(tree,4096); + } + timer_stop(0); + + chatting("perimeter is %d\n",count); + chatting("Time elapsed = %f milliseconds\n", timer_elapsed(0)); +#ifdef FUTURES + __ShutDown(); +#endif + exit(0); +} + diff --git a/test/ccured_olden/perimeter/maketree.c b/test/ccured_olden/perimeter/maketree.c new file mode 100644 index 00000000..294ff028 --- /dev/null +++ b/test/ccured_olden/perimeter/maketree.c @@ -0,0 +1,120 @@ +#include "perimeter.h" + +static int CheckOutside(int x, int y) +{ + int euclid = x*x+y*y; + + if (euclid > 4194304) return 1; + if (euclid < 1048576) return -1; + return 0; +} + +static int CheckIntersect(int center_x, int center_y, int size) +{ + int sum; + + if (!CheckOutside(center_x+size,center_y+size) && + !CheckOutside(center_x+size,center_y-size) && + !CheckOutside(center_x-size,center_y-size) && + !CheckOutside(center_x-size,center_y+size)) return 2; + sum=CheckOutside(center_x+size,center_y+size) + + CheckOutside(center_x+size,center_y-size) + + CheckOutside(center_x-size,center_y-size) + + CheckOutside(center_x-size,center_y+size); + if ((sum==4) || (sum==-4)) return 0; + return 1; +} + +QuadTree MakeTree(int size, int center_x, int center_y, int lo_proc, + int hi_proc, QuadTree parent, ChildType ct, int level) +{ + int intersect=0; + QuadTree retval; + +#ifdef FUTURES + retval = (QuadTree) ALLOC(lo_proc,sizeof(*retval)); +#else + retval = (QuadTree) mymalloc(sizeof(*retval)); +#endif + retval->parent = parent; + retval->childtype = ct; + + intersect = CheckIntersect(center_x,center_y,size); + size = size/2; + if ((intersect==0) && (size<512)) + { + retval->color = white; + retval->nw = NULL; + retval->ne = NULL; + retval->sw = NULL; + retval->se = NULL; + } + else if (intersect==2) + { + retval->color=black; + retval->nw = NULL; + retval->ne = NULL; + retval->sw = NULL; + retval->se = NULL; + } + else + { + if (!level) + { + retval->color = black; + retval->nw = NULL; + retval->ne = NULL; + retval->sw = NULL; + retval->se = NULL; + } + else + { + int mid1,mid2; +#ifdef FUTURES + future_cell_int fc_sw,fc_se,fc_ne; +#endif + + mid1 = (lo_proc+hi_proc)/2; + mid2 = (lo_proc+hi_proc+1)/2; + +#ifndef FUTURES + retval->sw = MakeTree(size,center_x-size,center_y-size, + (mid2+hi_proc+1)/2,hi_proc,retval, + southwest,level-1); + retval->se = MakeTree(size,center_x+size,center_y-size, + mid2,(mid2+hi_proc)/2,retval, + southeast,level-1); + retval->ne = MakeTree(size,center_x+size,center_y+size, + (lo_proc+mid1+1)/2,mid1,retval, + northeast,level-1); + retval->nw = MakeTree(size,center_x-size,center_y+size, + lo_proc,(lo_proc+mid1)/2,retval, + northwest,level-1); +#else + FUTURE(size,center_x-size,center_y-size, + (mid2+hi_proc+1)/2,hi_proc,retval, + southwest,level-1,MakeTree,&fc_sw); + FUTURE(size,center_x+size,center_y-size, + mid2,(mid2+hi_proc)/2,retval, + southeast,level-1,MakeTree,&fc_se); + FUTURE(size,center_x+size,center_y+size, + (lo_proc+mid1+1)/2,mid1,retval, + northeast,level-1,MakeTree,&fc_ne); + retval->nw = MakeTree(size,center_x-size,center_y+size, + lo_proc,(lo_proc+mid1)/2,retval, + northwest,level-1); + TOUCH(&fc_sw); + retval->sw = (QuadTree) fc_sw.value; + TOUCH(&fc_se); + retval->se = (QuadTree) fc_se.value; + TOUCH(&fc_ne); + retval->ne = (QuadTree) fc_ne.value; +#endif + retval->color = grey; + } + } + return retval; +} + + + diff --git a/test/ccured_olden/perimeter/out.orig b/test/ccured_olden/perimeter/out.orig new file mode 100644 index 00000000..98edab51 --- /dev/null +++ b/test/ccured_olden/perimeter/out.orig @@ -0,0 +1,3 @@ +Perimeter with 12 levels on 1 processors +# of leaves is 73432 +perimeter is 24576 diff --git a/test/ccured_olden/perimeter/output b/test/ccured_olden/perimeter/output new file mode 100644 index 00000000..5906be43 --- /dev/null +++ b/test/ccured_olden/perimeter/output @@ -0,0 +1,4 @@ +Perimeter with 12 levels on 1 processors +# of leaves is 73432 +perimeter is 24576 +Time elapsed = 2970.000000 milliseconds diff --git a/test/ccured_olden/perimeter/perimeter.h b/test/ccured_olden/perimeter/perimeter.h new file mode 100644 index 00000000..e5cc086b --- /dev/null +++ b/test/ccured_olden/perimeter/perimeter.h @@ -0,0 +1,54 @@ +#define NULL 0 + +#ifndef PLAIN +#include <cm/cmmd.h> + +#ifdef FUTURES +#include "future-cell.h" +#endif +#include "mem-ref.h" +#endif + +typedef enum {black, white, grey} Color; +typedef enum {northwest, northeast, southwest, southeast} ChildType; +typedef enum {north, east, south, west} Direction; + +typedef struct quad_struct { + Color color; + ChildType childtype; + struct quad_struct *nw ; // {50}; + struct quad_struct *ne ; //{50}; + struct quad_struct *sw ; // {50}; + struct quad_struct *se ; //{50}; + struct quad_struct *parent; // {50}; +} *QuadTree; + +QuadTree MakeTree(int size, int center_x, int center_y, int lo_proc, + int hi_proc, QuadTree parent, ChildType ct, int level); + + +#include <stdlib.h> //malloc +#include <stdio.h> // printf + +extern void exit(int); + +extern int __NumNodes; + +#ifdef PLAIN +#include <time.h> +#define local +#define mymalloc malloc +#define CMMD_node_timer_clear(x) (void)0 +#define TIMESTART(clk) {clk=(double)clock();} +#define TIMESTOP(clk) {clk=1000000.0 * ((double)clock()-(clk))/CLOCKS_PER_SEC;} +extern double wallclock; +#define timer_start(x) TIMESTART(wallclock) +#define timer_stop(x) TIMESTOP(wallclock) +#define timer_elapsed(x) (wallclock / 1000.0) +#define chatting printf +#define NOTEST() (void)0 +#define RETEST() (void)0 +#define mymalloc malloc +#endif + + diff --git a/test/ccured_olden/perimeter/testit b/test/ccured_olden/perimeter/testit new file mode 100755 index 00000000..35723c5f --- /dev/null +++ b/test/ccured_olden/perimeter/testit @@ -0,0 +1,25 @@ +#!/bin/sh +# test a perimeter binary + +if [ "$1" = "" ]; then + echo "usage: $0 ./perimeter.exe" + exit +fi + +# all of perimeter's output is to stdout +echo "running: $1 >output" +if ! $1 >output; then + echo "$1 failed directly" + exit 2 +fi + +if ! grep -v "Time elapsed" <output | diff out.orig - >out.diff 2>&1 ; then + # For some reason diff returns error code but an empty diff ! + if test -s out.diff; then + echo "$1 got the wrong answer. See out.diff." + exit 4 + fi +fi +echo "$1 seems to work" +rm -f out.diff +
\ No newline at end of file |