1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#include "nmglobal.h"
#include "randnum.h"
/*********************
** NUMERIC HEAPSORT **
**********************
** This test implements a heapsort algorithm, performed on an
** array of longs.
*/
static clock_t DoNumSortIteration(long *arraybase, unsigned long arraysize, unsigned int numarrays);
static void LoadNumArrayWithRand(long *array, unsigned long arraysize, unsigned int numarrays);
static inline void NumHeapSort(long *array, unsigned long bottom, unsigned long top);
static inline void NumSift(long *array, unsigned long min, unsigned long max);
/**************
** DoNumSort **
***************
** This routine performs the CPU numeric sort test.
*/
void
DoNumSort (void)
{
const char* context = "CPU:Numeric Sort";
SortStruct* numsortstruct = &global_numsortstruct;
clock_t total_time = 0;
int iterations = 0;
long* arraybase = NULL;
/*
** See if we need to do self adjustment code.
*/
if (numsortstruct->adjust == FALSE) {
numsortstruct->adjust = TRUE;
/*
** Self-adjustment code. The system begins by sorting 1
** array. If it does that in no time, then two arrays
** are built and sorted. This process continues until
** enough arrays are built to handle the tolerance.
*/
numsortstruct->numarrays = 1;
while (1) {
arraybase = realloc(arraybase, numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long));
if (!arraybase) {
fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
exit(1);
}
/*
** Do an iteration of the numeric sort. If the
** elapsed time is less than or equal to the permitted
** minimum, then allocate for more arrays and
** try again.
*/
if (DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays) > global_min_ticks) {
break;
}
if (numsortstruct->numarrays > NUMNUMARRAYS) {
puts("CPU:NSORT -- NUMNUMARRAYS hit.");
}
++numsortstruct->numarrays;
}
} else {
arraybase = malloc(numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long));
if (!arraybase) {
fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
exit(1);
}
}
/*
** All's well if we get here. Repeatedly perform sorts until the
** accumulated elapsed time is greater than # of seconds requested.
*/
do {
total_time += DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays);
++iterations;
} while (total_time < numsortstruct->request_secs * CLOCKS_PER_SEC);
free(arraybase);
numsortstruct->sortspersec = (double)(iterations * numsortstruct->numarrays * CLOCKS_PER_SEC) / (double)total_time;
}
/***********************
** DoNumSortIteration **
************************
** This routine executes one iteration of the numeric
** sort benchmark. It returns the number of ticks
** elapsed for the iteration.
*/
static clock_t
DoNumSortIteration(long *arraybase, unsigned long arraysize, unsigned int numarrays)
{
clock_t start, stop;
unsigned long i;
/*
** Load up the array with random numbers
*/
LoadNumArrayWithRand(arraybase, arraysize, numarrays);
start = clock();
for (i = 0; i < numarrays; i++) {
NumHeapSort(&arraybase[i], 0L, arraysize - 1L);
}
stop = clock();
return stop - start;
}
/*************************
** LoadNumArrayWithRand **
**************************
** Load up an array with random longs.
*/
static void
LoadNumArrayWithRand(long *array, unsigned long arraysize, unsigned int numarrays)
{
long i; /* Used for index */
long *darray; /* Destination array pointer */
/* Initialize the random number generator */
randnum(13);
/* Load up first array with randoms */
for (i = 0; i < arraysize; i++) {
array[i] = randnum(0);
}
/*
** Now, if there's more than one array to load, copy the
** first into each of the others.
*/
darray = array;
while (--numarrays) {
darray += arraysize;
memcpy(darray, array, arraysize * sizeof(long));
}
}
/****************
** NumHeapSort **
*****************
** Pass this routine a pointer to an array of long
** integers. Also pass in minimum and maximum offsets.
** This routine performs a heap sort on that array.
*/
static inline void
NumHeapSort(long *array, unsigned long bottom, unsigned long top)
{
unsigned long temp; /* Used to exchange elements */
unsigned long i; /* Loop index */
/*
** First, build a heap in the array
*/
for (i = (top / 2L); i > 0; i--) {
NumSift(array, i, top);
}
/*
** Repeatedly extract maximum from heap and place it at the
** end of the array. When we get done, we'll have a sorted
** array.
*/
for (i = top; i > 0; i--) {
NumSift(array, bottom, i);
temp = *array;
*array = *(array + i);
*(array + i) = temp;
}
}
/************
** NumSift **
*************
** Peforms the sift operation on a numeric array,
** constructing a heap in the array.
*/
static inline void
NumSift(long *array, unsigned long min, unsigned long max)
{
unsigned long k;
unsigned long temp; /* Used for exchange */
while ( ( min * 2 ) <= max ) {
k = min * 2;
if ( k < max ) {
if ( array[k] < array[k+1L] ) {
++k;
}
}
if ( array[min] < array[k] ) {
temp = array[k];
array[k] = array[min];
array[min] = temp;
min = k;
} else {
min = max + 1;
}
}
}
|
