Changeset 25404c7


Ignore:
Timestamp:
Jul 5, 2022, 9:36:59 AM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
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.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
1 added
13 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/Makefile

    r06bdba4 r25404c7  
    3434        base \
    3535        base_avg \
     36        base_ts2 \
    3637        cache-share \
    3738        cache-noshare \
  • doc/theses/thierry_delisle_PhD/thesis/fig/base.fig

    r06bdba4 r25404c7  
    13131 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200
    1414-6
    15 6 6375 5100 6675 5250
    16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6450 5175 20 20 6450 5175 6470 5175
    17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5175 20 20 6525 5175 6545 5175
    18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5175 20 20 6600 5175 6620 5175
     156 6450 5025 6750 5175
     161 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100
     171 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100
     181 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100
    1919-6
    20201 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400
     
    80802 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    8181         2400 2475 3000 2475
    82 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    83          3300 5210 3150 4950 2850 4950 2700 5210 2850 5470 3150 5470
    84          3300 5210
    85 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    86          4500 5210 4350 4950 4050 4950 3900 5210 4050 5470 4350 5470
    87          4500 5210
    88 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    89          5700 5210 5550 4950 5250 4950 5100 5210 5250 5470 5550 5470
    90          5700 5210
    91822 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    92          3600 5700 3600 1200
     83         3600 5400 3600 1200
    93842 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    94          4800 5700 4800 1200
     85         4800 5400 4800 1200
    95862 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
     882 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
     902 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
     922 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
     944 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001
     954 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001
     964 1 -1 50 -1 0 11 0.0000 2 120 210 2700 4450 TS\001
     974 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001
     984 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001
     994 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001
     1004 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  
    13131 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200
    1414-6
    15 6 6375 5100 6675 5250
    16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6450 5175 20 20 6450 5175 6470 5175
    17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5175 20 20 6525 5175 6545 5175
    18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5175 20 20 6600 5175 6620 5175
     156 6450 5025 6750 5175
     161 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100
     171 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100
     181 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100
    1919-6
    20201 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400
     
    52522 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    5353        1 1 1.00 45.00 90.00
    54          3900 3975 3900 3600
     54         3900 4200 3900 3600
    55552 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    5656        1 1 1.00 45.00 90.00
     
    61612 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6262        1 1 1.00 45.00 90.00
    63          5100 3975 5100 3600
     63         5100 4200 5100 3600
    64642 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6565        1 1 1.00 45.00 90.00
     
    67672 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6868        1 1 1.00 45.00 90.00
    69          6300 3975 6300 3600
     69         6300 4200 6300 3600
    70702 1 0 1 -1 7 50 -1 -1 0.000 0 0 -1 1 0 2
    7171        1 1 1.00 45.00 90.00
     
    75752 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    7676        1 1 1.00 45.00 90.00
    77          4500 3975 4500 3600
     77         4500 4200 4500 3600
    78782 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    7979         2400 3375 3000 3375
    80802 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    8181         2400 2475 3000 2475
    82 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    83          3300 5210 3150 4950 2850 4950 2700 5210 2850 5470 3150 5470
    84          3300 5210
    85 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    86          4500 5210 4350 4950 4050 4950 3900 5210 4050 5470 4350 5470
    87          4500 5210
    88 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
    89          5700 5210 5550 4950 5250 4950 5100 5210 5250 5470 5550 5470
    90          5700 5210
    91822 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    92          3600 5700 3600 1200
     83         3600 5400 3600 1200
    93842 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    94          4800 5700 4800 1200
     85         4800 5400 4800 1200
    95862 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
     882 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
     902 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
     922 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
    97942 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    9895         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
     964 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001
     974 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001
     984 1 -1 50 -1 0 11 0.0000 2 120 300 2700 4450 MA\001
     994 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001
     1004 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001
     1014 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001
     1024 2 -1 50 -1 0 12 0.0000 2 135 840 2100 5175 Processors\001
     1034 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  
    88-2
    991200 2
    10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 2475
    11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 2475
    12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4950 2550 456 456 4950 2550 4500 2475
    13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 2475
     101 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575
     111 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575
     121 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575
     131 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575
    14142 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 3300
     15         1200 2400 2100 2400 2100 2700 1200 2700 1200 2400
    16162 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 3900
     17         1200 3000 2100 3000 2100 3600 1200 3600 1200 3000
    18182 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 3300
     19         2400 2400 3300 2400 3300 2700 2400 2700 2400 2400
    20202 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 3900
     21         2400 3000 3300 3000 3300 3600 2400 3600 2400 3000
    22222 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 3300
     23         3600 2400 4500 2400 4500 2700 3600 2700 3600 2400
    24242 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 3900
     25         3600 3000 4500 3000 4500 3600 3600 3600 3600 3000
    26262 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 3300
     27         4800 2400 5700 2400 5700 2700 4800 2700 4800 2400
    28282 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
     29         4800 3000 5700 3000 5700 3600 4800 3600 4800 3000
    30302 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 4800
     31         1200 3900 3300 3900 3300 4800 1200 4800 1200 3900
    32322 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 4800
     33         3600 3900 5700 3900 5700 4800 3600 4800 3600 3900
    34342 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3535        1 1 1.00 60.00 45.00
    3636        1 1 1.00 60.00 45.00
    37          2550 3000 2550 3300
     37         1650 2100 1650 2400
    38382 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3939        1 1 1.00 60.00 45.00
    4040        1 1 1.00 60.00 45.00
    41          6150 3000 6150 3300
     41         5250 2100 5250 2400
    42422 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4343        1 1 1.00 60.00 45.00
    4444        1 1 1.00 60.00 45.00
    45          6150 3600 6150 3900
     45         5250 2700 5250 3000
    46462 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4747        1 1 1.00 60.00 45.00
    4848        1 1 1.00 60.00 45.00
    49          3750 3000 3750 3300
     49         2850 2100 2850 2400
    50502 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5151        1 1 1.00 60.00 45.00
    5252        1 1 1.00 60.00 45.00
    53          4950 3000 4950 3300
     53         4050 2100 4050 2400
    54542 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5555        1 1 1.00 60.00 45.00
    5656        1 1 1.00 60.00 45.00
    57          4950 3600 4950 3900
     57         4050 2700 4050 3000
    58582 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5959        1 1 1.00 60.00 45.00
    6060        1 1 1.00 60.00 45.00
    61          3750 3600 3750 3900
     61         1650 2700 1650 3000
    62622 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6363        1 1 1.00 60.00 45.00
    6464        1 1 1.00 60.00 45.00
    65          2550 3600 2550 3900
     65         1650 3600 1650 3900
    66662 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6767        1 1 1.00 60.00 45.00
    6868        1 1 1.00 60.00 45.00
    69          2550 4500 2550 4800
     69         2850 3600 2850 3900
    70702 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7171        1 1 1.00 60.00 45.00
    7272        1 1 1.00 60.00 45.00
    73          3750 4500 3750 4800
     73         4050 3600 4050 3900
    74742 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7575        1 1 1.00 60.00 45.00
    7676        1 1 1.00 60.00 45.00
    77          4950 4500 4950 4800
     77         5250 3600 5250 3900
    78782 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7979        1 1 1.00 60.00 45.00
    8080        1 1 1.00 60.00 45.00
    81          6150 4500 6150 4800
     81         3300 4350 3600 4350
    82822 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    8383        1 1 1.00 60.00 45.00
    8484        1 1 1.00 60.00 45.00
    85          4200 5250 4500 5250
    86 4 0 0 50 -1 0 11 0.0000 2 135 360 4725 2625 CPU2\001
    87 4 0 0 50 -1 0 11 0.0000 2 135 360 2325 2625 CPU0\001
    88 4 0 0 50 -1 0 11 0.0000 2 135 360 5925 2625 CPU3\001
    89 4 0 0 50 -1 0 11 0.0000 2 135 360 3525 2625 CPU1\001
    90 4 0 0 50 -1 0 11 0.0000 2 135 180 2475 3525 L1\001
    91 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 3525 L1\001
    92 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 3525 L1\001
    93 4 0 0 50 -1 0 11 0.0000 2 135 180 2400 4275 L2\001
    94 4 0 0 50 -1 0 11 0.0000 2 135 180 4875 4275 L2\001
    95 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 4275 L2\001
    96 4 0 0 50 -1 0 11 0.0000 2 135 180 6075 4275 L2\001
    97 4 0 0 50 -1 0 11 0.0000 2 135 180 3675 3525 L1\001
    98 4 0 0 50 -1 0 11 0.0000 2 135 180 3000 5250 L3\001
    99 4 0 0 50 -1 0 11 0.0000 2 135 180 5475 5250 L3\001
     85         2850 2700 2850 3000
     864 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001
     874 1 0 50 -1 0 12 0.0000 2 135 225 2250 4425 L3\001
     884 1 0 50 -1 0 12 0.0000 2 135 225 4650 4425 L3\001
     894 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001
     904 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001
     914 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001
     924 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001
     934 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001
     944 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001
     954 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001
     964 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001
     974 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001
     984 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001
     994 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  
    88-2
    991200 2
    10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 2475
    11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 2475
    12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4950 2550 456 456 4950 2550 4500 2475
    13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 2475
     101 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575
     111 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575
     121 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575
     131 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575
    14142 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 3300
     15         1200 2400 2100 2400 2100 2700 1200 2700 1200 2400
    16162 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 3900
     17         1200 3000 2100 3000 2100 3600 1200 3600 1200 3000
    18182 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 3300
     19         2400 2400 3300 2400 3300 2700 2400 2700 2400 2400
    20202 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 3900
     21         2400 3000 3300 3000 3300 3600 2400 3600 2400 3000
    22222 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 3300
     23         3600 2400 4500 2400 4500 2700 3600 2700 3600 2400
    24242 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 3900
     25         3600 3000 4500 3000 4500 3600 3600 3600 3600 3000
    26262 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 3300
     27         4800 2400 5700 2400 5700 2700 4800 2700 4800 2400
    28282 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
    32302 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3331        1 1 1.00 60.00 45.00
    3432        1 1 1.00 60.00 45.00
    35          2550 3000 2550 3300
     33         1650 2100 1650 2400
    36342 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3735        1 1 1.00 60.00 45.00
    3836        1 1 1.00 60.00 45.00
    39          3750 3000 3750 3300
     37         2850 2100 2850 2400
    40382 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4139        1 1 1.00 60.00 45.00
    4240        1 1 1.00 60.00 45.00
    43          4950 3000 4950 3300
     41         4050 2100 4050 2400
    44422 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4543        1 1 1.00 60.00 45.00
    4644        1 1 1.00 60.00 45.00
    47          6150 3000 6150 3300
     45         5250 2100 5250 2400
    48462 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4947        1 1 1.00 60.00 45.00
    5048        1 1 1.00 60.00 45.00
    51          6150 3600 6150 3900
     49         5250 2700 5250 3000
    52502 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5351        1 1 1.00 60.00 45.00
    5452        1 1 1.00 60.00 45.00
    55          4950 3600 4950 3900
     53         4050 2700 4050 3000
    56542 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5755        1 1 1.00 60.00 45.00
    5856        1 1 1.00 60.00 45.00
    59          3750 3600 3750 3900
     57         2850 2700 2850 3000
    60582 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6159        1 1 1.00 60.00 45.00
    6260        1 1 1.00 60.00 45.00
    63          2550 3600 2550 3900
     61         1650 2700 1650 3000
    64622 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6563        1 1 1.00 60.00 45.00
    6664        1 1 1.00 60.00 45.00
    67          2550 4500 2550 4800
     65         1650 3600 1650 3900
    68662 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6967        1 1 1.00 60.00 45.00
    7068        1 1 1.00 60.00 45.00
    71          3750 4500 3750 4800
     69         2850 3600 2850 3900
    72702 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7371        1 1 1.00 60.00 45.00
    7472        1 1 1.00 60.00 45.00
    75          4950 4500 4950 4800
     73         4050 3600 4050 3900
    76742 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7775        1 1 1.00 60.00 45.00
    7876        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
     782 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
     804 1 0 50 -1 0 12 0.0000 2 135 225 3450 4425 L3\001
     814 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001
     824 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001
     834 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001
     844 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001
     854 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001
     864 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001
     874 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001
     884 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001
     894 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001
     904 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001
     914 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001
     924 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  
    11\chapter{Scheduling Core}\label{core}
    22
    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.
     3Before 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.
     4For 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.
     5In short, the system is neither overloaded nor underloaded.
     6
     7It 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.
     8As 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.
     9Therefore, flaws in scheduling the steady state tend to be pervasive in all states.
    610
    711\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.
     12As 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.
     13To 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.
    914
    1015For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' :
     
    1722Applied 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.
    1823
    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:
     24In 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.
     25This 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.
     26This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees:
    2027\begin{enumerate}
    2128        \item A fairness guarantee: a \gls{thrd} that is ready to run is not prevented by another thread.
     
    2330\end{enumerate}
    2431
    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 
     32It 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.
     34Therefore, 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
     36Similar to the performance guarantee, the lack of interference among threads is only relevant up to a point.
     37Ideally, 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.
     38How much is an acceptable cost is obviously highly variable.
     39For this document, the performance experimentation attempts to show the cost of scheduling is at worst equivalent to existing algorithms used in popular languages.
     40This demonstration can be made by comparing applications built in \CFA to applications built with other languages or other models.
     41Recall programmer expectation is that the impact of the scheduler can be ignored.
     42Therefore, if the cost of scheduling is competitive to other popular languages, the guarantee is consider achieved.
    2943More precisely the scheduler should be:
    3044\begin{itemize}
     
    3448
    3549\subsection{Fairness Goals}
    36 For this work fairness will be considered as having two 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.
     50For 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.
     53In any running system, a \proc can stop dequeuing \ats if it starts running a \at that never blocks.
     54Without preemption, traditional work-stealing schedulers do not have starvation freedom in this case.
    4155Now this requirement begs the question, what about preemption?
    4256Generally speaking preemption happens on the timescale of several milliseconds, which brings us to the next requirement: ``fast'' load balancing.
    4357
    4458\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 millseconds to run are effectively starved.
     59For 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.
    4660Therefore load-balancing should be done at a faster pace, one that can detect starvation at the microsecond scale.
    4761With 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.
    4862
    4963\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.
     64An important performance factor in modern architectures is cache locality.
     65Waiting for data at lower levels or not present in the cache can have a major impact on performance.
     66Having multiple \glspl{hthrd} writing to the same cache lines also leads to cache lines that must be waited on.
     67It 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
     69For a scheduler, having good locality, \ie, having the data local to each \gls{hthrd}, generally conflicts with fairness.
     70Indeed, 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.
     71Note 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.
     72External locality is a much more complicated subject and is discussed in the next section.
     73
     74However, I claim that in practice it is possible to strike a balance between fairness and performance because these goals do not necessarily overlap temporally.
     75Figure~\ref{fig:fair} shows a visual representation of this behaviour.
     76As 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.
    5577
    5678\begin{figure}
     
    5880        \input{fairness.pstex_t}
    5981        \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.}
    6185        \label{fig:fair}
    6286\end{figure}
    6387
    6488\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.
     89While there exists a multitude of potential scheduling algorithms, they generally always have to contend with the same performance challenges.
     90Since 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.
    6691
    6792\subsubsection{Scalability}
     
    6994Given a large number of \procs and an even larger number of \ats, scalability measures how fast \procs can enqueue and dequeues \ats.
    7095One 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, auxillary scheduling features, \eg counting ready \ats, can also be sources of contention.
     96While 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.
    7297
    7398\subsubsection{Migration Cost}
    74 Another important source of latency in scheduling is migration.
    75 An \at is said to have migrated if it is executed by two different \proc consecutively, which is the process discussed in \ref{fairnessvlocal}.
    76 Migrations can have many different causes, but it 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 the latency penalty from migrations.
     99Another important source of scheduling latency is migration.
     100A \at migrates if it executes on two different \procs consecutively, which is the process discussed in \ref{fairnessvlocal}.
     101Migrations can have many different causes, but in certain programs, it can be impossible to limit migration.
     102Chapter~\ref{microbench} has a benchmark where any \at can potentially unblock any other \at, which can lead to \ats migrating frequently.
     103Hence, it is important to design the internal data structures of the scheduler to limit any latency penalty from migrations.
    79104
    80105
    81106\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.
     107In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance.
     108The problem is a single point of contention when adding/removing \ats.
     109As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}.
     110The 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
     112Before 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.
    85113
    86114\subsection{Work-Stealing}
    87115
    88 As mentioned in \ref{existing:workstealing}, a popular pattern shard the 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 workstealing happen in easier scheduling cases, \ie enough work for everyone but no more and no load balancing needed.
    91 In these cases, work-stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.
     116As mentioned in \ref{existing:workstealing}, a popular sharding approach for the ready-queue is work-stealing.
     117In 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.
     118The interesting aspect of work stealing happens in the steady-state scheduling case, \ie all \glspl{proc} have work and no load balancing is needed.
     119In this case, work stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.
    92120On the other hand, work-stealing schedulers only attempt to do load-balancing when a \gls{proc} runs out of work.
    93121This 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.
     122Chapter~\ref{microbench} shows that pathological cases work stealing can lead to indefinite starvation.
     123
     124Based 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}
     127A different scheduling approach is to create a ``relaxed-FIFO'' queue, as in \todo{cite Trevor's paper}.
     128This approach forgoes any ownership between \gls{proc} and subqueue, and simply creates a pool of ready-queues from which \glspl{proc} pick.
     129Scheduling is performed as follows:
     130\begin{itemize}
     131\item
     132All subqueues are protected by TryLocks.
     133\item
     134Timestamps are added to each element of a subqueue.
     135\item
     136A \gls{proc} randomly tests ready queues until it has acquired one or two queues.
     137\item
     138If two queues are acquired, the older of the two \ats at the front the acquired queues is dequeued.
     139\item
     140Otherwise the \ats from the single queue is dequeued.
     141\end{itemize}
     142The result is a queue that has both good scalability and sufficient fairness.
     143The 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.
     144This 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.
     145This unfairness persists until a \gls{proc} runs out of work and steals.
    106146
    107147An 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 the 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 too few ready \ats.
     148However, \glspl{proc} eagerly search for these older elements instead of focusing on specific queues, which negatively affects locality.
     149
     150While this scheme has good fairness, its performance suffers.
     151It requires wide sharding, \eg at least 4 queues per \gls{hthrd}, and finding non-empty queues is difficult when there are few ready \ats.
    112152
    113153\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.
     154The inherent fairness and good performance with many \ats, makes the relaxed-FIFO queue a good candidate to form the basis of a new scheduler.
     155The problem case is workloads where the number of \ats is barely greater than the number of \procs.
     156In these situations, the wide sharding of the ready queue means most of its subqueues are empty.
     157Furthermore, the non-empty subqueues are unlikely to hold more than one item.
     158The consequence is that a random dequeue operation is likely to pick an empty subqueue, resulting in an unbounded number of selections.
     159This state is generally unstable: each subqueue is likely to frequently toggle between being empty and nonempty.
     160Indeed, 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.
     161In the worst case, a check of the subqueues sees all are empty or full.
    119162
    120163As 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.
     164The 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}.
     165This sharded data can be organized in different forms, \eg a bitmask or a binary tree that tracks the nonempty subqueues.
     166Specifically, many modern architectures have powerful bitmask manipulation instructions or searching a binary tree has good Big-O complexity.
     167However, precisely tracking nonempty subqueues is problematic.
     168The reason is that the subqueues are initially sharded with a width presumably chosen to avoid contention.
     169However, tracking which ready queue is nonempty is only useful if the tracking data is dense, \ie denser than the sharded subqueues.
     170Otherwise, it does not provide useful information because reading this new data structure risks being as costly as simply picking a subqueue at random.
     171But if the tracking mechanism \emph{is} denser than the shared subqueues, than constant updates invariably create a new source of contention.
     172Early experiments with this approach showed that randomly picking, even with low success rates, is often faster than bit manipulations or tree walks.
    129173
    130174The 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 not complete.
    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 this information and its poor quality.
    136 
    137 However, using a very low cost approach to local tracking may actually 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 lead to a performance benefits.
    139 This leads to the following approach:
     175If 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.
     176However, the consequence of local tracking is that the information is incomplete.
     177Each \proc is only aware of the last state it saw about each subqueue so this information quickly becomes stale.
     178Even 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.
     179This result is due in part to the cost of maintaining information and its poor quality.
     180
     181However, using a very low cost but inaccurate approach for local tracking can actually be beneficial.
     182If 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.
     183This suggests to the following approach:
    140184
    141185\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 example some Linear Congruential Generators\cit{https://en.wikipedia.org/wiki/Linear\_congruential\_generator} support running the algorithm backwards while offering good quality and performance.
     186The Relaxed-FIFO approach can be made to handle the case of mostly empty subqueues by tweaking the \glsxtrlong{prng}.
     187The \glsxtrshort{prng} state can be seen as containing a list of all the future subqueues that will be accessed.
     188While 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.
     189Luckily, 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.
    146190This 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
     193Each \proc maintains two \glsxtrshort{prng} states, refereed to as $F$ and $B$.
     194\item
     195When a \proc attempts to dequeue a \at, it picks a subqueue by running $B$ backwards.
     196\item
     197When a \proc attempts to enqueue a \at, it runs $F$ forward picking a subqueue to enqueue to.
     198If the enqueue is successful, the state $B$ is overwritten with the content of $F$.
     199\end{itemize}
     200The result is that each \proc tends to dequeue \ats that it has itself enqueued.
     201When 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
     203Tests showed this approach performs better than relaxed-FIFO in many cases.
     204However, it is still not competitive with work-stealing algorithms.
    158205The 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.
     206This becomes problematic both because the scheduler is likely to get cache misses on internal data-structures and because migrations become frequent.
     207Therefore, the attempt to modify the relaxed-FIFO algorithm to behave more like work stealing did not pan out.
     208The alternative is to do it the other way around.
    161209
    162210\section{Work Stealing++}
    163 To add stronger fairness guarantees to workstealing a few changes.
     211To add stronger fairness guarantees to work stealing a few changes are needed.
    164212First, 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.
     213Therefore, the work-stealing algorithm must be prepended with some monitoring.
     214Before attempting to dequeue from a \proc's subqueue, the \proc must make some effort to ensure other subqueues are not being neglected.
     215To make this possible, \procs must be able to determine which \at has been on the ready queue the longest.
     216Second, the relaxed-FIFO approach needs timestamps for each \at to make this possible.
    170217
    171218\begin{figure}
    172219        \centering
    173220        \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.}
    175224        \label{fig:base}
    176225\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
     227Figure~\ref{fig:base} shows the algorithm structure.
     228This structure is similar to classic work-stealing except the subqueues are placed in an array so \procs can access them in constant time.
     229Sharding width can be adjusted based on contention.
     230Note, 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.
     231This organization keeps the highly accessed front TSs directly in the array.
     232When 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).
     233The oldest waiting \at is dequeued to provide global fairness.
     234
     235However, this na\"ive implemented has performance problems.
    183236First, 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.
     237Random effects like cache misses and preemption can add spurious but short bursts of latency negating the attempt to help.
     238These bursts can cause increased migrations and make this work stealing approach slowdown to the level of relaxed-FIFO.
    186239
    187240\begin{figure}
     
    192245\end{figure}
    193246
    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 the raw 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 have waited.
    197 To compare subqueues, the timestamp at the head must be compared to the current time, yielding the bestcase wait time for the \at at the head of the queue.
     247A 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}.
     248Note, this is more complex because the \at at the head of a subqueue is still waiting, so its wait time has not ended.
     249Therefore, the exponential moving average is actually an exponential moving average of how long each dequeued \at has waited.
     250To 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.
    198251This 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.
     252To 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.
     253Tests 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
     255With these additions to work stealing, scheduling can be made as fair as the relaxed-FIFO approach, avoiding the majority of unnecessary migrations.
     256Unfortunately, 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.
     257The 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.
     258To 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.
     259Conversely, the active subqueues do not benefit much from helping since starvation is already a non-issue.
     260This puts this algorithm in the awkward situation of paying for a cost that is largely unnecessary.
    209261The good news is that this problem can be mitigated
    210262
    211263\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.
     264The problem with polling remote subqueues is that correctness is critical.
     265There must be a consensus among \procs on which subqueues hold which \ats, as the \ats are in constant motion.
     266Furthermore, since timestamps are use for fairness, it is critical to have consensus on which \at is the oldest.
     267However, when deciding if a remote subqueue is worth polling, correctness is less of a problem.
     268Since the only requirement is that a subqueue is eventually polled, some data staleness is acceptable.
     269This leads to a situation where stale timestamps are only problematic in some cases.
     270Furthermore, stale timestamps can be desirable since lower freshness requirements mean less cache invalidations.
     271
     272Figure~\ref{fig:base-ts2} shows a solution with a second array containing a copy of the timestamps and average.
    228273This copy is updated \emph{after} the subqueue's critical sections using relaxed atomics.
    229274\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.
     275The 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
     285The correctness argument is somewhat subtle.
    233286The 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.
     287Therefore, it is acceptable if stale data makes queues appear older than they really are but appearing fresher can be a problem.
     288For the timestamps, this means missing writes to the timestamp is acceptable since they make the head \at look older.
     289For 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.
     290Therefore, this unprotected read of the timestamp and average satisfy the limited correctness that is required.
     291
     292With redundant timestamps, this scheduling algorithm achieves both the fairness and performance requirements on most machines.
     293The problem is that the cost of polling and helping is not necessarily consistent across each \gls{hthrd}.
     294For 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.
     295Cache misses satisfied by a remote CPU have significantly higher latency than from the local CPU.
     296However, these delays are not specific to systems with multiple CPUs.
     297Depending 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}.
    238298
    239299\begin{figure}
    240300        \centering
    241301        \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.}
    243303        \label{fig:cache-share}
    244 \end{figure}
    245 
    246 \begin{figure}
    247         \centering
     304
     305        \vspace{25pt}
     306
    248307        \input{cache-noshare.pstex_t}
    249         \caption[CPU design with a narrower L3 sharing]{CPU design with a narrower 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.}
    250309        \label{fig:cache-noshare}
    251310\end{figure}
    252311
    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.
     312Figures~\ref{fig:cache-share} and~\ref{fig:cache-noshare} show two different cache topologies that highlight this difference.
     313In Figure~\ref{fig:cache-share}, all cache misses are either private to a CPU or shared with another CPU.
     314This means latency due to cache misses is fairly consistent.
     315In contrast, in Figure~\ref{fig:cache-noshare} misses in the L2 cache can be satisfied by either instance of L3 cache.
     316However, the memory-access latency to the remote L3 is higher than the memory-access latency to the local L3.
     317The 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}.
     318Hence, as the number of L3 instances grow, so too does the chance that the random helping causes significant cache latency.
     319The solution is for the scheduler be aware of the cache topology.
    267320
    268321\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.
     322Building a scheduler that is cache aware poses two main challenges: discovering the cache topology and matching \procs to this cache structure.
     323Unfortunately, there is no portable way to discover cache topology, and it is outside the scope of this thesis to solve this problem.
     324This work uses the cache topology information from Linux's \texttt{/sys/devices/system/cpu} directory.
     325This 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.
     326Once 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{
     327Note that like other biases mentioned in this section, the actual bias value does not appear to need precise tuning.}
     328
     329The simplest approach for mapping subqueues to cache structure is to statically tie subqueues to CPUs.
     330Instead of having each subqueue local to a specific \proc, the system is initialized with subqueues for each hardware hyperthread/core up front.
     331Then \procs dequeue and enqueue by first asking which CPU id they are executing on, in order to identify which subqueues are the local ones.
    280332\Glspl{proc} can get the CPU id from \texttt{sched\_getcpu} or \texttt{librseq}.
    281333
    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, specifically systems with few \procs and many \glspl{hthrd}.
    284 In these cases, the large number of subqueues and the bias agains subqueues tied to different cache instances make it so it is very unlikely any single subqueue 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 before it gets randomly helped.
     334This approach solves the performance problems on systems with topologies with narrow L3 caches, similar to Figure \ref{fig:cache-noshare}.
     335However, it can still cause some subtle fairness problems in systems with few \procs and many \glspl{hthrd}.
     336In 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.
     337To make things worst, the small number of \procs mean that few helping attempts are made.
     338This 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.
    287339On 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.
    288340Therefore, a more dynamic matching of subqueues to cache instance is needed.
    289341
    290342\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 finess because reading this data structure must lead to fewer cache misses than not having the data structure in the first place.
     343Therefore, 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.
     344This 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.
    293345A 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.
     346Therefore the algorithm can be built as follows: before enqueueing or dequeuing a \at, each \proc queries the CPU id and the corresponding cache instance.
    295347Since subqueues are tied to \procs, each \proc can then update the cache instance mapped to the local subqueue(s).
    296348To avoid unnecessary cache line invalidation, the map is only written to if the mapping changes.
    297349
     350This 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  
    8383\usepackage{graphicx} % For including graphics
    8484\usepackage{subcaption}
     85\usepackage{comment} % Removes large sections of the document.
    8586
    8687% Hyperlinks make it very easy to navigate an electronic document.
  • src/Common/Eval.cc

    r06bdba4 r25404c7  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Jul 24 15:09:06 2019
    13 // Update Count     : 64
     12// Last Modified On : Fri Jul  1 08:41:03 2022
     13// Update Count     : 117
    1414//
    1515
     
    1717
    1818#include "Common/PassVisitor.h"
     19#include "CodeGen/OperatorTable.h"                                              // access: OperatorInfo
    1920#include "AST/Pass.hpp"
    2021#include "InitTweak/InitTweak.h"
     
    2425// Old AST
    2526struct 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)
    2832
    2933        void previsit( const BaseSyntaxNode * ) { visit_children = false; }
     
    8993// New AST
    9094struct 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)
    93100
    94101        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
    98109                value = expr->intValue();
    99110        }
    100111
    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.
    108161                auto arg = eval(expr->arg);
    109162                valid = arg.second;
    110163                value = arg.first;
    111                 // TODO: perform type conversion on value if valid
    112         }
    113 
    114         void postvisit( const ast::VariableExpr * expr ) { // No hit
     164                cfavalid = false;
     165        }
     166
     167        void postvisit( const ast::VariableExpr * expr ) {
    115168                if ( const ast::EnumInstType * inst = dynamic_cast<const ast::EnumInstType *>(expr->result.get()) ) {
    116169                        if ( const ast::EnumDecl * decl = inst->base ) {
     
    128181                const std::string & fname = function->name;
    129182                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;
    135208                        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
    152248                // TODO: implement other intrinsic functions
    153249        }
    154250};
    155251
    156 std::pair<long long int, bool> eval( const Expression * expr) {
     252std::pair<long long int, bool> eval( const Expression * expr ) {
    157253        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 );
    161257        } else {
    162                 return std::make_pair(0, false);
     258                return std::make_pair( 0, false );
    163259        }
    164260}
    165261
    166 std::pair<long long int, bool> eval(const ast::Expr * expr) {
     262std::pair<long long int, bool> eval( const ast::Expr * expr ) {
    167263        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 );
    171267        } else {
    172                 return std::make_pair(0, false);
     268                return std::make_pair( 0, false );
    173269        }
    174270}
  • src/Parser/parser.yy

    r06bdba4 r25404c7  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat May 14 09:16:22 2022
    13 // Update Count     : 5401
     12// Last Modified On : Fri Jul  1 15:35:08 2022
     13// Update Count     : 5405
    1414//
    1515
     
    24412441        // empty
    24422442                { $$ = nullptr; }
    2443         // | '=' constant_expression
    2444         //      { $$ = $2; }
    2445         | simple_assignment_operator initializer
    2446                 { $$ = $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 ); }
    24472447        ;
    24482448
  • src/ResolvExpr/CurrentObject.cc

    r06bdba4 r25404c7  
    99// Author           : Rob Schluntz
    1010// Created On       : Tue Jun 13 15:28:32 2017
    11 // Last Modified By : Rob Schluntz
    12 // Last Modified On : Tue Jun 13 15:28:44 2017
    13 // Update Count     : 2
     11// Last Modified By : Peter A. Buhr
     12// Last Modified On : Fri Jul  1 09:16:01 2022
     13// Update Count     : 15
    1414//
    1515
     
    158158
    159159        private:
    160                 void setSize( Expression * expr ) { // replace this logic with an eval call
    161                         auto res = eval(expr);
     160                void setSize( Expression * expr ) {
     161                        auto res = eval( expr );
    162162                        if (res.second) {
    163163                                size = res.first;
     
    170170                void setPosition( Expression * expr ) {
    171171                        // 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                        // }
    192196                }
    193197
     
    329333                                        assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
    330334                                } 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() );
    332336                                } // if
    333337                        } // if
     
    637641
    638642                void setSize( const Expr * expr ) {
    639                         auto res = eval(expr);
     643                        auto res = eval( expr );
    640644                        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 ) );
    643646                        }
    644647                        size = res.first;
     
    646649
    647650        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 ) {
    650652                        PRINT( std::cerr << "Creating array iterator: " << at << std::endl; )
    651653                        memberIter.reset( createMemberIterator( loc, base ) );
     
    660662                        // enumeration constants, character constants, sizeof expressions, alignof expressions,
    661663                        // 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                        // }
    680682                }
    681683
     
    723725                                std::deque< InitAlternative > ret = memberIter->first();
    724726                                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 ) );
    727728                                }
    728729                                return ret;
     
    788789                                        return;
    789790                                }
    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() );
    792792                        } 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() );
    795794                        }
    796795                }
  • src/SynTree/AggregateDecl.cc

    r06bdba4 r25404c7  
    1010// Created On       : Sun May 17 23:56:39 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Dec 16 15:07:20 2019
    13 // Update Count     : 31
     12// Last Modified On : Fri Jul  1 09:12:33 2022
     13// Update Count     : 32
    1414//
    1515
     
    125125                                SingleInit * init = strict_dynamic_cast< SingleInit * >( field->init );
    126126                                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" ) );
    128128                                currentValue = result.first;
    129129                        }
  • tests/.expect/attributes.nast.arm64.txt

    r06bdba4 r25404c7  
    13381338        }
    13391339
    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);
    13451341    }
    13461342    {
  • tests/enum.cfa

    r06bdba4 r25404c7  
    2424}
    2525
     26// test constant-expressions
     27
     28struct S {
     29    int i;
     30};
     31enum K { P = 3 + 4 };
     32enum Y { W = 9 + (3 && 4 || 7)};
     33int p[W];
     34enum { X = W + -3 + ~1 / 2 * (int)4 + sizeof(struct S) + _Alignof(struct S) || 3 && 5 + (3 ? 1 : 2 ) + __builtin_offsetof(struct S, i ) };
     35int x[X];
     36enum { B = 3 + 4 - 7 * 20 / 34 << 3 >> 4 > 8 < 9 <= 23 >= 42 == 12 != 13  & 4 ^ 2 | 8 + sizeof(struct S) + _Alignof(struct S) };
     37int y[B];
     38enum { J = +3 + -4 / ~20 * ! 0 };
     39int z[J] = { 1, 2, 3 };
     40int aa[41] @= { [3] : 3, [1] : 6 };
     41
    2642//Dummy main
    2743int main(int argc, char const *argv[]) {
Note: See TracChangeset for help on using the changeset viewer.