반응형
|
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327 |
//==================================================== file = genzipf.c =====
//= Program to generate Zipf (power law) distributed random variables =
//===========================================================================
//= Notes: 1) Writes to a user specified output file =
//= 2) Generates user specified number of values =
//= 3) Run times is same as an empirical distribution generator =
//= 4) Implements p(i) = C/i^alpha for i = 1 to N where C is the =
//= normalization constant (i.e., sum of p(i) = 1). =
//=-------------------------------------------------------------------------=
//= Example user input: =
//= =
//= ---------------------------------------- genzipf.c ----- =
//= - Program to generate Zipf random variables - =
//= -------------------------------------------------------- =
//= Output file name ===================================> output.dat =
//= Random number seed =================================> 1 =
//= Alpha vlaue ========================================> 1.0 =
//= N value ============================================> 1000 =
//= Number of values to generate =======================> 5 =
//= -------------------------------------------------------- =
//= - Generating samples to file - =
//= -------------------------------------------------------- =
//= -------------------------------------------------------- =
//= - Done! =
//= -------------------------------------------------------- =
//=-------------------------------------------------------------------------=
//= Example output file ("output.dat" for above): =
//= =
//= 1 =
//= 1 =
//= 161 =
//= 17 =
//= 30 =
//=-------------------------------------------------------------------------=
//= Build: bcc32 genzipf.c =
//=-------------------------------------------------------------------------=
//= Execute: genzipf =
//=-------------------------------------------------------------------------=
//= Author: Kenneth J. Christensen =
//= University of South Florida =
//= WWW: http://www.csee.usf.edu/~christen =
//= Email: christen@csee.usf.edu =
//=-------------------------------------------------------------------------=
//= History: KJC (11/16/03) - Genesis (from genexp.c) =
//===========================================================================
//----- Include files -------------------------------------------------------
#include <assert.h> // Needed for assert() macro
#include <stdio.h> // Needed for printf()
#include <stdlib.h> // Needed for exit() and ato*()
#include <math.h> // Needed for pow()
#include <iostream>
#include <thread>
using namespace std;
//----- Constants -----------------------------------------------------------
#define FALSE 0 // Boolean false
#define TRUE 1 // Boolean true
//----- Function prototypes -------------------------------------------------
int zipf(double alpha, int n, int thrNum); // Returns a Zipf random variable
double rand_val(int seed); // Jain's RNG
#define N 80000000
#define T 4
#define STKSIZE N
int* arr = NULL;
int top = 0;
int stack[STKSIZE];
static int first[T] = { TRUE, }; // Static first time flag
static double c[T] = { 0, }; // Normalization constant
void init_stack() {
top = 0;
}
void push(int i) {
if (top < STKSIZE)
stack[top++] = i;
else {
printf("stack full\n");
exit(0);
return;
}
}
int pop() {
if (top != 0)
return stack[--top];
else
return 0;
}
int isStackEmpty() {
if (top != 0)
return 0;
else
return 1;
}
void quickSort() {
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = N - 1;
push(r);
push(l);
while (!isStackEmpty()) {
l = pop();
r = pop();
if (r - l > 0) {
p = arr[r];
i = l - 1;
j = r;
while (1) {
while (arr[++i] < p);
while (arr[--j] > p);
if (i >= j)
break;
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[i];
arr[i] = arr[r];
arr[r] = t;
push(r);
push(i + 1);
push(i - 1);
push(l);
}
}
}
void threadZipf(double alpha, double n, int nrData, int* arr, int thrNum) {
for (int i = 0; i < nrData; i++)
{
arr[i] = zipf(alpha, n, thrNum);
}
}
//===== Main program ========================================================
void main(void)
{
FILE *fp; // File pointer to output file
char file_name[256]; // Output file name string
char temp_string[256]; // Temporary string variable
double alpha; // Alpha parameter
double n; // N parameter
//int num_values; // Number of values
int zipf_rv; // Zipf random variable
int i; // Loop counter
arr = (int*)malloc(sizeof(int)*N);
for (int i = 0; i < T; i++) {
first[i] = TRUE;
c[i] = 0;
}
// Output banner
printf("---------------------------------------- genzipf.c ----- \n");
printf("- Program to generate Zipf random variables - \n");
printf("-------------------------------------------------------- \n");
// Prompt for output filename and then create/open the file
printf("Output file name ===================================> ");
scanf("%s", file_name);
// Prompt for random number seed and then use it
printf("Random number seed (greater than 0) ================> ");
scanf("%s", temp_string);
rand_val((int)atoi(temp_string));
// Prompt for alpha value
printf("Alpha value ========================================> ");
scanf("%s", temp_string);
alpha = atof(temp_string);
// Prompt for N value
printf("N value ============================================> ");
scanf("%s", temp_string);
n = atoi(temp_string);
//// Prompt for number of values to generate
// Output "generating" message
printf("-------------------------------------------------------- \n");
printf("- Generating samples to file - \n");
printf("-------------------------------------------------------- \n");
int nrData = N / T;
printf("nrData:%d\n", nrData);
int** dArr = (int**)malloc(sizeof(int*)*T);
for (int i = 0; i < T; i++) {
dArr[i] = (int*)malloc(sizeof(int)*nrData);
}
printf("start threading..\n");
thread* thr[T];
for (int i = 0; i < T; i++) {
thr[i] = new thread(threadZipf, alpha, n, nrData, dArr[i], i);
}
printf("go\n");
for (int i = 0; i < T; i++) {
thr[i]->join();
}
printf("finish threading..\n");
for (int i = 0; i < T; i++) {
for (int j = 0; j < nrData; j++) {
arr[i*nrData + j] = dArr[i][j];
}
}
for (int i = 0; i < T; i++) {
delete thr[i];
}
//// Generate and output zipf random variables
quickSort();
printf("start writing...\n");
fp = fopen(file_name, "wb");
if (fp == NULL) {
printf("ERROR in creating output file (%s) \n", file_name);
exit(1);
}
int wholeData = N;
fwrite(&wholeData, sizeof(int), 1, fp);
fwrite(arr, sizeof(int), N, fp);
// Output "done" message and close the output file
printf("-------------------------------------------------------- \n");
printf("- Done! \n");
printf("-------------------------------------------------------- \n");
fclose(fp);
for (int i = 0; i < T; i++) {
free(dArr[i]);
}
free(dArr);
free(arr);
}
int zipf(double alpha, int n, int thrNum)
{
double z; // Uniform random number (0 < z < 1)
double sum_prob; // Sum of probabilities
double zipf_value; // Computed exponential value to be returned
int i; // Loop counter
// Compute normalization constant on first call only
if (first[thrNum] == TRUE)
{
/*for (i = 1; i <= n; i++)
c = c + (1.0 / pow((double)i, alpha));*/
c[thrNum] = 2.0 * sqrt(n) - 2;
c[thrNum] = 1.0 / c[thrNum];
first[thrNum] = FALSE;
}
// Pull a uniform random number (0 < z < 1)
do
{
z = rand_val(0);
} while ((z == 0) || (z == 1));
// Map z to the value
sum_prob = 0;
//for (i = 1; i <= n; i++)
double t = z / (2.0 * c[thrNum]) + 1;
t *= t;
t -= 1;
zipf_value = t;
return(zipf_value);
}
//=========================================================================
//= Multiplicative LCG for generating uniform(0.0, 1.0) random numbers =
//= - x_n = 7^5*x_(n-1)mod(2^31 - 1) =
//= - With x seeded to 1 the 10000th x value should be 1043618065 =
//= - From R. Jain, "The Art of Computer Systems Performance Analysis," =
//= John Wiley & Sons, 1991. (Page 443, Figure 26.2) =
//=========================================================================
double rand_val(int seed)
{
const long a = 16807; // Multiplier
const long m = 2147483647; // Modulus
const long q = 127773; // m div a
const long r = 2836; // m mod a
static long x; // Random int value
long x_div_q; // x divided by q
long x_mod_q; // x modulo q
long x_new; // New x value
// Set the seed if argument is non-zero and then return zero
if (seed > 0)
{
x = seed;
return(0.0);
}
// RNG using integer arithmetic
x_div_q = x / q;
x_mod_q = x % q;
x_new = (a * x_mod_q) - (r * x_div_q);
if (x_new > 0)
x = x_new;
else
x = x_new + m;
// Return a random value between 0.0 and 1.0
return((double)x / m);
} |
cs |
반응형
'컴퓨터 공학' 카테고리의 다른 글
| 데이터베이스 용어 정리 (0) | 2018.09.12 |
|---|---|
| 엔비디아 (Nvidia) GPU 사용률 확인 프로그램 (0) | 2017.06.02 |
| 인텔 컴파일러 클러스터 버전 무료로 설치하는 방법 (+ SIMD 사용) (0) | 2017.04.18 |
| 데이터 과학 프로젝트를 위한 17 가지의 데이터셋 (0) | 2017.03.18 |
| [퍼옴] __declspec(align(32)) volatile 해석하기 (0) | 2017.03.18 |