docThe Design and Implementation of the PBIW - LSCAD
download 
Denúncia Transcrição
The Design and Implementation of the PBIW - LSCAD
The Design and Implementation of the PBIW Encoding on the ρ-Vex Processor Renan Albuquerque Marks School of Computing Federal University of Mato Grosso do Sul Campo Grande - MS Brazil April, 12, 2012 Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 1 / 24 Contents 1 Evolution of ρ-Vex PBIW encoding PBIW 1.0 Encoding PBIW 2.0 Encoding 2 Static Results 3 Final remarks Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 2 / 24 PBIW 1.0 Initial phase of development: Following strictly all PBIW guidelines; Some edge-cases showing undesirable results; The encoding algorithm was complex; Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 3 / 24 PBIW 1.0 Encoding Read Registers Pattern Pointer 0 1 2 3 4 Write Regs 5 6 7 8 9 10 11 Br Src 9 bit Imm 12 bit Imm 6 bits 40 bits 18 bits Figure: Instruction format Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 4 / 24 PBIW 1.0 Encoding Operation Operation Operation Operation 96 bits Figure: Pattern format 24 bits Opcode (7 bits) Imm Sw (2 bits) Read Reg 1 (4 bits) Read Reg 2 (4 bits) Br Destiny (3 bits) Figure: Operation Format Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 5 / 24 PBIW 2.0 Mature phase of development: Added some customizations to the encoding; The “bad” edge-cases addressed more efficiently; The encoding algorithm became more simple; Added data dependency analysis; As fast as 1.0 version; Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 6 / 24 PBIW 2.0 Encoding Read and Write Registers Br Src & Destiny Registers Pattern Pointer 0 6 bits 1 2 3 4 5 6 BR Src BRF Src 40 bits 7 8 9 10 11 9 bit Imm 12 bit Imm 18 bits Figure: Instruction format Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 7 / 24 PBIW 2.0 Encoding Operation Operation Operation Operation 96 bits Figure: Pattern format 24 bits Opcode (7 bits) Imm Sw (2 bits) Read Reg 1 (4 bits) Read Reg 2 (4 bits) Br Destiny (3 bits) Figure: Operation Format Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 8 / 24 PBIW 2.0 Encoding 24 bits Opcode (4 bits) Imm Sw (2 bits) 000 Br Src (3 bits) Read Reg 1 (4 bits) Read Reg 2 (4 bits) Br Destiny (3 bits) Figure: Operations that uses Branch Source Registers Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 9 / 24 PBIW 2.0 Encoding Br Src & Destiny Registers 0 1 2 3 4 5 6 7 8 9 10 11 000 Br Src (3 bits) Br Destiny (3 bits) Figure: Branch Source and Destiny pointers Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 10 / 24 PBIW 2.0 Encoding Br Src & Destiny Registers 0 1 2 3 BR 0100 4 5 6 7 8 9 10 11 101 Br Src (3 bits) Br Destiny (3 bits) Figure: Branch (True) Syllable Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 11 / 24 PBIW 2.0 Encoding Br Src & Destiny Registers 0 1 2 3 BRF 0100 4 5 6 7 8 9 10 11 110 Br Src (3 bits) Br Destiny (3 bits) Figure: Branch False Syllable Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 12 / 24 Static Results R-Vex PBIW 1.0 Benchmark alloca_test Codificação PBIW Tamanho em Bytes Quantidade Instruções Padrões Instruções Padrões rVex Total Quantidade Tamanho em Bytes Taxa Compressão Taxa Reuso Variação em Bytes 44 15 352 180 532 31 496 1,07 2,93 36 avl_tree 558 44 4464 528 4992 481 7696 0,65 12,68 -2704 bmm 261 53 2088 636 2724 178 2848 0,96 4,92 -124 counting_sort 134 23 1072 276 1348 95 1520 0,89 5,83 -172 dag 132 41 1056 492 1548 68 1088 1,42 3,22 460 double_linked_list 128 33 1024 396 1420 89 1424 1,00 3,88 -4 eight 7 7 56 84 140 7 112 1,25 1,00 28 fact2 26 11 208 132 340 16 256 1,33 2,36 84 fib 11 10 88 120 208 8 128 1,63 1,10 80 fib_mem 21 15 168 180 348 15 240 1,45 1,40 108 fir 420 94 3360 1128 4488 164 2624 1,71 4,47 1864 fir_int 30 14 240 168 408 21 336 1,21 2,14 72 hyper 7 7 56 84 140 7 112 1,25 1,00 28 ifthen 7 7 56 84 140 7 112 1,25 1,00 28 122 30 976 360 1336 91 1456 0,92 4,07 -120 28 11 224 132 356 18 288 1,24 2,55 68 3 3 24 36 60 3 48 1,25 1,00 12 mergesort 162 36 1296 432 1728 102 1632 1,06 4,50 96 mm 107 33 856 396 1252 61 976 1,28 3,24 276 mm_dyn 103 29 824 348 1172 928 1,26 3,55 nested 100 31 800 372 1172 50 800 1,47 3,23 372 nested_complex 623 70 4984 840 5824 373 5968 0,98 8,90 -144 linked_list local_var_test longlong params_test2 58 244 23 6 184 72 256 14 224 1,14 3,83 32 608 115 4864 1380 6244 197 3152 1,98 5,29 3092 84 25 672 300 972 64 1024 0,95 3,36 -52 struct_test 4 3 32 36 68 3 48 1,42 1,33 20 switch_test 22 9 176 108 284 20 320 0,89 2,44 -36 sqrt strcpy binary_tree wave 65 26 520 312 832 48 768 1,08 2,50 64 66 21 528 252 780 43 688 1,13 3,14 92 Total Geral 3906 822 31248 9864 41112 2332 37312 35,11 100,87 3800,00 Média Geral 260 28 1078 340 1418 80 1287 1,21 3,48 131,03 R-Vex PBIW 2.0 Benchmark alloca_test Codificação PBIW Tamanho em Bytes Quantidade Instruções Padrões Instruções Padrões rVex Total Quantidade Tamanho em Bytes Taxa Compressão Taxa Reuso Variação em Variação Bytes PBIW Bytes 1.0 vs Raw vs 2.0 42 20 336 240 576 31 496 1,16 2,10 80 8,27 avl_tree 531 67 4248 804 5052 481 7696 0,66 7,93 -2644 1,20 bmm 220 95 1760 1140 2900 178 2848 1,02 2,32 52 counting_sort 120 43 960 516 1476 95 1520 0,97 2,79 -44 9,50 96 60 768 720 1488 68 1088 1,37 1,60 400 -3,88 108 49 864 588 1452 89 1424 1,02 2,20 28 2,25 eight 7 7 56 84 140 7 112 1,25 1,00 28 fact2 18 16 144 192 336 16 256 1,31 1,13 80 -1,18 8 8 64 96 160 8 128 1,25 1,00 32 -23,08 dag double_linked_list fib fib_mem 6,46 0,00 21 18 168 216 384 15 240 1,60 1,17 144 10,34 178 86 1424 1032 2456 164 2624 0,94 2,07 -168 -45,28 fir_int 29 19 232 228 460 21 336 1,37 1,53 124 12,75 hyper 7 7 56 84 140 7 112 1,25 1,00 28 0,00 ifthen 7 7 56 84 140 7 112 1,25 1,00 28 0,00 107 46 856 552 1408 91 1456 0,97 2,33 -48 5,39 27 16 216 192 408 18 288 1,42 1,69 120 14,61 3 3 24 36 60 3 48 1,25 1,00 12 0,00 fir linked_list local_var_test longlong mergesort 141 55 1128 660 1788 102 1632 1,10 2,56 156 3,47 mm 85 48 680 576 1256 61 976 1,29 1,77 280 0,32 mm_dyn 81 51 648 612 1260 58 928 1,36 1,59 332 nested nested_complex params_test2 sqrt strcpy 7,51 86 42 688 504 1192 50 800 1,49 2,05 392 1,71 511 113 4088 1356 5444 373 5968 0,91 4,52 -524 -6,52 22 8 176 96 272 14 224 1,21 2,75 48 6,25 208 106 1664 1272 2936 197 3152 0,93 1,96 -216 -52,98 76 37 608 444 1052 64 1024 1,03 2,05 28 8,23 struct_test 4 4 32 48 80 3 48 1,67 1,00 32 17,65 switch_test 22 10 176 120 296 20 320 0,93 2,20 -24 4,23 binary_tree 63 34 504 408 912 48 768 1,19 1,85 144 9,62 wave 57 36 456 432 888 43 688 1,29 1,58 200 13,85 Total Geral 2885 1111 23080 13332 36412 2332 37312 34,43 59,73 -900,00 10,68 Média Geral 192 38 796 460 1256 80 1287 1,19 2,06 -31,03 0,37 0 R-Vex PBIW 1.0 R-Vex PBIW 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Number of PBIW Instructions 700 600 500 400 300 200 100 0 R-Vex PBIW 1.0 R-Vex PBIW 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Number of PBIW Patterns 140 120 100 80 60 40 20 0,00 R-Vex PBIW 1.0 R-Vex PBIW 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Reuse Ratio 14,00 12,00 10,00 8,00 6,00 4,00 2,00 0,00 R-Vex PBIW 1.0 R-Vex PBIW 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Compression Ratio 2,50 2,00 1,50 1,00 0,50 Percent 30 20 10 0 -10 -20 -30 -40 -50 -60 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Size variation in % from 2.0 vs 1.0 Percent 4000 R-Vex PBIW 1.0 3000 2000 1000 0 -1000 -2000 -3000 R-Vex PBIW 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test Size variation in bytes: Uncompressed vs PBIW 0 R-Vex PBIW 1.0 R-Vex PBIW 2.0 Size variation in % from 1.0 to 2.0 wave binary_tree switch_test struct_test strcpy sqrt params_test2 nested_complex nested mm_dyn mm mergesort longlong local_var_test linked_list ifthen hyper fir_int fir fib_mem fib fact2 eight double_linked_list dag counting_sort bmm avl_tree alloca_test PBIW Total Size 7000 30,00 6000 20,00 5000 10,00 0,00 4000 -10,00 3000 -20,00 2000 -30,00 1000 -40,00 -50,00 -60,00 Final Remarks Collect data for: Dynamic analysis; Power analysis; Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 23 / 24 Thanks! Renan A. Marks (FACOM - UFMS) Design PBIW Encoding for ρ-Vex April, 12, 2012 24 / 24
,! ' %$ @ C !"#$ @