Changes in / [25404c7:06bdba4]


Ignore:
Files:
1 deleted
13 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/thesis/Makefile

    r25404c7 r06bdba4  
    3434        base \
    3535        base_avg \
    36         base_ts2 \
    3736        cache-share \
    3837        cache-noshare \

  • doc/theses/thierry_delisle_PhD/thesis/fig/base.fig

    r25404c7 r06bdba4  
    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 6450 5025 6750 5175
    16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100
    17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100
    18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100
     156 6375 5100 6675 5250
     161 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6450 5175 20 20 6450 5175 6470 5175
     171 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5175 20 20 6525 5175 6545 5175
     181 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5175 20 20 6600 5175 6620 5175
    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
     822 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
     852 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
     882 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
    82912 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    83          3600 5400 3600 1200
     92         3600 5700 3600 1200
    84932 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    85          4800 5400 4800 1200
     94         4800 5700 4800 1200
    86952 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    87          6000 5400 6000 1200
    88 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    89          2700 4800 3300 4800 3300 5400 2700 5400 2700 4800
    90 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    91          3900 4800 4500 4800 4500 5400 3900 5400 3900 4800
    92 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    93          5100 4800 5700 4800 5700 5400 5100 5400 5100 4800
    94 4 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001
    95 4 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001
    96 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 4450 TS\001
    97 4 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001
    98 4 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001
    99 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001
    100 4 2 -1 50 -1 0 12 0.0000 2 135 840 2100 5175 Processors\001
     96         6000 5700 6000 1200
     974 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001
     984 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001
     994 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4450 TS\001
     1004 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001
     1014 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001
     1024 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001
     1034 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001
     1044 2 -1 50 -1 0 12 0.0000 2 135 900 2100 5175 Processors\001

  • doc/theses/thierry_delisle_PhD/thesis/fig/base_avg.fig

    r25404c7 r06bdba4  
    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 6450 5025 6750 5175
    16 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5100 20 20 6525 5100 6545 5100
    17 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5100 20 20 6600 5100 6620 5100
    18 1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6675 5100 20 20 6675 5100 6695 5100
     156 6375 5100 6675 5250
     161 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6450 5175 20 20 6450 5175 6470 5175
     171 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5175 20 20 6525 5175 6545 5175
     181 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5175 20 20 6600 5175 6620 5175
    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 4200 3900 3600
     54         3900 3975 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 4200 5100 3600
     63         5100 3975 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 4200 6300 3600
     69         6300 3975 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 4200 4500 3600
     77         4500 3975 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
     822 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
     852 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
     882 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
    82912 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    83          3600 5400 3600 1200
     92         3600 5700 3600 1200
    84932 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    85          4800 5400 4800 1200
     94         4800 5700 4800 1200
    86952 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2
    87          6000 5400 6000 1200
    88 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    89          2700 4800 3300 4800 3300 5400 2700 5400 2700 4800
    90 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    91          3900 4800 4500 4800 4500 5400 3900 5400 3900 4800
    92 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    93          5100 4800 5700 4800 5700 5400 5100 5400 5100 4800
     96         6000 5700 6000 1200
    94972 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    9598         2400 4050 3000 4050
    96 4 2 -1 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001
    97 4 2 -1 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001
    98 4 1 -1 50 -1 0 11 0.0000 2 120 300 2700 4450 MA\001
    99 4 2 -1 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001
    100 4 2 -1 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001
    101 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 3550 TS\001
    102 4 2 -1 50 -1 0 12 0.0000 2 135 840 2100 5175 Processors\001
    103 4 1 -1 50 -1 0 11 0.0000 2 120 210 2700 4225 TS\001
     994 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001
     1004 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001
     1014 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4450 MA\001
     1024 2 -1 50 -1 0 12 0.0000 2 165 720 2100 4200 Array of\001
     1034 2 -1 50 -1 0 12 0.0000 2 150 540 2100 4425 Queues\001
     1044 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001
     1054 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001
     1064 2 -1 50 -1 0 12 0.0000 2 135 900 2100 5175 Processors\001
     1074 1 -1 50 -1 0 11 0.0000 2 135 180 2700 4200 TS\001

  • doc/theses/thierry_delisle_PhD/thesis/fig/cache-noshare.fig

    r25404c7 r06bdba4  
    88-2
    991200 2
    10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575
    11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575
    12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575
    13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575
     101 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 2475
     111 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 2475
     121 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4950 2550 456 456 4950 2550 4500 2475
     131 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 2475
    14142 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    15          1200 2400 2100 2400 2100 2700 1200 2700 1200 2400
     15         2100 3300 3000 3300 3000 3600 2100 3600 2100 3300
    16162 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    17          1200 3000 2100 3000 2100 3600 1200 3600 1200 3000
     17         2100 3900 3000 3900 3000 4500 2100 4500 2100 3900
    18182 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    19          2400 2400 3300 2400 3300 2700 2400 2700 2400 2400
     19         3300 3300 4200 3300 4200 3600 3300 3600 3300 3300
    20202 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    21          2400 3000 3300 3000 3300 3600 2400 3600 2400 3000
     21         3300 3900 4200 3900 4200 4500 3300 4500 3300 3900
    22222 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    23          3600 2400 4500 2400 4500 2700 3600 2700 3600 2400
     23         4500 3300 5400 3300 5400 3600 4500 3600 4500 3300
    24242 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    25          3600 3000 4500 3000 4500 3600 3600 3600 3600 3000
     25         4500 3900 5400 3900 5400 4500 4500 4500 4500 3900
    26262 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    27          4800 2400 5700 2400 5700 2700 4800 2700 4800 2400
     27         5700 3300 6600 3300 6600 3600 5700 3600 5700 3300
    28282 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    29          4800 3000 5700 3000 5700 3600 4800 3600 4800 3000
     29         5700 3900 6600 3900 6600 4500 5700 4500 5700 3900
    30302 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    31          1200 3900 3300 3900 3300 4800 1200 4800 1200 3900
     31         2100 4800 4200 4800 4200 5700 2100 5700 2100 4800
    32322 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    33          3600 3900 5700 3900 5700 4800 3600 4800 3600 3900
     33         4500 4800 6600 4800 6600 5700 4500 5700 4500 4800
    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          1650 2100 1650 2400
     37         2550 3000 2550 3300
    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          5250 2100 5250 2400
     41         6150 3000 6150 3300
    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          5250 2700 5250 3000
     45         6150 3600 6150 3900
    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          2850 2100 2850 2400
     49         3750 3000 3750 3300
    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          4050 2100 4050 2400
     53         4950 3000 4950 3300
    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          4050 2700 4050 3000
     57         4950 3600 4950 3900
    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          1650 2700 1650 3000
     61         3750 3600 3750 3900
    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          1650 3600 1650 3900
     65         2550 3600 2550 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          2850 3600 2850 3900
     69         2550 4500 2550 4800
    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          4050 3600 4050 3900
     73         3750 4500 3750 4800
    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          5250 3600 5250 3900
     77         4950 4500 4950 4800
    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          3300 4350 3600 4350
     81         6150 4500 6150 4800
    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          2850 2700 2850 3000
    86 4 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001
    87 4 1 0 50 -1 0 12 0.0000 2 135 225 2250 4425 L3\001
    88 4 1 0 50 -1 0 12 0.0000 2 135 225 4650 4425 L3\001
    89 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001
    90 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001
    91 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001
    92 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001
    93 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001
    94 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001
    95 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001
    96 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001
    97 4 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001
    98 4 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001
    99 4 1 0 50 -1 0 12 0.0000 2 165 945 5250 1725 CORE$_3$\001
     85         4200 5250 4500 5250
     864 0 0 50 -1 0 11 0.0000 2 135 360 4725 2625 CPU2\001
     874 0 0 50 -1 0 11 0.0000 2 135 360 2325 2625 CPU0\001
     884 0 0 50 -1 0 11 0.0000 2 135 360 5925 2625 CPU3\001
     894 0 0 50 -1 0 11 0.0000 2 135 360 3525 2625 CPU1\001
     904 0 0 50 -1 0 11 0.0000 2 135 180 2475 3525 L1\001
     914 0 0 50 -1 0 11 0.0000 2 135 180 4875 3525 L1\001
     924 0 0 50 -1 0 11 0.0000 2 135 180 6075 3525 L1\001
     934 0 0 50 -1 0 11 0.0000 2 135 180 2400 4275 L2\001
     944 0 0 50 -1 0 11 0.0000 2 135 180 4875 4275 L2\001
     954 0 0 50 -1 0 11 0.0000 2 135 180 3675 4275 L2\001
     964 0 0 50 -1 0 11 0.0000 2 135 180 6075 4275 L2\001
     974 0 0 50 -1 0 11 0.0000 2 135 180 3675 3525 L1\001
     984 0 0 50 -1 0 11 0.0000 2 135 180 3000 5250 L3\001
     994 0 0 50 -1 0 11 0.0000 2 135 180 5475 5250 L3\001

  • doc/theses/thierry_delisle_PhD/thesis/fig/cache-share.fig

    r25404c7 r06bdba4  
    88-2
    991200 2
    10 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1650 1650 456 456 1650 1650 1200 1575
    11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4050 1650 456 456 4050 1650 3600 1575
    12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5250 1650 456 456 5250 1650 4800 1575
    13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2850 1650 456 456 2850 1650 2400 1575
     101 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 2550 456 456 2550 2550 2100 2475
     111 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3750 2550 456 456 3750 2550 3300 2475
     121 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4950 2550 456 456 4950 2550 4500 2475
     131 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6150 2550 456 456 6150 2550 5700 2475
    14142 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    15          1200 2400 2100 2400 2100 2700 1200 2700 1200 2400
     15         2100 3300 3000 3300 3000 3600 2100 3600 2100 3300
    16162 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    17          1200 3000 2100 3000 2100 3600 1200 3600 1200 3000
     17         2100 3900 3000 3900 3000 4500 2100 4500 2100 3900
    18182 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    19          2400 2400 3300 2400 3300 2700 2400 2700 2400 2400
     19         3300 3300 4200 3300 4200 3600 3300 3600 3300 3300
    20202 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    21          2400 3000 3300 3000 3300 3600 2400 3600 2400 3000
     21         3300 3900 4200 3900 4200 4500 3300 4500 3300 3900
    22222 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    23          3600 2400 4500 2400 4500 2700 3600 2700 3600 2400
     23         4500 3300 5400 3300 5400 3600 4500 3600 4500 3300
    24242 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    25          3600 3000 4500 3000 4500 3600 3600 3600 3600 3000
     25         4500 3900 5400 3900 5400 4500 4500 4500 4500 3900
    26262 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    27          4800 2400 5700 2400 5700 2700 4800 2700 4800 2400
     27         5700 3300 6600 3300 6600 3600 5700 3600 5700 3300
    28282 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    29          4800 3000 5700 3000 5700 3600 4800 3600 4800 3000
     29         5700 3900 6600 3900 6600 4500 5700 4500 5700 3900
     302 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
    30322 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3133        1 1 1.00 60.00 45.00
    3234        1 1 1.00 60.00 45.00
    33          1650 2100 1650 2400
     35         2550 3000 2550 3300
    34362 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3537        1 1 1.00 60.00 45.00
    3638        1 1 1.00 60.00 45.00
    37          2850 2100 2850 2400
     39         3750 3000 3750 3300
    38402 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    3941        1 1 1.00 60.00 45.00
    4042        1 1 1.00 60.00 45.00
    41          4050 2100 4050 2400
     43         4950 3000 4950 3300
    42442 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4345        1 1 1.00 60.00 45.00
    4446        1 1 1.00 60.00 45.00
    45          5250 2100 5250 2400
     47         6150 3000 6150 3300
    46482 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    4749        1 1 1.00 60.00 45.00
    4850        1 1 1.00 60.00 45.00
    49          5250 2700 5250 3000
     51         6150 3600 6150 3900
    50522 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5153        1 1 1.00 60.00 45.00
    5254        1 1 1.00 60.00 45.00
    53          4050 2700 4050 3000
     55         4950 3600 4950 3900
    54562 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5557        1 1 1.00 60.00 45.00
    5658        1 1 1.00 60.00 45.00
    57          2850 2700 2850 3000
     59         3750 3600 3750 3900
    58602 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    5961        1 1 1.00 60.00 45.00
    6062        1 1 1.00 60.00 45.00
    61          1650 2700 1650 3000
     63         2550 3600 2550 3900
    62642 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6365        1 1 1.00 60.00 45.00
    6466        1 1 1.00 60.00 45.00
    65          1650 3600 1650 3900
     67         2550 4500 2550 4800
    66682 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    6769        1 1 1.00 60.00 45.00
    6870        1 1 1.00 60.00 45.00
    69          2850 3600 2850 3900
     71         3750 4500 3750 4800
    70722 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7173        1 1 1.00 60.00 45.00
    7274        1 1 1.00 60.00 45.00
    73          4050 3600 4050 3900
     75         4950 4500 4950 4800
    74762 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7577        1 1 1.00 60.00 45.00
    7678        1 1 1.00 60.00 45.00
    77          5250 3600 5250 3900
    78 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    79          1200 3900 5700 3900 5700 4800 1200 4800 1200 3900
    80 4 1 0 50 -1 0 12 0.0000 2 135 225 3450 4425 L3\001
    81 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 3375 L2\001
    82 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 3375 L2\001
    83 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 3375 L2\001
    84 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 3375 L2\001
    85 4 1 0 50 -1 0 12 0.0000 2 135 225 5250 2625 L1\001
    86 4 1 0 50 -1 0 12 0.0000 2 135 225 4050 2625 L1\001
    87 4 1 0 50 -1 0 12 0.0000 2 135 225 2850 2625 L1\001
    88 4 1 0 50 -1 0 12 0.0000 2 135 225 1650 2625 L1\001
    89 4 1 0 50 -1 0 12 0.0000 2 165 945 1650 1725 CORE$_0$\001
    90 4 1 0 50 -1 0 12 0.0000 2 165 945 2850 1725 CORE$_1$\001
    91 4 1 0 50 -1 0 12 0.0000 2 165 945 4050 1725 CORE$_2$\001
    92 4 1 0 50 -1 0 12 0.0000 2 165 945 5250 1725 CORE$_3$\001
     79         6150 4500 6150 4800
     804 0 0 50 -1 0 11 0.0000 2 135 360 4725 2625 CPU2\001
     814 0 0 50 -1 0 11 0.0000 2 135 360 2325 2625 CPU0\001
     824 0 0 50 -1 0 11 0.0000 2 135 360 5925 2625 CPU3\001
     834 0 0 50 -1 0 11 0.0000 2 135 360 3525 2625 CPU1\001
     844 0 0 50 -1 0 11 0.0000 2 135 180 2475 3525 L1\001
     854 0 0 50 -1 0 11 0.0000 2 135 180 4875 3525 L1\001
     864 0 0 50 -1 0 11 0.0000 2 135 180 6075 3525 L1\001
     874 0 0 50 -1 0 11 0.0000 2 135 180 2400 4275 L2\001
     884 0 0 50 -1 0 11 0.0000 2 135 180 4875 4275 L2\001
     894 0 0 50 -1 0 11 0.0000 2 135 180 3675 4275 L2\001
     904 0 0 50 -1 0 11 0.0000 2 135 180 6075 4275 L2\001
     914 0 0 50 -1 0 11 0.0000 2 135 180 3675 3525 L1\001
     924 0 0 50 -1 0 11 0.0000 2 135 180 4275 5325 L3\001

  • doc/theses/thierry_delisle_PhD/thesis/text/core.tex

    r25404c7 r06bdba4  
    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.
    4 For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and the system has the resources necessary to accomplish the work, \eg, enough workers.
    5 In short, the system is neither overloaded nor underloaded.
    6 
    7 It is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected.
    8 As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to this new load and return to the steady state, \eg, by adding or removing workers.
    9 Therefore, flaws in scheduling the steady state tend to be pervasive in all states.
     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. 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
     5It 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.
    106
    117\section{Design Goals}
    12 As with most of the design decisions behind \CFA, an important goal is to match the expectation of the programmer according to their execution mental-model.
    13 To match expectations, the design must offer the programmer sufficient guarantees so that, as long as they respect the execution mental-model, the system also respects this model.
     8As 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.
    149
    1510For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' :
    … …  
    2217Applied 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.
    2318
    24 In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with each other but simply share the hardware.
    25 This assumption makes it easier to reason about threading because ready \glspl{thrd} can be thought of in isolation and the effect of the scheduler can be virtually ignored.
    26 This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees:
     19In 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:
    2720\begin{enumerate}
    2821        \item A fairness guarantee: a \gls{thrd} that is ready to run is not prevented by another thread.
    … …  
    3023\end{enumerate}
    3124
    32 It is important to note that these guarantees are expected only up to a point.
    33 \Glspl{thrd} that are ready to run should not be prevented to do so, but they still share the limited hardware resources.
    34 Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware resources, even if that share is very small.
    35 
    36 Similar to the performance guarantee, the lack of interference among threads is only relevant up to a point.
    37 Ideally, the cost of running and blocking should be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention.
    38 How much is an acceptable cost is obviously highly variable.
    39 For this document, the performance experimentation attempts to show the cost of scheduling is at worst equivalent to existing algorithms used in popular languages.
    40 This demonstration can be made by comparing applications built in \CFA to applications built with other languages or other models.
    41 Recall programmer expectation is that the impact of the scheduler can be ignored.
    42 Therefore, if the cost of scheduling is competitive to other popular languages, the guarantee is consider achieved.
     25It 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
     27Similarly 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
    4329More precisely the scheduler should be:
    4430\begin{itemize}
    … …  
    4834
    4935\subsection{Fairness Goals}
    50 For this work, fairness is considered to have two strongly related requirements: true starvation freedom and ``fast'' load balancing.
    51 
    52 \paragraph{True starvation freedom} means as long as at least one \proc continues to dequeue \ats, all ready \ats should be able to run eventually, \ie, eventual progress.
    53 In any running system, a \proc can stop dequeuing \ats if it starts running a \at that never blocks.
    54 Without preemption, traditional work-stealing schedulers do not have starvation freedom in this case.
     36For 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.
     39In any running system, \procs can stop dequeing \ats if they start running a \at that will simply never park.
     40Traditional workstealing schedulers do not have starvation freedom in these cases.
    5541Now this requirement begs the question, what about preemption?
    5642Generally speaking preemption happens on the timescale of several milliseconds, which brings us to the next requirement: ``fast'' load balancing.
    5743
    5844\paragraph{Fast load balancing} means that load balancing should happen faster than preemption would normally allow.
    59 For interactive applications that need to run at 60, 90, 120 frames per second, \ats having to wait for several milliseconds to run are effectively starved.
     45For 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.
    6046Therefore load-balancing should be done at a faster pace, one that can detect starvation at the microsecond scale.
    6147With 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.
    6248
    6349\subsection{Fairness vs Scheduler Locality} \label{fairnessvlocal}
    64 An important performance factor in modern architectures is cache locality.
    65 Waiting for data at lower levels or not present in the cache can have a major impact on performance.
    66 Having multiple \glspl{hthrd} writing to the same cache lines also leads to cache lines that must be waited on.
    67 It is therefore preferable to divide data among each \gls{hthrd}\footnote{This partitioning can be an explicit division up front or using data structures where different \glspl{hthrd} are naturally routed to different cache lines.}.
    68 
    69 For a scheduler, having good locality, \ie, having the data local to each \gls{hthrd}, generally conflicts with fairness.
    70 Indeed, good locality often requires avoiding the movement of cache lines, while fairness requires dynamically moving a \gls{thrd}, and as consequence cache lines, to a \gls{hthrd} that is currently available.
    71 Note that this section discusses \emph{internal locality}, \ie, the locality of the data used by the scheduler versus \emph{external locality}, \ie, how the data used by the application is affected by scheduling.
    72 External locality is a much more complicated subject and is discussed in the next section.
    73 
    74 However, I claim that in practice it is possible to strike a balance between fairness and performance because these goals do not necessarily overlap temporally.
    75 Figure~\ref{fig:fair} shows a visual representation of this behaviour.
    76 As mentioned, some unfairness is acceptable; therefore it is desirable to have an algorithm that prioritizes cache locality as long as thread delay does not exceed the execution mental-model.
     50An 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
     52For 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
     54However, 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.
    7755
    7856\begin{figure}
    … …  
    8058        \input{fairness.pstex_t}
    8159        \vspace*{-10pt}
    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.}
     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.}
    8561        \label{fig:fair}
    8662\end{figure}
    8763
    8864\subsection{Performance Challenges}\label{pref:challenge}
    89 While there exists a multitude of potential scheduling algorithms, they generally always have to contend with the same performance challenges.
    90 Since these challenges are recurring themes in the design of a scheduler it is relevant to describe the central ones here before looking at the design.
     65While 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.
    9166
    9267\subsubsection{Scalability}
    … …  
    9469Given a large number of \procs and an even larger number of \ats, scalability measures how fast \procs can enqueue and dequeues \ats.
    9570One 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.
    96 While the ready-queue itself can be sharded to alleviate the main source of contention, auxiliary scheduling features, \eg counting ready \ats, can also be sources of contention.
     71While 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.
    9772
    9873\subsubsection{Migration Cost}
    99 Another important source of scheduling latency is migration.
    100 A \at migrates if it executes on two different \procs consecutively, which is the process discussed in \ref{fairnessvlocal}.
    101 Migrations can have many different causes, but in certain programs, it can be impossible to limit migration.
    102 Chapter~\ref{microbench} has a benchmark where any \at can potentially unblock any other \at, which can lead to \ats migrating frequently.
    103 Hence, it is important to design the internal data structures of the scheduler to limit any latency penalty from migrations.
     74Another important source of latency in scheduling is migration.
     75An \at is said to have migrated if it is executed by two different \proc consecutively, which is the process discussed in \ref{fairnessvlocal}.
     76Migrations can have many different causes, but it certain programs it can be all but impossible to limit migrations.
     77Chapter~\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.
     78Because of this it is important to design the internal data structures of the scheduler to limit the latency penalty from migrations.
    10479
    10580
    10681\section{Inspirations}
    107 In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance.
    108 The problem is a single point of contention when adding/removing \ats.
    109 As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}.
    110 The solution to this problem is to shard the ready-queue: create multiple \emph{subqueues} forming the logical ready-queue and the subqueues are accessed by multiple \glspl{hthrd} without interfering.
    111 
    112 Before going into the design of \CFA's scheduler, it is relevant to discuss two sharding solutions that served as the inspiration scheduler in this thesis.
     82In 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
     84Before 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.
    11385
    11486\subsection{Work-Stealing}
    11587
    116 As mentioned in \ref{existing:workstealing}, a popular sharding approach for the ready-queue is work-stealing.
    117 In this approach, each \gls{proc} has its own local subqueue and \glspl{proc} only access each other's subqueue if they run out of work on their local ready-queue.
    118 The interesting aspect of work stealing happens in the steady-state scheduling case, \ie all \glspl{proc} have work and no load balancing is needed.
    119 In this case, work stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.
     88As mentioned in \ref{existing:workstealing}, a popular pattern shard the ready-queue is work-stealing.
     89In 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.
     90The interesting aspect of workstealing happen in easier scheduling cases, \ie enough work for everyone but no more and no load balancing needed.
     91In these cases, work-stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.
    12092On the other hand, work-stealing schedulers only attempt to do load-balancing when a \gls{proc} runs out of work.
    12193This means that the scheduler never balances unfair loads unless they result in a \gls{proc} running out of work.
    122 Chapter~\ref{microbench} shows that pathological cases work stealing can lead to indefinite starvation.
    123 
    124 Based on these observation, the conclusion is that a \emph{perfect} scheduler should behave similar to work-stealing in the steady-state case, but load balance proactively when the need arises.
    125 
    126 \subsection{Relaxed-FIFO}
    127 A different scheduling approach is to create a ``relaxed-FIFO'' queue, as in \todo{cite Trevor's paper}.
    128 This approach forgoes any ownership between \gls{proc} and subqueue, and simply creates a pool of ready-queues from which \glspl{proc} pick.
    129 Scheduling is performed as follows:
    130 \begin{itemize}
    131 \item
    132 All subqueues are protected by TryLocks.
    133 \item
    134 Timestamps are added to each element of a subqueue.
    135 \item
    136 A \gls{proc} randomly tests ready queues until it has acquired one or two queues.
    137 \item
    138 If two queues are acquired, the older of the two \ats at the front the acquired queues is dequeued.
    139 \item
    140 Otherwise the \ats from the single queue is dequeued.
    141 \end{itemize}
    142 The result is a queue that has both good scalability and sufficient fairness.
    143 The lack of ownership ensures that as long as one \gls{proc} is still able to repeatedly dequeue elements, it is unlikely any element will delay longer than any other element.
    144 This guarantee contrasts with work-stealing, where a \gls{proc} with a long subqueue results in unfairness for its \ats in comparison to a \gls{proc} with a short subqueue.
    145 This unfairness persists until a \gls{proc} runs out of work and steals.
     94Chapter~\ref{microbench} shows that in pathological cases this problem can lead to indefinite starvation.
     95
     96
     97Based 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}
     100An 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.
     102All subqueues are protected by TryLocks and \procs simply pick a different subqueue if they fail to acquire the TryLock.
     103The result is a queue that has both decent scalability and sufficient fairness.
     104The 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.
     105This 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.
    146106
    147107An 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.
    148 However, \glspl{proc} eagerly search for these older elements instead of focusing on specific queues, which negatively affects locality.
    149 
    150 While this scheme has good fairness, its performance suffers.
    151 It requires wide sharding, \eg at least 4 queues per \gls{hthrd}, and finding non-empty queues is difficult when there are few ready \ats.
     108However, another major aspect is that \glspl{proc} will eagerly search for these older elements instead of focusing on specific queues.
     109
     110While the fairness, of this scheme is good, it does suffer in terms of performance.
     111It 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.
    152112
    153113\section{Relaxed-FIFO++}
    154 The inherent fairness and good performance with many \ats, makes the relaxed-FIFO queue a good candidate to form the basis of a new scheduler.
    155 The problem case is workloads where the number of \ats is barely greater than the number of \procs.
    156 In these situations, the wide sharding of the ready queue means most of its subqueues are empty.
    157 Furthermore, the non-empty subqueues are unlikely to hold more than one item.
    158 The consequence is that a random dequeue operation is likely to pick an empty subqueue, resulting in an unbounded number of selections.
    159 This state is generally unstable: each subqueue is likely to frequently toggle between being empty and nonempty.
    160 Indeed, when the number of \ats is \emph{equal} to the number of \procs, every pop operation is expected to empty a subqueue and every push is expected to add to an empty subqueue.
    161 In the worst case, a check of the subqueues sees all are empty or full.
     114Since 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.
     115The most obvious problems is for workloads where the number of \ats is barely greater than the number of \procs.
     116In these situations, the wide sharding means most of the sub-queues from which the relaxed queue is formed will be empty.
     117The 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.
     118This problem can repeat an unbounded number of times.
    162119
    163120As this is the most obvious challenge, it is worth addressing first.
    164 The obvious solution is to supplement each sharded subqueue with data that indicates if the queue is empty/nonempty to simplify finding nonempty queues, \ie ready \glspl{at}.
    165 This sharded data can be organized in different forms, \eg a bitmask or a binary tree that tracks the nonempty subqueues.
    166 Specifically, many modern architectures have powerful bitmask manipulation instructions or searching a binary tree has good Big-O complexity.
    167 However, precisely tracking nonempty subqueues is problematic.
    168 The reason is that the subqueues are initially sharded with a width presumably chosen to avoid contention.
    169 However, tracking which ready queue is nonempty is only useful if the tracking data is dense, \ie denser than the sharded subqueues.
    170 Otherwise, it does not provide useful information because reading this new data structure risks being as costly as simply picking a subqueue at random.
    171 But if the tracking mechanism \emph{is} denser than the shared subqueues, than constant updates invariably create a new source of contention.
    172 Early experiments with this approach showed that randomly picking, even with low success rates, is often faster than bit manipulations or tree walks.
     121The obvious solution is to supplement each subqueue with some sharded data structure that keeps track of which subqueues are empty.
     122This data structure can take many forms, for example simple bitmask or a binary tree that tracks which branch are empty.
     123Following a binary tree on each pick has fairly good Big O complexity and many modern architectures have powerful bitmask manipulation instructions.
     124However, precisely tracking which sub-queues are empty is actually fundamentally problematic.
     125The reason is that each subqueues are already a form of sharding and the sharding width has presumably already chosen to avoid contention.
     126However, 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.
     127But 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.
     128Early 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.
    173129
    174130The exception to this rule is using local tracking.
    175 If each \proc locally keeps track of empty subqueues, than this can be done with a very dense data structure without introducing a new source of contention.
    176 However, the consequence of local tracking is that the information is incomplete.
    177 Each \proc is only aware of the last state it saw about each subqueue so this information quickly becomes stale.
    178 Even on systems with low \gls{hthrd} count, \eg 4 or 8, this approach can quickly lead to the local information being no better than the random pick.
    179 This result is due in part to the cost of maintaining information and its poor quality.
    180 
    181 However, using a very low cost but inaccurate approach for local tracking can actually be beneficial.
    182 If the local tracking is no more costly than a random pick, than \emph{any} improvement to the success rate, however low it is, leads to a performance benefits.
    183 This suggests to the following approach:
     131If 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.
     132The consequence of local tracking however, is that the information is not complete.
     133Each \proc is only aware of the last state it saw each subqueues but does not have any information about freshness.
     134Even 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.
     135This is due in part to the cost of this maintaining this information and its poor quality.
     136
     137However, using a very low cost approach to local tracking may actually be beneficial.
     138If 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.
     139This leads to the following approach:
    184140
    185141\subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
    186 The Relaxed-FIFO approach can be made to handle the case of mostly empty subqueues by tweaking the \glsxtrlong{prng}.
    187 The \glsxtrshort{prng} state can be seen as containing a list of all the future subqueues that will be accessed.
    188 While this concept is not particularly useful on its own, the consequence is that if the \glsxtrshort{prng} algorithm can be run \emph{backwards}, then the state also contains a list of all the subqueues that were accessed.
    189 Luckily, bidirectional \glsxtrshort{prng} algorithms do exist, \eg some Linear Congruential Generators\cit{https://en.wikipedia.org/wiki/Linear\_congruential\_generator} support running the algorithm backwards while offering good quality and performance.
     142The Relaxed-FIFO approach can be made to handle the case of mostly empty sub-queues by tweaking the \glsxtrlong{prng}.
     143The \glsxtrshort{prng} state can be seen as containing a list of all the future sub-queues that will be accessed.
     144While 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.
     145Luckily, 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.
    190146This particular \glsxtrshort{prng} can be used as follows:
    191 \begin{itemize}
    192 \item
    193 Each \proc maintains two \glsxtrshort{prng} states, refereed to as $F$ and $B$.
    194 \item
    195 When a \proc attempts to dequeue a \at, it picks a subqueue by running $B$ backwards.
    196 \item
    197 When a \proc attempts to enqueue a \at, it runs $F$ forward picking a subqueue to enqueue to.
    198 If the enqueue is successful, the state $B$ is overwritten with the content of $F$.
    199 \end{itemize}
    200 The result is that each \proc tends to dequeue \ats that it has itself enqueued.
    201 When most subqueues are empty, this technique increases the odds of finding \ats at very low cost, while also offering an improvement on locality in many cases.
    202 
    203 Tests showed this approach performs better than relaxed-FIFO in many cases.
    204 However, it is still not competitive with work-stealing algorithms.
     147
     148Each \proc maintains two \glsxtrshort{prng} states, which whill be refered to as \texttt{F} and \texttt{B}.
     149
     150When a \proc attempts to dequeue a \at, it picks the subqueues by running the \texttt{B} backwards.
     151When a \proc attempts to enqueue a \at, it runs \texttt{F} forward to pick to subqueue to enqueue to.
     152If the enqueue is successful, the state \texttt{B} is overwritten with the content of \texttt{F}.
     153
     154The result is that each \proc will tend to dequeue \ats that it has itself enqueued.
     155When 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
     157However, while this approach does notably improve performance in many cases, this algorithm is still not competitive with work-stealing algorithms.
    205158The fundamental problem is that the constant randomness limits how much locality the scheduler offers.
    206 This becomes problematic both because the scheduler is likely to get cache misses on internal data-structures and because migrations become frequent.
    207 Therefore, the attempt to modify the relaxed-FIFO algorithm to behave more like work stealing did not pan out.
    208 The alternative is to do it the other way around.
     159This becomes problematic both because the scheduler is likely to get cache misses on internal data-structures and because migration become very frequent.
     160Therefore 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.
    209161
    210162\section{Work Stealing++}
    211 To add stronger fairness guarantees to work stealing a few changes are needed.
     163To add stronger fairness guarantees to workstealing a few changes.
    212164First, the relaxed-FIFO algorithm has fundamentally better fairness because each \proc always monitors all subqueues.
    213 Therefore, the work-stealing algorithm must be prepended with some monitoring.
    214 Before attempting to dequeue from a \proc's subqueue, the \proc must make some effort to ensure other subqueues are not being neglected.
    215 To make this possible, \procs must be able to determine which \at has been on the ready queue the longest.
    216 Second, the relaxed-FIFO approach needs timestamps for each \at to make this possible.
     165Therefore the workstealing algorithm must be prepended with some monitoring.
     166Before attempting to dequeue from a \proc's local queue, the \proc must make some effort to make sure remote queues are not being neglected.
     167To make this possible, \procs must be able to determie which \at has been on the ready-queue the longest.
     168Which is the second aspect that much be added.
     169The relaxed-FIFO approach uses timestamps for each \at and this is also what is done here.
    217170
    218171\begin{figure}
    219172        \centering
    220173        \input{base.pstex_t}
    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.}
     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.}
    224175        \label{fig:base}
    225176\end{figure}
    226 
    227 Figure~\ref{fig:base} shows the algorithm structure.
    228 This structure is similar to classic work-stealing except the subqueues are placed in an array so \procs can access them in constant time.
    229 Sharding width can be adjusted based on contention.
    230 Note, as an optimization, the TS of a \at is stored in the \at in front of it, so the first TS is in the array and the last \at has no TS.
    231 This organization keeps the highly accessed front TSs directly in the array.
    232 When a \proc attempts to dequeue a \at, it first picks a random remote subqueue and compares its timestamp to the timestamps of its local subqueue(s).
    233 The oldest waiting \at is dequeued to provide global fairness.
    234 
    235 However, this na\"ive implemented has performance problems.
     177The algorithm is structure as shown in Figure~\ref{fig:base}.
     178This 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.
     179Sharding width can be adjusted based on need.
     180When 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
     182Implemented as as naively state above, this approach has some obvious performance problems.
    236183First, it is necessary to have some damping effect on helping.
    237 Random effects like cache misses and preemption can add spurious but short bursts of latency negating the attempt to help.
    238 These bursts can cause increased migrations and make this work stealing approach slowdown to the level of relaxed-FIFO.
     184Random effects like cache misses and preemption can add spurious but short bursts of latency for which helping is not helpful, pun intended.
     185The 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.
    239186
    240187\begin{figure}
    … …  
    245192\end{figure}
    246193
    247 A simple solution to this problem is to use an exponential moving average\cit{https://en.wikipedia.org/wiki/Moving\_average\#Exponential\_moving\_average} (MA) instead of a raw timestamps, shown in Figure~\ref{fig:base-ma}.
    248 Note, this is more complex because the \at at the head of a subqueue is still waiting, so its wait time has not ended.
    249 Therefore, the exponential moving average is actually an exponential moving average of how long each dequeued \at has waited.
    250 To compare subqueues, the timestamp at the head must be compared to the current time, yielding the best-case wait-time for the \at at the head of the queue.
     194A 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}.
     195Note 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.
     196Therefore the exponential moving average is actually an exponential moving average of how long each already dequeued \at have waited.
     197To 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.
    251198This new waiting is averaged with the stored average.
    252 To further limit migration, a bias can be added to a local subqueue, where a remote subqueue is helped only if its moving average is more than $X$ times the local subqueue's average.
    253 Tests for this approach indicate the choice of the weight for the moving average or the bias is not important, \ie weights and biases of similar \emph{magnitudes} have similar effects.
    254 
    255 With these additions to work stealing, scheduling can be made as fair as the relaxed-FIFO approach, avoiding the majority of unnecessary migrations.
    256 Unfortunately, the work to achieve fairness has a performance cost, especially when the workload is inherently fair, and hence, there is only short-term or no starvation.
    257 The problem is that the constant polling, \ie reads, of remote subqueues generally entail a cache miss because the TSs are constantly being updated, \ie, writes.
    258 To make things worst, remote subqueues that are very active, \ie \ats are frequently enqueued and dequeued from them, lead to higher chances that polling will incur a cache-miss.
    259 Conversely, the active subqueues do not benefit much from helping since starvation is already a non-issue.
    260 This puts this algorithm in the awkward situation of paying for a cost that is largely unnecessary.
     199To 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.
     200None 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.
     201Weigths and biases of similar \emph{magnitudes} have similar effects.
     202
     203With these additions to workstealing, scheduling can be made as fair as the relaxed-FIFO approach, well avoiding the majority of unnecessary migrations.
     204Unfortunately, the performance of this approach does suffer in the cases with no risks of starvation.
     205The problem is that the constant polling of remote subqueues generally entail a cache miss.
     206To 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.
     207Conversly, the active subqueues do not benefit much from helping since starvation is already a non-issue.
     208This puts this algorithm in an akward situation where it is paying for a cost, but the cost itself suggests the operation was unnecessary.
    261209The good news is that this problem can be mitigated
    262210
    263211\subsection{Redundant Timestamps}
    264 The problem with polling remote subqueues is that correctness is critical.
    265 There must be a consensus among \procs on which subqueues hold which \ats, as the \ats are in constant motion.
    266 Furthermore, since timestamps are use for fairness, it is critical to have consensus on which \at is the oldest.
    267 However, when deciding if a remote subqueue is worth polling, correctness is less of a problem.
    268 Since the only requirement is that a subqueue is eventually polled, some data staleness is acceptable.
    269 This leads to a situation where stale timestamps are only problematic in some cases.
    270 Furthermore, stale timestamps can be desirable since lower freshness requirements mean less cache invalidations.
    271 
    272 Figure~\ref{fig:base-ts2} shows a solution with a second array containing a copy of the timestamps and average.
     212The problem with polling remote queues is due to a tension between the consistency requirement on the subqueue.
     213For the subqueues, correctness is critical. There must be a consensus among \procs on which subqueues hold which \ats.
     214Since the timestamps are use for fairness, it is alco important to have consensus and which \at is the oldest.
     215However, when deciding if a remote subqueue is worth polling, correctness is much less of a problem.
     216Since the only need is that a subqueue will eventually be polled, some data staleness can be acceptable.
     217This leads to a tension where stale timestamps are only problematic in some cases.
     218Furthermore, 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}
     227A solution to this is to create a second array containing a copy of the timestamps and average.
    273228This copy is updated \emph{after} the subqueue's critical sections using relaxed atomics.
    274229\Glspl{proc} now check if polling is needed by comparing the copy of the remote timestamp instead of the actual timestamp.
    275 The result is that since there is no fencing, the writes can be buffered in the hardware and cause fewer cache invalidations.
    276 
    277 \begin{figure}
    278         \centering
    279         \input{base_ts2.pstex_t}
    280         \caption[\CFA design with Redundant Timestamps]{\CFA design with Redundant Timestamps \smallskip\newline An array is added containing a copy of the timestamps.
    281         These timestamps are written to with relaxed atomics, so there is no order among concurrent memory accesses, leading to fewer cache invalidations.}
    282         \label{fig:base-ts2}
    283 \end{figure}
    284 
    285 The correctness argument is somewhat subtle.
     230The result is that since there is no fencing, the writes can be buffered and cause fewer cache invalidations.
     231
     232The correctness argument here is somewhat subtle.
    286233The data used for deciding whether or not to poll a queue can be stale as long as it does not cause starvation.
    287 Therefore, it is acceptable if stale data makes queues appear older than they really are but appearing fresher can be a problem.
    288 For the timestamps, this means missing writes to the timestamp is acceptable since they make the head \at look older.
    289 For the moving average, as long as the operations are just atomic reads/writes, the average is guaranteed to yield a value that is between the oldest and newest values written.
    290 Therefore, this unprotected read of the timestamp and average satisfy the limited correctness that is required.
    291 
    292 With redundant timestamps, this scheduling algorithm achieves both the fairness and performance requirements on most machines.
     234Therefore, it is acceptable if stale data make queues appear older than they really are but not fresher.
     235For the timestamps, this means that missing writes to the timestamp is acceptable since they will make the head \at look older.
     236For 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.
     237Therefore this unprotected read of the timestamp and average satisfy the limited correctness that is required.
     238
     239\begin{figure}
     240        \centering
     241        \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.}
     243        \label{fig:cache-share}
     244\end{figure}
     245
     246\begin{figure}
     247        \centering
     248        \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.}
     250        \label{fig:cache-noshare}
     251\end{figure}
     252
     253With redundant tiemstamps this scheduling algorithm achieves both the fairness and performance requirements, on some machines.
    293254The problem is that the cost of polling and helping is not necessarily consistent across each \gls{hthrd}.
    294 For example, on machines with a CPU containing multiple hyperthreads and cores and multiple CPU sockets, cache misses can be satisfied from the caches on same (local) CPU, or by a CPU on a different (remote) socket.
    295 Cache misses satisfied by a remote CPU have significantly higher latency than from the local CPU.
    296 However, these delays are not specific to systems with multiple CPUs.
    297 Depending on the cache structure, cache misses can have different latency on the same CPU, \eg the AMD EPYC 7662 CPUs used in Chapter~\ref{microbench}.
    298 
    299 \begin{figure}
    300         \centering
    301         \input{cache-share.pstex_t}
    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.}
    303         \label{fig:cache-share}
    304 
    305         \vspace{25pt}
    306 
    307         \input{cache-noshare.pstex_t}
    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.}
    309         \label{fig:cache-noshare}
    310 \end{figure}
    311 
    312 Figures~\ref{fig:cache-share} and~\ref{fig:cache-noshare} show two different cache topologies that highlight this difference.
    313 In Figure~\ref{fig:cache-share}, all cache misses are either private to a CPU or shared with another CPU.
    314 This means latency due to cache misses is fairly consistent.
    315 In contrast, in Figure~\ref{fig:cache-noshare} misses in the L2 cache can be satisfied by either instance of L3 cache.
    316 However, the memory-access latency to the remote L3 is higher than the memory-access latency to the local L3.
    317 The impact of these different designs on this algorithm is that scheduling only scales well on architectures with a wide L3 cache, similar to Figure~\ref{fig:cache-share}, and less well on architectures with many narrower L3 cache instances, similar to Figure~\ref{fig:cache-noshare}.
    318 Hence, as the number of L3 instances grow, so too does the chance that the random helping causes significant cache latency.
    319 The solution is for the scheduler be aware of the cache topology.
     255For 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.
     256Cache misses that are satisfied by a remote CPU will have higher latency than if it is satisfied by the local CPU.
     257However, this is not specific to systems with multiple CPUs.
     258Depending on the cache structure, cache-misses can have different latency for the same CPU.
     259The AMD EPYC 7662 CPUs that is described in Chapter~\ref{microbench} is an example of that.
     260Figure~\ref{fig:cache-share} and Figure~\ref{fig:cache-noshare} show two different cache topologies with highlight this difference.
     261In 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.
     262By comparison, in Figure~\ref{fig:cache-noshare} misses in the L2 cache can be satisfied by a hit in either instance of the L3.
     263However, the memory access latency to the remote L3 instance will be notably higher than the memory access latency to the local L3.
     264The 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.
     265This is simply because as the number of L3 instances grow, so two does the chances that the random helping will cause significant latency.
     266The solution is to have the scheduler be aware of the cache topology.
    320267
    321268\subsection{Per CPU Sharding}
    322 Building a scheduler that is cache aware poses two main challenges: discovering the cache topology and matching \procs to this cache structure.
    323 Unfortunately, there is no portable way to discover cache topology, and it is outside the scope of this thesis to solve this problem.
    324 This work uses the cache topology information from Linux's \texttt{/sys/devices/system/cpu} directory.
    325 This leaves the challenge of matching \procs to cache structure, or more precisely identifying which subqueues of the ready queue are local to which subcomponents of the cache structure.
    326 Once a matching is generated, the helping algorithm is changed to add bias so that \procs more often help subqueues local to the same cache substructure.\footnote{
    327 Note that like other biases mentioned in this section, the actual bias value does not appear to need precise tuning.}
    328 
    329 The simplest approach for mapping subqueues to cache structure is to statically tie subqueues to CPUs.
    330 Instead of having each subqueue local to a specific \proc, the system is initialized with subqueues for each hardware hyperthread/core up front.
    331 Then \procs dequeue and enqueue by first asking which CPU id they are executing on, in order to identify which subqueues are the local ones.
     269Building a scheduler that is aware of cache topology poses two main challenges: discovering cache topology and matching \procs to cache instance.
     270Sadly, there is no standard portable way to discover cache topology in C.
     271Therefore, while this is a significant portability challenge, it is outside the scope of this thesis to design a cross-platform cache discovery mechanisms.
     272The rest of this work assumes discovering the cache topology based on Linux's \texttt{/sys/devices/system/cpu} directory.
     273This 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.
     274Once 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
     277The obvious approach to mapping cache instances to subqueues is to statically tie subqueues to CPUs.
     278Instead of having each subqueue local to a specific \proc, the system is initialized with subqueues for each \glspl{hthrd} up front.
     279Then \procs dequeue and enqueue by first asking which CPU id they are local to, in order to identify which subqueues are the local ones.
    332280\Glspl{proc} can get the CPU id from \texttt{sched\_getcpu} or \texttt{librseq}.
    333281
    334 This approach solves the performance problems on systems with topologies with narrow L3 caches, similar to Figure \ref{fig:cache-noshare}.
    335 However, it can still cause some subtle fairness problems in systems with few \procs and many \glspl{hthrd}.
    336 In this case, the large number of subqueues and the bias against subqueues tied to different cache substructures make it unlikely that every subqueue is picked.
    337 To make things worst, the small number of \procs mean that few helping attempts are made.
    338 This combination of low selection and few helping attempts allow a \at to become stranded on a subqueue for a long time until it gets randomly helped.
     282This approach solves the performance problems on systems with topologies similar to Figure~\ref{fig:cache-noshare}.
     283However, it actually causes some subtle fairness problems in some systems, specifically systems with few \procs and many \glspl{hthrd}.
     284In 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.
     285To make things worst, the small number of \procs mean that few helping attempts will be made.
     286This 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.
    339287On 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.
    340288Therefore, a more dynamic matching of subqueues to cache instance is needed.
    341289
    342290\subsection{Topological Work Stealing}
    343 Therefore, the approach used in the \CFA scheduler is to have per-\proc subqueues, but have an explicit data-structure track which cache substructure each subqueue is tied to.
    344 This tracking requires some finesse because reading this data structure must lead to fewer cache misses than not having the data structure in the first place.
     291The 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.
     292This 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.
    345293A 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}.
    346 Therefore the algorithm can be built as follows: before enqueueing or dequeuing a \at, each \proc queries the CPU id and the corresponding cache instance.
     294Therefore the algorithm can be built as follows: Before enqueuing or dequeing a \at, each \proc queries the CPU id and the corresponding cache instance.
    347295Since subqueues are tied to \procs, each \proc can then update the cache instance mapped to the local subqueue(s).
    348296To avoid unnecessary cache line invalidation, the map is only written to if the mapping changes.
    349297
    350 This scheduler is used in the remainder of the thesis for managing CPU execution, but additional scheduling is needed to handle long-term blocking and unblocking, such as I/O.
    351 

  • doc/theses/thierry_delisle_PhD/thesis/thesis.tex

    r25404c7 r06bdba4  
    8383\usepackage{graphicx} % For including graphics
    8484\usepackage{subcaption}
    85 \usepackage{comment} % Removes large sections of the document.
    8685
    8786% Hyperlinks make it very easy to navigate an electronic document.

  • src/Common/Eval.cc

    r25404c7 r06bdba4  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jul  1 08:41:03 2022
    13 // Update Count     : 117
     12// Last Modified On : Wed Jul 24 15:09:06 2019
     13// Update Count     : 64
    1414//
    1515
    … …  
    1717
    1818#include "Common/PassVisitor.h"
    19 #include "CodeGen/OperatorTable.h"                                              // access: OperatorInfo
    2019#include "AST/Pass.hpp"
    2120#include "InitTweak/InitTweak.h"
    … …  
    2524// Old AST
    2625struct EvalOld : public WithShortCircuiting {
    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)
     26        long long int value = 0;
     27        bool valid = true;
    3228
    3329        void previsit( const BaseSyntaxNode * ) { visit_children = false; }
    … …  
    9389// New AST
    9490struct EvalNew : public ast::WithShortCircuiting {
    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)
     91        long long int value = 0;
     92        bool valid = true;
    10093
    10194        void previsit( const ast::Node * ) { visit_children = false; }
    102         void postvisit( const ast::Node * ) { cfavalid = valid = false; }
     95        void postvisit( const ast::Node * ) { valid = false; }
    10396
    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
     97        void postvisit( const ast::ConstantExpr * expr ) {
    10998                value = expr->intValue();
    11099        }
    111100
    112         void postvisit( const ast::SizeofExpr * ) {
    113                 // do not change valid or value => let C figure it out
    114                 cfavalid = false;
     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" ) );
    115105        }
    116106
    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.
     107        void postvisit( const ast::CastExpr * expr ) {
    161108                auto arg = eval(expr->arg);
    162109                valid = arg.second;
    163110                value = arg.first;
    164                 cfavalid = false;
     111                // TODO: perform type conversion on value if valid
    165112        }
    166113
    167         void postvisit( const ast::VariableExpr * expr ) {
     114        void postvisit( const ast::VariableExpr * expr ) { // No hit
    168115                if ( const ast::EnumInstType * inst = dynamic_cast<const ast::EnumInstType *>(expr->result.get()) ) {
    169116                        if ( const ast::EnumDecl * decl = inst->base ) {
    … …  
    181128                const std::string & fname = function->name;
    182129                assertf( expr->args.size() == 1 || expr->args.size() == 2, "Intrinsic function with %zd arguments: %s", expr->args.size(), fname.c_str() );
    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;
     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 ) {
     135                        arg2 = eval(expr->args.back());
     136                        valid = valid && arg2.second;
    189137                        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;
    208                         arg2 = eval(expr->args.back());
    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
     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                }
    248152                // TODO: implement other intrinsic functions
    249153        }
    250154};
    251155
    252 std::pair<long long int, bool> eval( const Expression * expr ) {
     156std::pair<long long int, bool> eval( const Expression * expr) {
    253157        PassVisitor<EvalOld> ev;
    254         if ( expr ) {
    255                 expr->accept( ev );
    256                 return std::make_pair( ev.pass.value, ev.pass.valid );
     158        if (expr) {
     159                expr->accept(ev);
     160                return std::make_pair(ev.pass.value, ev.pass.valid);
    257161        } else {
    258                 return std::make_pair( 0, false );
     162                return std::make_pair(0, false);
    259163        }
    260164}
    261165
    262 std::pair<long long int, bool> eval( const ast::Expr * expr ) {
     166std::pair<long long int, bool> eval(const ast::Expr * expr) {
    263167        ast::Pass<EvalNew> ev;
    264         if ( expr ) {
    265                 expr->accept( ev );
    266                 return std::make_pair( ev.core.value, ev.core.valid );
     168        if (expr) {
     169                expr->accept(ev);
     170                return std::make_pair(ev.core.value, ev.core.valid);
    267171        } else {
    268                 return std::make_pair( 0, false );
     172                return std::make_pair(0, false);
    269173        }
    270174}

  • src/Parser/parser.yy

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

  • src/ResolvExpr/CurrentObject.cc

    r25404c7 r06bdba4  
    99// Author           : Rob Schluntz
    1010// Created On       : Tue Jun 13 15:28:32 2017
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jul  1 09:16:01 2022
    13 // Update Count     : 15
     11// Last Modified By : Rob Schluntz
     12// Last Modified On : Tue Jun 13 15:28:44 2017
     13// Update Count     : 2
    1414//
    1515
    … …  
    158158
    159159        private:
    160                 void setSize( Expression * expr ) {
    161                         auto res = eval( expr );
     160                void setSize( Expression * expr ) { // replace this logic with an eval call
     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                         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                         // }
     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                        }
    196192                }
    197193
    … …  
    333329                                        assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
    334330                                } else {
    335                                         assertf( false, "3 bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() );
     331                                        assertf( false, "bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() );
    336332                                } // if
    337333                        } // if
    … …  
    641637
    642638                void setSize( const Expr * expr ) {
    643                         auto res = eval( expr );
     639                        auto res = eval(expr);
    644640                        if ( ! res.second ) {
    645                                 SemanticError( location, toString( "Array designator must be a constant expression: ", expr ) );
     641                                SemanticError( location,
     642                                        toString("Array designator must be a constant expression: ", expr ) );
    646643                        }
    647644                        size = res.first;
    … …  
    649646
    650647        public:
    651                 ArrayIterator( const CodeLocation & loc, const ArrayType * at ) : location( loc ), array( at ), base( at->base ) {
     648                ArrayIterator( const CodeLocation & loc, const ArrayType * at )
     649                : location( loc ), array( at ), base( at->base ) {
    652650                        PRINT( std::cerr << "Creating array iterator: " << at << std::endl; )
    653651                        memberIter.reset( createMemberIterator( loc, base ) );
    … …  
    662660                        // enumeration constants, character constants, sizeof expressions, alignof expressions,
    663661                        // cast expressions
    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                         // }
     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                        }
    682680                }
    683681
    … …  
    725723                                std::deque< InitAlternative > ret = memberIter->first();
    726724                                for ( InitAlternative & alt : ret ) {
    727                                         alt.designation.get_and_mutate()->designators.emplace_front( ConstantExpr::from_ulong( location, index ) );
     725                                        alt.designation.get_and_mutate()->designators.emplace_front(
     726                                                ConstantExpr::from_ulong( location, index ) );
    728727                                }
    729728                                return ret;
    … …  
    789788                                        return;
    790789                                }
    791                                 assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
     790                                assertf( false,
     791                                        "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
    792792                        } else {
    793                                 assertf( false, "1 bad designator given to %s: %s", kind.c_str(), toString( *begin ).c_str() );
     793                                assertf( false,
     794                                        "bad designator given to %s: %s", kind.c_str(), toString( *begin ).c_str() );
    794795                        }
    795796                }

  • src/SynTree/AggregateDecl.cc

    r25404c7 r06bdba4  
    1010// Created On       : Sun May 17 23:56:39 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jul  1 09:12:33 2022
    13 // Update Count     : 32
     12// Last Modified On : Mon Dec 16 15:07:20 2019
     13// Update Count     : 31
    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( "Enumerator value for '", field, "' is not an integer constant" ) );
     127                                if ( ! result.second ) SemanticError( init->location, toString( "Non-constexpr in initialization of enumerator: ", field ) );
    128128                                currentValue = result.first;
    129129                        }

  • tests/.expect/attributes.nast.arm64.txt

    r25404c7 r06bdba4  
    13381338        }
    13391339
    1340         return (*_X4_dstM12__anonymous4_2);
     1340        {
     1341            ((void)(_X4_retM12__anonymous4_2=(*_X4_dstM12__anonymous4_2)) /* ?{} */);
     1342        }
     1343
     1344        return _X4_retM12__anonymous4_2;
    13411345    }
    13421346    {

  • tests/enum.cfa

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