summaryrefslogtreecommitdiff
path: root/cesar/ecos/packages/kernel/current/tests_smp/radix.C
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/ecos/packages/kernel/current/tests_smp/radix.C')
-rw-r--r--cesar/ecos/packages/kernel/current/tests_smp/radix.C909
1 files changed, 909 insertions, 0 deletions
diff --git a/cesar/ecos/packages/kernel/current/tests_smp/radix.C b/cesar/ecos/packages/kernel/current/tests_smp/radix.C
new file mode 100644
index 0000000000..b23dd6d356
--- /dev/null
+++ b/cesar/ecos/packages/kernel/current/tests_smp/radix.C
@@ -0,0 +1,909 @@
+/*************************************************************************/
+/* */
+/* Copyright (c) 1994 Stanford University */
+/* */
+/* All rights reserved. */
+/* */
+/* Permission is given to use, copy, and modify this software for any */
+/* non-commercial purpose as long as this copyright notice is not */
+/* removed. All other uses, including redistribution in whole or in */
+/* part, are forbidden without prior written permission. */
+/* */
+/* This software is provided with absolutely no warranty and no */
+/* support. */
+/* */
+/*************************************************************************/
+
+/*************************************************************************/
+/* */
+/* Integer radix sort of non-negative integers. */
+/* */
+/* Command line options: */
+/* */
+/* -pP : P = number of processors. */
+/* -rR : R = radix for sorting. Must be power of 2. */
+/* -nN : N = number of keys to sort. */
+/* -mM : M = maximum key value. Integer keys k will be generated such */
+/* that 0 <= k <= M. */
+/* -s : Print individual processor timing statistics. */
+/* -t : Check to make sure all keys are sorted correctly. */
+/* -o : Print out sorted keys. */
+/* -h : Print out command line options. */
+/* */
+/* Default: RADIX -p1 -n262144 -r1024 -m524288 */
+/* */
+/* Note: This version works under both the FORK and SPROC models */
+/* */
+/*************************************************************************/
+
+#include <stdio.h>
+#include <math.h>
+#include <tests_smp/getopt.h>
+
+#define DEFAULT_P 1
+#define DEFAULT_N 262144
+#define DEFAULT_R 1024
+#define DEFAULT_M 524288
+#define MAX_PROCESSORS 64
+#define RADIX_S 8388608.0e0
+#define RADIX 70368744177664.0e0
+#define SEED 314159265.0e0
+#define RATIO 1220703125.0e0
+#define PAGE_SIZE 4096
+#define PAGE_MASK (~(PAGE_SIZE-1))
+#define MAX_RADIX 4096
+
+#include <tests_smp/radix_arg.c>
+
+MAIN_ENV
+
+struct prefix_node {
+ int densities[MAX_RADIX];
+ int ranks[MAX_RADIX];
+ PAUSEDEC(done)
+ char pad[PAGE_SIZE];
+};
+
+struct global_memory {
+ int Index; /* process ID */
+ LOCKDEC(lock_Index) /* for fetch and add to get ID */
+ LOCKDEC(rank_lock) /* for fetch and add to get ID */
+ ALOCKDEC(section_lock,MAX_PROCESSORS) /* key locks */
+ BARDEC(barrier_rank) /* for ranking process */
+ BARDEC(barrier_key) /* for key sorting process */
+ double *ranktime;
+ double *sorttime;
+ double *totaltime;
+ int final;
+ unsigned int starttime;
+ unsigned int rs;
+ unsigned int rf;
+ struct prefix_node prefix_tree[2 * MAX_PROCESSORS];
+} *global;
+
+struct global_private {
+ char pad[PAGE_SIZE];
+ int *rank_ff; /* overall processor ranks */
+} gp[MAX_PROCESSORS];
+
+int *key[2]; /* sort from one index into the other */
+int **rank_me; /* individual processor ranks */
+int *key_partition; /* keys a processor works on */
+int *rank_partition; /* ranks a processor works on */
+
+int number_of_processors = DEFAULT_P;
+int max_num_digits;
+int radix = DEFAULT_R;
+int num_keys = DEFAULT_N;
+int max_key = DEFAULT_M;
+int log2_radix;
+int log2_keys;
+int dostats = 0;
+int test_result = 0;
+int doprint = 0;
+volatile cyg_thread *thread_array[64];
+
+int dbg_on = 0;
+double ran_num_init(unsigned int,double,double);
+double product_mod_46(double,double);
+int get_max_digits(int);
+int get_log2_radix(int);
+int get_log2_keys(int);
+void slave_sort();
+int log_2(int);
+void printerr(char *);
+void init(int,int,int);
+void test_sort(int);
+void printout();
+
+
+int smp_cyg_test_main(argc, argv)
+
+int argc;
+char **argv;
+
+{
+ int i;
+ int p;
+ int quotient;
+ int remainder;
+ int sum_i;
+ int sum_f;
+ int mistake=0;
+ int size;
+ int **temp;
+ int **temp2;
+ int *a;
+ int c;
+ int n1;
+ extern char *optarg;
+ double mint, maxt, avgt;
+ double minrank, maxrank, avgrank;
+ double minsort, maxsort, avgsort;
+ unsigned int start;
+ int done = 0;
+ int start_p;
+ int end_p;
+ int level;
+ int index;
+ int base;
+ int offset;
+ int toffset;
+
+
+ memset (thread_array,0,sizeof(thread_array));
+
+ CLOCK(start)
+
+ while ((c = getopt(argc, argv, "p:r:n:m:stoh")) != -1) {
+ switch(c) {
+ case 'p': number_of_processors = atoi(optarg);
+ number_of_processors = HAL_SMP_CPU_MAX;
+ if (number_of_processors < 1) {
+ printerr("P must be >= 1\n");
+ exit(-1);
+ }
+ if (number_of_processors > MAX_PROCESSORS) {
+ printerr("Maximum processors (MAX_PROCESSORS) exceeded\n");
+ exit(-1);
+ }
+ break;
+ case 'r': radix = atoi(optarg);
+ if (radix < 1) {
+ printerr("Radix must be a power of 2 greater than 0\n");
+ exit(-1);
+ }
+ log2_radix = log_2(radix);
+ if (log2_radix == -1) {
+ printerr("Radix must be a power of 2\n");
+ exit(-1);
+ }
+ break;
+ case 'n': num_keys = atoi(optarg);
+ if (num_keys < 1) {
+ printerr("Number of keys must be >= 1\n");
+ exit(-1);
+ }
+ break;
+ case 'm': max_key = atoi(optarg);
+ if (max_key < 1) {
+ printerr("Maximum key must be >= 1\n");
+ exit(-1);
+ }
+ break;
+ case 's': dostats = !dostats;
+ break;
+ case 't': test_result = !test_result;
+ break;
+ case 'o': doprint = !doprint;
+ break;
+ case 'h': diag_printf("Usage: RADIX <options>\n\n");
+ diag_printf(" -pP : P = number of processors.\n");
+ diag_printf(" -rR : R = radix for sorting. Must be power of 2.\n");
+ diag_printf(" -nN : N = number of keys to sort.\n");
+ diag_printf(" -mM : M = maximum key value. Integer keys k will be generated such\n");
+ diag_printf(" that 0 <= k <= M.\n");
+ diag_printf(" -s : Print individual processor timing statistics.\n");
+ diag_printf(" -t : Check to make sure all keys are sorted correctly.\n");
+ diag_printf(" -o : Print out sorted keys.\n");
+ diag_printf(" -h : Print out command line options.\n\n");
+ diag_printf("Default: RADIX -p%1d -n%1d -r%1d -m%1d\n",
+ DEFAULT_P,DEFAULT_N,DEFAULT_R,DEFAULT_M);
+ exit(0);
+ }
+ }
+
+ if (number_of_processors > 64) {
+ printf("Maximal 64 processes\n");
+ exit(0);
+ }
+
+ MAIN_INITENV(,80000000)
+
+ log2_radix = log_2(radix);
+ log2_keys = log_2(num_keys);
+ global = (struct global_memory *) G_MALLOC(sizeof(struct global_memory))
+ key[0] = (int *) G_MALLOC(num_keys*sizeof(int));
+ key[1] = (int *) G_MALLOC(num_keys*sizeof(int));
+ key_partition = (int *) G_MALLOC((number_of_processors+1)*sizeof(int));
+ rank_partition = (int *) G_MALLOC((number_of_processors+1)*sizeof(int));
+
+ if ((global == NULL)) {
+ diag_printf("ERROR: Cannot malloc enough memory %d\n",sizeof(struct global_memory));
+ }
+
+ global->ranktime = (double *) G_MALLOC(number_of_processors*sizeof(double));
+ global->sorttime = (double *) G_MALLOC(number_of_processors*sizeof(double));
+ global->totaltime = (double *) G_MALLOC(number_of_processors*sizeof(double));
+ size = number_of_processors*(radix*sizeof(int)+sizeof(int *));
+ rank_me = (int **) G_MALLOC(size);
+
+ if ((global == NULL) || (key[0] == NULL) || (key[1] == NULL) ||
+ (key_partition == NULL) || (rank_partition == NULL) ||
+ (rank_me == NULL)) {
+ diag_printf("ERROR: Cannot malloc enough memory\n");
+ exit(-1);
+ }
+
+ temp = rank_me;
+ temp2 = temp + number_of_processors;
+ a = (int *) temp2;
+ for (i=0;i<number_of_processors;i++) {
+ *temp = (int *) a;
+ temp++;
+ a += radix;
+ }
+ for (i=0;i<number_of_processors;i++) {
+ gp[i].rank_ff = (int *) G_MALLOC(radix*sizeof(int)+PAGE_SIZE);
+ }
+ LOCKINIT(global->lock_Index)
+ LOCKINIT(global->rank_lock)
+ ALOCKINIT(global->section_lock,MAX_PROCESSORS)
+ BARINIT(global->barrier_rank)
+ BARINIT(global->barrier_key)
+
+ for (i=0; i<2*number_of_processors; i++) {
+ PAUSEINIT(global->prefix_tree[i].done);
+ }
+
+ global->Index = 0;
+ max_num_digits = get_max_digits(max_key);
+ diag_printf("\n");
+ diag_printf("Integer Radix Sort\n");
+ diag_printf(" %d Keys\n",num_keys);
+ diag_printf(" %d Processors\n",number_of_processors);
+ diag_printf(" Radix = %d\n",radix);
+ diag_printf(" Max key = %d\n",max_key);
+ diag_printf("\n");
+
+ quotient = num_keys / number_of_processors;
+ remainder = num_keys % number_of_processors;
+ sum_i = 0;
+ sum_f = 0;
+ p = 0;
+ diag_printf("key_partition\n",max_key);
+ while (sum_i < num_keys) {
+ key_partition[p] = sum_i;
+ p++;
+ sum_i = sum_i + quotient;
+ sum_f = sum_f + remainder;
+ sum_i = sum_i + sum_f / number_of_processors;
+ sum_f = sum_f % number_of_processors;
+ }
+ key_partition[p] = num_keys;
+
+ quotient = radix / number_of_processors;
+ remainder = radix % number_of_processors;
+ sum_i = 0;
+ sum_f = 0;
+ p = 0;
+ diag_printf("rank_partition\n",max_key);
+ while (sum_i < radix) {
+ rank_partition[p] = sum_i;
+ p++;
+ sum_i = sum_i + quotient;
+ sum_f = sum_f + remainder;
+ sum_i = sum_i + sum_f / number_of_processors;
+ sum_f = sum_f % number_of_processors;
+ }
+ rank_partition[p] = radix;
+
+/* POSSIBLE ENHANCEMENT: Here is where one might distribute the key,
+ rank_me, rank, and gp data structures across physically
+ distributed memories as desired.
+
+ One way to place data is as follows:
+
+ for (i=0;i<number_of_processors;i++) {
+ Place all addresses x such that:
+ &(key[0][key_partition[i]]) <= x < &(key[0][key_partition[i+1]])
+ on node i
+ &(key[1][key_partition[i]]) <= x < &(key[1][key_partition[i+1]])
+ on node i
+ &(rank_me[i][0]) <= x < &(rank_me[i][radix-1]) on node i
+ &(gp[i]) <= x < &(gp[i+1]) on node i
+ &(gp[i].rank_ff[0]) <= x < &(gp[i].rank_ff[radix]) on node i
+ }
+ start_p = 0;
+ i = 0;
+
+ for (toffset = 0; toffset < number_of_processors; toffset ++) {
+ offset = toffset;
+ level = number_of_processors >> 1;
+ base = number_of_processors;
+ while ((offset & 0x1) != 0) {
+ offset >>= 1;
+ index = base + offset;
+ Place all addresses x such that:
+ &(global->prefix_tree[index]) <= x <
+ &(global->prefix_tree[index + 1]) on node toffset
+ base += level;
+ level >>= 1;
+ }
+ } */
+
+ /* Fill the random-number array. */
+
+ for (i = 1; i < number_of_processors; i++) {
+ CREATE(slave_sort,thread_array[i])
+ }
+
+ slave_sort();
+
+ for (i = 1; i < number_of_processors; i++) {
+ while(thread_array[i]) {};
+ }
+
+ diag_printf("\n");
+ diag_printf(" PROCESS STATISTICS\n");
+ diag_printf(" Total Rank Sort\n");
+ diag_printf(" Proc Time Time Time\n");
+ diag_printf(" 0 %10.0f %10.0f %10.0f\n",
+ global->totaltime[0],global->ranktime[0],
+ global->sorttime[0]);
+ if (dostats) {
+ maxt = avgt = mint = global->totaltime[0];
+ maxrank = avgrank = minrank = global->ranktime[0];
+ maxsort = avgsort = minsort = global->sorttime[0];
+ for (i=1; i<number_of_processors; i++) {
+ if (global->totaltime[i] > maxt) {
+ maxt = global->totaltime[i];
+ }
+ if (global->totaltime[i] < mint) {
+ mint = global->totaltime[i];
+ }
+ if (global->ranktime[i] > maxrank) {
+ maxrank = global->ranktime[i];
+ }
+ if (global->ranktime[i] < minrank) {
+ minrank = global->ranktime[i];
+ }
+ if (global->sorttime[i] > maxsort) {
+ maxsort = global->sorttime[i];
+ }
+ if (global->sorttime[i] < minsort) {
+ minsort = global->sorttime[i];
+ }
+ avgt += global->totaltime[i];
+ avgrank += global->ranktime[i];
+ avgsort += global->sorttime[i];
+ }
+ avgt = avgt / number_of_processors;
+ avgrank = avgrank / number_of_processors;
+ avgsort = avgsort / number_of_processors;
+ for (i=1; i<number_of_processors; i++) {
+ diag_printf(" %3d %10.0f %10.0f %10.0f\n",
+ i,global->totaltime[i],global->ranktime[i],
+ global->sorttime[i]);
+ }
+ diag_printf(" Avg %10.0f %10.0f %10.0f\n",avgt,avgrank,avgsort);
+ diag_printf(" Min %10.0f %10.0f %10.0f\n",mint,minrank,minsort);
+ diag_printf(" Max %10.0f %10.0f %10.0f\n",maxt,maxrank,maxsort);
+ diag_printf("\n");
+ }
+
+ diag_printf("\n");
+ global->starttime = start;
+ diag_printf(" TIMING INFORMATION\n");
+ diag_printf("Start time : %16d\n",
+ global->starttime);
+ diag_printf("Initialization finish time : %16d\n",
+ global->rs);
+ diag_printf("Overall finish time : %16d\n",
+ global->rf);
+ diag_printf("Total time with initialization : %16d\n",
+ global->rf-global->starttime);
+ diag_printf("Total time without initialization : %16d\n",
+ global->rf-global->rs);
+ diag_printf("\n");
+
+ if (doprint) {
+ printout();
+ }
+ if (test_result) {
+ test_sort(global->final);
+ }
+
+ MAIN_END;
+}
+
+void slave_sort()
+{
+ int i, j, k, kk, Ind;
+ int MyNum;
+ int this_key;
+ int tmp;
+ int last_key;
+ int loopnum;
+ double ran_num;
+ double sum;
+ int shiftnum;
+ int bb;
+ int my_key;
+ int key_start;
+ int key_stop;
+ int rank_start;
+ int rank_stop;
+ int from=0;
+ int to=1;
+ int *key_density; /* individual processor key densities */
+ unsigned int time1;
+ unsigned int time2;
+ unsigned int time3;
+ unsigned int time4;
+ unsigned int time5;
+ unsigned int time6;
+ double ranktime=0;
+ double sorttime=0;
+ int *key_from;
+ int *key_to;
+ int *rank_me_mynum;
+ int *rank_me_i;
+ int *rank_ff_mynum;
+ int stats;
+ struct prefix_node* n;
+ struct prefix_node* r;
+ struct prefix_node* l;
+ struct prefix_node* my_node;
+ struct prefix_node* their_node;
+ volatile int* prefx;
+ int index;
+ int level;
+ int base;
+ int offset;
+
+ diag_printf("SlaveSort %d\n",cyg_hal_get_current_threadid());
+
+ stats = dostats;
+
+ LOCK(global->lock_Index)
+ MyNum = global->Index;
+ global->Index++;
+ UNLOCK(global->lock_Index)
+
+/* POSSIBLE ENHANCEMENT: Here is where one might pin processes to
+ processors to avoid migration */
+
+ key_density = (int *) malloc(radix*sizeof(int));
+
+ /* Fill the random-number array. */
+
+ key_start = key_partition[MyNum];
+ key_stop = key_partition[MyNum + 1];
+ rank_start = rank_partition[MyNum];
+ rank_stop = rank_partition[MyNum + 1];
+ if (rank_stop == radix) {
+ rank_stop--;
+ }
+
+ diag_printf("init %d, %d-%d\n",cyg_hal_get_current_threadid(),key_start,key_stop);
+ init(key_start,key_stop,from);
+
+ BARRIER(global->barrier_key, number_of_processors, 1 )
+
+/* POSSIBLE ENHANCEMENT: Here is where one might reset the
+ statistics that one is measuring about the parallel execution */
+
+ BARRIER(global->barrier_key, number_of_processors, 2)
+
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time1)
+ }
+
+/* Do 1 iteration per digit. */
+
+ rank_me_mynum = rank_me[MyNum];
+ rank_ff_mynum = gp[MyNum].rank_ff;
+ for (loopnum=0;loopnum<max_num_digits;loopnum++) {
+ shiftnum = (loopnum * log2_radix);
+ bb = (radix-1) << shiftnum;
+
+/* generate histograms based on one digit */
+
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time2)
+ }
+
+ for (i = 0; i < radix; i++) {
+ rank_me_mynum[i] = 0;
+ }
+ key_from = (int *) key[from];
+ key_to = (int *) key[to];
+ for (i=key_start;i<key_stop;i++) {
+ my_key = key_from[i] & bb;
+ my_key = my_key >> shiftnum;
+ rank_me_mynum[my_key]++;
+ }
+ key_density[0] = rank_me_mynum[0];
+ for (i=1;i<radix;i++) {
+ key_density[i] = key_density[i-1] + rank_me_mynum[i];
+ }
+
+ BARRIER(global->barrier_rank, number_of_processors,3)
+
+ n = &(global->prefix_tree[MyNum]);
+ for (i = 0; i < radix; i++) {
+ n->densities[i] = key_density[i];
+ n->ranks[i] = rank_me_mynum[i];
+ }
+ offset = MyNum;
+ level = number_of_processors >> 1;
+ base = number_of_processors;
+ if ((MyNum & 0x1) == 0) {
+ SETPAUSE(global->prefix_tree[base + (offset >> 1)].done);
+ }
+ while ((offset & 0x1) != 0) {
+ offset >>= 1;
+ r = n;
+ l = n - 1;
+ index = base + offset;
+ n = &(global->prefix_tree[index]);
+ WAITPAUSE(n->done);
+ CLEARPAUSE(n->done);
+ if (offset != (level - 1)) {
+ for (i = 0; i < radix; i++) {
+ n->densities[i] = r->densities[i] + l->densities[i];
+ n->ranks[i] = r->ranks[i] + l->ranks[i];
+ }
+ } else {
+ for (i = 0; i < radix; i++) {
+ n->densities[i] = r->densities[i] + l->densities[i];
+ }
+ }
+ base += level;
+ level >>= 1;
+ if ((offset & 0x1) == 0) {
+ SETPAUSE(global->prefix_tree[base + (offset >> 1)].done);
+ }
+ }
+ BARRIER(global->barrier_rank, number_of_processors,4);
+
+ if (MyNum != (number_of_processors - 1)) {
+ offset = MyNum;
+ level = number_of_processors;
+ base = 0;
+ while ((offset & 0x1) != 0) {
+ offset >>= 1;
+ base += level;
+ level >>= 1;
+ }
+ my_node = &(global->prefix_tree[base + offset]);
+ offset >>= 1;
+ base += level;
+ level >>= 1;
+ while ((offset & 0x1) != 0) {
+ offset >>= 1;
+ base += level;
+ level >>= 1;
+ }
+ their_node = &(global->prefix_tree[base + offset]);
+ WAITPAUSE(my_node->done);
+ CLEARPAUSE(my_node->done);
+ for (i = 0; i < radix; i++) {
+ my_node->densities[i] = their_node->densities[i];
+ }
+ } else {
+ my_node = &(global->prefix_tree[(2 * number_of_processors) - 2]);
+ }
+ offset = MyNum;
+ level = number_of_processors;
+ base = 0;
+ while ((offset & 0x1) != 0) {
+ SETPAUSE(global->prefix_tree[base + offset - 1].done);
+ offset >>= 1;
+ base += level;
+ level >>= 1;
+ }
+ offset = MyNum;
+ level = number_of_processors;
+ base = 0;
+ for(i = 0; i < radix; i++) {
+ rank_ff_mynum[i] = 0;
+ }
+ while (offset != 0) {
+ if ((offset & 0x1) != 0) {
+ /* Add ranks of node to your left at this level */
+ l = &(global->prefix_tree[base + offset - 1]);
+ for (i = 0; i < radix; i++) {
+ rank_ff_mynum[i] += l->ranks[i];
+ }
+ }
+ base += level;
+ level >>= 1;
+ offset >>= 1;
+ }
+ for (i = 1; i < radix; i++) {
+ rank_ff_mynum[i] += my_node->densities[i - 1];
+ }
+
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time3);
+ }
+
+ BARRIER(global->barrier_rank, number_of_processors,5);
+
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time4);
+ }
+
+ /* put it in order according to this digit */
+
+ for (i = key_start; i < key_stop; i++) {
+ this_key = key_from[i] & bb;
+ this_key = this_key >> shiftnum;
+ tmp = rank_ff_mynum[this_key];
+ key_to[tmp] = key_from[i];
+ rank_ff_mynum[this_key]++;
+ } /* i */
+
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time5);
+ }
+
+ if (loopnum != max_num_digits-1) {
+ from = from ^ 0x1;
+ to = to ^ 0x1;
+ }
+
+ BARRIER(global->barrier_rank, number_of_processors, 6)
+
+ if ((MyNum == 0) || (stats)) {
+ ranktime += (time3 - time2);
+ sorttime += (time5 - time4);
+ }
+ } /* for */
+
+ BARRIER(global->barrier_rank, number_of_processors, 7)
+ if ((MyNum == 0) || (stats)) {
+ CLOCK(time6)
+ global->ranktime[MyNum] = ranktime;
+ global->sorttime[MyNum] = sorttime;
+ global->totaltime[MyNum] = time6-time1;
+ }
+ if (MyNum == 0) {
+ global->rs = time1;
+ global->rf = time6;
+ global->final = to;
+ }
+
+ thread_array[MyNum] = 0;
+}
+
+double product_mod_46(t1, t2) /* product_mod_46() returns the product
+ (mod 2^46) of t1 and t2. */
+double t1;
+double t2;
+
+{
+ double a1;
+ double b1;
+ double a2;
+ double b2;
+
+ a1 = (double)((int)(t1 / RADIX_S)); /* Decompose the arguments. */
+ a2 = t1 - a1 * RADIX_S;
+ b1 = (double)((int)(t2 / RADIX_S));
+ b2 = t2 - b1 * RADIX_S;
+ t1 = a1 * b2 + a2 * b1; /* Multiply the arguments. */
+ t2 = (double)((int)(t1 / RADIX_S));
+ t2 = t1 - t2 * RADIX_S;
+ t1 = t2 * RADIX_S + a2 * b2;
+ t2 = (double)((int)(t1 / RADIX));
+
+ return (t1 - t2 * RADIX); /* Return the product. */
+}
+
+double ran_num_init(k, b, t) /* finds the (k)th random number,
+ given the seed, b, and the ratio, t. */
+unsigned int k;
+double b;
+double t;
+
+{
+ unsigned int j;
+
+ while (k != 0) { /* while() is executed m times
+ such that 2^m > k. */
+ j = k >> 1;
+ if ((j << 1) != k) {
+ b = product_mod_46(b, t);
+ }
+ t = product_mod_46(t, t);
+ k = j;
+ }
+
+ return b;
+}
+
+int get_max_digits(max_key)
+
+int max_key;
+
+{
+ int done = 0;
+ int temp = 1;
+ int key_val;
+
+ key_val = max_key;
+ while (!done) {
+ key_val = key_val / radix;
+ if (key_val == 0) {
+ done = 1;
+ } else {
+ temp ++;
+ }
+ }
+ return temp;
+}
+
+int get_log2_radix(rad)
+
+int rad;
+
+{
+ int cumulative=1;
+ int out;
+
+ for (out = 0; out < 20; out++) {
+ if (cumulative == rad) {
+ return(out);
+ } else {
+ cumulative = cumulative * 2;
+ }
+ }
+ diag_printf("ERROR: Radix %d not a power of 2\n", rad);
+ exit(-1);
+}
+
+int get_log2_keys(num_keys)
+
+int num_keys;
+
+{
+ int cumulative=1;
+ int out;
+
+ for (out = 0; out < 30; out++) {
+ if (cumulative == num_keys) {
+ return(out);
+ } else {
+ cumulative = cumulative * 2;
+ }
+ }
+ diag_printf("ERROR: Number of keys %d not a power of 2\n", num_keys);
+ exit(-1);
+}
+
+int log_2(number)
+
+int number;
+
+{
+ int cumulative = 1;
+ int out = 0;
+ int done = 0;
+
+ while ((cumulative < number) && (!done) && (out < 50)) {
+ if (cumulative == number) {
+ done = 1;
+ } else {
+ cumulative = cumulative * 2;
+ out ++;
+ }
+ }
+
+ if (cumulative == number) {
+ return(out);
+ } else {
+ return(-1);
+ }
+}
+
+void printerr(s)
+
+char *s;
+
+{
+ diag_printf("ERROR: %s\n",s);
+}
+
+void init(key_start,key_stop,from)
+
+int key_start;
+int key_stop;
+int from;
+
+{
+ double ran_num;
+ double sum;
+ int tmp;
+ int i;
+ int *key_from;
+
+ ran_num = ran_num_init((key_start << 2) + 1, SEED, RATIO);
+ sum = ran_num / RADIX;
+ key_from = (int *) key[from];
+ for (i = key_start; i < key_stop; i++) {
+ ran_num = product_mod_46(ran_num, RATIO);
+ sum = sum + ran_num / RADIX;
+ ran_num = product_mod_46(ran_num, RATIO);
+ sum = sum + ran_num / RADIX;
+ ran_num = product_mod_46(ran_num, RATIO);
+ sum = sum + ran_num / RADIX;
+ key_from[i] = (int) ((sum / 4.0) * max_key);
+ tmp = (int) ((key_from[i])/100);
+ ran_num = product_mod_46(ran_num, RATIO);
+ sum = ran_num / RADIX;
+ }
+
+}
+
+void test_sort(final)
+
+int final;
+
+{
+ int i;
+ int mistake = 0;
+ int *key_final;
+
+ diag_printf("\n");
+ diag_printf(" TESTING RESULTS\n");
+ key_final = key[final];
+ for (i = 0; i < num_keys-1; i++) {
+ if (key_final[i] > key_final[i + 1]) {
+ diag_printf("error with key %d, value %d %d \n",
+ i,key_final[i],key_final[i + 1]);
+ mistake++;
+ }
+ }
+
+ if (mistake) {
+ diag_printf("FAILED: %d keys out of place.\n", mistake);
+ } else {
+ diag_printf("PASSED: All keys in place.\n");
+ }
+ diag_printf("\n");
+}
+
+void printout()
+
+{
+ int i;
+ int mistake;
+ int *key_final;
+
+ key_final = (int *) key[global->final];
+ diag_printf("\n");
+ diag_printf(" SORTED KEY VALUES\n");
+ diag_printf("%8d ",key_final[0]);
+ for (i = 0; i < num_keys-1; i++) {
+ diag_printf("%8d ",key_final[i+1]);
+ if ((i+2)%5 == 0) {
+ diag_printf("\n");
+ }
+ }
+ diag_printf("\n");
+}
+
+#include <tests_smp/getopt.c>