3
\$\begingroup\$

I wrote the following C++ code a while ago to generate random graphs for a project I was working on:

#include "stdafx.h"
#include <iostream>
#include <algorithm>    // std::min_element, std::max_element
#include <sstream>
#include <fstream>
#include <string>
#include <iterator>
#include <random>
#include <vector>



#define NoOfNodes 30


struct GPU_data
{
    int number_Copies;
    int workItems;
    int workGroups;
    bool memory;
    double power_consumption;
    double execTime;
};


struct DAG_data
{
    int processid; //Node's ID
    int PEid; //Processor's ID to which node is assigned
    std::vector<GPU_data> Node_config;
    int precede;
    int follow; //nodes following this node
    int noOfCopies;
    double transData;
    double ExecTime;
    double powerDraw;
};

void CreateandAssignEdges(DAG_data Sample, int NoOfEdges)
{
    
    unsigned int i = 0;

    if (Sample.processid == 0)
    {
        //parent process- so there will be no edges
        Sample.precede = 0;
        Sample.follow = rand()% NoOfEdges + 1;
    }

    else if (Sample.processid == NoOfNodes - 1)
    {
        //sink process- so there will be no following edges
        Sample.follow = 0;
    }

    else
    {
        //which nodes will the edges connect to (Anywhere from among the following nodes, including the sink node)
        Sample.follow = (Sample.processid + 1) + (std::rand() % (29 - (Sample.processid) + 1));

        if (Sample.follow == 30)
        {
            Sample.follow -= 1;
        }
    }

}

DAG_data EdgeAssignment(DAG_data Sample, int NoOfEdges)
{

    unsigned int i = 0;

    if (Sample.processid == 0)
    {
        //parent process- so there will be no edges
        Sample.precede = 0;
        Sample.follow = rand() % NoOfEdges + 1;

        return Sample;
    }

    else if (Sample.processid == NoOfNodes - 1)
    {
        //sink process- so there will be no following edges
        Sample.follow = 0;

        return Sample;
    }

    else
    {
        //which nodes will the edges connect to (Anywhere from among the following nodes, including the sink node)
        Sample.follow = (Sample.processid + 1) + (std::rand() % (29 - (Sample.processid) + 1));

        return Sample;
    }

}


        //Sample->precede = rand() % NoOfEdges;
        //Sample->follow = rand() % NoOfEdges;

        ////Preceding and following edges of a node should not be the same.
        //while (Sample->precede > Sample->follow || Sample->precede == Sample->follow)
        //{
        //  //assign both edges again
        //  Sample->follow = rand() % NoOfEdges;
        //  Sample->precede = rand() % NoOfEdges;
        //}

    



void whenPEisGPU(DAG_data Sample, int processorID)
{
    GPU_data emptySet;
    int i = 0;
    int NoOfConfigs = rand() % 5;
    GPU_data* sub_tasks = &emptySet;
    while (i != NoOfConfigs)
    {
        sub_tasks->memory = rand() % 1;
        sub_tasks->number_Copies = rand() % 3;
        sub_tasks->workGroups = rand() % 10 +1;
        sub_tasks->workItems = rand() % (sub_tasks->workGroups * 2) + 1;
        sub_tasks->power_consumption = rand() % 250;
        sub_tasks->execTime = rand() % (int)(Sample.ExecTime / 2);
        Sample.Node_config.push_back(*sub_tasks);
        i++;
    }
}

void PESpecificParameters(DAG_data Sample, int processorID)
{
    if (processorID == 0)
    {
        Sample.ExecTime = rand() % 100;
        Sample.powerDraw = 0.0;
        Sample.noOfCopies = 0;

    }
    else if (processorID == 1)
    {
        Sample.PEid = processorID;
        //whenPEisGPU(Sample, processorID);
        int i = 0;
        int NoOfConfigs = rand() % 5;
        GPU_data sub_tasks;
        while (i != NoOfConfigs)
        {
            sub_tasks.memory = rand() % 1;
            sub_tasks.number_Copies = rand() % 3+1;
            sub_tasks.workGroups = rand() % 10 + 1;
            sub_tasks.workItems = rand() % (sub_tasks.workGroups * 2) + 1;
            sub_tasks.power_consumption = rand() % 250;
            sub_tasks.execTime = rand() % (int)(Sample.ExecTime / 2);
            Sample.Node_config.push_back(sub_tasks);
            i++;
        }

    }

}

DAG_data PEParameters(DAG_data Sample, int processorID)
{
    if (processorID == 0)
    {
        Sample.ExecTime = rand() % 100;
        Sample.powerDraw = 0.0;
        Sample.noOfCopies = 0;

        return Sample;

    }
    else if (processorID == 1)
    {
        Sample.PEid = processorID;
        //whenPEisGPU(Sample, processorID);
        int i = 0;
        int NoOfConfigs = rand() % 5;
        GPU_data sub_tasks;
        while (i != NoOfConfigs)
        {
            sub_tasks.memory = rand() % 1;
            sub_tasks.number_Copies = rand() % 3 + 1;
            sub_tasks.workGroups = rand() % 10 + 1;
            sub_tasks.workItems = rand() % (sub_tasks.workGroups * 2) + 1;
            sub_tasks.power_consumption = rand() % 250;
            sub_tasks.execTime = rand() % (int)(Sample.ExecTime / 2) + 1;
            Sample.Node_config.push_back(sub_tasks);
            i++;
        }

        return Sample;

    }

}

void generateEdges(std::vector<DAG_data> &myTaskGraph)
{
    unsigned int i = 0;

    while (i != myTaskGraph.size())
    {
        for (unsigned int j = (myTaskGraph[i].processid)+1; j < myTaskGraph.size(); j++)
        {
            if (myTaskGraph[i].follow == 30)
            {
                myTaskGraph[i].follow -= 1;
            }
            //create an edge between the current node and any of its following nodes according to the following random number 
            if (rand() % 100 < 30)
            {
                myTaskGraph[i].follow = j;              
                break;
            }           
        }
        i++;
    }
}

int main()
{
        
    DAG_data emptyDAG;
    unsigned int i = 0;

    std::ofstream myFile;


    std::vector<DAG_data> All_DAGs;

    while (i != NoOfNodes)
    {
        DAG_data DAG1;

        DAG1.processid = i;
        DAG1.transData = i + 1;
        DAG1.PEid = 0;

        DAG1= PEParameters(DAG1, DAG1.PEid);
        DAG1= EdgeAssignment(DAG1, 10);

        All_DAGs.push_back(DAG1);
        //DAG1.Node_config.clear();

        i++;
    }

    generateEdges(All_DAGs);

    for (int h = 0; h < All_DAGs.size(); h++)
    {
        if (h % 2 != 0)
        {
            DAG_data forNewPE =PEParameters(All_DAGs[h], 1);

            All_DAGs.push_back(forNewPE);
            All_DAGs[h].Node_config.clear();
            if (All_DAGs[h].processid ==29)
            {
                break;
            }
        }
    
    }

    myFile.open("TG_Data_30NewEdges.txt");

    for (int i = 0; i < All_DAGs.size(); i++)
    {
        myFile << "Node id: " << All_DAGs[i].processid << std::endl;
        myFile << "Following Edge: " << All_DAGs[i].follow << std::endl;
        myFile << "Transfer Data: " << All_DAGs[i].transData << std::endl;
        myFile << "Node PE: " << All_DAGs[i].PEid << std::endl;
        if (All_DAGs[i].PEid == 0)
        {
            myFile << "Execution time: " << All_DAGs[i].ExecTime << std::endl;
        }
        else
        {
            myFile << "-------------------------------" << std::endl;
            for (int j = 0; j < All_DAGs[i].Node_config.size(); j++)
            {
                myFile << "Execution time: " << All_DAGs[i].Node_config[j].execTime << std::endl;
                myFile << "Copies: " << All_DAGs[i].Node_config[j].number_Copies << std::endl;
                myFile << "Memory: " << All_DAGs[i].Node_config[j].memory << std::endl;
                myFile << "Work-Items: " << All_DAGs[i].Node_config[j].workItems << std::endl;
                myFile << "Work-Groups: " << All_DAGs[i].Node_config[j].workGroups << std::endl;
                myFile << "Power: " << All_DAGs[i].Node_config[j].power_consumption << std::endl;   
                myFile << "++++++++++++++++++" << std::endl;
            }
        }
        myFile << "=================" << std::endl;
    }
    
    myFile.close();

    std::cout << "DONE NOW." << std::endl;

    std::cin.get();

}

The code fulfilled its objective for me but there is a lot of room for improvement for this code. Please advise how this code can be rewritten to better adhere to the desired C++ practices.

\$\endgroup\$
2
  • \$\begingroup\$ What is a DAG? I read the question and all answers, but it is still unclear. \$\endgroup\$
    – Aganju
    Jan 15, 2021 at 22:34
  • 1
    \$\begingroup\$ @Aganju DAG stands for Directed Acyclic Graph. \$\endgroup\$
    – a_sid
    Jan 15, 2021 at 23:17

2 Answers 2

10
\$\begingroup\$

Important errors:

  • your random isn't random (seed it)

  • your random isn't uniform (use uniform distributions rather than just taking the modulus, which will skew the distribution)

  • precede is often uninitialized; NoOfConfigs is often uninitialized, and never used?

  • The last loop before writing the output file modifies the collection while iterating:

     for (size_t h = 0; h < nodes.size(); h++) {
         // ...
         nodes.push_back(forNewPE);
    

    This is an anti-pattern. You only just get away with it because of

         if (nodes[h].processid == 29) { break; }
    

    which of course suffers from magic numbers, and could easily have been put in the loop condition instead:

     for (size_t h = 0; h < NoOfNodes; ++h) {
    
  • void PESpecificParameters(DAG_data Sample, int processorID) is not used.

    When used, it will never have any effect (because it has netiher return values nor holds references to anything outside)

  • Same with whenPEisGPU

  • After removing duplicate code, it looks like PEParameters was identical to PESpecificParameters (see below)

  • Likewise CreateandAssignEdges was unused and seems to be duplicating EdgeAssignment?

Major notes:

  • Naming! DAG_Data means next to nothing. Your graph model represents something in real life. The fact that it is a DAG is like calling variables "textstring" instead of "FirstName" and "ZipCode"

  • Extract some functions. Use them to

    • separate responsibilities,
    • levels of abstraction
    • reduce duplication
  • Optionally group related functions with their data into classes (see "BONUS" section below)


Here comes a blow by blow of things I addressed:

  1. Use warnings (-Wall -Wextra -pedantic at minimum) and swat them:

    test.cpp:43:18: warning: unused variable ‘i’ [-Wunused-variable]
       43 |     unsigned int i = 0;
    test.cpp:74:18: warning: unused variable ‘i’ [-Wunused-variable]
       74 |     unsigned int i = 0;
    test.cpp:119:39: warning: unused parameter ‘processorID’ [-Wunused-parameter]
      119 | void whenPEisGPU(DAG_data Sample, int processorID)
    test.cpp:259:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<DAG_data>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
      259 |     for (int h = 0; h < All_DAGs.size(); h++)
    test.cpp:277:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<DAG_data>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
      277 |     for (int i = 0; i < All_DAGs.size(); i++)
    test.cpp:290:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<GPU_data>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
      290 |             for (int j = 0; j < All_DAGs[i].Node_config.size(); j++)
    test.cpp:204:1: warning: control reaches end of non-void function [-Wreturn-type]
      204 | }
    

    Changes:

    CreateandAssignEdges:
    -    unsigned int i = 0;
    
    EdgeAssignment:
    -    unsigned int i = 0;
    
    -void whenPEisGPU(DAG_data Sample, int processorID)
    +void whenPEisGPU(DAG_data Sample, int /*processorID*/)
    
    PEParameters:
    +    throw std::range_error("processorID");
    
    -    for (int h = 0; h < All_DAGs.size(); h++)
    +    for (size_t h = 0; h < All_DAGs.size(); h++)
    
    -    for (int i = 0; i < All_DAGs.size(); i++)
    +    for (size_t i = 0; i < All_DAGs.size(); i++)
    
    -            for (int j = 0; j < All_DAGs[i].Node_config.size(); j++)
    +            for (size_t j = 0; j < All_DAGs[i].Node_config.size(); j++)
    
  2. Running modernize/readability check shows a lot of magic number warning and some easy improvements:

    clang-apply-replacements version 9.0.0
    clang-tidy-9 -header-filter=.* -checks=-*,readability-*,modernize-*,-modernize-use-trailing-return-type -export-fixes /tmp/tmp6CfbSr/tmpYGk6CX.yaml -p=/home/sehe/Projects/stackoverflow /home/sehe/Projects/stackoverflow/test.cpp
    /home/sehe/Projects/stackoverflow/test.cpp:59:66: warning: 29 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            Sample.follow = (Sample.processid + 1) + (std::rand() % (29 - (Sample.processid) + 1));
                                                                     ^
    /home/sehe/Projects/stackoverflow/test.cpp:61:30: warning: 30 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            if (Sample.follow == 30)
                                 ^
    /home/sehe/Projects/stackoverflow/test.cpp:81:5: warning: do not use 'else' after 'return' [readability-else-after-return]
        else if (Sample.processid == NoOfNodes - 1)
        ^~~~~
    /home/sehe/Projects/stackoverflow/test.cpp:92:66: warning: 29 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            Sample.follow = (Sample.processid + 1) + (std::rand() % (29 - (Sample.processid) + 1));
                                                                     ^
    /home/sehe/Projects/stackoverflow/test.cpp:119:32: warning: 5 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
        int NoOfConfigs = rand() % 5;
                                   ^
    /home/sehe/Projects/stackoverflow/test.cpp:123:29: warning: implicit conversion 'int' -> bool [readability-implicit-bool-conversion]
            sub_tasks->memory = rand() % 1;
                                ^
                                ((        ) != 0)
    /home/sehe/Projects/stackoverflow/test.cpp:125:42: warning: 10 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            sub_tasks->workGroups = rand() % 10 +1;
                                             ^
    /home/sehe/Projects/stackoverflow/test.cpp:127:49: warning: 250 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            sub_tasks->power_consumption = rand() % 250;
                                                    ^
    /home/sehe/Projects/stackoverflow/test.cpp:138:36: warning: 100 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            Sample.ExecTime = rand() % 100;
                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:148:36: warning: 5 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            int NoOfConfigs = rand() % 5;
                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:152:32: warning: implicit conversion 'int' -> bool [readability-implicit-bool-conversion]
                sub_tasks.memory = rand() % 1;
                                   ^
                                   ((        ) != 0)
    /home/sehe/Projects/stackoverflow/test.cpp:154:45: warning: 10 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                sub_tasks.workGroups = rand() % 10 + 1;
                                                ^
    /home/sehe/Projects/stackoverflow/test.cpp:156:52: warning: 250 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                sub_tasks.power_consumption = rand() % 250;
                                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:170:36: warning: 100 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            Sample.ExecTime = rand() % 100;
                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:177:5: warning: do not use 'else' after 'return' [readability-else-after-return]
        else if (processorID == 1)
        ^~~~~
    /home/sehe/Projects/stackoverflow/test.cpp:182:36: warning: 5 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            int NoOfConfigs = rand() % 5;
                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:186:32: warning: implicit conversion 'int' -> bool [readability-implicit-bool-conversion]
                sub_tasks.memory = rand() % 1;
                                   ^
                                   ((        ) != 0)
    /home/sehe/Projects/stackoverflow/test.cpp:188:45: warning: 10 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                sub_tasks.workGroups = rand() % 10 + 1;
                                                ^
    /home/sehe/Projects/stackoverflow/test.cpp:190:52: warning: 250 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                sub_tasks.power_consumption = rand() % 250;
                                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:211:42: warning: 30 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                if (myTaskGraph[i].follow == 30)
                                             ^
    /home/sehe/Projects/stackoverflow/test.cpp:216:26: warning: 100 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                if (rand() % 100 < 30)
                             ^
    /home/sehe/Projects/stackoverflow/test.cpp:216:32: warning: 30 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                if (rand() % 100 < 30)
                                   ^
    /home/sehe/Projects/stackoverflow/test.cpp:246:36: warning: 10 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
            DAG1= EdgeAssignment(DAG1, 10);
                                       ^
    /home/sehe/Projects/stackoverflow/test.cpp:264:41: warning: 29 is a magic number; consider replacing it with a named constant [readability-magic-numbers]
                if (All_DAGs[h].processid ==29)
                                            ^
    /home/sehe/Projects/stackoverflow/test.cpp:274:5: warning: use range-based for loop instead [modernize-loop-convert]
        for (size_t i = 0; i < All_DAGs.size(); i++)
        ^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            (auto & All_DAG : All_DAGs)
    7510 warnings generated.
    Suppressed 7485 warnings (7485 in non-user code).
    Use -header-filter=.* to display errors from all non-system headers. Use -system-headers to display errors from system headers as well.
    Applying fixes ...
    

    At least take the ranged-for loop immediately:

    for (auto& DAG : All_DAGs)
    {
        myFile << "Node id: "        << DAG.processid << std::endl;
        myFile << "Following Edge: " << DAG.follow    << std::endl;
        myFile << "Transfer Data: "  << DAG.transData << std::endl;
        myFile << "Node PE: "        << DAG.PEid      << std::endl;
        if (DAG.PEid == 0)
        {
            myFile << "Execution time: " << DAG.ExecTime << std::endl;
        }
        else
        {
            myFile << "-------------------------------" << std::endl;
            for (auto& cfg : DAG.Node_config)
            {
                myFile << "Execution time: " << cfg.execTime          << std::endl;
                myFile << "Copies: "         << cfg.number_Copies     << std::endl;
                myFile << "Memory: "         << cfg.memory            << std::endl;
                myFile << "Work-Items: "     << cfg.workItems         << std::endl;
                myFile << "Work-Groups: "    << cfg.workGroups        << std::endl;
                myFile << "Power: "          << cfg.power_consumption << std::endl;
                myFile << "++++++++++++++++++" << std::endl;
            }
        }
        myFile << "=================" << std::endl;
    }
    
  3. Don't unnecessarily separate initialization from declaration.

    std::ofstream myFile;
    // 40 lines...
    myFile.open("TG_Data_30NewEdges.txt");
    

    Don't unnecessarily manually resource manage:

    myFile.close();
    

    C++'s RAII pattern means the file will always be closed.

    {
        std::ofstream output("TG_Data_30NewEdges.txt");
    
        for (auto& DAG : All_DAGs)
        {
            // ...
        }
    }
    

    Note I also renamed myFile to something more descriptive.

  4. Time to extract some functions for the above:

    std::ofstream output("TG_Data_30NewEdges.txt");
    writeReport(output, All_DAGs);
    

    And then somewhere else:

    using DAGs = std::vector<DAG_data>;
    
    void writeReport(std::ostream& output, DAGs const& graphs) {
        for (auto& g : graphs) {
            // ...
        }
    }
    
  5. De-mystify loops

    unsigned int i = 0;
    while (i != myTaskGraph.size()) {
        // ...
        i++;
    }
    

    Is conventionally written as

    for (size_t i = 0; i < myTaskGraph.size(); ++i) {
        // ...
    }
    

    Or, ever since c++0x:

    for (Node& node : myTaskGraph) {
        // ...
    }
    
  6. Likewise the loops that build containers should probably read more like:

    Nodes nodes(NoOfNodes);
    
    size_t i = 0;
    for (auto& current : nodes) {
        current.processid = i;
        current.transData = i + 1;
        current.PEid = 0;
    
        i++;
    
        current = PEParameters(current, current.PEid);
        current = EdgeAssignment(current, 10);
    }
    

    And

    void whenPEisGPU(Node& node, int /*processorID*/)
    {
        int NoOfConfigs = rand() % 5;
        node.Node_config.assign(NoOfConfigs, {});
    
        for (auto& sub_task : node.Node_config) {
            sub_task.memory            = ((rand() % 1) != 0);
            sub_task.number_Copies     = rand() % 3;
            sub_task.workGroups        = rand() % 10 +1;
            sub_task.workItems         = rand() % (sub_task.workGroups * 2) + 1;
            sub_task.power_consumption = rand() % 250;
            sub_task.execTime          = rand() % (int)(node.ExecTime / 2);
        }
    }
    

    etc.

    I'd probably write them as std::generate_n calls in real life, but maybe we'll naturally arrive there, later below

  7. Naming. Somewhere halfway the code, suddenly we get a glimpse of what we're really dealing with:

    void generateEdges(std::vector<DAG_data> &myTaskGraph)
    

    So, I guess we could name DAG_data Node or Task (or even TaskNode?).

    Likewise, we get subtle hints here:

    if (Sample.processid == 0) {
        //parent process- so there will be no edges
    

    and

    else if (node.processid == NoOfNodes - 1) {
        // sink process- so there will be no following edges
    

    Side Note: you use parent as if it means "no edges". Which is demonstratively inaccurate, because you immediately do set a follower edge. What you seem to mean is the "parent without a parent", which in a DAG is usually known as a "root". Note also, that if you have a DAG with only 1 root, why not call it a Tree?

    // file under: naming is important

    So, we should make that more readable:

    using ProcessID = int;
    static constexpr size_t NoOfNodes = 30;
    static constexpr ProcessID RootNodeId = 0;
    static constexpr ProcessID SinkNodeId = NoOfNodes - 1;
    
    // ...
    static bool constexpr IsSink(ProcessID id) { return SinkNodeId == id; }
    static bool constexpr IsSink(Node const& node) { return IsSink(node.processid); }
    // etc?
    
  8. In fact, maybe it's better to combine the whole thing:

    enum ProcessID : int {
        RootNodeId = 0,
        NoOfNodes  = 30,
        SinkNodeId = NoOfNodes -1,
    };
    

    This leads to a great reduction of all magic numbers ( = 0 becomes = RootNodeId etc).

    However, it forces us to address the problem with the other "magic" assignements:

    node.follow = rand() % NoOfEdges + 1;
    node.follow =
        (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1));
    

    I mean, we were going to address those anways (because, ugh and skewed random).

  9. So, let's address random! You started out correctly:

    #include <random>
    

    but never used a thing from that treasure trove!

    std::mt19937 prng { std::random_device{} () };
    

    Now we have our UniformRandomBitGenerator and we securely seeded it!

    Let's create some helper functions that will help us generate uniformly distributed numbers:

    Generate numbers up to and including max:

    auto gen_number(int max, bool includeZero = true) {
        using Dist  = std::uniform_int_distribution<>;
        using Param = Dist::param_type;
        static Dist dist;
    
        auto min = includeZero? 0:1;
        assert(max >= min);
        return dist(prng, Param(min, max));
    }
    

    Adding a short hand for [1, max] random sample:

    auto gen_positive(int max) {
        return gen_number(max, false);
    }
    

    Now, to generate ProcessID we need some conversions and we can assume some defaults for the range limits:

    ProcessID gen_follower(int from = FirstFollow, int to = NoOfNodes) {
        using T     = std::underlying_type_t<ProcessID>;
        using Dist  = std::uniform_int_distribution<T>;
        using Param = Dist::param_type;
    
        static Param full{static_cast<T>(FirstFollow), static_cast<T>(NoOfNodes)};
        static Dist dist(full);
    
        return static_cast<ProcessID>(dist(prng, Param(from, to)));
    }
    

    Now we can rephrase the expressions:

    // node.follow = rand() % NoOfEdges + 1;
    node.follow = gen_follower(FirstFollow, NoOfEdges);
    

    And

    // node.follow =
    //     (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1));
    node.follow = gen_follower(node.processid+1);
    

    Much simpler, type-safe and uniform!

    Now, there's some weird things about this.

    • Everywhere follow is implied to be from the ProcessId domain. However, the expression gen_follower(FirstFollow, NoOfEdges) uses NoOfEdges instead of NoOfNodes?! NoOfEdges is also just hardcoded at 10 for the one call to EdgeAssignment.

      Are you sure you meant to "arbitrarily" limit follower nodes for the Root Node to [1..10] regardless of NoOfNodes?

      Since subsequent followers are always taken "down-stream" I can guess that you wanted to pick from a "first 10" partition only to increase the likelihood of subtasks to beget "grand children". If so, the name NoOfEdges is completely misleading, and could be something like FirstGenerationNodes?)

    • There are two locations where the result of these expressions is being corrected:

       if (myTaskGraph[i].follow == 30) {
           myTaskGraph[i].follow -= 1;
       }
      
       if (Sample.follow == 30) {
           Sample.follow -= 1;
       }
      

      If that's the desired range, simply fix your expressions!

      As written it makes the code hard to understand, spreads responsibility across functions (which invites bugs) and also further skews the distribution: 29 is now a much more likely edge target.

      I chose to fix the expression to match the implied intent from this other comment:

      // which nodes will the edges connect to (Anywhere from among the
      // following nodes, including the sink node)
      node.follow = gen_follower(node.processid+1, SinkNodeId);
      
  10. Code duplication. The generation of subtasks (node.Node_config) is duplicated, with some spurious differences that might be bugs, but could be intentional?

    E.g.:

    sub_task.number_Copies = rand() % 3 + 1;
    

    One of three copies omit +1 which is likely a bug.

    In similar fashion we see one copy of

    sub_task.execTime = rand() % static_cast<int>(node.ExecTime / 2);
    

    that adds an +1. Likely this avoids zero execTime, and is a code smell that this too should have been a strong-typed, uniform real random distribution.

    It's hard to guess what you actually want execTime to mean. If you mean it to be such that parent node's execTime always totals the sum of their subtasks, that is much easier to express with some business logic, rather than having the data redundant in your datastructure and add undocumented invariants (which, again, invite bugs).

    For fun, I added how I'd write the distribution on a whim:

        void distributeExecTime(Node& node) {
            std::vector<double> weights;
            std::uniform_real_distribution<> dist;
            std::generate_n(
                back_inserter(weights),
                node.Node_config.size(),
                [&dist] { return dist(prng); });
    
            auto total_w = std::accumulate(begin(weights), end(weights), 0.);
    
            for (size_t i = 0; i < weights.size(); ++i) {
                node.Node_config[i].execTime = (weights[i]/total_w) * node.ExecTime;
            }
        }
    
  11. For total power draw there seems to be similar things going on. Perhaps you can replace powerDraw with a function:

    double powerDraw() const {
        return std::accumulate(begin(Node_config), end(Node_config), 0.);
    };
    

BONUS

Going over the edge, we can envision a world where the generating is "automatic", as is the reporting:

  • Consider moving generation into constructors:

     struct GPU_data {
         int number_Copies        = gen_positive(3);
         int workGroups           = gen_positive(10); // order is important!
         int workItems            = gen_positive(workGroups * 2);
         bool memory              = odds(50);
         double power_consumption = gen_real(249);
         double execTime          = 0; // see distributeExecTime
     };
    

    Note

    • we're using C++11 NSMI to generate the default constructor for us
     struct Node {
         enum Type { CPUNode, GPUNode };
    
         Type      PEid;      // Processor's ID to which node is assigned
         ProcessID processid; // Node's ID
         Configs   sub_tasks;
         ProcessID follow    = RootNodeId; // nodes following this node
         double    transData = 0;
         double    ExecTime  = 0;
    
         explicit Node(int id, int NoOfEdges = 10)
           : PEid(CPUNode),
             processid(ProcessID(id)),
             transData(id + 1)
         {
             PEParameters();
             EdgeAssignment(NoOfEdges);
         }
    
         explicit Node(Node const& node)
          : PEid(GPUNode),
            processid(node.processid),
            sub_tasks(),
            follow(node.follow),
            transData(node.transData),
            ExecTime(node.ExecTime)
         {
             PEParameters();
         }
    
         double powerDraw() const;
         bool isGPU() const { return PEid == GPUNode; }
    
       private:
         void PEParameters();
         void EdgeAssignment(int NoOfEdges);
         void distributeExecTime();
     };
    

    Now, Node can group with it's manipulating functions:

    • This sort of assumes the types are not already in use elsewhere. In case that's not the case, we can sub-class the types and benefit from object slicing to convert back to its base class.

    • Note as well that several places in the code (PEParameters, output and EdgeAssignment) switch behaviour on PEid which apparently has only two valid values. I've changed that to be an enum reflecting that fact:

      enum Type { CPUNode, GPUNode };
      Type      PEid;      // Processor's ID to which node is assigned
      

      As an exercise for the reader, it might make sense to change Node to some kind of polymorphic type instead of switching all the time:

      using Node = std::variant<CPUNode, GPUNode>;
      

      Or using virtual types (inheritance).

Demo Listing(s)

All revisison are here in a Gist: https://gist.github.com/sehe/32c07118031a049042bd9fb469355caf/revisions

Live On Coliru

#include <iostream>
#include <algorithm>    // std::min_element, std::max_element
#include <fstream>
#include <string>
#include <random>
#include <vector>
#include <cassert>

namespace {
    static std::mt19937 prng { std::random_device{} () };

    enum ProcessID : int {
        RootNodeId /*= 0 */,
        NoOfNodes    = 30,

        FirstFollow  = RootNodeId +1,
        SinkNodeId   = NoOfNodes -1,
    };

    auto gen_number(int max, bool includeZero = true) {
        using Dist  = std::uniform_int_distribution<>;
        using Param = Dist::param_type;
        static Dist dist;

        auto min = includeZero? 0:1;
        assert(max >= min);
        return dist(prng, Param(min, max));
    }

    auto gen_positive(int max) {
        return gen_number(max, false);
    }

    ProcessID gen_follower(int from = FirstFollow, int to = NoOfNodes) {
        using T     = std::underlying_type_t<ProcessID>;
        using Dist  = std::uniform_int_distribution<T>;
        using Param = Dist::param_type;

        static Param full{static_cast<T>(FirstFollow), static_cast<T>(NoOfNodes)};
        static Dist dist(full);

        return static_cast<ProcessID>(dist(prng, Param(from, to)));
    }

    bool odds(int percentage) {
        if (percentage == 100)
            return true;
        assert(percentage > 0 && percentage < 100);
        return std::discrete_distribution<bool>(percentage, 100-percentage)(prng);
    }

    double gen_real(double mean = 100.0, double stddev = 0) {
        if (stddev == 0)
            stddev = mean/4;
        assert(stddev>0);
        return std::normal_distribution(mean, stddev)(prng);
    }
}

struct GPU_data {
    int number_Copies        = gen_positive(3);
    int workGroups           = gen_positive(10); // order is important!
    int workItems            = gen_positive(workGroups * 2);
    bool memory              = odds(50);
    double power_consumption = gen_real(249);
    double execTime          = 0; // see distributeExecTime
};

using Configs = std::vector<GPU_data>;

struct Node {
    enum Type { CPUNode, GPUNode };

    Type      PEid;      // Processor's ID to which node is assigned
    ProcessID processid; // Node's      ID
    Configs   sub_tasks;
    ProcessID follow    = RootNodeId; // nodes following this node
    double    transData = 0;
    double    ExecTime  = 0;

    explicit Node(int id, int NoOfEdges = 10)
      : PEid(CPUNode),
        processid(ProcessID(id)),
        transData(id + 1)
    {
        PEParameters();
        EdgeAssignment(NoOfEdges);
    }

    explicit Node(Node const& node)
     : PEid(GPUNode),
       processid(node.processid),
       sub_tasks(),
       follow(node.follow),
       transData(node.transData),
       ExecTime(node.ExecTime)
    {
        PEParameters();
    }

    double powerDraw() const {
        double total = 0;
        for (auto& sub: sub_tasks) {
            total += sub.power_consumption;
        }
        return total;
    };

    bool isGPU() const { return PEid == GPUNode; }

  private:
    void PEParameters() {
        switch(PEid) {
          case CPUNode:
            ExecTime = gen_real(100.0);
            break;
          case GPUNode:
            sub_tasks.resize(gen_number(5));
            distributeExecTime();
            break;
          default:
            throw std::range_error("PEid");
        }
    }

    void EdgeAssignment(int NoOfEdges) {
        if (processid == RootNodeId) {
            // parent process- so there will be no edges
            follow  = gen_follower(FirstFollow, NoOfEdges);
        }
        else if (processid == SinkNodeId) {
            // sink process- so there will be no following edges
            follow = RootNodeId;
        }
        else {
            // which nodes will the edges connect to (Anywhere from among the
            // following nodes, including the sink node)
            follow = gen_follower(processid+1, SinkNodeId);
        }
    }

    void distributeExecTime() {
        std::vector<double> weights;
        std::uniform_real_distribution<> dist;
        std::generate_n(
            back_inserter(weights),
            sub_tasks.size(),
            [&dist] { return dist(prng); });

        auto total_w = std::accumulate(begin(weights), end(weights), 0.);

        for (size_t i = 0; i < weights.size(); ++i) {
            sub_tasks[i].execTime = (weights[i]/total_w) * ExecTime;
        }
    }
};

using Nodes = std::vector<Node>;

void generateEdges(Nodes& nodes) {
    for (Node& node : nodes) {
        // Create an edges to following nodes given 30% odds
        for (size_t j = node.processid+1; j < nodes.size(); j++) {
            if (odds(30)) {
                node.follow = static_cast<ProcessID>(j);              
                break;
            }           
        }
    }
}

static std::ostream& operator<<(std::ostream& os, Node const& n);

int main() {
    Nodes nodes;
    for (auto id = 0; id < NoOfNodes; ++id) {
        nodes.emplace_back(id);
    }

    generateEdges(nodes);

    for (size_t h = 0; h < NoOfNodes; h++) {
        if (h % 2 == 0)
            continue;

        nodes.emplace_back(nodes[h]);
        nodes[h].sub_tasks.clear();
    }

    std::ofstream output("TG_Data_30NewEdges.txt");
    for (auto& n : nodes) {
        output << n << "=================\n";
    }

    std::cout << "DONE" << std::endl;
}

static std::ostream& operator<<(std::ostream& os, GPU_data const& cfg) {
    return os 
        << "Execution time: " << cfg.execTime          << "\n"
        << "Copies: "         << cfg.number_Copies     << "\n"
        << "Memory: "         << cfg.memory            << "\n"
        << "Work-Items: "     << cfg.workItems         << "\n"
        << "Work-Groups: "    << cfg.workGroups        << "\n"
        << "Power: "          << cfg.power_consumption << "\n";
}

static std::ostream& operator<<(std::ostream& os, Node const& n) {
    os << "Node id: "        << n.processid   << "\n"
       << "Following Edge: " << n.follow      << "\n"
       << "Transfer Data: "  << n.transData   << "\n"
       << "Node powerDraw: " << n.powerDraw() << "\n"
       << "Node PE: "        << n.PEid        << "\n";

    if (n.isGPU()) {
        os << "-------------------------------\n";
        for (auto& cfg : n.sub_tasks) {
            os << cfg << "++++++++++++++++++\n";
        }
    } else {
        os << "Execution time: " << n.ExecTime << "\n";
    }
    return os;
}

Prints, e.g.

DONE

And generates TG_Data_30NewEdges.txt:

Node id: 0
Following Edge: 1
Transfer Data: 1
Node powerDraw: 1020.61
Node PE: 1
-------------------------------
Execution time: 12.2428
Copies: 1
Memory: 1
Work-Items: 10
Work-Groups: 9
Power: 229.989
++++++++++++++++++
Execution time: 39.2756
Copies: 1

// ...
// 825 lines snipped
// ...

Copies: 3
Memory: 1
Work-Items: 3
Work-Groups: 9
Power: 235.512
++++++++++++++++++
=================
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Added all revisison are here in a Gist: gist.github.com/sehe/32c07118031a049042bd9fb469355caf/revisions \$\endgroup\$
    – sehe
    Jan 12, 2021 at 19:58
  • 1
    \$\begingroup\$ Thank you very much for responding to my request to review my code and thank you again for posting such a comprehensive review. The "new" code has many C++ concepts I did not know about earlier. I can enhance my C++ knowledge considerably just by reading this review :) \$\endgroup\$
    – a_sid
    Jan 13, 2021 at 18:51
  • \$\begingroup\$ What's happening?! A month later I suddenly get a stream of upvotes on this answer :) Not complaining, just confused \$\endgroup\$
    – sehe
    Feb 4, 2021 at 15:44
  • \$\begingroup\$ It's on the c++ subreddit 😄 \$\endgroup\$ Feb 5, 2021 at 7:21
  • \$\begingroup\$ I just have to say how impressed I am at the level of detail and positive advice you've given here, it's really impressive. I can only imagine how much time it took you. Really wholesome and generous. Kudos \$\endgroup\$ Feb 5, 2021 at 7:22
1
\$\begingroup\$
#define NoOfNodes 30

I think it would be better to use a static constexpr here rather than a preprocessor macro.

    //which nodes will the edges connect to (Anywhere from among the following nodes, including the sink node)
    Sample.follow = (Sample.processid + 1) + (std::rand() % (29 - (Sample.processid) + 1));

    if (Sample.follow == 30)
    {
        Sample.follow -= 1;
    }

Where do the constants 29 and 30 come from? Should they be derived from NoOfNodes instead?

It may be better to use the C++ <random> library than std::rand().

CreateandAssignEdges() and EdgeAssignment() are very similar - I think the duplication can be greatly reduced.

   //Sample->precede = rand() % NoOfEdges;
    //Sample->follow = rand() % NoOfEdges;

    ////Preceding and following edges of a node should not be the same.
    //while (Sample->precede > Sample->follow || Sample->precede == Sample->follow)
    //{
    //  //assign both edges again
    //  Sample->follow = rand() % NoOfEdges;
    //  Sample->precede = rand() % NoOfEdges;
    //}

Chunks of commented-out code like this often become a problem, becoming out of date and inconsistent as the surrounding code changes. Either remove it, or find a way to ensure it gets compiled and unit-tested with the rest of the code.

    myFile << "Node id: " << All_DAGs[i].processid << std::endl;
    myFile << "Following Edge: " << All_DAGs[i].follow << std::endl;
    myFile << "Transfer Data: " << All_DAGs[i].transData << std::endl;
    myFile << "Node PE: " << All_DAGs[i].PEid << std::endl;

There's no real need to flush myFile each statement - prefer '\n' to std::endl for all of these (and most/all of the remaining uses).

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for this answer. Do you think it would be better to split my code into classes? \$\endgroup\$
    – a_sid
    Jan 11, 2021 at 19:44
  • \$\begingroup\$ Where do the constants 29 and 30 come from? Should they be derived from NoOfNodes instead? Yes. Those values should be coming from NoOfNodes. \$\endgroup\$
    – a_sid
    Jan 11, 2021 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.