source: perf/stream2runs/stream2runs.cxx @ 495

Last change on this file since 495 was 495, checked in by ksherdy, 9 years ago

Update svn:externals

File size: 16.9 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3#include <errno.h>
4#include <string.h>
5#include <sys/types.h>
6#include <sys/stat.h>
7#include <unistd.h>
8#include <sched.h>
9#include <iostream>
10using namespace std;
11
12// Test Repetitions
13#define RUNS 1
14
15// Test Versions
16#define DEFAULT
17//#define BRANCH_REDUCTION
18
19// Performance Measurement
20#ifdef PAPI
21#include "../clocker/cc.h"
22#include "../clocker/cc.cxx"
23CC * code_clocker;
24#endif
25
26// Templated SIMD
27#define TEMPLATED_SIMD_LIB
28#include "./lib/lib_simd.h"
29
30typedef SIMD_type BytePack;
31typedef SIMD_type BitBlock;
32
33#define SIMD_REGISTER_BIT_WIDTH (sizeof(SIMD_type) << 3)
34#define REGISTER_BIT_WIDTH (sizeof(void *) << 3)
35
36// Bit stream methods
37#ifdef TEMPLATED_SIMD_LIB
38#define s2p_step(s0, s1, hi_mask, shift, p0, p1) \
39{\
40  BitBlock t0, t1;\
41  t0 = simd<16>::pack<h,h>(s0, s1);\
42  t1 = simd<16>::pack<l,l>(s0, s1);\
43  p0 = simd_if(hi_mask, t0, simd<16>::srli<shift>(t1));\
44  p1 = simd_if(hi_mask, simd<16>::slli<shift>(t0), t1);\
45}
46#endif
47#ifndef TEMPLATED_SIMD_LIB
48#define s2p_step(s0, s1, hi_mask, shift, p0, p1) \
49{\
50  BitBlock t0, t1;\
51  t0 = simd_pack_16_hh(s0, s1);\
52  t1 = simd_pack_16_ll(s0, s1);\
53  p0 = simd_if(hi_mask, t0, simd_srli_16(t1, shift));\
54  p1 = simd_if(hi_mask, simd_slli_16(t0, shift), t1);\
55}
56#endif
57
58static inline void s2p_bytepack(BytePack s[], BitBlock p[]) {
59#ifdef TEMPLATED_SIMD_LIB
60    BitBlock mask_2 = simd<2>::himask();
61    BitBlock mask_4 = simd<4>::himask();
62    BitBlock mask_8 = simd<8>::himask();
63#endif
64#ifndef TEMPLATED_SIMD_LIB
65    BitBlock mask_2 = simd_himask_2;
66    BitBlock mask_4 = simd_himask_4;
67    BitBlock mask_8 = simd_himask_8;
68#endif
69    BitBlock bit00224466_0, bit00224466_1, bit00224466_2, bit00224466_3;
70    BitBlock bit11335577_0, bit11335577_1, bit11335577_2, bit11335577_3;
71    BitBlock bit00004444_0, bit22226666_0, bit00004444_1, bit22226666_1;
72    BitBlock bit11115555_0, bit33337777_0, bit11115555_1, bit33337777_1;
73#if (BYTE_ORDER == BIG_ENDIAN)
74    s2p_step(s[0], s[1], mask_2, 1, bit00224466_0, bit11335577_0);
75    s2p_step(s[2], s[3], mask_2, 1, bit00224466_1, bit11335577_1);
76    s2p_step(s[4], s[5], mask_2, 1, bit00224466_2, bit11335577_2);
77    s2p_step(s[6], s[7], mask_2, 1, bit00224466_3, bit11335577_3);
78#endif
79#if (BYTE_ORDER == LITTLE_ENDIAN)
80    s2p_step(s[7], s[6], mask_2, 1, bit00224466_0, bit11335577_0);
81    s2p_step(s[5], s[4], mask_2, 1, bit00224466_1, bit11335577_1);
82    s2p_step(s[3], s[2], mask_2, 1, bit00224466_2, bit11335577_2);
83    s2p_step(s[1], s[0], mask_2, 1, bit00224466_3, bit11335577_3);
84#endif
85    s2p_step(bit00224466_0, bit00224466_1, mask_4, 2, bit00004444_0, bit22226666_0);
86    s2p_step(bit00224466_2, bit00224466_3, mask_4, 2, bit00004444_1, bit22226666_1);
87    s2p_step(bit11335577_0, bit11335577_1, mask_4, 2, bit11115555_0, bit33337777_0);
88    s2p_step(bit11335577_2, bit11335577_3, mask_4, 2, bit11115555_1, bit33337777_1);
89    s2p_step(bit00004444_0, bit00004444_1, mask_8, 4, p[0], p[4]);
90    s2p_step(bit11115555_0, bit11115555_1, mask_8, 4, p[1], p[5]);
91    s2p_step(bit22226666_0, bit22226666_1, mask_8, 4, p[2], p[6]);
92    s2p_step(bit33337777_0, bit33337777_1, mask_8, 4, p[3], p[7]);
93}
94
95#define double_int64_adc(x1, x2, y1, y2, rslt1, rslt2, carry) \
96  __asm__  ("sahf\n\t" \
97        "adc %[e1], %[z1]\n\t" \
98        "adc %[e2], %[z2]\n\t" \
99        "lahf\n\t" \
100     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
101         : "[z1]" (x1), "[z2]" (x2), \
102           [e1] "r" (y1), [e2] "r" (y2), \
103           "[carryflag]" (carry) \
104         : "cc")
105
106#define adc128(first, second, carry, sum) \
107do\
108{\
109  union {__m128i bitblock;\
110         uint64_t int64[2];} rslt;\
111\
112  union {__m128i bitblock;\
113         uint64_t int64[2];} x;\
114\
115  union {__m128i bitblock;\
116         uint64_t int64[2];} y;\
117\
118  x.bitblock = first;\
119  y.bitblock = second;\
120\
121  double_int64_adc(x.int64[0], x.int64[1], y.int64[0], y.int64[1], rslt.int64[0], rslt.int64[1], carry);\
122  sum = rslt.bitblock;\
123}while(0)
124
125#define double_int64_sbb(x1, x2, y1, y2, rslt1, rslt2, carry) \
126  __asm__  ("sahf\n\t" \
127        "sbb %[e1], %[z1]\n\t" \
128        "sbb %[e2], %[z2]\n\t" \
129        "lahf\n\t" \
130     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
131         : "[z1]" (x1), "[z2]" (x2), \
132           [e1] "r" (y1), [e2] "r" (y2), \
133           "[carryflag]" (carry) \
134         : "cc")
135
136#define sbb128(first, second, carry, sum) \
137do\
138{ union {__m128i bitblock;\
139         uint64_t int64[2];} rslt;\
140\
141  union {__m128i bitblock;\
142         uint64_t int64[2];} x;\
143\
144  union {__m128i bitblock;\
145         uint64_t int64[2];} y;\
146\
147  x.bitblock = first;\
148  y.bitblock = second;\
149\
150  double_int64_sbb(x.int64[0], x.int64[1], y.int64[0], y.int64[1], \
151                   rslt.int64[0], rslt.int64[1], carry);\
152  sum = rslt.bitblock;\
153}while(0)
154
155static inline BitBlock bytepack2bitblock(BytePack U8[]);
156static inline BitBlock bytepack2bitblock(BytePack U8[]) {
157
158        // --- GENERATED CODE ---
159        BitBlock result;
160        BitBlock array_u8bit__5_;
161        //BitBlock AllOne = simd_const_1(1);
162        //BitBlock AllZero = simd_const_1(0);
163        BitBlock array_u8bit__2_;
164        BitBlock array_u8bit__3_;
165        BitBlock array_u8bit__4_;
166        BitBlock _strct_s2iclass__classify_bytes__temp4;
167        BitBlock _strct_s2iclass__classify_bytes__temp5;
168        BitBlock _strct_s2iclass__classify_bytes__temp2;
169        BitBlock _strct_s2iclass__classify_bytes__temp3;
170        BitBlock array_u8bit__6_;
171        BitBlock _strct_s2iclass__classify_bytes__temp1;
172        BitBlock array_u8bit__0_;
173        BitBlock array_u8bit__1_;
174        BitBlock array_u8bit__7_;       
175       
176        BitBlock u8[8];
177       
178        s2p_bytepack(U8,u8);
179        array_u8bit__0_ = u8[0];
180        array_u8bit__1_ = u8[1];
181        array_u8bit__2_ = u8[2];
182        array_u8bit__3_ = u8[3];
183        array_u8bit__4_ = u8[4];
184        array_u8bit__5_ = u8[5];
185        array_u8bit__6_ = u8[6];
186        array_u8bit__7_ = u8[7];
187
188        _strct_s2iclass__classify_bytes__temp1 = simd_or(array_u8bit__0_,array_u8bit__1_);
189        _strct_s2iclass__classify_bytes__temp2 = simd_and(array_u8bit__2_,array_u8bit__3_);
190        _strct_s2iclass__classify_bytes__temp3 = simd_andc(_strct_s2iclass__classify_bytes__temp2,_strct_s2iclass__classify_bytes__temp1);
191        _strct_s2iclass__classify_bytes__temp4 = simd_or(array_u8bit__5_,array_u8bit__6_);
192        _strct_s2iclass__classify_bytes__temp5 = simd_and(array_u8bit__4_,_strct_s2iclass__classify_bytes__temp4);     
193        result = simd_andc(_strct_s2iclass__classify_bytes__temp3,_strct_s2iclass__classify_bytes__temp5);
194       
195        return result;
196}
197
198static inline size_t scan_thru(size_t cursor, size_t stream);
199static inline size_t scan_thru(size_t cursor, size_t stream) {
200        return (cursor + stream) & (~stream);
201}
202
203#ifdef DEFAULT
204
205/**
206 * Given a span stream buffer (bit stream) returns parallel arrays of span starts, span lengths, and the span count.
207 *
208 * bit_stream_buffer                                    IN  - Bit stream input buffer.
209 * bit_stream_general_register_blocks   IN  - Stream buffer count expressed as a count of the number of general registers widths ().
210 * start_index                                                  OUT - Bit stream span start positions, 0-based index.
211 * lengths                                                              OUT - Bit stream span lengths.
212 * span_count                                                   OUT - Total span count. start_index & lengths are parallel arrays.
213 *
214 * This routine leverages carry propagation together with the compiler builtin instruction to efficiently scan/calculate the start position
215 * and length of bit stream spans.
216 *
217 * --- Performance Analysis ---
218 *
219 * For each general register width we load a general register with the next bitstream value and complement this value.
220 *
221 * For each scan_thru operation some probability exists that we hit a general register width boundary and the
222 * condition cursor != 0 *may be* mispredicted. 
223 *
224 * One hypothesis is that for short spans and gaps branch mis-predictions are reduced since the branch predictor may
225 * be a better to train on this conditional.
226 *
227 * A second hypothesis is that the most significant penalty of short spans and gaps is that short spans and gaps result
228 * in more calls to the count forward leading zeroes.
229 *
230 */
231
232static inline void stream2runs(size_t bit_stream_buffer [], size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count);
233static inline void stream2runs(size_t bit_stream_buffer [], size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count) {
234       
235  size_t stream = 0;
236  size_t not_stream = 0;
237  size_t parallel_arrays_index = 0;
238 
239  size_t block_index = 0;
240  size_t cursor = 1;
241 
242  size_t leading_zeroes = 0;
243  size_t shift = 0;
244 
245  if(0 < bit_stream_general_register_blocks) {
246          stream = bit_stream_buffer[parallel_arrays_index];
247          not_stream = ~stream;
248  }
249   
250  while(block_index < bit_stream_general_register_blocks) {
251 
252          while(1) { 
253                         
254                        cursor = scan_thru(cursor, not_stream);
255                       
256                        if(cursor != 0) { // found span start
257                                leading_zeroes = cfzl(cursor);
258                                start_index[parallel_arrays_index] = leading_zeroes + (block_index * REGISTER_BIT_WIDTH); // stores (memory writes) may be the largest cost                             
259                                break;
260                        } else {
261                                block_index++;
262                                if(block_index >= bit_stream_general_register_blocks) { // this *should* be predicted correctly
263                                        break; 
264                                }
265                                stream = bit_stream_buffer[block_index];
266                                not_stream = ~stream;
267                                cursor = 1;
268                        }       
269          }
270         
271          while(1) {
272                 
273                        cursor = scan_thru(cursor, stream);
274                       
275                        if(cursor != 0) {       
276                                lengths[parallel_arrays_index] = cfzl(cursor) + (block_index * REGISTER_BIT_WIDTH) - start_index[parallel_arrays_index];
277                                parallel_arrays_index++;
278                                break;
279                        } else {
280                                block_index++;
281                                if(block_index >= bit_stream_general_register_blocks) { 
282                                        break; 
283                                }
284                                stream = bit_stream_buffer[block_index];
285                                not_stream = ~stream;
286                                cursor = 1;
287                        }                 
288          }
289  }
290 
291  *span_count = parallel_arrays_index;
292}
293#endif
294
295#ifdef BRANCH_REDUCTION
296
297static inline void stream2runs(unsigned char * bit_stream_buffer, size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count);
298static inline void stream2runs(unsigned char * bit_stream_buffer, size_t bit_stream_general_register_blocks, size_t start_index [], size_t lengths [], size_t * span_count) {
299       
300  size_t stream = 0;
301  size_t not_stream = 0;
302  size_t index = 0;
303
304 
305  size_t buffer_index = 0;
306  size_t block_index = 0;
307  size_t cursor = 1;
308 
309  size_t leading_zeroes = 0;
310  size_t stream_shift = 0;
311 
312  if(0 < bit_stream_general_register_blocks) {
313          stream = *(((size_t *) bit_stream_buffer) + index);
314          not_stream = ~stream;
315  }
316   
317  while(buffer_index < bit_stream_general_register_blocks) {
318 
319          while(1) { 
320                         
321                        cursor = scan_thru(cursor, not_stream);
322                       
323                        if(cursor != 0) {
324                                leading_zeroes = cfzl(cursor);
325                                start_index[index] = leading_zeroes + (buffer_index << 3);
326
327                                stream_shift = leading_zeroes >> 3;
328                                buffer_index += stream_shift;
329                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
330                                not_stream = ~(*((size_t *) (bit_stream_buffer + buffer_index)));
331                                cursor = cursor >> (stream_shift << 3);                 
332                                break;
333                               
334                        } else {
335                                buffer_index++;
336                                if(buffer_index >= bit_stream_general_register_blocks) {
337                                        break;
338                                }                               
339                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
340                                not_stream = ~stream;
341                                cursor = 1;
342                        }
343               
344          }
345         
346          while(1) {
347                 
348                        cursor = scan_thru(cursor, stream);
349                       
350                        if(cursor != 0) {
351                                leading_zeroes = cfzl(cursor);
352                                lengths[index] = leading_zeroes + (buffer_index << 3) - start_index[index];
353                                index++;
354       
355                                stream_shift = leading_zeroes >> 3;
356                                buffer_index += stream_shift;
357                                stream = *((size_t *) (bit_stream_buffer + buffer_index ));
358                                not_stream = ~(*((size_t *) (bit_stream_buffer + buffer_index )));
359                                cursor = cursor >> (stream_shift << 3);
360                                break;
361                               
362                        } else {
363                                buffer_index++;
364                                if(buffer_index >= bit_stream_general_register_blocks) {
365                                        break;
366                                }                               
367                                stream = *((size_t *) (bit_stream_buffer + buffer_index));
368                                not_stream = ~stream;
369                                cursor = 1;
370                        }                 
371          }
372  }
373 
374  *span_count = index;
375}
376#endif
377
378void print_chars(const char * str, size_t length);
379void print_chars(const char * str, size_t length) {
380
381        for(int i=0;i<length;i++) {
382                printf("%c",str[i]);
383        }
384        printf("\n");
385       
386}
387
388/*
389 * Binds a process to a core - Linux specifc (sched.h).
390 */
391void SetCPUAffinity();
392void SetCPUAffinity() {
393
394        printf("Setting CPU Affinity...\n");
395       
396    cpu_set_t mask;
397    unsigned int len = sizeof(mask);
398    if (sched_getaffinity(0, len, &mask) < 0) {
399        perror("sched_getaffinity");
400    }
401
402    printf("Original CPU Affinity Mask: %08lx\n", mask.__bits[0]);
403
404    //CPU_CLR(0, &mask); // (CPU 1)
405    //CPU_CLR(1, &mask); // (CPU 0)
406
407    if (sched_setaffinity(0, len, &mask) < 0) {
408       perror("sched_setaffinity");
409    }
410
411    printf("Modified CPU Affinity Mask: %08lx\n", mask.__bits[0]);
412} 
413
414int main(int argc, char * argv[]) {
415
416  if (argc < 2) {
417    printf("Usage: %s <filename> [<outputfile>]\n", argv[0]);
418          exit(-1);
419  }
420  char * filename = argv[1];
421
422  FILE *infile, *outfile;
423  infile = fopen(filename, "rb");
424  if (!infile) {
425      fprintf(stderr, "Error: cannot open %s for input.\n", filename);
426      exit(-1);
427  }
428
429  if (argc < 3) outfile = stdout;
430  else {
431    outfile = fopen(argv[2], "wb");
432    if (!outfile) {
433      fprintf(stderr, "Error: cannot open %s for writing.\n", argv[2]);
434      exit(-1);
435    }
436  }
437
438#ifdef PAPI
439    SetCPUAffinity();
440        char * src_filename = argv[1];
441        char * cmdline = new char[strlen(argv[0]) + strlen(argv[1]) +1 +1]; 
442        strcat(cmdline, argv[0]);
443        strcat(cmdline," ");
444        strcat(cmdline,argv[1]); 
445       
446        #define NUM_EVENTS 2
447        // PAPI_TOT_CYC 0x8000003b  Yes   No   Total cycles
448        // PAPI_L1_DCM  0x80000000  Yes   No   Level 1 data cache misses
449        // PAPI_L2_DCM  0x80000002  Yes   Yes  Level 2 data cache misses
450        // PAPI_L3_DCM  0x80000004  No    No   Level 3 data cache misses
451        // PAPI_BR_CN   0x8000002b  Yes   No   Conditional branch instructions
452        // PAPI_BR_TKN  0x8000002c  Yes   No   Conditional branch instructions taken
453        // PAPI_BR_NTK  0x8000002d  Yes   Yes  Conditional branch instructions not taken
454        // PAPI_BR_MSP  0x8000002e  Yes   No   Conditional branch instructions mispredicted
455        // PAPI_BR_PRC  0x8000002f  Yes   Yes  Conditional branch instructions correctly predicted
456       
457        int Events[NUM_EVENTS] = {PAPI_TOT_CYC, PAPI_BR_MSP};
458        int cal_size = 1000;
459        code_clocker = new CC(Events,NUM_EVENTS,cal_size);
460        code_clocker->set_cmd(cmdline);
461#endif 
462       
463  struct stat st;
464  stat(filename, &st);
465  int filesize = st.st_size;
466  size_t bytes = filesize;
467 
468  bytes += sizeof(SIMD_type);
469 
470  // allocate a byte buffer and pad with sizeof(SIMD_type) trailing zeroes
471  unsigned char * byte_buffer = (unsigned char *)simd_new(bytes);
472     
473  // slurp a source file into a byte buffer
474  int chars_read = fread(byte_buffer, sizeof(char), filesize, infile);
475  while(chars_read > 0) {
476          chars_read = fread(byte_buffer+chars_read, sizeof(char), filesize, infile);
477  }
478 
479  // mask trailing zeroes
480  memset(byte_buffer + filesize, 0, sizeof(SIMD_type)); 
481 
482  // allocate bit stream buffer
483  int simd_packs = bytes/sizeof(SIMD_type);
484 
485  #ifdef DEFAULT 
486    BitBlock * bit_stream_buffer = simd_new(simd_packs);
487  #endif 
488 
489  #ifdef BRANCH_REDUCTION
490    BitBlock * bit_stream_buffer = simd_new(simd_packs + 1); // pad at least an additional general width of bytes
491  #endif
492 
493  if(bit_stream_buffer == NULL) {
494      fprintf(stderr, "Error: out of memory.\n");
495      exit(-1);   
496  }
497
498  cout << "Source bytes: " << filesize << endl;
499  cout << "Allocate bytes: " << bytes << endl;
500  cout << "SIMD packs: " << simd_packs << endl; 
501  cout << "SIMD pack bytes: " << simd_packs * sizeof(SIMD_type) << endl << endl;
502 
503  #ifdef PAPI
504        code_clocker->start_interval();
505  #endif       
506               
507  // convert byte packs to bit streams
508  for(int i=0,j=0;i<simd_packs;i++,j+=SIMD_REGISTER_BIT_WIDTH) {
509          bit_stream_buffer[i] = bytepack2bitblock((BytePack *)(&byte_buffer[j]));
510  }
511
512  size_t max_span_count = simd_packs * SIMD_REGISTER_BIT_WIDTH /2;     
513  size_t * starts = new size_t[max_span_count];
514  size_t * lengths = new size_t[max_span_count];
515  size_t span_count = 0;
516
517  size_t general_register_blocks;
518               
519  #ifdef DEFAULT       
520        general_register_blocks = simd_packs * SIMD_REGISTER_BIT_WIDTH / REGISTER_BIT_WIDTH;
521        stream2runs((size_t *)bit_stream_buffer, general_register_blocks, starts, lengths, &span_count);
522  #endif 
523         
524  #ifdef BRANCH_REDUCTION
525        general_register_blocks = simd_packs * sizeof(SIMD_type);       
526        stream2runs((unsigned char *)bit_stream_buffer, general_register_blocks, starts, lengths, &span_count); // reduce bit stream butt
527  #endif
528
529  #ifdef PAPI
530        code_clocker->end_interval(bytes);
531  #endif       
532
533  printf("(pos,lgth) = span_value\n");
534  for(int i =0; i<span_count; i++) {
535        printf("(%zu,%zu) = ", starts[i], lengths[i]);
536        print_chars(((char *) byte_buffer) + starts[i], lengths[i]);     
537  }     
538  printf("\n");
539               
540  delete [] starts;
541  delete [] lengths;
542 
543  if(byte_buffer != NULL) {
544          simd_delete((SIMD_type *)byte_buffer);
545  }
546 
547  if(bit_stream_buffer != NULL) {
548          simd_delete(bit_stream_buffer);
549  }
550
551  if(infile != NULL) {
552          fclose(infile);
553  }
554 
555  if(argc > 3) {
556          fclose(outfile);
557  }
558 
559  #ifdef PAPI 
560        code_clocker->write_xml_file();
561        code_clocker->display_system_info();
562        code_clocker->display_raw_event_data();
563        delete code_clocker; 
564  #endif
565       
566  fprintf(stdout, "Done.\n");
567 
568  return(0);
569}
570
571
572
Note: See TracBrowser for help on using the repository browser.