Ignore:
Timestamp:
Feb 10, 2020, 11:58:55 AM (20 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
686cb63, 7102540
Parents:
92a9768 (diff), 3b56166 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/code/relaxed_list.cpp

    r92a9768 r3966d9a  
    99#include <vector>
    1010
     11#include <getopt.h>
    1112#include <unistd.h>
    1213#include <sys/sysinfo.h>
     
    2122
    2223        int value;
    23         Node(int value): value(value) {
    24                 creates++;
    25         }
    26 
    27         ~Node() {
    28                 destroys++;
    29         }
     24        int id;
     25
     26        Node() { creates++; }
     27        Node(int value): value(value) { creates++; }
     28        ~Node() { destroys++; }
    3029};
    3130
     
    3332std::atomic_size_t Node::destroys = { 0 };
    3433
    35 static const constexpr int nodes_per_threads = 128;
    36 struct NodeArray {
    37         __attribute__((aligned(64))) Node * array[nodes_per_threads];
    38         __attribute__((aligned(64))) char pad;
    39 };
    40 
    4134bool enable_stats = false;
     35
     36template<>
     37thread_local relaxed_list<Node>::TLS relaxed_list<Node>::tls = {};
     38
     39template<>
     40relaxed_list<Node> * relaxed_list<Node>::head = nullptr;
     41
     42#ifndef NO_STATS
     43template<>
     44relaxed_list<Node>::GlobalStats relaxed_list<Node>::global_stats = {};
     45#endif
     46
     47// ================================================================================================
     48//                        UTILS
     49// ================================================================================================
    4250
    4351struct local_stat_t {
     
    4755        size_t crc_in  = 0;
    4856        size_t crc_out = 0;
     57        size_t valmax = 0;
     58        size_t valmin = 100000000ul;
    4959};
    5060
    51 __attribute__((noinline)) void run_body(
    52         std::atomic<bool>& done,
    53         Random & rand,
    54         Node * (&my_nodes)[128],
    55         local_stat_t & local,
    56         relaxed_list<Node> & list
    57 ) {
    58         while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) {
    59                 int idx = rand.next() % nodes_per_threads;
    60                 if (auto node = my_nodes[idx]) {
    61                         local.crc_in += node->value;
    62                         list.push(node);
    63                         my_nodes[idx] = nullptr;
    64                         local.in++;
    65                 }
    66                 else if(auto node = list.pop()) {
    67                         local.crc_out += node->value;
    68                         my_nodes[idx] = node;
    69                         local.out++;
    70                 }
    71                 else {
    72                         local.empty++;
    73                 }
    74         }
    75 }
    76 
    77 void run(unsigned nthread, unsigned nqueues, unsigned fill, double duration) {
    78         // List being tested
    79         relaxed_list<Node> list = { nthread * nqueues };
    80 
    81         // Barrier for synchronization
    82         barrier_t barrier(nthread + 1);
    83 
    84         // Data to check everything is OK
    85         struct {
    86                 std::atomic_size_t in  = { 0 };
    87                 std::atomic_size_t out = { 0 };
    88                 std::atomic_size_t empty = { 0 };
    89                 std::atomic_size_t crc_in  = { 0 };
    90                 std::atomic_size_t crc_out = { 0 };
    91                 struct {
    92                         struct {
    93                                 std::atomic_size_t attempt = { 0 };
    94                                 std::atomic_size_t success = { 0 };
    95                         } push;
    96                         struct {
    97                                 std::atomic_size_t attempt = { 0 };
    98                                 std::atomic_size_t success = { 0 };
    99                         } pop;
    100                 } pick;
    101         } global;
    102 
    103         // Flag to signal termination
    104         std::atomic_bool done  = { false };
    105 
    106         // Prep nodes
    107         std::cout << "Initializing ";
    108         size_t nnodes  = 0;
    109         size_t npushed = 0;
    110         NodeArray all_nodes[nthread];
    111         for(auto & nodes : all_nodes) {
    112                 Random rand(rdtscl());
    113                 for(auto & node : nodes.array) {
    114                         auto r = rand.next() % 100;
    115                         if(r < fill) {
    116                                 node = new Node(rand.next() % 100);
    117                                 nnodes++;
    118                         } else {
    119                                 node = nullptr;
    120                         }
    121                 }
    122 
    123                 for(int i = 0; i < 10; i++) {
    124                         int idx = rand.next() % nodes_per_threads;
    125                         if (auto node = nodes.array[idx]) {
    126                                 global.crc_in += node->value;
    127                                 list.push(node);
    128                                 npushed++;
    129                                 nodes.array[idx] = nullptr;
    130                         }
    131                 }
    132         }
    133 
    134         std::cout << nnodes << " nodes " << fill << "% (" << npushed << " pushed)" << std::endl;
    135 
    136         enable_stats = true;
    137 
    138         std::thread * threads[nthread];
    139         unsigned i = 1;
    140         for(auto & t : threads) {
    141                 auto & my_nodes = all_nodes[i - 1].array;
    142                 t = new std::thread([&done, &list, &barrier, &global, &my_nodes](unsigned tid) {
    143                         Random rand(tid + rdtscl());
    144 
    145                         local_stat_t local;
    146 
    147                         // affinity(tid);
    148 
    149                         barrier.wait(tid);
    150 
    151                         // EXPERIMENT START
    152 
    153                         run_body(done, rand, my_nodes, local, list);
    154 
    155                         // EXPERIMENT END
    156 
    157                         barrier.wait(tid);
    158 
    159                         global.in    += local.in;
    160                         global.out   += local.out;
    161                         global.empty += local.empty;
    162 
    163                         for(auto node : my_nodes) {
    164                                 delete node;
    165                         }
    166 
    167                         global.crc_in  += local.crc_in;
    168                         global.crc_out += local.crc_out;
    169 
    170                         global.pick.push.attempt += relaxed_list<Node>::tls.pick.push.attempt;
    171                         global.pick.push.success += relaxed_list<Node>::tls.pick.push.success;
    172                         global.pick.pop .attempt += relaxed_list<Node>::tls.pick.pop.attempt;
    173                         global.pick.pop .success += relaxed_list<Node>::tls.pick.pop.success;
    174                 }, i++);
    175         }
    176 
     61struct global_stat_t {
     62        std::atomic_size_t in  = { 0 };
     63        std::atomic_size_t out = { 0 };
     64        std::atomic_size_t empty = { 0 };
     65        std::atomic_size_t crc_in  = { 0 };
     66        std::atomic_size_t crc_out = { 0 };
     67        std::atomic_size_t valmax = { 0 };
     68        std::atomic_size_t valmin = { 100000000ul };
     69};
     70
     71void atomic_max(std::atomic_size_t & target, size_t value) {
     72        for(;;) {
     73                size_t expect = target.load(std::memory_order_relaxed);
     74                if(value <= expect) return;
     75                bool success = target.compare_exchange_strong(expect, value);
     76                if(success) return;
     77        }
     78}
     79
     80void atomic_min(std::atomic_size_t & target, size_t value) {
     81        for(;;) {
     82                size_t expect = target.load(std::memory_order_relaxed);
     83                if(value >= expect) return;
     84                bool success = target.compare_exchange_strong(expect, value);
     85                if(success) return;
     86        }
     87}
     88
     89void tally_stats(global_stat_t & global, local_stat_t & local) {
     90
     91        global.in    += local.in;
     92        global.out   += local.out;
     93        global.empty += local.empty;
     94
     95        global.crc_in  += local.crc_in;
     96        global.crc_out += local.crc_out;
     97
     98        atomic_max(global.valmax, local.valmax);
     99        atomic_min(global.valmin, local.valmin);
     100
     101        relaxed_list<Node>::stats_tls_tally();
     102}
     103
     104void waitfor(double & duration, barrier_t & barrier, std::atomic_bool & done) {
    177105        std::cout << "Starting" << std::endl;
    178106        auto before = Clock::now();
     
    196124        duration = durr.count();
    197125        std::cout << "\rClosing down" << std::endl;
    198 
    199         for(auto t : threads) {
    200                 t->join();
    201                 delete t;
    202         }
    203 
    204         enable_stats = false;
    205 
    206         while(auto node = list.pop()) {
    207                 global.crc_out += node->value;
    208                 delete node;
    209         }
    210 
     126}
     127
     128void waitfor(double & duration, barrier_t & barrier, const std::atomic_size_t & count) {
     129        std::cout << "Starting" << std::endl;
     130        auto before = Clock::now();
     131        barrier.wait(0);
     132
     133        while(true) {
     134                usleep(100000);
     135                size_t c = count.load();
     136                if( c == 0 ) {
     137                        break;
     138                }
     139                std::cout << "\r" << c;
     140                std::cout.flush();
     141        }
     142
     143        barrier.wait(0);
     144        auto after = Clock::now();
     145        duration_t durr = after - before;
     146        duration = durr.count();
     147        std::cout << "\rClosing down" << std::endl;
     148}
     149
     150void print_stats(double duration, unsigned nthread, global_stat_t & global) {
    211151        assert(Node::creates == Node::destroys);
    212152        assert(global.crc_in == global.crc_out);
     
    224164        std::cout << "Ops/sec       : " << ops_sec << "\n";
    225165        std::cout << "Total ops     : " << ops << "(" << global.in << "i, " << global.out << "o, " << global.empty << "e)\n";
     166        if(global.valmax != 0) {
     167                std::cout << "Max runs      : " << global.valmax << "\n";
     168                std::cout << "Min runs      : " << global.valmin << "\n";
     169        }
    226170        #ifndef NO_STATS
    227                 double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
    228                 double pop_sur  = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
    229                 std::cout << "Push Pick %   : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
    230                 std::cout << "Pop  Pick %   : " << pop_sur  << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
     171                relaxed_list<Node>::stats_print(std::cout);
    231172        #endif
    232173}
    233174
    234 void usage(char * argv[]) {
    235         std::cerr << argv[0] << ": [DURATION (FLOAT:SEC)] [NTHREADS] [NQUEUES] [FILL]" << std::endl;;
    236         std::exit(1);
     175void save_fairness(const int data[], int factor, unsigned nthreads, size_t columns, size_t rows, const std::string & output);
     176
     177// ================================================================================================
     178//                        EXPERIMENTS
     179// ================================================================================================
     180
     181// ================================================================================================
     182__attribute__((noinline)) void runChurn_body(
     183        std::atomic<bool>& done,
     184        Random & rand,
     185        Node * my_nodes[],
     186        unsigned nslots,
     187        local_stat_t & local,
     188        relaxed_list<Node> & list
     189) {
     190        while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) {
     191                int idx = rand.next() % nslots;
     192                if (auto node = my_nodes[idx]) {
     193                        local.crc_in += node->value;
     194                        list.push(node);
     195                        my_nodes[idx] = nullptr;
     196                        local.in++;
     197                }
     198                else if(auto node = list.pop()) {
     199                        local.crc_out += node->value;
     200                        my_nodes[idx] = node;
     201                        local.out++;
     202                }
     203                else {
     204                        local.empty++;
     205                }
     206        }
     207}
     208
     209void runChurn(unsigned nthread, unsigned nqueues, double duration, unsigned nnodes, const unsigned nslots) {
     210        std::cout << "Churn Benchmark" << std::endl;
     211        assert(nnodes <= nslots);
     212        // List being tested
     213
     214        // Barrier for synchronization
     215        barrier_t barrier(nthread + 1);
     216
     217        // Data to check everything is OK
     218        global_stat_t global;
     219
     220        // Flag to signal termination
     221        std::atomic_bool done  = { false };
     222
     223        // Prep nodes
     224        std::cout << "Initializing ";
     225        size_t npushed = 0;
     226        relaxed_list<Node> list = { nthread * nqueues };
     227        {
     228                Node** all_nodes[nthread];
     229                for(auto & nodes : all_nodes) {
     230                        nodes = new __attribute__((aligned(64))) Node*[nslots + 8];
     231                        Random rand(rdtscl());
     232                        for(unsigned i = 0; i < nnodes; i++) {
     233                                nodes[i] = new Node(rand.next() % 100);
     234                        }
     235
     236                        for(unsigned i = nnodes; i < nslots; i++) {
     237                                nodes[i] = nullptr;
     238                        }
     239
     240                        for(int i = 0; i < 10 && i < (int)nslots; i++) {
     241                                int idx = rand.next() % nslots;
     242                                if (auto node = nodes[idx]) {
     243                                        global.crc_in += node->value;
     244                                        list.push(node);
     245                                        npushed++;
     246                                        nodes[idx] = nullptr;
     247                                }
     248                        }
     249                }
     250
     251                std::cout << nnodes << " nodes (" << nslots << " slots)" << std::endl;
     252
     253                enable_stats = true;
     254
     255                std::thread * threads[nthread];
     256                unsigned i = 1;
     257                for(auto & t : threads) {
     258                        auto & my_nodes = all_nodes[i - 1];
     259                        t = new std::thread([&done, &list, &barrier, &global, &my_nodes, nslots](unsigned tid) {
     260                                Random rand(tid + rdtscl());
     261
     262                                local_stat_t local;
     263
     264                                // affinity(tid);
     265
     266                                barrier.wait(tid);
     267
     268                                // EXPERIMENT START
     269
     270                                runChurn_body(done, rand, my_nodes, nslots, local, list);
     271
     272                                // EXPERIMENT END
     273
     274                                barrier.wait(tid);
     275
     276                                tally_stats(global, local);
     277
     278                                for(unsigned i = 0; i < nslots; i++) {
     279                                        delete my_nodes[i];
     280                                }
     281                        }, i++);
     282                }
     283
     284                waitfor(duration, barrier, done);
     285
     286                for(auto t : threads) {
     287                        t->join();
     288                        delete t;
     289                }
     290
     291                enable_stats = false;
     292
     293                while(auto node = list.pop()) {
     294                        global.crc_out += node->value;
     295                        delete node;
     296                }
     297
     298                for(auto nodes : all_nodes) {
     299                        delete[] nodes;
     300                }
     301        }
     302
     303        print_stats(duration, nthread, global);
     304}
     305
     306// ================================================================================================
     307__attribute__((noinline)) void runPingPong_body(
     308        std::atomic<bool>& done,
     309        Node initial_nodes[],
     310        unsigned nnodes,
     311        local_stat_t & local,
     312        relaxed_list<Node> & list
     313) {
     314        Node * nodes[nnodes];
     315        {
     316                unsigned i = 0;
     317                for(auto & n : nodes) {
     318                        n = &initial_nodes[i++];
     319                }
     320        }
     321
     322        while(__builtin_expect(!done.load(std::memory_order_relaxed), true)) {
     323
     324                for(Node * & node : nodes) {
     325                        local.crc_in += node->value;
     326                        list.push(node);
     327                        local.in++;
     328                }
     329
     330                // -----
     331
     332                for(Node * & node : nodes) {
     333                        node = list.pop();
     334                        assert(node);
     335                        local.crc_out += node->value;
     336                        local.out++;
     337                }
     338        }
     339}
     340
     341void runPingPong(unsigned nthread, unsigned nqueues, double duration, unsigned nnodes) {
     342        std::cout << "PingPong Benchmark" << std::endl;
     343
     344
     345        // Barrier for synchronization
     346        barrier_t barrier(nthread + 1);
     347
     348        // Data to check everything is OK
     349        global_stat_t global;
     350
     351        // Flag to signal termination
     352        std::atomic_bool done  = { false };
     353
     354        std::cout << "Initializing ";
     355        // List being tested
     356        relaxed_list<Node> list = { nthread * nqueues };
     357        {
     358                enable_stats = true;
     359
     360                std::thread * threads[nthread];
     361                unsigned i = 1;
     362                for(auto & t : threads) {
     363                        t = new std::thread([&done, &list, &barrier, &global, nnodes](unsigned tid) {
     364                                Random rand(tid + rdtscl());
     365
     366                                Node nodes[nnodes];
     367                                for(auto & n : nodes) {
     368                                        n.value = (int)rand.next() % 100;
     369                                }
     370
     371                                local_stat_t local;
     372
     373                                // affinity(tid);
     374
     375                                barrier.wait(tid);
     376
     377                                // EXPERIMENT START
     378
     379                                runPingPong_body(done, nodes, nnodes, local, list);
     380
     381                                // EXPERIMENT END
     382
     383                                barrier.wait(tid);
     384
     385                                tally_stats(global, local);
     386                        }, i++);
     387                }
     388
     389                waitfor(duration, barrier, done);
     390
     391                for(auto t : threads) {
     392                        t->join();
     393                        delete t;
     394                }
     395
     396                enable_stats = false;
     397        }
     398
     399        print_stats(duration, nthread, global);
     400}
     401
     402// ================================================================================================
     403__attribute__((noinline)) void runFairness_body(
     404        unsigned tid,
     405        size_t width,
     406        size_t length,
     407        int output[],
     408        std::atomic_size_t & count,
     409        Node initial_nodes[],
     410        unsigned nnodes,
     411        local_stat_t & local,
     412        relaxed_list<Node> & list
     413) {
     414        Node * nodes[nnodes];
     415        {
     416                unsigned i = 0;
     417                for(auto & n : nodes) {
     418                        n = &initial_nodes[i++];
     419                }
     420        }
     421
     422        while(__builtin_expect(0 != count.load(std::memory_order_relaxed), true)) {
     423
     424                for(Node * & node : nodes) {
     425                        local.crc_in += node->id;
     426                        list.push(node);
     427                        local.in++;
     428                }
     429
     430                // -----
     431
     432                for(Node * & node : nodes) {
     433                        node = list.pop();
     434                        assert(node);
     435
     436                        if (unsigned(node->value) < length) {
     437                                size_t idx = (node->value * width) + node->id;
     438                                assert(idx < (width * length));
     439                                output[idx] = tid;
     440                        }
     441
     442                        node->value++;
     443                        if(unsigned(node->value) == length) count--;
     444
     445                        local.crc_out += node->id;
     446                        local.out++;
     447                }
     448        }
     449}
     450
     451void runFairness(unsigned nthread, unsigned nqueues, double duration, unsigned nnodes, const std::string & output) {
     452        std::cout << "Fairness Benchmark, outputing to : " << output << std::endl;
     453
     454        // Barrier for synchronization
     455        barrier_t barrier(nthread + 1);
     456
     457        // Data to check everything is OK
     458        global_stat_t global;
     459
     460        std::cout << "Initializing ";
     461
     462        // Check fairness by creating a png of where the threads ran
     463        size_t width = nthread * nnodes;
     464        size_t length = 100000;
     465
     466        std::unique_ptr<int[]> data_out { new int[width * length] };
     467
     468        // Flag to signal termination
     469        std::atomic_size_t count = width;
     470
     471        // List being tested
     472        relaxed_list<Node> list = { nthread * nqueues };
     473        {
     474                enable_stats = true;
     475
     476                std::thread * threads[nthread];
     477                unsigned i = 1;
     478                for(auto & t : threads) {
     479                        t = new std::thread([&count, &list, &barrier, &global, nnodes, width, length, data_out = data_out.get()](unsigned tid) {
     480                                unsigned int start = (tid - 1) * nnodes;
     481                                Node nodes[nnodes];
     482                                for(auto & n : nodes) {
     483                                        n.id = start;
     484                                        n.value = 0;
     485                                        start++;
     486                                }
     487
     488                                local_stat_t local;
     489
     490                                // affinity(tid);
     491
     492                                barrier.wait(tid);
     493
     494                                // EXPERIMENT START
     495
     496                                runFairness_body(tid, width, length, data_out, count, nodes, nnodes, local, list);
     497
     498                                // EXPERIMENT END
     499
     500                                barrier.wait(tid);
     501
     502                                for(const auto & n : nodes) {
     503                                        local.valmax = max(local.valmax, size_t(n.value));
     504                                        local.valmin = min(local.valmin, size_t(n.value));
     505                                }
     506
     507                                tally_stats(global, local);
     508                        }, i++);
     509                }
     510
     511                waitfor(duration, barrier, count);
     512
     513                for(auto t : threads) {
     514                        t->join();
     515                        delete t;
     516                }
     517
     518                enable_stats = false;
     519        }
     520
     521        print_stats(duration, nthread, global);
     522
     523        save_fairness(data_out.get(), 100, nthread, width, length, output);
     524}
     525
     526// ================================================================================================
     527
     528bool iequals(const std::string& a, const std::string& b)
     529{
     530    return std::equal(a.begin(), a.end(),
     531                      b.begin(), b.end(),
     532                      [](char a, char b) {
     533                          return std::tolower(a) == std::tolower(b);
     534                      });
    237535}
    238536
     
    241539        double duration   = 5.0;
    242540        unsigned nthreads = 2;
    243         unsigned nqueues  = 2;
    244         unsigned fill     = 100;
     541        unsigned nqueues  = 4;
     542        unsigned nnodes   = 100;
     543        unsigned nslots   = 100;
     544        std::string out   = "fairness.png";
     545
     546        enum {
     547                Churn,
     548                PingPong,
     549                Fairness,
     550                NONE
     551        } benchmark = NONE;
    245552
    246553        std::cout.imbue(std::locale(""));
    247554
    248         switch (argc)
    249         {
     555        for(;;) {
     556                static struct option options[] = {
     557                        {"duration",  required_argument, 0, 'd'},
     558                        {"nthreads",  required_argument, 0, 't'},
     559                        {"nqueues",   required_argument, 0, 'q'},
     560                        {"benchmark", required_argument, 0, 'b'},
     561                        {0, 0, 0, 0}
     562                };
     563
     564                int idx = 0;
     565                int opt = getopt_long(argc, argv, "d:t:q:b:", options, &idx);
     566
     567                std::string arg = optarg ? optarg : "";
     568                size_t len = 0;
     569                switch(opt) {
     570                        // Exit Case
     571                        case -1:
     572                                /* paranoid */ assert(optind <= argc);
     573                                switch(benchmark) {
     574                                case NONE:
     575                                        std::cerr << "Must specify a benchmark" << std::endl;
     576                                        goto usage;
     577                                case PingPong:
     578                                        nnodes = 1;
     579                                        nslots = 1;
     580                                        switch(argc - optind) {
     581                                        case 0: break;
     582                                        case 1:
     583                                                try {
     584                                                        arg = optarg = argv[optind];
     585                                                        nnodes = stoul(optarg, &len);
     586                                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     587                                                } catch(std::invalid_argument &) {
     588                                                        std::cerr << "Number of nodes must be a positive integer, was " << arg << std::endl;
     589                                                        goto usage;
     590                                                }
     591                                                break;
     592                                        default:
     593                                                std::cerr << "'PingPong' benchmark doesn't accept more than 2 extra arguments" << std::endl;
     594                                                goto usage;
     595                                        }
     596                                        break;
     597                                case Churn:
     598                                        nnodes = 100;
     599                                        nslots = 100;
     600                                        switch(argc - optind) {
     601                                        case 0: break;
     602                                        case 1:
     603                                                try {
     604                                                        arg = optarg = argv[optind];
     605                                                        nnodes = stoul(optarg, &len);
     606                                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     607                                                        nslots = nnodes;
     608                                                } catch(std::invalid_argument &) {
     609                                                        std::cerr << "Number of nodes must be a positive integer, was " << arg << std::endl;
     610                                                        goto usage;
     611                                                }
     612                                                break;
     613                                        case 2:
     614                                                try {
     615                                                        arg = optarg = argv[optind];
     616                                                        nnodes = stoul(optarg, &len);
     617                                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     618                                                } catch(std::invalid_argument &) {
     619                                                        std::cerr << "Number of nodes must be a positive integer, was " << arg << std::endl;
     620                                                        goto usage;
     621                                                }
     622                                                try {
     623                                                        arg = optarg = argv[optind + 1];
     624                                                        nslots = stoul(optarg, &len);
     625                                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     626                                                } catch(std::invalid_argument &) {
     627                                                        std::cerr << "Number of slots must be a positive integer, was " << arg << std::endl;
     628                                                        goto usage;
     629                                                }
     630                                                break;
     631                                        default:
     632                                                std::cerr << "'Churn' benchmark doesn't accept more than 2 extra arguments" << std::endl;
     633                                                goto usage;
     634                                        }
     635                                        break;
     636                                case Fairness:
     637                                        nnodes = 1;
     638                                        switch(argc - optind) {
     639                                        case 0: break;
     640                                        case 1:
     641                                                arg = optarg = argv[optind];
     642                                                out = arg;
     643                                                break;
     644                                        default:
     645                                                std::cerr << "'Churn' benchmark doesn't accept more than 2 extra arguments" << std::endl;
     646                                                goto usage;
     647                                        }
     648                                }
     649                                goto run;
     650                        // Benchmarks
     651                        case 'b':
     652                                if(benchmark != NONE) {
     653                                        std::cerr << "Only when benchmark can be run" << std::endl;
     654                                        goto usage;
     655                                }
     656                                if(iequals(arg, "churn")) {
     657                                        benchmark = Churn;
     658                                        break;
     659                                }
     660                                if(iequals(arg, "pingpong")) {
     661                                        benchmark = PingPong;
     662                                        break;
     663                                }
     664                                if(iequals(arg, "fairness")) {
     665                                        benchmark = Fairness;
     666                                        break;
     667                                }
     668                                std::cerr << "Unkown benchmark " << arg << std::endl;
     669                                goto usage;
     670                        // Numeric Arguments
     671                        case 'd':
     672                                try {
     673                                        duration = stod(optarg, &len);
     674                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     675                                } catch(std::invalid_argument &) {
     676                                        std::cerr << "Duration must be a valid double, was " << arg << std::endl;
     677                                        goto usage;
     678                                }
     679                                break;
     680                        case 't':
     681                                try {
     682                                        nthreads = stoul(optarg, &len);
     683                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     684                                } catch(std::invalid_argument &) {
     685                                        std::cerr << "Number of threads must be a positive integer, was " << arg << std::endl;
     686                                        goto usage;
     687                                }
     688                                break;
     689                        case 'q':
     690                                try {
     691                                        nqueues = stoul(optarg, &len);
     692                                        if(len != arg.size()) { throw std::invalid_argument(""); }
     693                                } catch(std::invalid_argument &) {
     694                                        std::cerr << "Number of queues must be a positive integer, was " << arg << std::endl;
     695                                        goto usage;
     696                                }
     697                                break;
     698                        // Other cases
     699                        default: /* ? */
     700                                std::cerr << opt << std::endl;
     701                        usage:
     702                                std::cerr << "Usage: " << argv[0] << ": [options] -b churn [NNODES] [NSLOTS = NNODES]" << std::endl;
     703                                std::cerr << "  or:  " << argv[0] << ": [options] -b pingpong [NNODES]" << std::endl;
     704                                std::cerr << std::endl;
     705                                std::cerr << "  -d, --duration=DURATION  Duration of the experiment, in seconds" << std::endl;
     706                                std::cerr << "  -t, --nthreads=NTHREADS  Number of kernel threads" << std::endl;
     707                                std::cerr << "  -q, --nqueues=NQUEUES    Number of queues per threads" << std::endl;
     708                                std::exit(1);
     709                }
     710        }
     711        run:
     712
     713        check_cache_line_size();
     714
     715        std::cout << "Running " << nthreads << " threads (" << (nthreads * nqueues) << " queues) for " << duration << " seconds" << std::endl;
     716        switch(benchmark) {
     717                case Churn:
     718                        runChurn(nthreads, nqueues, duration, nnodes, nslots);
     719                        break;
     720                case PingPong:
     721                        runPingPong(nthreads, nqueues, duration, nnodes);
     722                        break;
     723                case Fairness:
     724                        runFairness(nthreads, nqueues, duration, nnodes, out);
     725                        break;
     726                default:
     727                        abort();
     728        }
     729        return 0;
     730}
     731
     732const char * __my_progname = "Relaxed List";
     733
     734struct rgb_t {
     735    double r;       // a fraction between 0 and 1
     736    double g;       // a fraction between 0 and 1
     737    double b;       // a fraction between 0 and 1
     738};
     739
     740struct hsv_t {
     741    double h;       // angle in degrees
     742    double s;       // a fraction between 0 and 1
     743    double v;       // a fraction between 0 and 1
     744};
     745
     746rgb_t hsv2rgb(hsv_t in) {
     747        double hh, p, q, t, ff;
     748        long   i;
     749        rgb_t  out;
     750
     751        if(in.s <= 0.0) {       // < is bogus, just shuts up warnings
     752                out.r = in.v;
     753                out.g = in.v;
     754                out.b = in.v;
     755                return out;
     756        }
     757        hh = in.h;
     758        if(hh >= 360.0) hh = 0.0;
     759        hh /= 60.0;
     760        i = (long)hh;
     761        ff = hh - i;
     762        p = in.v * (1.0 - in.s);
     763        q = in.v * (1.0 - (in.s * ff));
     764        t = in.v * (1.0 - (in.s * (1.0 - ff)));
     765
     766        switch(i) {
     767        case 0:
     768                out.r = in.v;
     769                out.g = t;
     770                out.b = p;
     771                break;
     772        case 1:
     773                out.r = q;
     774                out.g = in.v;
     775                out.b = p;
     776                break;
     777        case 2:
     778                out.r = p;
     779                out.g = in.v;
     780                out.b = t;
     781                break;
     782
     783        case 3:
     784                out.r = p;
     785                out.g = q;
     786                out.b = in.v;
     787                break;
     788        case 4:
     789                out.r = t;
     790                out.g = p;
     791                out.b = in.v;
     792                break;
    250793        case 5:
    251                 fill = std::stoul(argv[4]);
    252                 [[fallthrough]];
    253         case 4:
    254                 nqueues = std::stoul(argv[3]);
    255                 [[fallthrough]];
    256         case 3:
    257                 nthreads = std::stoul(argv[2]);
    258                 [[fallthrough]];
    259         case 2:
    260                 duration = std::stod(argv[1]);
    261                 if( duration <= 0.0 ) {
    262                         std::cerr << "Duration must be positive, was " << argv[1] << "(" << duration << ")" << std::endl;
    263                         usage(argv);
    264                 }
    265                 [[fallthrough]];
    266         case 1:
     794        default:
     795                out.r = in.v;
     796                out.g = p;
     797                out.b = q;
    267798                break;
    268         default:
    269                 usage(argv);
    270                 break;
    271         }
    272 
    273         check_cache_line_size();
    274 
    275         std::cout << "Running " << nthreads << " threads (" << (nthreads * nqueues) << " queues) for " << duration << " seconds" << std::endl;
    276         run(nthreads, nqueues, fill, duration);
    277 
    278         return 0;
    279 }
    280 
    281 template<>
    282 thread_local relaxed_list<Node>::TLS relaxed_list<Node>::tls = {};
    283 
    284 template<>
    285 relaxed_list<Node>::intrusive_queue_t::stat::Dif relaxed_list<Node>::intrusive_queue_t::stat::dif = {};
    286 
    287 const char * __my_progname = "Relaxed List";
     799        }
     800        return out;
     801}
     802
     803void save_fairness(const int data[], int factor, unsigned nthreads, size_t columns, size_t rows, const std::string & output) {
     804        std::ofstream os(output);
     805        os << "<html>\n";
     806        os << "<head>\n";
     807        os << "<style>\n";
     808        os << "</style>\n";
     809        os << "</head>\n";
     810        os << "<body>\n";
     811        os << "<table style=\"width=100%\">\n";
     812
     813        size_t idx = 0;
     814        for(size_t r = 0ul; r < rows; r++) {
     815                os << "<tr>\n";
     816                for(size_t c = 0ul; c < columns; c++) {
     817                        os << "<td class=\"custom custom" << data[idx] << "\"></td>\n";
     818                        idx++;
     819                }
     820                os << "</tr>\n";
     821        }
     822
     823        os << "</table>\n";
     824        os << "</body>\n";
     825        os << "</html>\n";
     826        os << std::endl;
     827}
     828
     829#include <png.h>
     830#include <setjmp.h>
     831
     832/*
     833void save_fairness(const int data[], int factor, unsigned nthreads, size_t columns, size_t rows, const std::string & output) {
     834        int width  = columns * factor;
     835        int height = rows / factor;
     836
     837        int code = 0;
     838        int idx = 0;
     839        FILE *fp = NULL;
     840        png_structp png_ptr = NULL;
     841        png_infop info_ptr = NULL;
     842        png_bytep row = NULL;
     843
     844        // Open file for writing (binary mode)
     845        fp = fopen(output.c_str(), "wb");
     846        if (fp == NULL) {
     847                fprintf(stderr, "Could not open file %s for writing\n", output.c_str());
     848                code = 1;
     849                goto finalise;
     850        }
     851
     852           // Initialize write structure
     853        png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
     854        if (png_ptr == NULL) {
     855                fprintf(stderr, "Could not allocate write struct\n");
     856                code = 1;
     857                goto finalise;
     858        }
     859
     860        // Initialize info structure
     861        info_ptr = png_create_info_struct(png_ptr);
     862        if (info_ptr == NULL) {
     863                fprintf(stderr, "Could not allocate info struct\n");
     864                code = 1;
     865                goto finalise;
     866        }
     867
     868        // Setup Exception handling
     869        if (setjmp(png_jmpbuf(png_ptr))) {
     870                fprintf(stderr, "Error during png creation\n");
     871                code = 1;
     872                goto finalise;
     873        }
     874
     875        png_init_io(png_ptr, fp);
     876
     877        // Write header (8 bit colour depth)
     878        png_set_IHDR(png_ptr, info_ptr, width, height,
     879                8, PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE,
     880                PNG_COMPRESSION_TYPE_BASE, PNG_FILTER_TYPE_BASE);
     881
     882        png_write_info(png_ptr, info_ptr);
     883
     884        // Allocate memory for one row (3 bytes per pixel - RGB)
     885        row = (png_bytep) malloc(3 * width * sizeof(png_byte));
     886
     887        // Write image data
     888        int x, y;
     889        for (y=0 ; y<height ; y++) {
     890                for (x=0 ; x<width ; x++) {
     891                        auto & r = row[(x * 3) + 0];
     892                        auto & g = row[(x * 3) + 1];
     893                        auto & b = row[(x * 3) + 2];
     894                        assert(idx < (rows * columns));
     895                        int color = data[idx] - 1;
     896                        assert(color < nthreads);
     897                        assert(color >= 0);
     898                        idx++;
     899
     900                        double angle = double(color) / double(nthreads);
     901
     902                        auto c = hsv2rgb({ 360.0 * angle, 0.8, 0.8 });
     903
     904                        r = char(c.r * 255.0);
     905                        g = char(c.g * 255.0);
     906                        b = char(c.b * 255.0);
     907
     908                }
     909                png_write_row(png_ptr, row);
     910        }
     911
     912        assert(idx == (rows * columns));
     913
     914        // End write
     915        png_write_end(png_ptr, NULL);
     916
     917        finalise:
     918        if (fp != NULL) fclose(fp);
     919        if (info_ptr != NULL) png_free_data(png_ptr, info_ptr, PNG_FREE_ALL, -1);
     920        if (png_ptr != NULL) png_destroy_write_struct(&png_ptr, (png_infopp)NULL);
     921        if (row != NULL) free(row);
     922}
     923*/
Note: See TracChangeset for help on using the changeset viewer.