Changeset 25404c7
- Timestamp:
- Jul 5, 2022, 9:36:59 AM (2 years ago)
- Branches:
- ADT, ast-experimental, master, pthread-emulation, qualifiedEnum
- Children:
- d4b37ab
- Parents:
- 06bdba4 (diff), 9c6443e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Files:
-
- 1 added
- 13 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/thesis/Makefile
r06bdba4 r25404c7 34 34 base \ 35 35 base_avg \ 36 base_ts2 \ 36 37 cache-share \ 37 38 cache-noshare \ -
doc/theses/thierry_delisle_PhD/thesis/fig/base.fig
r06bdba4 r25404c7 13 13 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 14 14 -6 15 6 6 375 5100 6675 525016 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6 450 5175 20 20 6450 5175 6470 517517 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6 525 5175 20 20 6525 5175 6545 517518 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 66 00 5175 20 20 6600 5175 6620 517515 6 6450 5025 6750 5175 16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100 17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100 18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100 19 19 -6 20 20 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400 … … 80 80 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 81 81 2400 2475 3000 2475 82 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 783 3300 5210 3150 4950 2850 4950 2700 5210 2850 5470 3150 547084 3300 521085 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 786 4500 5210 4350 4950 4050 4950 3900 5210 4050 5470 4350 547087 4500 521088 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 789 5700 5210 5550 4950 5250 4950 5100 5210 5250 5470 5550 547090 5700 521091 82 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 92 3600 5 700 3600 120083 3600 5400 3600 1200 93 84 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 94 4800 5 700 4800 120085 4800 5400 4800 1200 95 86 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 96 6000 5700 6000 1200 97 4 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001 98 4 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001 99 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4450 TS\001 100 4 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001 101 4 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001 102 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001 103 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001 104 4 2 -1 50 -1 0 12 0.0000 2 135 900 2100 5175 Processors\001 87 6000 5400 6000 1200 88 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 89 2700 4800 3300 4800 3300 5400 2700 5400 2700 4800 90 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 91 3900 4800 4500 4800 4500 5400 3900 5400 3900 4800 92 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 93 5100 4800 5700 4800 5700 5400 5100 5400 5100 4800 94 4 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 95 4 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 96 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 4450 TS\001 97 4 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 98 4 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 99 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001 100 4 2 -1 50 -1 0 12 0.0000 2 135 840 2100 5175 Processors\001 -
doc/theses/thierry_delisle_PhD/thesis/fig/base_avg.fig
r06bdba4 r25404c7 13 13 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 14 14 -6 15 6 6 375 5100 6675 525016 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6 450 5175 20 20 6450 5175 6470 517517 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6 525 5175 20 20 6525 5175 6545 517518 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 66 00 5175 20 20 6600 5175 6620 517515 6 6450 5025 6750 5175 16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100 17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100 18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100 19 19 -6 20 20 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400 … … 52 52 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 53 53 1 1 1.00 45.00 90.00 54 3900 39753900 360054 3900 4200 3900 3600 55 55 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 56 56 1 1 1.00 45.00 90.00 … … 61 61 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 62 62 1 1 1.00 45.00 90.00 63 5100 39755100 360063 5100 4200 5100 3600 64 64 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 65 65 1 1 1.00 45.00 90.00 … … 67 67 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 68 68 1 1 1.00 45.00 90.00 69 6300 39756300 360069 6300 4200 6300 3600 70 70 2 1 0 1 -1 7 50 -1 -1 0.000 0 0 -1 1 0 2 71 71 1 1 1.00 45.00 90.00 … … 75 75 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 76 76 1 1 1.00 45.00 90.00 77 4500 39754500 360077 4500 4200 4500 3600 78 78 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 79 79 2400 3375 3000 3375 80 80 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 81 81 2400 2475 3000 2475 82 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 783 3300 5210 3150 4950 2850 4950 2700 5210 2850 5470 3150 547084 3300 521085 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 786 4500 5210 4350 4950 4050 4950 3900 5210 4050 5470 4350 547087 4500 521088 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 789 5700 5210 5550 4950 5250 4950 5100 5210 5250 5470 5550 547090 5700 521091 82 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 92 3600 5 700 3600 120083 3600 5400 3600 1200 93 84 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 94 4800 5 700 4800 120085 4800 5400 4800 1200 95 86 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 96 6000 5700 6000 1200 87 6000 5400 6000 1200 88 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 89 2700 4800 3300 4800 3300 5400 2700 5400 2700 4800 90 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 91 3900 4800 4500 4800 4500 5400 3900 5400 3900 4800 92 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 93 5100 4800 5700 4800 5700 5400 5100 5400 5100 4800 97 94 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 98 95 2400 4050 3000 4050 99 4 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001 100 4 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001 101 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4450 MA\001 102 4 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001 103 4 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001 104 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001 105 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001 106 4 2 -1 50 -1 0 12 0.0000 2 135 900 2100 5175 Processors\001 107 4 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4200 TS\001 96 4 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 97 4 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 98 4 1 -1 50 -1 0 11 0.0000 2 120 300 2700 4450 MA\001 99 4 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 100 4 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 101 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001 102 4 2 -1 50 -1 0 12 0.0000 2 135 840 2100 5175 Processors\001 103 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 4225 TS\001 -
doc/theses/thierry_delisle_PhD/thesis/fig/cache-noshare.fig
r06bdba4 r25404c7 8 8 -2 9 9 1200 2 10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 247511 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 247512 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4 950 2550 456 456 4950 2550 4500 247513 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 247510 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575 11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575 12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575 13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575 14 14 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 15 2100 3300 3000 3300 3000 3600 2100 3600 2100 330015 1200 2400 2100 2400 2100 2700 1200 2700 1200 2400 16 16 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 17 2100 3900 3000 3900 3000 4500 2100 4500 2100 390017 1200 3000 2100 3000 2100 3600 1200 3600 1200 3000 18 18 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 19 3300 3300 4200 3300 4200 3600 3300 3600 3300 330019 2400 2400 3300 2400 3300 2700 2400 2700 2400 2400 20 20 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 21 3300 3900 4200 3900 4200 4500 3300 4500 3300 390021 2400 3000 3300 3000 3300 3600 2400 3600 2400 3000 22 22 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 23 4500 3300 5400 3300 5400 3600 4500 3600 4500 330023 3600 2400 4500 2400 4500 2700 3600 2700 3600 2400 24 24 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 25 4500 3900 5400 3900 5400 4500 4500 4500 4500 390025 3600 3000 4500 3000 4500 3600 3600 3600 3600 3000 26 26 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 27 5700 3300 6600 3300 6600 3600 5700 3600 5700 330027 4800 2400 5700 2400 5700 2700 4800 2700 4800 2400 28 28 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 29 5700 3900 6600 3900 6600 4500 5700 4500 5700 390029 4800 3000 5700 3000 5700 3600 4800 3600 4800 3000 30 30 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 31 2100 4800 4200 4800 4200 5700 2100 5700 2100 480031 1200 3900 3300 3900 3300 4800 1200 4800 1200 3900 32 32 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 33 4500 4800 6600 4800 6600 5700 4500 5700 4500 480033 3600 3900 5700 3900 5700 4800 3600 4800 3600 3900 34 34 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 35 35 1 1 1.00 60.00 45.00 36 36 1 1 1.00 60.00 45.00 37 2550 3000 2550 330037 1650 2100 1650 2400 38 38 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 39 39 1 1 1.00 60.00 45.00 40 40 1 1 1.00 60.00 45.00 41 6150 3000 6150 330041 5250 2100 5250 2400 42 42 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 43 43 1 1 1.00 60.00 45.00 44 44 1 1 1.00 60.00 45.00 45 6150 3600 6150 390045 5250 2700 5250 3000 46 46 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 47 47 1 1 1.00 60.00 45.00 48 48 1 1 1.00 60.00 45.00 49 3750 3000 3750 330049 2850 2100 2850 2400 50 50 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 51 51 1 1 1.00 60.00 45.00 52 52 1 1 1.00 60.00 45.00 53 4 950 3000 4950 330053 4050 2100 4050 2400 54 54 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 55 55 1 1 1.00 60.00 45.00 56 56 1 1 1.00 60.00 45.00 57 4 950 3600 4950 390057 4050 2700 4050 3000 58 58 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 59 59 1 1 1.00 60.00 45.00 60 60 1 1 1.00 60.00 45.00 61 3750 3600 3750 390061 1650 2700 1650 3000 62 62 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 63 63 1 1 1.00 60.00 45.00 64 64 1 1 1.00 60.00 45.00 65 2550 3600 2550 390065 1650 3600 1650 3900 66 66 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 67 67 1 1 1.00 60.00 45.00 68 68 1 1 1.00 60.00 45.00 69 2 550 4500 2550 480069 2850 3600 2850 3900 70 70 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 71 71 1 1 1.00 60.00 45.00 72 72 1 1 1.00 60.00 45.00 73 3750 4500 3750 480073 4050 3600 4050 3900 74 74 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 75 75 1 1 1.00 60.00 45.00 76 76 1 1 1.00 60.00 45.00 77 4950 4500 4950 480077 5250 3600 5250 3900 78 78 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 79 79 1 1 1.00 60.00 45.00 80 80 1 1 1.00 60.00 45.00 81 6150 4500 6150 480081 3300 4350 3600 4350 82 82 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 83 83 1 1 1.00 60.00 45.00 84 84 1 1 1.00 60.00 45.00 85 4200 5250 4500 525086 4 0 0 50 -1 0 11 0.0000 2 135 360 4725 2625 CPU2\00187 4 0 0 50 -1 0 11 0.0000 2 135 360 2325 2625 CPU0\00188 4 0 0 50 -1 0 11 0.0000 2 135 360 5925 2625 CPU3\00189 4 0 0 50 -1 0 11 0.0000 2 135 360 3525 2625 CPU1\00190 4 0 0 50 -1 0 11 0.0000 2 135 180 2475 3525 L1\00191 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 3525 L1\00192 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 3525 L1\00193 4 0 0 50 -1 0 11 0.0000 2 135 180 2400 4275 L2\00194 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 4275 L2\00195 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 4275 L2\00196 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 4275 L2\00197 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 3525 L1\00198 4 0 0 50 -1 0 11 0.0000 2 135 180 3000 5250 L3\00199 4 0 0 50 -1 0 11 0.0000 2 135 180 5475 5250 L3\00185 2850 2700 2850 3000 86 4 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001 87 4 1 0 50 -1 0 12 0.0000 2 135 225 2250 4425 L3\001 88 4 1 0 50 -1 0 12 0.0000 2 135 225 4650 4425 L3\001 89 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001 90 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001 91 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001 92 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001 93 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001 94 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001 95 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001 96 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001 97 4 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001 98 4 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001 99 4 1 0 50 -1 0 12 0.0000 2 165 945 5250 1725 CORE$_3$\001 -
doc/theses/thierry_delisle_PhD/thesis/fig/cache-share.fig
r06bdba4 r25404c7 8 8 -2 9 9 1200 2 10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 247511 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 247512 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4950 2550 456 456 4950 2550 4500 247513 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 247510 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575 11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575 12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575 13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575 14 14 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 15 2100 3300 3000 3300 3000 3600 2100 3600 2100 330015 1200 2400 2100 2400 2100 2700 1200 2700 1200 2400 16 16 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 17 2100 3900 3000 3900 3000 4500 2100 4500 2100 390017 1200 3000 2100 3000 2100 3600 1200 3600 1200 3000 18 18 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 19 3300 3300 4200 3300 4200 3600 3300 3600 3300 330019 2400 2400 3300 2400 3300 2700 2400 2700 2400 2400 20 20 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 21 3300 3900 4200 3900 4200 4500 3300 4500 3300 390021 2400 3000 3300 3000 3300 3600 2400 3600 2400 3000 22 22 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 23 4500 3300 5400 3300 5400 3600 4500 3600 4500 330023 3600 2400 4500 2400 4500 2700 3600 2700 3600 2400 24 24 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 25 4500 3900 5400 3900 5400 4500 4500 4500 4500 390025 3600 3000 4500 3000 4500 3600 3600 3600 3600 3000 26 26 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 27 5700 3300 6600 3300 6600 3600 5700 3600 5700 330027 4800 2400 5700 2400 5700 2700 4800 2700 4800 2400 28 28 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 29 5700 3900 6600 3900 6600 4500 5700 4500 5700 3900 30 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 31 2100 4800 6600 4800 6600 5775 2100 5775 2100 4800 29 4800 3000 5700 3000 5700 3600 4800 3600 4800 3000 32 30 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 33 31 1 1 1.00 60.00 45.00 34 32 1 1 1.00 60.00 45.00 35 2550 3000 2550 330033 1650 2100 1650 2400 36 34 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 37 35 1 1 1.00 60.00 45.00 38 36 1 1 1.00 60.00 45.00 39 3750 3000 3750 330037 2850 2100 2850 2400 40 38 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 41 39 1 1 1.00 60.00 45.00 42 40 1 1 1.00 60.00 45.00 43 4 950 3000 4950 330041 4050 2100 4050 2400 44 42 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 45 43 1 1 1.00 60.00 45.00 46 44 1 1 1.00 60.00 45.00 47 6150 3000 6150 330045 5250 2100 5250 2400 48 46 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 49 47 1 1 1.00 60.00 45.00 50 48 1 1 1.00 60.00 45.00 51 6150 3600 6150 390049 5250 2700 5250 3000 52 50 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 53 51 1 1 1.00 60.00 45.00 54 52 1 1 1.00 60.00 45.00 55 4 950 3600 4950 390053 4050 2700 4050 3000 56 54 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 57 55 1 1 1.00 60.00 45.00 58 56 1 1 1.00 60.00 45.00 59 3750 3600 3750 390057 2850 2700 2850 3000 60 58 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 61 59 1 1 1.00 60.00 45.00 62 60 1 1 1.00 60.00 45.00 63 2550 3600 2550 390061 1650 2700 1650 3000 64 62 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 65 63 1 1 1.00 60.00 45.00 66 64 1 1 1.00 60.00 45.00 67 2550 4500 2550 480065 1650 3600 1650 3900 68 66 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 69 67 1 1 1.00 60.00 45.00 70 68 1 1 1.00 60.00 45.00 71 3750 4500 3750 480069 2850 3600 2850 3900 72 70 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 73 71 1 1 1.00 60.00 45.00 74 72 1 1 1.00 60.00 45.00 75 4 950 4500 4950 480073 4050 3600 4050 3900 76 74 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 77 75 1 1 1.00 60.00 45.00 78 76 1 1 1.00 60.00 45.00 79 6150 4500 6150 4800 80 4 0 0 50 -1 0 11 0.0000 2 135 360 4725 2625 CPU2\001 81 4 0 0 50 -1 0 11 0.0000 2 135 360 2325 2625 CPU0\001 82 4 0 0 50 -1 0 11 0.0000 2 135 360 5925 2625 CPU3\001 83 4 0 0 50 -1 0 11 0.0000 2 135 360 3525 2625 CPU1\001 84 4 0 0 50 -1 0 11 0.0000 2 135 180 2475 3525 L1\001 85 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 3525 L1\001 86 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 3525 L1\001 87 4 0 0 50 -1 0 11 0.0000 2 135 180 2400 4275 L2\001 88 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 4275 L2\001 89 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 4275 L2\001 90 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 4275 L2\001 91 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 3525 L1\001 92 4 0 0 50 -1 0 11 0.0000 2 135 180 4275 5325 L3\001 77 5250 3600 5250 3900 78 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 79 1200 3900 5700 3900 5700 4800 1200 4800 1200 3900 80 4 1 0 50 -1 0 12 0.0000 2 135 225 3450 4425 L3\001 81 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001 82 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001 83 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001 84 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001 85 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001 86 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001 87 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001 88 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001 89 4 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001 90 4 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001 91 4 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001 92 4 1 0 50 -1 0 12 0.0000 2 165 945 5250 1725 CORE$_3$\001 -
doc/theses/thierry_delisle_PhD/thesis/text/core.tex
r06bdba4 r25404c7 1 1 \chapter{Scheduling Core}\label{core} 2 2 3 Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenario, where the system has reached a steady state. For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and the system has the resources necessary to accomplish the work, \eg, enough workers. In short, the system is neither overloaded nor underloaded. 4 5 It is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to this new load and return to the steady state, \eg, by adding or removing workers. Therefore, flaws in scheduling the steady state tend to be pervasive in all states. 3 Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenario, where the system has reached a steady state. 4 For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and the system has the resources necessary to accomplish the work, \eg, enough workers. 5 In short, the system is neither overloaded nor underloaded. 6 7 It is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. 8 As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to this new load and return to the steady state, \eg, by adding or removing workers. 9 Therefore, flaws in scheduling the steady state tend to be pervasive in all states. 6 10 7 11 \section{Design Goals} 8 As with most of the design decisions behind \CFA, an important goal is to match the expectation of the programmer according to their execution mental-model. To match expectations, the design must offer the programmer sufficient guarantees so that, as long as they respect the execution mental-model, the system also respects this model. 12 As with most of the design decisions behind \CFA, an important goal is to match the expectation of the programmer according to their execution mental-model. 13 To match expectations, the design must offer the programmer sufficient guarantees so that, as long as they respect the execution mental-model, the system also respects this model. 9 14 10 15 For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' : … … 17 22 Applied to threads, this model states that every ready \gls{thrd} immediately runs in parallel with all other ready \glspl{thrd}. While a strict implementation of this model is not feasible, programmers still have expectations about scheduling that come from this model. 18 23 19 In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with each other but simply share the hardware. This assumption makes it easier to reason about threading because ready \glspl{thrd} can be thought of in isolation and the effect of the scheduler can be virtually ignored. This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees: 24 In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with each other but simply share the hardware. 25 This assumption makes it easier to reason about threading because ready \glspl{thrd} can be thought of in isolation and the effect of the scheduler can be virtually ignored. 26 This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees: 20 27 \begin{enumerate} 21 28 \item A fairness guarantee: a \gls{thrd} that is ready to run is not prevented by another thread. … … 23 30 \end{enumerate} 24 31 25 It is important to note that these guarantees are expected only up to a point. \Glspl{thrd} that are ready to run should not be prevented to do so, but they still share the limited hardware resources. Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware resources, even if that share is very small. 26 27 Similarly the performance guarantee, the lack of interference among threads, is only relevant up to a point. Ideally, the cost of running and blocking should be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. How much is an acceptable cost is obviously highly variable. For this document, the performance experimentation attempts to show the cost of scheduling is at worst equivalent to existing algorithms used in popular languages. This demonstration can be made by comparing applications built in \CFA to applications built with other languages or other models. Recall programmer expectation is that the impact of the scheduler can be ignored. Therefore, if the cost of scheduling is compatitive to other popular languages, the guarantee will be consider achieved. 28 32 It is important to note that these guarantees are expected only up to a point. 33 \Glspl{thrd} that are ready to run should not be prevented to do so, but they still share the limited hardware resources. 34 Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware resources, even if that share is very small. 35 36 Similar to the performance guarantee, the lack of interference among threads is only relevant up to a point. 37 Ideally, the cost of running and blocking should be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. 38 How much is an acceptable cost is obviously highly variable. 39 For this document, the performance experimentation attempts to show the cost of scheduling is at worst equivalent to existing algorithms used in popular languages. 40 This demonstration can be made by comparing applications built in \CFA to applications built with other languages or other models. 41 Recall programmer expectation is that the impact of the scheduler can be ignored. 42 Therefore, if the cost of scheduling is competitive to other popular languages, the guarantee is consider achieved. 29 43 More precisely the scheduler should be: 30 44 \begin{itemize} … … 34 48 35 49 \subsection{Fairness Goals} 36 For this work fairness will be considered as havingtwo strongly related requirements: true starvation freedom and ``fast'' load balancing.37 38 \paragraph{True starvation freedom} is more easily defined: As long as at least one \proc continues to dequeue \ats, all read \ats should be able to run eventually.39 In any running system, \procs can stop dequeing \ats if they start running a \at that will simply never park.40 Traditional workstealing schedulers do not have starvation freedom in these cases.50 For this work, fairness is considered to have two strongly related requirements: true starvation freedom and ``fast'' load balancing. 51 52 \paragraph{True starvation freedom} means as long as at least one \proc continues to dequeue \ats, all ready \ats should be able to run eventually, \ie, eventual progress. 53 In any running system, a \proc can stop dequeuing \ats if it starts running a \at that never blocks. 54 Without preemption, traditional work-stealing schedulers do not have starvation freedom in this case. 41 55 Now this requirement begs the question, what about preemption? 42 56 Generally speaking preemption happens on the timescale of several milliseconds, which brings us to the next requirement: ``fast'' load balancing. 43 57 44 58 \paragraph{Fast load balancing} means that load balancing should happen faster than preemption would normally allow. 45 For interactive applications that need to run at 60, 90, 120 frames per second, \ats having to wait for several mill seconds to run are effectively starved.59 For interactive applications that need to run at 60, 90, 120 frames per second, \ats having to wait for several milliseconds to run are effectively starved. 46 60 Therefore load-balancing should be done at a faster pace, one that can detect starvation at the microsecond scale. 47 61 With that said, this is a much fuzzier requirement since it depends on the number of \procs, the number of \ats and the general load of the system. 48 62 49 63 \subsection{Fairness vs Scheduler Locality} \label{fairnessvlocal} 50 An important performance factor in modern architectures is cache locality. Waiting for data at lower levels or not present in the cache can have a major impact on performance. Having multiple \glspl{hthrd} writing to the same cache lines also leads to cache lines that must be waited on. It is therefore preferable to divide data among each \gls{hthrd}\footnote{This partitioning can be an explicit division up front or using data structures where different \glspl{hthrd} are naturally routed to different cache lines.}. 51 52 For a scheduler, having good locality\footnote{This section discusses \emph{internal locality}, \ie, the locality of the data used by the scheduler versus \emph{external locality}, \ie, how the data used by the application is affected by scheduling. External locality is a much more complicated subject and is discussed in the next section.}, \ie, having the data local to each \gls{hthrd}, generally conflicts with fairness. Indeed, good locality often requires avoiding the movement of cache lines, while fairness requires dynamically moving a \gls{thrd}, and as consequence cache lines, to a \gls{hthrd} that is currently available. 53 54 However, I claim that in practice it is possible to strike a balance between fairness and performance because these goals do not necessarily overlap temporally, where Figure~\ref{fig:fair} shows a visual representation of this behaviour. As mentioned, some unfairness is acceptable; therefore it is desirable to have an algorithm that prioritizes cache locality as long as thread delay does not exceed the execution mental-model. 64 An important performance factor in modern architectures is cache locality. 65 Waiting for data at lower levels or not present in the cache can have a major impact on performance. 66 Having multiple \glspl{hthrd} writing to the same cache lines also leads to cache lines that must be waited on. 67 It is therefore preferable to divide data among each \gls{hthrd}\footnote{This partitioning can be an explicit division up front or using data structures where different \glspl{hthrd} are naturally routed to different cache lines.}. 68 69 For a scheduler, having good locality, \ie, having the data local to each \gls{hthrd}, generally conflicts with fairness. 70 Indeed, good locality often requires avoiding the movement of cache lines, while fairness requires dynamically moving a \gls{thrd}, and as consequence cache lines, to a \gls{hthrd} that is currently available. 71 Note that this section discusses \emph{internal locality}, \ie, the locality of the data used by the scheduler versus \emph{external locality}, \ie, how the data used by the application is affected by scheduling. 72 External locality is a much more complicated subject and is discussed in the next section. 73 74 However, I claim that in practice it is possible to strike a balance between fairness and performance because these goals do not necessarily overlap temporally. 75 Figure~\ref{fig:fair} shows a visual representation of this behaviour. 76 As mentioned, some unfairness is acceptable; therefore it is desirable to have an algorithm that prioritizes cache locality as long as thread delay does not exceed the execution mental-model. 55 77 56 78 \begin{figure} … … 58 80 \input{fairness.pstex_t} 59 81 \vspace*{-10pt} 60 \caption[Fairness vs Locality graph]{Rule of thumb Fairness vs Locality graph \smallskip\newline The importance of Fairness and Locality while a ready \gls{thrd} awaits running is shown as the time the ready \gls{thrd} waits increases, Ready Time, the chances that its data is still in cache, Locality, decreases. At the same time, the need for fairness increases since other \glspl{thrd} may have the chance to run many times, breaking the fairness model. Since the actual values and curves of this graph can be highly variable, the graph is an idealized representation of the two opposing goals.} 82 \caption[Fairness vs Locality graph]{Rule of thumb Fairness vs Locality graph \smallskip\newline The importance of Fairness and Locality while a ready \gls{thrd} awaits running is shown as the time the ready \gls{thrd} waits increases, Ready Time, the chances that its data is still in cache decreases, Locality. 83 At the same time, the need for fairness increases since other \glspl{thrd} may have the chance to run many times, breaking the fairness model. 84 Since the actual values and curves of this graph can be highly variable, the graph is an idealized representation of the two opposing goals.} 61 85 \label{fig:fair} 62 86 \end{figure} 63 87 64 88 \subsection{Performance Challenges}\label{pref:challenge} 65 While there exists a multitude of potential scheduling algorithms, they generally always have to contend with the same performance challenges. Since these challenges are recurring themes in the design of a scheduler it is relevant to describe the central ones here before looking at the design. 89 While there exists a multitude of potential scheduling algorithms, they generally always have to contend with the same performance challenges. 90 Since these challenges are recurring themes in the design of a scheduler it is relevant to describe the central ones here before looking at the design. 66 91 67 92 \subsubsection{Scalability} … … 69 94 Given a large number of \procs and an even larger number of \ats, scalability measures how fast \procs can enqueue and dequeues \ats. 70 95 One could expect that doubling the number of \procs would double the rate at which \ats are dequeued, but contention on the internal data structure of the scheduler can lead to worst improvements. 71 While the ready-queue itself can be sharded to alleviate the main source of contention, auxil lary scheduling features, \eg counting ready \ats, can also be sources of contention.96 While the ready-queue itself can be sharded to alleviate the main source of contention, auxiliary scheduling features, \eg counting ready \ats, can also be sources of contention. 72 97 73 98 \subsubsection{Migration Cost} 74 Another important source of latency in schedulingis migration.75 A n \at is said to have migrated if it is executed by two different \procconsecutively, which is the process discussed in \ref{fairnessvlocal}.76 Migrations can have many different causes, but i t certain programs it can be all but impossible to limit migrations.77 Chapter~\ref{microbench} for example, has a benchmark where any \at can potentially unblock any other \at, which can leat to \ats migrating more often than not.78 Because of this it is important to design the internal data structures of the scheduler to limit thelatency penalty from migrations.99 Another important source of scheduling latency is migration. 100 A \at migrates if it executes on two different \procs consecutively, which is the process discussed in \ref{fairnessvlocal}. 101 Migrations can have many different causes, but in certain programs, it can be impossible to limit migration. 102 Chapter~\ref{microbench} has a benchmark where any \at can potentially unblock any other \at, which can lead to \ats migrating frequently. 103 Hence, it is important to design the internal data structures of the scheduler to limit any latency penalty from migrations. 79 104 80 105 81 106 \section{Inspirations} 82 In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance. The problem is adding/removing \glspl{thrd} is a single point of contention. As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}. The solution to this problem is to shard the ready-queue : create multiple sub-ready-queues that multiple \glspl{hthrd} can access and modify without interfering. 83 84 Before going into the design of \CFA's scheduler proper, it is relevant to discuss two sharding solutions which served as the inspiration scheduler in this thesis. 107 In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance. 108 The problem is a single point of contention when adding/removing \ats. 109 As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}. 110 The solution to this problem is to shard the ready-queue: create multiple \emph{subqueues} forming the logical ready-queue and the subqueues are accessed by multiple \glspl{hthrd} without interfering. 111 112 Before going into the design of \CFA's scheduler, it is relevant to discuss two sharding solutions that served as the inspiration scheduler in this thesis. 85 113 86 114 \subsection{Work-Stealing} 87 115 88 As mentioned in \ref{existing:workstealing}, a popular pattern shardthe ready-queue is work-stealing.89 In this pattern each \gls{proc} has its own local ready-queue and \glspl{proc} only access each other's ready-queue if they run out of work on their local ready-queue.90 The interesting aspect of work stealing happen in easier scheduling cases, \ie enough work for everyone but no more and no load balancingneeded.91 In th ese cases, work-stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.116 As mentioned in \ref{existing:workstealing}, a popular sharding approach for the ready-queue is work-stealing. 117 In this approach, each \gls{proc} has its own local subqueue and \glspl{proc} only access each other's subqueue if they run out of work on their local ready-queue. 118 The interesting aspect of work stealing happens in the steady-state scheduling case, \ie all \glspl{proc} have work and no load balancing is needed. 119 In this case, work stealing is close to optimal scheduling: it can achieve perfect locality and have no contention. 92 120 On the other hand, work-stealing schedulers only attempt to do load-balancing when a \gls{proc} runs out of work. 93 121 This means that the scheduler never balances unfair loads unless they result in a \gls{proc} running out of work. 94 Chapter~\ref{microbench} shows that in pathological cases this problem can lead to indefinite starvation. 95 96 97 Based on these observation, the conclusion is that a \emph{perfect} scheduler should behave very similarly to work-stealing in the easy cases, but should have more proactive load-balancing if the need arises. 98 99 \subsection{Relaxed-Fifo} 100 An entirely different scheme is to create a ``relaxed-FIFO'' queue as in \todo{cite Trevor's paper}. This approach forgos any ownership between \gls{proc} and ready-queue, and simply creates a pool of ready-queues from which the \glspl{proc} can pick from. 101 \Glspl{proc} choose ready-queus at random, but timestamps are added to all elements of the queue and dequeues are done by picking two queues and dequeing the oldest element. 102 All subqueues are protected by TryLocks and \procs simply pick a different subqueue if they fail to acquire the TryLock. 103 The result is a queue that has both decent scalability and sufficient fairness. 104 The lack of ownership means that as long as one \gls{proc} is still able to repeatedly dequeue elements, it is unlikely that any element will stay on the queue for much longer than any other element. 105 This contrasts with work-stealing, where \emph{any} \gls{proc} busy for an extended period of time results in all the elements on its local queue to have to wait. Unless another \gls{proc} runs out of work. 122 Chapter~\ref{microbench} shows that pathological cases work stealing can lead to indefinite starvation. 123 124 Based on these observation, the conclusion is that a \emph{perfect} scheduler should behave similar to work-stealing in the steady-state case, but load balance proactively when the need arises. 125 126 \subsection{Relaxed-FIFO} 127 A different scheduling approach is to create a ``relaxed-FIFO'' queue, as in \todo{cite Trevor's paper}. 128 This approach forgoes any ownership between \gls{proc} and subqueue, and simply creates a pool of ready-queues from which \glspl{proc} pick. 129 Scheduling is performed as follows: 130 \begin{itemize} 131 \item 132 All subqueues are protected by TryLocks. 133 \item 134 Timestamps are added to each element of a subqueue. 135 \item 136 A \gls{proc} randomly tests ready queues until it has acquired one or two queues. 137 \item 138 If two queues are acquired, the older of the two \ats at the front the acquired queues is dequeued. 139 \item 140 Otherwise the \ats from the single queue is dequeued. 141 \end{itemize} 142 The result is a queue that has both good scalability and sufficient fairness. 143 The lack of ownership ensures that as long as one \gls{proc} is still able to repeatedly dequeue elements, it is unlikely any element will delay longer than any other element. 144 This guarantee contrasts with work-stealing, where a \gls{proc} with a long subqueue results in unfairness for its \ats in comparison to a \gls{proc} with a short subqueue. 145 This unfairness persists until a \gls{proc} runs out of work and steals. 106 146 107 147 An important aspects of this scheme's fairness approach is that the timestamps make it possible to evaluate how long elements have been on the queue. 108 However, another major aspect is that \glspl{proc} will eagerly search for these older elements instead of focusing on specific queues.109 110 While th e fairness, of this scheme is good, it does suffer in terms of performance.111 It requires very wide sharding, \eg at least 4 queues per \gls{hthrd}, and finding non-empty queues can be difficult if there are toofew ready \ats.148 However, \glspl{proc} eagerly search for these older elements instead of focusing on specific queues, which negatively affects locality. 149 150 While this scheme has good fairness, its performance suffers. 151 It requires wide sharding, \eg at least 4 queues per \gls{hthrd}, and finding non-empty queues is difficult when there are few ready \ats. 112 152 113 153 \section{Relaxed-FIFO++} 114 Since it has inherent fairness quelities and decent performance in the presence of many \ats, the relaxed-FIFO queue appears as a good candidate to form the basis of a scheduler. 115 The most obvious problems is for workloads where the number of \ats is barely greater than the number of \procs. 116 In these situations, the wide sharding means most of the sub-queues from which the relaxed queue is formed will be empty. 117 The consequence is that when a dequeue operations attempts to pick a sub-queue at random, it is likely that it picks an empty sub-queue and will have to pick again. 118 This problem can repeat an unbounded number of times. 154 The inherent fairness and good performance with many \ats, makes the relaxed-FIFO queue a good candidate to form the basis of a new scheduler. 155 The problem case is workloads where the number of \ats is barely greater than the number of \procs. 156 In these situations, the wide sharding of the ready queue means most of its subqueues are empty. 157 Furthermore, the non-empty subqueues are unlikely to hold more than one item. 158 The consequence is that a random dequeue operation is likely to pick an empty subqueue, resulting in an unbounded number of selections. 159 This state is generally unstable: each subqueue is likely to frequently toggle between being empty and nonempty. 160 Indeed, when the number of \ats is \emph{equal} to the number of \procs, every pop operation is expected to empty a subqueue and every push is expected to add to an empty subqueue. 161 In the worst case, a check of the subqueues sees all are empty or full. 119 162 120 163 As this is the most obvious challenge, it is worth addressing first. 121 The obvious solution is to supplement each subqueue with some sharded data structure that keeps track of which subqueues are empty. 122 This data structure can take many forms, for example simple bitmask or a binary tree that tracks which branch are empty. 123 Following a binary tree on each pick has fairly good Big O complexity and many modern architectures have powerful bitmask manipulation instructions. 124 However, precisely tracking which sub-queues are empty is actually fundamentally problematic. 125 The reason is that each subqueues are already a form of sharding and the sharding width has presumably already chosen to avoid contention. 126 However, tracking which ready queue is empty is only useful if the tracking mechanism uses denser sharding than the sub queues, then it will invariably create a new source of contention. 127 But if the tracking mechanism is not denser than the sub-queues, then it will generally not provide useful because reading this new data structure risks being as costly as simply picking a sub-queue at random. 128 Early experiments with this approach have shown that even with low success rates, randomly picking a sub-queue can be faster than a simple tree walk. 164 The obvious solution is to supplement each sharded subqueue with data that indicates if the queue is empty/nonempty to simplify finding nonempty queues, \ie ready \glspl{at}. 165 This sharded data can be organized in different forms, \eg a bitmask or a binary tree that tracks the nonempty subqueues. 166 Specifically, many modern architectures have powerful bitmask manipulation instructions or searching a binary tree has good Big-O complexity. 167 However, precisely tracking nonempty subqueues is problematic. 168 The reason is that the subqueues are initially sharded with a width presumably chosen to avoid contention. 169 However, tracking which ready queue is nonempty is only useful if the tracking data is dense, \ie denser than the sharded subqueues. 170 Otherwise, it does not provide useful information because reading this new data structure risks being as costly as simply picking a subqueue at random. 171 But if the tracking mechanism \emph{is} denser than the shared subqueues, than constant updates invariably create a new source of contention. 172 Early experiments with this approach showed that randomly picking, even with low success rates, is often faster than bit manipulations or tree walks. 129 173 130 174 The exception to this rule is using local tracking. 131 If each \proc keeps track locally of which sub-queue is empty, then this can be done with a very dense data structure without introducing a new source of contention.132 The consequence of local tracking however, is that the information is notcomplete.133 Each \proc is only aware of the last state it saw each subqueues but does not have any information about freshness.134 Even on systems with low \gls{hthrd} count, \eg 4 or 8, this can quickly lead to the local information being no better than the random pick.135 This is due in part to the cost of this maintaining thisinformation and its poor quality.136 137 However, using a very low cost approach to local tracking mayactually be beneficial.138 If the local tracking is no more costly than the random pick, than \emph{any} improvement to the succes rate, however low it is, would leadto a performance benefits.139 This leads to the following approach:175 If each \proc locally keeps track of empty subqueues, than this can be done with a very dense data structure without introducing a new source of contention. 176 However, the consequence of local tracking is that the information is incomplete. 177 Each \proc is only aware of the last state it saw about each subqueue so this information quickly becomes stale. 178 Even on systems with low \gls{hthrd} count, \eg 4 or 8, this approach can quickly lead to the local information being no better than the random pick. 179 This result is due in part to the cost of maintaining information and its poor quality. 180 181 However, using a very low cost but inaccurate approach for local tracking can actually be beneficial. 182 If the local tracking is no more costly than a random pick, than \emph{any} improvement to the success rate, however low it is, leads to a performance benefits. 183 This suggests to the following approach: 140 184 141 185 \subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/} 142 The Relaxed-FIFO approach can be made to handle the case of mostly empty sub -queues by tweaking the \glsxtrlong{prng}.143 The \glsxtrshort{prng} state can be seen as containing a list of all the future sub -queues that will be accessed.144 While this is not particularly useful on its own, the consequence is that if the \glsxtrshort{prng} algorithm can be run \emph{backwards}, then the state also contains a list of all the subqueues that were accessed.145 Luckily, bidirectional \glsxtrshort{prng} algorithms do exist, for examplesome Linear Congruential Generators\cit{https://en.wikipedia.org/wiki/Linear\_congruential\_generator} support running the algorithm backwards while offering good quality and performance.186 The Relaxed-FIFO approach can be made to handle the case of mostly empty subqueues by tweaking the \glsxtrlong{prng}. 187 The \glsxtrshort{prng} state can be seen as containing a list of all the future subqueues that will be accessed. 188 While this concept is not particularly useful on its own, the consequence is that if the \glsxtrshort{prng} algorithm can be run \emph{backwards}, then the state also contains a list of all the subqueues that were accessed. 189 Luckily, bidirectional \glsxtrshort{prng} algorithms do exist, \eg some Linear Congruential Generators\cit{https://en.wikipedia.org/wiki/Linear\_congruential\_generator} support running the algorithm backwards while offering good quality and performance. 146 190 This particular \glsxtrshort{prng} can be used as follows: 147 148 Each \proc maintains two \glsxtrshort{prng} states, which whill be refered to as \texttt{F} and \texttt{B}. 149 150 When a \proc attempts to dequeue a \at, it picks the subqueues by running the \texttt{B} backwards. 151 When a \proc attempts to enqueue a \at, it runs \texttt{F} forward to pick to subqueue to enqueue to. 152 If the enqueue is successful, the state \texttt{B} is overwritten with the content of \texttt{F}. 153 154 The result is that each \proc will tend to dequeue \ats that it has itself enqueued. 155 When most sub-queues are empty, this technique increases the odds of finding \ats at very low cost, while also offering an improvement on locality in many cases. 156 157 However, while this approach does notably improve performance in many cases, this algorithm is still not competitive with work-stealing algorithms. 191 \begin{itemize} 192 \item 193 Each \proc maintains two \glsxtrshort{prng} states, refereed to as $F$ and $B$. 194 \item 195 When a \proc attempts to dequeue a \at, it picks a subqueue by running $B$ backwards. 196 \item 197 When a \proc attempts to enqueue a \at, it runs $F$ forward picking a subqueue to enqueue to. 198 If the enqueue is successful, the state $B$ is overwritten with the content of $F$. 199 \end{itemize} 200 The result is that each \proc tends to dequeue \ats that it has itself enqueued. 201 When most subqueues are empty, this technique increases the odds of finding \ats at very low cost, while also offering an improvement on locality in many cases. 202 203 Tests showed this approach performs better than relaxed-FIFO in many cases. 204 However, it is still not competitive with work-stealing algorithms. 158 205 The fundamental problem is that the constant randomness limits how much locality the scheduler offers. 159 This becomes problematic both because the scheduler is likely to get cache misses on internal data-structures and because migration become very frequent. 160 Therefore since the approach of modifying to relaxed-FIFO algorithm to behave more like work stealing does not seem to pan out, the alternative is to do it the other way around. 206 This becomes problematic both because the scheduler is likely to get cache misses on internal data-structures and because migrations become frequent. 207 Therefore, the attempt to modify the relaxed-FIFO algorithm to behave more like work stealing did not pan out. 208 The alternative is to do it the other way around. 161 209 162 210 \section{Work Stealing++} 163 To add stronger fairness guarantees to work stealing a few changes.211 To add stronger fairness guarantees to work stealing a few changes are needed. 164 212 First, the relaxed-FIFO algorithm has fundamentally better fairness because each \proc always monitors all subqueues. 165 Therefore the workstealing algorithm must be prepended with some monitoring. 166 Before attempting to dequeue from a \proc's local queue, the \proc must make some effort to make sure remote queues are not being neglected. 167 To make this possible, \procs must be able to determie which \at has been on the ready-queue the longest. 168 Which is the second aspect that much be added. 169 The relaxed-FIFO approach uses timestamps for each \at and this is also what is done here. 213 Therefore, the work-stealing algorithm must be prepended with some monitoring. 214 Before attempting to dequeue from a \proc's subqueue, the \proc must make some effort to ensure other subqueues are not being neglected. 215 To make this possible, \procs must be able to determine which \at has been on the ready queue the longest. 216 Second, the relaxed-FIFO approach needs timestamps for each \at to make this possible. 170 217 171 218 \begin{figure} 172 219 \centering 173 220 \input{base.pstex_t} 174 \caption[Base \CFA design]{Base \CFA design \smallskip\newline A Pool of sub-ready queues offers the sharding, two per \glspl{proc}. Each \gls{proc} have local subqueues, however \glspl{proc} can access any of the sub-queues. Each \at is timestamped when enqueued.} 221 \caption[Base \CFA design]{Base \CFA design \smallskip\newline A pool of subqueues offers the sharding, two per \glspl{proc}. 222 Each \gls{proc} can access all of the subqueues. 223 Each \at is timestamped when enqueued.} 175 224 \label{fig:base} 176 225 \end{figure} 177 The algorithm is structure as shown in Figure~\ref{fig:base}. 178 This is very similar to classic workstealing except the local queues are placed in an array so \procs can access eachother's queue in constant time. 179 Sharding width can be adjusted based on need. 180 When a \proc attempts to dequeue a \at, it first picks a random remote queue and compares its timestamp to the timestamps of the local queue(s), dequeue from the remote queue if needed. 181 182 Implemented as as naively state above, this approach has some obvious performance problems. 226 227 Figure~\ref{fig:base} shows the algorithm structure. 228 This structure is similar to classic work-stealing except the subqueues are placed in an array so \procs can access them in constant time. 229 Sharding width can be adjusted based on contention. 230 Note, as an optimization, the TS of a \at is stored in the \at in front of it, so the first TS is in the array and the last \at has no TS. 231 This organization keeps the highly accessed front TSs directly in the array. 232 When a \proc attempts to dequeue a \at, it first picks a random remote subqueue and compares its timestamp to the timestamps of its local subqueue(s). 233 The oldest waiting \at is dequeued to provide global fairness. 234 235 However, this na\"ive implemented has performance problems. 183 236 First, it is necessary to have some damping effect on helping. 184 Random effects like cache misses and preemption can add spurious but short bursts of latency for which helping is not helpful, pun intended.185 The effect of these bursts would be to cause more migrations than needed and make this workstealing approach slowdown to the match the relaxed-FIFO approach.237 Random effects like cache misses and preemption can add spurious but short bursts of latency negating the attempt to help. 238 These bursts can cause increased migrations and make this work stealing approach slowdown to the level of relaxed-FIFO. 186 239 187 240 \begin{figure} … … 192 245 \end{figure} 193 246 194 A simple solution to this problem is to compare an exponential moving average\cit{https://en.wikipedia.org/wiki/Moving\_average\#Exponential\_moving\_average} instead if theraw timestamps, shown in Figure~\ref{fig:base-ma}.195 Note that this is slightly more complex than it sounds because since the \at at the head of a subqueue is still waiting,its wait time has not ended.196 Therefore the exponential moving average is actually an exponential moving average of how long each already dequeued \at havewaited.197 To compare subqueues, the timestamp at the head must be compared to the current time, yielding the best case waittime for the \at at the head of the queue.247 A simple solution to this problem is to use an exponential moving average\cit{https://en.wikipedia.org/wiki/Moving\_average\#Exponential\_moving\_average} (MA) instead of a raw timestamps, shown in Figure~\ref{fig:base-ma}. 248 Note, this is more complex because the \at at the head of a subqueue is still waiting, so its wait time has not ended. 249 Therefore, the exponential moving average is actually an exponential moving average of how long each dequeued \at has waited. 250 To compare subqueues, the timestamp at the head must be compared to the current time, yielding the best-case wait-time for the \at at the head of the queue. 198 251 This new waiting is averaged with the stored average. 199 To limit even more the amount of unnecessary migration, a bias can be added to the local queue, where a remote queue is helped only if its moving average is more than \emph{X} times the local queue's average. 200 None of the experimentation that I have run with these scheduler seem to indicate that the choice of the weight for the moving average or the choice of bis is particularly important. 201 Weigths and biases of similar \emph{magnitudes} have similar effects. 202 203 With these additions to workstealing, scheduling can be made as fair as the relaxed-FIFO approach, well avoiding the majority of unnecessary migrations. 204 Unfortunately, the performance of this approach does suffer in the cases with no risks of starvation. 205 The problem is that the constant polling of remote subqueues generally entail a cache miss. 206 To make things worst, remote subqueues that are very active, \ie \ats are frequently enqueued and dequeued from them, the higher the chances are that polling will incurr a cache-miss. 207 Conversly, the active subqueues do not benefit much from helping since starvation is already a non-issue. 208 This puts this algorithm in an akward situation where it is paying for a cost, but the cost itself suggests the operation was unnecessary. 252 To further limit migration, a bias can be added to a local subqueue, where a remote subqueue is helped only if its moving average is more than $X$ times the local subqueue's average. 253 Tests for this approach indicate the choice of the weight for the moving average or the bias is not important, \ie weights and biases of similar \emph{magnitudes} have similar effects. 254 255 With these additions to work stealing, scheduling can be made as fair as the relaxed-FIFO approach, avoiding the majority of unnecessary migrations. 256 Unfortunately, the work to achieve fairness has a performance cost, especially when the workload is inherently fair, and hence, there is only short-term or no starvation. 257 The problem is that the constant polling, \ie reads, of remote subqueues generally entail a cache miss because the TSs are constantly being updated, \ie, writes. 258 To make things worst, remote subqueues that are very active, \ie \ats are frequently enqueued and dequeued from them, lead to higher chances that polling will incur a cache-miss. 259 Conversely, the active subqueues do not benefit much from helping since starvation is already a non-issue. 260 This puts this algorithm in the awkward situation of paying for a cost that is largely unnecessary. 209 261 The good news is that this problem can be mitigated 210 262 211 263 \subsection{Redundant Timestamps} 212 The problem with polling remote queues is due to a tension between the consistency requirement on the subqueue. 213 For the subqueues, correctness is critical. There must be a consensus among \procs on which subqueues hold which \ats. 214 Since the timestamps are use for fairness, it is alco important to have consensus and which \at is the oldest. 215 However, when deciding if a remote subqueue is worth polling, correctness is much less of a problem. 216 Since the only need is that a subqueue will eventually be polled, some data staleness can be acceptable. 217 This leads to a tension where stale timestamps are only problematic in some cases. 218 Furthermore, stale timestamps can be somewhat desirable since lower freshness requirements means less tension on the cache coherence protocol. 219 220 221 \begin{figure} 222 \centering 223 % \input{base_ts2.pstex_t} 224 \caption[\CFA design with Redundant Timestamps]{\CFA design with Redundant Timestamps \smallskip\newline A array is added containing a copy of the timestamps. These timestamps are written to with relaxed atomics, without fencing, leading to fewer cache invalidations.} 225 \label{fig:base-ts2} 226 \end{figure} 227 A solution to this is to create a second array containing a copy of the timestamps and average. 264 The problem with polling remote subqueues is that correctness is critical. 265 There must be a consensus among \procs on which subqueues hold which \ats, as the \ats are in constant motion. 266 Furthermore, since timestamps are use for fairness, it is critical to have consensus on which \at is the oldest. 267 However, when deciding if a remote subqueue is worth polling, correctness is less of a problem. 268 Since the only requirement is that a subqueue is eventually polled, some data staleness is acceptable. 269 This leads to a situation where stale timestamps are only problematic in some cases. 270 Furthermore, stale timestamps can be desirable since lower freshness requirements mean less cache invalidations. 271 272 Figure~\ref{fig:base-ts2} shows a solution with a second array containing a copy of the timestamps and average. 228 273 This copy is updated \emph{after} the subqueue's critical sections using relaxed atomics. 229 274 \Glspl{proc} now check if polling is needed by comparing the copy of the remote timestamp instead of the actual timestamp. 230 The result is that since there is no fencing, the writes can be buffered and cause fewer cache invalidations. 231 232 The correctness argument here is somewhat subtle. 275 The result is that since there is no fencing, the writes can be buffered in the hardware and cause fewer cache invalidations. 276 277 \begin{figure} 278 \centering 279 \input{base_ts2.pstex_t} 280 \caption[\CFA design with Redundant Timestamps]{\CFA design with Redundant Timestamps \smallskip\newline An array is added containing a copy of the timestamps. 281 These timestamps are written to with relaxed atomics, so there is no order among concurrent memory accesses, leading to fewer cache invalidations.} 282 \label{fig:base-ts2} 283 \end{figure} 284 285 The correctness argument is somewhat subtle. 233 286 The data used for deciding whether or not to poll a queue can be stale as long as it does not cause starvation. 234 Therefore, it is acceptable if stale data make queues appear older than they really are but not fresher. 235 For the timestamps, this means that missing writes to the timestamp is acceptable since they will make the head \at look older. 236 For the moving average, as long as the operation are RW-safe, the average is guaranteed to yield a value that is between the oldest and newest values written. 237 Therefore this unprotected read of the timestamp and average satisfy the limited correctness that is required. 287 Therefore, it is acceptable if stale data makes queues appear older than they really are but appearing fresher can be a problem. 288 For the timestamps, this means missing writes to the timestamp is acceptable since they make the head \at look older. 289 For the moving average, as long as the operations are just atomic reads/writes, the average is guaranteed to yield a value that is between the oldest and newest values written. 290 Therefore, this unprotected read of the timestamp and average satisfy the limited correctness that is required. 291 292 With redundant timestamps, this scheduling algorithm achieves both the fairness and performance requirements on most machines. 293 The problem is that the cost of polling and helping is not necessarily consistent across each \gls{hthrd}. 294 For example, on machines with a CPU containing multiple hyperthreads and cores and multiple CPU sockets, cache misses can be satisfied from the caches on same (local) CPU, or by a CPU on a different (remote) socket. 295 Cache misses satisfied by a remote CPU have significantly higher latency than from the local CPU. 296 However, these delays are not specific to systems with multiple CPUs. 297 Depending on the cache structure, cache misses can have different latency on the same CPU, \eg the AMD EPYC 7662 CPUs used in Chapter~\ref{microbench}. 238 298 239 299 \begin{figure} 240 300 \centering 241 301 \input{cache-share.pstex_t} 242 \caption[CPU design with wide L3 sharing]{CPU design with wide L3 sharing \smallskip\newline A very simple CPU with 4 \glspl{hthrd}. L1 and L2 are private to each \gls{hthrd} but the L3 is shared across to entire core.}302 \caption[CPU design with wide L3 sharing]{CPU design with wide L3 sharing \smallskip\newline A CPU with 4 cores, where caches L1 and L2 are private to each core, and the L3 cache is shared across all cores.} 243 303 \label{fig:cache-share} 244 \end{figure} 245 246 \begin{figure} 247 \centering 304 305 \vspace{25pt} 306 248 307 \input{cache-noshare.pstex_t} 249 \caption[CPU design with a narrower L3 sharing]{CPU design with a narrow er L3 sharing \smallskip\newline A different CPU design, still with 4 \glspl{hthrd}. L1 and L2 are still private to each \gls{hthrd} but the L3 is shared some of the CPU but there is still two distinct L3 instances.}308 \caption[CPU design with a narrower L3 sharing]{CPU design with a narrow L3 sharing \smallskip\newline A CPU with 4 cores, where caches L1 and L2 are private to each core, and the L3 cache is shared across a pair of cores.} 250 309 \label{fig:cache-noshare} 251 310 \end{figure} 252 311 253 With redundant tiemstamps this scheduling algorithm achieves both the fairness and performance requirements, on some machines. 254 The problem is that the cost of polling and helping is not necessarily consistent across each \gls{hthrd}. 255 For example, on machines where the motherboard holds multiple CPU, cache misses can be satisfied from a cache that belongs to the CPU that missed, the \emph{local} CPU, or by a different CPU, a \emph{remote} one. 256 Cache misses that are satisfied by a remote CPU will have higher latency than if it is satisfied by the local CPU. 257 However, this is not specific to systems with multiple CPUs. 258 Depending on the cache structure, cache-misses can have different latency for the same CPU. 259 The AMD EPYC 7662 CPUs that is described in Chapter~\ref{microbench} is an example of that. 260 Figure~\ref{fig:cache-share} and Figure~\ref{fig:cache-noshare} show two different cache topologies with highlight this difference. 261 In Figure~\ref{fig:cache-share}, all cache instances are either private to a \gls{hthrd} or shared to the entire system, this means latency due to cache-misses are likely fairly consistent. 262 By comparison, in Figure~\ref{fig:cache-noshare} misses in the L2 cache can be satisfied by a hit in either instance of the L3. 263 However, the memory access latency to the remote L3 instance will be notably higher than the memory access latency to the local L3. 264 The impact of these different design on this algorithm is that scheduling will scale very well on architectures similar to Figure~\ref{fig:cache-share}, both will have notably worst scalling with many narrower L3 instances. 265 This is simply because as the number of L3 instances grow, so two does the chances that the random helping will cause significant latency. 266 The solution is to have the scheduler be aware of the cache topology. 312 Figures~\ref{fig:cache-share} and~\ref{fig:cache-noshare} show two different cache topologies that highlight this difference. 313 In Figure~\ref{fig:cache-share}, all cache misses are either private to a CPU or shared with another CPU. 314 This means latency due to cache misses is fairly consistent. 315 In contrast, in Figure~\ref{fig:cache-noshare} misses in the L2 cache can be satisfied by either instance of L3 cache. 316 However, the memory-access latency to the remote L3 is higher than the memory-access latency to the local L3. 317 The impact of these different designs on this algorithm is that scheduling only scales well on architectures with a wide L3 cache, similar to Figure~\ref{fig:cache-share}, and less well on architectures with many narrower L3 cache instances, similar to Figure~\ref{fig:cache-noshare}. 318 Hence, as the number of L3 instances grow, so too does the chance that the random helping causes significant cache latency. 319 The solution is for the scheduler be aware of the cache topology. 267 320 268 321 \subsection{Per CPU Sharding} 269 Building a scheduler that is aware of cache topology poses two main challenges: discovering cache topology and matching \procs to cache instance. 270 Sadly, there is no standard portable way to discover cache topology in C. 271 Therefore, while this is a significant portability challenge, it is outside the scope of this thesis to design a cross-platform cache discovery mechanisms. 272 The rest of this work assumes discovering the cache topology based on Linux's \texttt{/sys/devices/system/cpu} directory. 273 This leaves the challenge of matching \procs to cache instance, or more precisely identifying which subqueues of the ready queue are local to which cache instance. 274 Once this matching is available, the helping algorithm can be changed to add bias so that \procs more often help subqueues local to the same cache instance 275 \footnote{Note that like other biases mentioned in this section, the actual bias value does not appear to need precise tuinng.}. 276 277 The obvious approach to mapping cache instances to subqueues is to statically tie subqueues to CPUs. 278 Instead of having each subqueue local to a specific \proc, the system is initialized with subqueues for each \glspl{hthrd} up front. 279 Then \procs dequeue and enqueue by first asking which CPU id they are local to, in order to identify which subqueues are the local ones. 322 Building a scheduler that is cache aware poses two main challenges: discovering the cache topology and matching \procs to this cache structure. 323 Unfortunately, there is no portable way to discover cache topology, and it is outside the scope of this thesis to solve this problem. 324 This work uses the cache topology information from Linux's \texttt{/sys/devices/system/cpu} directory. 325 This leaves the challenge of matching \procs to cache structure, or more precisely identifying which subqueues of the ready queue are local to which subcomponents of the cache structure. 326 Once a matching is generated, the helping algorithm is changed to add bias so that \procs more often help subqueues local to the same cache substructure.\footnote{ 327 Note that like other biases mentioned in this section, the actual bias value does not appear to need precise tuning.} 328 329 The simplest approach for mapping subqueues to cache structure is to statically tie subqueues to CPUs. 330 Instead of having each subqueue local to a specific \proc, the system is initialized with subqueues for each hardware hyperthread/core up front. 331 Then \procs dequeue and enqueue by first asking which CPU id they are executing on, in order to identify which subqueues are the local ones. 280 332 \Glspl{proc} can get the CPU id from \texttt{sched\_getcpu} or \texttt{librseq}. 281 333 282 This approach solves the performance problems on systems with topologies similar to Figure~\ref{fig:cache-noshare}.283 However, it actually causes some subtle fairness problems in some systems, specificallysystems with few \procs and many \glspl{hthrd}.284 In th ese cases, the large number of subqueues and the bias agains subqueues tied to different cache instances make it so it is very unlikely any singlesubqueue is picked.285 To make things worst, the small number of \procs mean that few helping attempts will be made.286 This combination of few attempts and low chances make it so a \at stranded on a subqueue that is not actively dequeued from may wait very long beforeit gets randomly helped.334 This approach solves the performance problems on systems with topologies with narrow L3 caches, similar to Figure \ref{fig:cache-noshare}. 335 However, it can still cause some subtle fairness problems in systems with few \procs and many \glspl{hthrd}. 336 In this case, the large number of subqueues and the bias against subqueues tied to different cache substructures make it unlikely that every subqueue is picked. 337 To make things worst, the small number of \procs mean that few helping attempts are made. 338 This combination of low selection and few helping attempts allow a \at to become stranded on a subqueue for a long time until it gets randomly helped. 287 339 On a system with 2 \procs, 256 \glspl{hthrd} with narrow cache sharing, and a 100:1 bias, it can actually take multiple seconds for a \at to get dequeued from a remote queue. 288 340 Therefore, a more dynamic matching of subqueues to cache instance is needed. 289 341 290 342 \subsection{Topological Work Stealing} 291 The approach that is used in the \CFA scheduler is to have per-\proc subqueue, but have an excplicit data-structure track which cache instance each subqueue is tied to.292 This is requires some finessbecause reading this data structure must lead to fewer cache misses than not having the data structure in the first place.343 Therefore, the approach used in the \CFA scheduler is to have per-\proc subqueues, but have an explicit data-structure track which cache substructure each subqueue is tied to. 344 This tracking requires some finesse because reading this data structure must lead to fewer cache misses than not having the data structure in the first place. 293 345 A key element however is that, like the timestamps for helping, reading the cache instance mapping only needs to give the correct result \emph{often enough}. 294 Therefore the algorithm can be built as follows: Before enqueuing or dequeing a \at, each \proc queries the CPU id and the corresponding cache instance.346 Therefore the algorithm can be built as follows: before enqueueing or dequeuing a \at, each \proc queries the CPU id and the corresponding cache instance. 295 347 Since subqueues are tied to \procs, each \proc can then update the cache instance mapped to the local subqueue(s). 296 348 To avoid unnecessary cache line invalidation, the map is only written to if the mapping changes. 297 349 350 This scheduler is used in the remainder of the thesis for managing CPU execution, but additional scheduling is needed to handle long-term blocking and unblocking, such as I/O. 351 -
doc/theses/thierry_delisle_PhD/thesis/thesis.tex
r06bdba4 r25404c7 83 83 \usepackage{graphicx} % For including graphics 84 84 \usepackage{subcaption} 85 \usepackage{comment} % Removes large sections of the document. 85 86 86 87 % Hyperlinks make it very easy to navigate an electronic document. -
src/Common/Eval.cc
r06bdba4 r25404c7 10 10 // Created On : Mon May 18 07:44:20 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Wed Jul 24 15:09:06 201913 // Update Count : 6412 // Last Modified On : Fri Jul 1 08:41:03 2022 13 // Update Count : 117 14 14 // 15 15 … … 17 17 18 18 #include "Common/PassVisitor.h" 19 #include "CodeGen/OperatorTable.h" // access: OperatorInfo 19 20 #include "AST/Pass.hpp" 20 21 #include "InitTweak/InitTweak.h" … … 24 25 // Old AST 25 26 struct EvalOld : public WithShortCircuiting { 26 long long int value = 0; 27 bool valid = true; 27 long long int value = 0; // compose the result of the constant expression 28 bool valid = true; // true => constant expression and value is the result 29 // false => not constant expression, e.g., ++i 30 bool cfavalid = true; // true => constant expression and value computable 31 // false => constant expression but value not computable, e.g., sizeof(int) 28 32 29 33 void previsit( const BaseSyntaxNode * ) { visit_children = false; } … … 89 93 // New AST 90 94 struct EvalNew : public ast::WithShortCircuiting { 91 long long int value = 0; 92 bool valid = true; 95 long long int value = 0; // compose the result of the constant expression 96 bool valid = true; // true => constant expression and value is the result 97 // false => not constant expression, e.g., ++i 98 bool cfavalid = true; // true => constant expression and value computable 99 // false => constant expression but value not computable, e.g., sizeof(int) 93 100 94 101 void previsit( const ast::Node * ) { visit_children = false; } 95 void postvisit( const ast::Node * ) { valid = false; } 96 97 void postvisit( const ast::ConstantExpr * expr ) { 102 void postvisit( const ast::Node * ) { cfavalid = valid = false; } 103 104 void postvisit( const ast::UntypedExpr * ) { 105 assertf( false, "UntypedExpr in constant expression evaluation" ); // FIX ME, resolve variable 106 } 107 108 void postvisit( const ast::ConstantExpr * expr ) { // only handle int constants 98 109 value = expr->intValue(); 99 110 } 100 111 101 void postvisit( const ast::SizeofExpr * expr ) { 102 if ( expr->expr ) value = eval(expr->expr).first; 103 else if ( expr->type ) value = eval(expr->expr).first; 104 else SemanticError( expr->location, ::toString( "Internal error: SizeofExpr has no expression or type value" ) ); 105 } 106 107 void postvisit( const ast::CastExpr * expr ) { 112 void postvisit( const ast::SizeofExpr * ) { 113 // do not change valid or value => let C figure it out 114 cfavalid = false; 115 } 116 117 void postvisit( const ast::AlignofExpr * ) { 118 // do not change valid or value => let C figure it out 119 cfavalid = false; 120 } 121 122 void postvisit( const ast::OffsetofExpr * ) { 123 // do not change valid or value => let C figure it out 124 cfavalid = false; 125 } 126 127 void postvisit( const ast::LogicalExpr * expr ) { 128 std::pair<long long int, bool> arg1, arg2; 129 arg1 = eval( expr->arg1 ); 130 valid &= arg1.second; 131 if ( ! valid ) return; 132 arg2 = eval( expr->arg2 ); 133 valid &= arg2.second; 134 if ( ! valid ) return; 135 136 if ( expr->isAnd ) { 137 value = arg1.first && arg2.first; 138 } else { 139 value = arg1.first || arg2.first; 140 } // if 141 } 142 143 void postvisit( const ast::ConditionalExpr * expr ) { 144 std::pair<long long int, bool> arg1, arg2, arg3; 145 arg1 = eval( expr->arg1 ); 146 valid &= arg1.second; 147 if ( ! valid ) return; 148 arg2 = eval( expr->arg2 ); 149 valid &= arg2.second; 150 if ( ! valid ) return; 151 arg3 = eval( expr->arg3 ); 152 valid &= arg3.second; 153 if ( ! valid ) return; 154 155 value = arg1.first ? arg2.first : arg3.first; 156 } 157 158 void postvisit( const ast::CastExpr * expr ) { 159 // cfa-cc generates a cast before every constant and many other places, e.g., (int)3, so the cast argument must 160 // be evaluated to get the constant value. 108 161 auto arg = eval(expr->arg); 109 162 valid = arg.second; 110 163 value = arg.first; 111 // TODO: perform type conversion on value if valid112 } 113 114 void postvisit( const ast::VariableExpr * expr ) { // No hit164 cfavalid = false; 165 } 166 167 void postvisit( const ast::VariableExpr * expr ) { 115 168 if ( const ast::EnumInstType * inst = dynamic_cast<const ast::EnumInstType *>(expr->result.get()) ) { 116 169 if ( const ast::EnumDecl * decl = inst->base ) { … … 128 181 const std::string & fname = function->name; 129 182 assertf( expr->args.size() == 1 || expr->args.size() == 2, "Intrinsic function with %zd arguments: %s", expr->args.size(), fname.c_str() ); 130 std::pair<long long int, bool> arg1, arg2; 131 arg1 = eval(expr->args.front()); 132 valid = valid && arg1.second; 133 if ( ! valid ) return; 134 if ( expr->args.size() == 2 ) { 183 184 if ( expr->args.size() == 1 ) { 185 // pre/postfix operators ++ and -- => assignment, which is not constant 186 std::pair<long long int, bool> arg1; 187 arg1 = eval(expr->args.front()); 188 valid &= arg1.second; 189 if ( ! valid ) return; 190 191 if (fname == "+?") { 192 value = arg1.first; 193 } else if (fname == "-?") { 194 value = -arg1.first; 195 } else if (fname == "~?") { 196 value = ~arg1.first; 197 } else if (fname == "!?") { 198 value = ! arg1.first; 199 } else { 200 valid = false; 201 } // if 202 } else { // => expr->args.size() == 2 203 // infix assignment operators => assignment, which is not constant 204 std::pair<long long int, bool> arg1, arg2; 205 arg1 = eval(expr->args.front()); 206 valid &= arg1.second; 207 if ( ! valid ) return; 135 208 arg2 = eval(expr->args.back()); 136 valid = valid && arg2.second; 137 if ( ! valid ) return; 138 } 139 if (fname == "?+?") { 140 value = arg1.first + arg2.first; 141 } else if (fname == "?-?") { 142 value = arg1.first - arg2.first; 143 } else if (fname == "?*?") { 144 value = arg1.first * arg2.first; 145 } else if (fname == "?/?") { 146 value = arg1.first / arg2.first; 147 } else if (fname == "?%?") { 148 value = arg1.first % arg2.first; 149 } else { 150 valid = false; 151 } 209 valid &= arg2.second; 210 if ( ! valid ) return; 211 212 if (fname == "?+?") { 213 value = arg1.first + arg2.first; 214 } else if (fname == "?-?") { 215 value = arg1.first - arg2.first; 216 } else if (fname == "?*?") { 217 value = arg1.first * arg2.first; 218 } else if (fname == "?/?") { 219 value = arg1.first / arg2.first; 220 } else if (fname == "?%?") { 221 value = arg1.first % arg2.first; 222 } else if (fname == "?<<?") { 223 value = arg1.first << arg2.first; 224 } else if (fname == "?>>?") { 225 value = arg1.first >> arg2.first; 226 } else if (fname == "?<?") { 227 value = arg1.first < arg2.first; 228 } else if (fname == "?>?") { 229 value = arg1.first > arg2.first; 230 } else if (fname == "?<=?") { 231 value = arg1.first <= arg2.first; 232 } else if (fname == "?>=?") { 233 value = arg1.first >= arg2.first; 234 } else if (fname == "?==?") { 235 value = arg1.first == arg2.first; 236 } else if (fname == "?!=?") { 237 value = arg1.first != arg2.first; 238 } else if (fname == "?&?") { 239 value = arg1.first & arg2.first; 240 } else if (fname == "?^?") { 241 value = arg1.first ^ arg2.first; 242 } else if (fname == "?|?") { 243 value = arg1.first | arg2.first; 244 } else { 245 valid = false; 246 } 247 } // if 152 248 // TODO: implement other intrinsic functions 153 249 } 154 250 }; 155 251 156 std::pair<long long int, bool> eval( const Expression * expr ) {252 std::pair<long long int, bool> eval( const Expression * expr ) { 157 253 PassVisitor<EvalOld> ev; 158 if ( expr) {159 expr->accept( ev);160 return std::make_pair( ev.pass.value, ev.pass.valid);254 if ( expr ) { 255 expr->accept( ev ); 256 return std::make_pair( ev.pass.value, ev.pass.valid ); 161 257 } else { 162 return std::make_pair( 0, false);258 return std::make_pair( 0, false ); 163 259 } 164 260 } 165 261 166 std::pair<long long int, bool> eval( const ast::Expr * expr) {262 std::pair<long long int, bool> eval( const ast::Expr * expr ) { 167 263 ast::Pass<EvalNew> ev; 168 if ( expr) {169 expr->accept( ev);170 return std::make_pair( ev.core.value, ev.core.valid);264 if ( expr ) { 265 expr->accept( ev ); 266 return std::make_pair( ev.core.value, ev.core.valid ); 171 267 } else { 172 return std::make_pair( 0, false);268 return std::make_pair( 0, false ); 173 269 } 174 270 } -
src/Parser/parser.yy
r06bdba4 r25404c7 10 10 // Created On : Sat Sep 1 20:22:55 2001 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat May 14 09:16:22202213 // Update Count : 540 112 // Last Modified On : Fri Jul 1 15:35:08 2022 13 // Update Count : 5405 14 14 // 15 15 … … 2441 2441 // empty 2442 2442 { $$ = nullptr; } 2443 // | '=' constant_expression2444 // { $$ = $2; }2445 | simple_assignment_operator initializer2446 { $$ = $1 == OperKinds::Assign ? $2 : $2->set_maybeConstructed( false ); }2443 | '=' constant_expression { $$ = new InitializerNode( $2 ); } 2444 | '=' '{' initializer_list_opt comma_opt '}' { $$ = new InitializerNode( $3, true ); } 2445 // | simple_assignment_operator initializer 2446 // { $$ = $1 == OperKinds::Assign ? $2 : $2->set_maybeConstructed( false ); } 2447 2447 ; 2448 2448 -
src/ResolvExpr/CurrentObject.cc
r06bdba4 r25404c7 9 9 // Author : Rob Schluntz 10 10 // Created On : Tue Jun 13 15:28:32 2017 11 // Last Modified By : Rob Schluntz12 // Last Modified On : Tue Jun 13 15:28:44 201713 // Update Count : 211 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Fri Jul 1 09:16:01 2022 13 // Update Count : 15 14 14 // 15 15 … … 158 158 159 159 private: 160 void setSize( Expression * expr ) { // replace this logic with an eval call161 auto res = eval( expr);160 void setSize( Expression * expr ) { 161 auto res = eval( expr ); 162 162 if (res.second) { 163 163 size = res.first; … … 170 170 void setPosition( Expression * expr ) { 171 171 // need to permit integer-constant-expressions, including: integer constants, enumeration constants, character constants, sizeof expressions, _Alignof expressions, cast expressions 172 if ( ConstantExpr * constExpr = dynamic_cast< ConstantExpr * >( expr ) ) { 173 try { 174 index = constExpr->intValue(); 175 } catch( SemanticErrorException & ) { 176 SemanticError( expr, "Constant expression of non-integral type in array designator: " ); 177 } 178 } else if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) { 179 setPosition( castExpr->get_arg() ); 180 } else if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( expr ) ) { 181 EnumInstType * inst = dynamic_cast<EnumInstType *>( varExpr->get_result() ); 182 assertf( inst, "ArrayIterator given variable that isn't an enum constant : %s", toString( expr ).c_str() ); 183 long long int value; 184 if ( inst->baseEnum->valueOf( varExpr->var, value ) ) { 185 index = value; 186 } 187 } else if ( dynamic_cast< SizeofExpr * >( expr ) || dynamic_cast< AlignofExpr * >( expr ) ) { 188 index = 0; // xxx - get actual sizeof/alignof value? 189 } else { 190 assertf( false, "bad designator given to ArrayIterator: %s", toString( expr ).c_str() ); 191 } 172 auto arg = eval( expr ); 173 index = arg.first; 174 return; 175 176 // if ( ConstantExpr * constExpr = dynamic_cast< ConstantExpr * >( expr ) ) { 177 // try { 178 // index = constExpr->intValue(); 179 // } catch( SemanticErrorException & ) { 180 // SemanticError( expr, "Constant expression of non-integral type in array designator: " ); 181 // } 182 // } else if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) { 183 // setPosition( castExpr->get_arg() ); 184 // } else if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( expr ) ) { 185 // EnumInstType * inst = dynamic_cast<EnumInstType *>( varExpr->get_result() ); 186 // assertf( inst, "ArrayIterator given variable that isn't an enum constant : %s", toString( expr ).c_str() ); 187 // long long int value; 188 // if ( inst->baseEnum->valueOf( varExpr->var, value ) ) { 189 // index = value; 190 // } 191 // } else if ( dynamic_cast< SizeofExpr * >( expr ) || dynamic_cast< AlignofExpr * >( expr ) ) { 192 // index = 0; // xxx - get actual sizeof/alignof value? 193 // } else { 194 // assertf( false, "4 bad designator given to ArrayIterator: %s", toString( expr ).c_str() ); 195 // } 192 196 } 193 197 … … 329 333 assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() ); 330 334 } else { 331 assertf( false, " bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() );335 assertf( false, "3 bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() ); 332 336 } // if 333 337 } // if … … 637 641 638 642 void setSize( const Expr * expr ) { 639 auto res = eval( expr);643 auto res = eval( expr ); 640 644 if ( ! res.second ) { 641 SemanticError( location, 642 toString("Array designator must be a constant expression: ", expr ) ); 645 SemanticError( location, toString( "Array designator must be a constant expression: ", expr ) ); 643 646 } 644 647 size = res.first; … … 646 649 647 650 public: 648 ArrayIterator( const CodeLocation & loc, const ArrayType * at ) 649 : location( loc ), array( at ), base( at->base ) { 651 ArrayIterator( const CodeLocation & loc, const ArrayType * at ) : location( loc ), array( at ), base( at->base ) { 650 652 PRINT( std::cerr << "Creating array iterator: " << at << std::endl; ) 651 653 memberIter.reset( createMemberIterator( loc, base ) ); … … 660 662 // enumeration constants, character constants, sizeof expressions, alignof expressions, 661 663 // cast expressions 662 if ( auto constExpr = dynamic_cast< const ConstantExpr * >( expr ) ) { 663 try {664 index = constExpr->intValue();665 } catch ( SemanticErrorException & ) {666 SemanticError( expr, 667 "Constant expression of non-integral type in array designator: " );668 }669 } else if ( auto castExpr = dynamic_cast< const CastExpr * >( expr ) ) {670 setPosition( castExpr->arg );671 } else if (672 dynamic_cast< const SizeofExpr * >( expr )673 || dynamic_cast< const AlignofExpr * >( expr )674 ) {675 index = 0;676 } else {677 assertf( false,678 "bad designator given to ArrayIterator: %s", toString( expr ).c_str() );679 }664 665 auto arg = eval( expr ); 666 index = arg.first; 667 return; 668 669 // if ( auto constExpr = dynamic_cast< const ConstantExpr * >( expr ) ) { 670 // try { 671 // index = constExpr->intValue(); 672 // } catch ( SemanticErrorException & ) { 673 // SemanticError( expr, "Constant expression of non-integral type in array designator: " ); 674 // } 675 // } else if ( auto castExpr = dynamic_cast< const CastExpr * >( expr ) ) { 676 // setPosition( castExpr->arg ); 677 // } else if ( dynamic_cast< const SizeofExpr * >( expr ) || dynamic_cast< const AlignofExpr * >( expr ) ) { 678 // index = 0; 679 // } else { 680 // assertf( false, "2 bad designator given to ArrayIterator: %s", toString( expr ).c_str() ); 681 // } 680 682 } 681 683 … … 723 725 std::deque< InitAlternative > ret = memberIter->first(); 724 726 for ( InitAlternative & alt : ret ) { 725 alt.designation.get_and_mutate()->designators.emplace_front( 726 ConstantExpr::from_ulong( location, index ) ); 727 alt.designation.get_and_mutate()->designators.emplace_front( ConstantExpr::from_ulong( location, index ) ); 727 728 } 728 729 return ret; … … 788 789 return; 789 790 } 790 assertf( false, 791 "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() ); 791 assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() ); 792 792 } else { 793 assertf( false, 794 "bad designator given to %s: %s", kind.c_str(), toString( *begin ).c_str() ); 793 assertf( false, "1 bad designator given to %s: %s", kind.c_str(), toString( *begin ).c_str() ); 795 794 } 796 795 } -
src/SynTree/AggregateDecl.cc
r06bdba4 r25404c7 10 10 // Created On : Sun May 17 23:56:39 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Dec 16 15:07:20 201913 // Update Count : 3 112 // Last Modified On : Fri Jul 1 09:12:33 2022 13 // Update Count : 32 14 14 // 15 15 … … 125 125 SingleInit * init = strict_dynamic_cast< SingleInit * >( field->init ); 126 126 auto result = eval( init->value ); 127 if ( ! result.second ) SemanticError( init->location, toString( " Non-constexpr in initialization of enumerator: ", field) );127 if ( ! result.second ) SemanticError( init->location, toString( "Enumerator value for '", field, "' is not an integer constant" ) ); 128 128 currentValue = result.first; 129 129 } -
tests/.expect/attributes.nast.arm64.txt
r06bdba4 r25404c7 1338 1338 } 1339 1339 1340 { 1341 ((void)(_X4_retM12__anonymous4_2=(*_X4_dstM12__anonymous4_2)) /* ?{} */); 1342 } 1343 1344 return _X4_retM12__anonymous4_2; 1340 return (*_X4_dstM12__anonymous4_2); 1345 1341 } 1346 1342 { -
tests/enum.cfa
r06bdba4 r25404c7 24 24 } 25 25 26 // test constant-expressions 27 28 struct S { 29 int i; 30 }; 31 enum K { P = 3 + 4 }; 32 enum Y { W = 9 + (3 && 4 || 7)}; 33 int p[W]; 34 enum { X = W + -3 + ~1 / 2 * (int)4 + sizeof(struct S) + _Alignof(struct S) || 3 && 5 + (3 ? 1 : 2 ) + __builtin_offsetof(struct S, i ) }; 35 int x[X]; 36 enum { B = 3 + 4 - 7 * 20 / 34 << 3 >> 4 > 8 < 9 <= 23 >= 42 == 12 != 13 & 4 ^ 2 | 8 + sizeof(struct S) + _Alignof(struct S) }; 37 int y[B]; 38 enum { J = +3 + -4 / ~20 * ! 0 }; 39 int z[J] = { 1, 2, 3 }; 40 int aa[41] @= { [3] : 3, [1] : 6 }; 41 26 42 //Dummy main 27 43 int main(int argc, char const *argv[]) {
Note: See TracChangeset
for help on using the changeset viewer.