Code C ++ pour générer des DAG aléatoires
J'ai écrit le code C ++ suivant il y a quelque temps pour générer des graphiques aléatoires pour un projet sur lequel je travaillais:
#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();
}
Le code a rempli son objectif pour moi, mais il y a encore beaucoup à faire pour ce code. Veuillez indiquer comment ce code peut être réécrit pour mieux adhérer aux pratiques C ++ souhaitées.
Réponses
Erreurs importantes:
votre aléatoire n'est pas aléatoire (semez-le)
votre aléatoire n'est pas uniforme (utilisez des distributions uniformes plutôt que de simplement prendre le module, ce qui faussera la distribution)
precedeest souvent non initialisé;NoOfConfigsest souvent non initialisé et jamais utilisé?La dernière boucle avant l'écriture du fichier de sortie modifie la collection lors de l'itération :
for (size_t h = 0; h < nodes.size(); h++) { // ... nodes.push_back(forNewPE);C'est un anti-modèle. Tu t'en vas juste à cause de
if (nodes[h].processid == 29) { break; }qui souffre bien sûr de nombres magiques, et aurait facilement pu être mis dans la condition de boucle à la place:
for (size_t h = 0; h < NoOfNodes; ++h) {void PESpecificParameters(DAG_data Sample, int processorID)N'est pas utilisé.Lorsqu'il est utilisé, il n'aura jamais aucun effet (car il a des valeurs de retour netiher ni contient des références à quoi que ce soit à l'extérieur)
Même avec
whenPEisGPUAprès avoir supprimé le code en double, il semble que
PEParametersc'était identique àPESpecificParameters(voir ci-dessous)De même
CreateandAssignEdgesétait-il inutilisé et semble dupliquerEdgeAssignment?
Notes majeures:
Appellation!
DAG_Datasignifie presque rien. Votre modèle graphique représente quelque chose dans la vraie vie. Le fait qu'il s'agisse d'un DAG revient à appeler des variables "textstring" au lieu de "FirstName" et "ZipCode"Extrayez quelques fonctions. Utilisez-les pour
- responsabilités distinctes,
- niveaux d'abstraction
- réduire la duplication
Regroupez éventuellement les fonctions associées avec leurs données dans des classes (voir la section "BONUS" ci-dessous)
Voici un coup par coup des choses que j'ai abordées:
Utilisez les avertissements (-Wall -Wextra -pedantic au minimum) et écrasez-les:
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 | }Changements:
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++)L'exécution de la vérification de la modernisation / de la lisibilité montre de nombreux avertissements de nombres magiques et quelques améliorations faciles:
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 ...Au moins, prenez immédiatement la boucle à distance:
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; }Ne séparez pas inutilement l'initialisation de la déclaration.
std::ofstream myFile; // 40 lines... myFile.open("TG_Data_30NewEdges.txt");Ne pas gérer manuellement les ressources inutilement:
myFile.close();Le modèle RAII de C ++ signifie que le fichier sera toujours fermé.
{ std::ofstream output("TG_Data_30NewEdges.txt"); for (auto& DAG : All_DAGs) { // ... } }Notez que j'ai également renommé
myFilequelque chose de plus descriptif.Il est temps d'extraire certaines fonctions pour ce qui précède:
std::ofstream output("TG_Data_30NewEdges.txt"); writeReport(output, All_DAGs);Et puis ailleurs:
using DAGs = std::vector<DAG_data>; void writeReport(std::ostream& output, DAGs const& graphs) { for (auto& g : graphs) { // ... } }Démystifier les boucles
unsigned int i = 0; while (i != myTaskGraph.size()) { // ... i++; }Est conventionnellement écrit comme
for (size_t i = 0; i < myTaskGraph.size(); ++i) { // ... }Ou, depuis C ++ 0x:
for (Node& node : myTaskGraph) { // ... }De même, les boucles qui construisent des conteneurs devraient probablement se lire davantage comme:
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); }Et
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.
Je les écrirais probablement comme des
std::generate_nappels dans la vraie vie, mais peut-être que nous y arriverons naturellement, plus tard ci-dessousAppellation. Quelque part à mi-chemin du code, nous avons soudainement un aperçu de ce à quoi nous avons vraiment affaire:
void generateEdges(std::vector<DAG_data> &myTaskGraph)Donc, je suppose que nous pourrions nommer
DAG_dataNodeouTask(ou mêmeTaskNode?).De même, nous obtenons des indices subtils ici:
if (Sample.processid == 0) { //parent process- so there will be no edgeset
else if (node.processid == NoOfNodes - 1) { // sink process- so there will be no following edgesNote latérale: vous utilisez
parentcomme si cela signifiait "pas d'arêtes". Ce qui est inexact démonstrativement, parce que vous immédiatement ne définissez un bord suiveur. Ce que vous semblez vouloir dire est le «parent sans parent», qui dans un DAG est généralement appelé «racine». Notez également que si vous avez un DAG avec une seule racine, pourquoi ne pas l'appeler un arbre?// fichier sous: le nom est important
Donc, nous devrions rendre cela plus lisible:
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?En fait, il vaut peut-être mieux combiner le tout:
enum ProcessID : int { RootNodeId = 0, NoOfNodes = 30, SinkNodeId = NoOfNodes -1, };Cela conduit à une grande réduction de tous les nombres magiques (
= 0devient= RootNodeIdetc.).Cependant, cela nous oblige à résoudre le problème avec les autres affectations «magiques»:
node.follow = rand() % NoOfEdges + 1; node.follow = (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1));Je veux dire, nous allions aborder ces voies (parce que, pouah et biaisée au hasard).
Alors, parlons au hasard! Vous avez bien commencé:
#include <random>mais jamais utilisé une chose de ce trésor !
std::mt19937 prng { std::random_device{} () };Maintenant, nous avons notre UniformRandomBitGenerator et nous l'avons semé en toute sécurité!
Créons des fonctions d'aide qui nous aideront à générer des nombres uniformément répartis:
Générer des nombres jusqu'à et y compris 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)); }Ajout d'une main courte pour [1, max] échantillon aléatoire:
auto gen_positive(int max) { return gen_number(max, false); }Maintenant, pour générer ProcessID, nous avons besoin de quelques conversions et nous pouvons supposer des valeurs par défaut pour les limites de plage:
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))); }Maintenant, nous pouvons reformuler les expressions:
// node.follow = rand() % NoOfEdges + 1; node.follow = gen_follower(FirstFollow, NoOfEdges);Et
// node.follow = // (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1)); node.follow = gen_follower(node.processid+1);Beaucoup plus simple, sûr de type et uniforme!
Maintenant, il y a des choses étranges à ce sujet.
Partout
followest implicite d'être duProcessIddomaine. Cependant, l'expressiongen_follower(FirstFollow, NoOfEdges)utiliseNoOfEdgesau lieu deNoOfNodes?!NoOfEdgesest également simplement codé en dur10pour le seul appel àEdgeAssignment.Êtes - vous sûr que vous vouliez « arbitrairement » noeuds suiveurs limites pour le nœud racine à
[1..10]quel que soitNoOfNodes?Étant donné que les abonnés suivants sont toujours pris «en aval», je peux deviner que vous vouliez choisir parmi les «10 premières» partitions uniquement pour augmenter la probabilité que les sous-tâches engendrent des «petits-enfants». Si tel est le cas, le nom
NoOfEdgesest complètement trompeur et pourrait être quelque chose comme çaFirstGenerationNodes?)Il existe deux emplacements où le résultat de ces expressions est corrigé:
if (myTaskGraph[i].follow == 30) { myTaskGraph[i].follow -= 1; } if (Sample.follow == 30) { Sample.follow -= 1; }Si c'est la plage souhaitée, corrigez simplement vos expressions!
Tel qu'il est écrit, il rend le code difficile à comprendre, répartit la responsabilité entre les fonctions (ce qui provoque des bogues) et faussera davantage la distribution:
29est maintenant une cible de périphérie beaucoup plus probable.J'ai choisi de corriger l'expression pour qu'elle corresponde à l'intention implicite de cet autre commentaire:
// 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);
Duplication de code. La génération des sous-tâches (
node.Node_config) est dupliquée, avec quelques fausses différences qui pourraient être des bogues, mais qui pourraient être intentionnelles?Par exemple:
sub_task.number_Copies = rand() % 3 + 1;L'une des trois copies est omise,
+1ce qui est probablement un bogue.De la même manière, nous voyons une copie de
sub_task.execTime = rand() % static_cast<int>(node.ExecTime / 2);qui ajoute un
+1. Cela évite probablement zéroexecTime, et c'est une odeur de code que cela aussi aurait dû être une distribution aléatoire réelle uniforme et fortement typée.Il est difficile de deviner ce que vous voulez vraiment
execTimedire. Si vous voulez dire que l'execTime du nœud parent totalise toujours la somme de leurs sous-tâches, c'est beaucoup plus facile à exprimer avec une logique métier, plutôt que d'avoir les données redondantes dans votre structure de données et d'ajouter des invariants non documentés (qui, encore une fois, invitent des bogues ).Pour le plaisir, j'ai ajouté comment j'écrirais la distribution sur un coup de tête:
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; } }Pour la consommation totale de puissance, il semble y avoir des choses similaires. Vous pouvez peut-être remplacer powerDraw par une fonction:
double powerDraw() const { return std::accumulate(begin(Node_config), end(Node_config), 0.); };
PRIME
En dépassant les limites, nous pouvons imaginer un monde où la génération est «automatique», tout comme le reporting:
Envisagez de déplacer la génération vers les constructeurs:
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 };Remarque
- nous utilisons C ++ 11 NSMI pour générer le constructeur par défaut pour nous
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(); };Maintenant,
Nodepeut grouper avec ses fonctions de manipulation:Cela suppose que les types ne sont pas déjà utilisés ailleurs. Dans le cas où ce n'est pas le cas, nous pouvons sous-classer les types et bénéficier du découpage d'objets pour reconvertir dans sa classe de base.
Notez également que plusieurs endroits dans le code (PEParameters, output et EdgeAssignment) commutent le comportement sur PEid qui n'a apparemment que deux valeurs valides. J'ai changé cela pour être une énumération reflétant ce fait:
enum Type { CPUNode, GPUNode }; Type PEid; // Processor's ID to which node is assignedEn tant qu'exercice pour le lecteur, il peut être judicieux de passer
Nodeà une sorte de type polymorphe au lieu de changer tout le temps:using Node = std::variant<CPUNode, GPUNode>;Ou en utilisant des types virtuels (héritage).
Liste (s) de démonstration
Toutes les révisions sont ici dans un Gist: https://gist.github.com/sehe/32c07118031a049042bd9fb469355caf/revisions
En direct sur 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;
}
Impressions, par exemple
DONE
Et génère 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
++++++++++++++++++
=================
#define NoOfNodes 30
Je pense qu'il serait préférable d'utiliser une static constexprmacro ici plutôt qu'une macro de préprocesseur.
//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; }
D'où viennent les constantes 29et d'où 30viennent-elles? Devraient-ils plutôt être dérivés NoOfNodes?
Il peut être préférable d'utiliser la <random>bibliothèque C ++ que std::rand().
CreateandAssignEdges()et EdgeAssignment()sont très similaires - je pense que la duplication peut être considérablement réduite.
//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; //}
Des morceaux de code commenté comme celui-ci deviennent souvent un problème, devenant obsolètes et incohérents à mesure que le code environnant change. Supprimez-le ou trouvez un moyen de vous assurer qu'il est compilé et testé unitaire avec le reste du 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;
Il n'y a pas de réel besoin de rincer myFilechaque déclaration - préfèrent '\n'à std::endlpour tous ces (et plus / toutes les autres utilisations).