Código C ++ para gerar DAGs aleatórios
Escrevi o seguinte código C ++ há algum tempo para gerar gráficos aleatórios para um projeto em que estava trabalhando:
#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();
}
O código cumpriu seu objetivo para mim, mas há muito espaço para melhorias para este código. Informe como este código pode ser reescrito para melhor aderir às práticas desejadas de C ++.
Respostas
Erros importantes:
o seu aleatório não é aleatório (semeie)
seu aleatório não é uniforme (use distribuições uniformes em vez de apenas tomar o módulo, o que distorcerá a distribuição)
precedegeralmente não é inicializado;NoOfConfigsgeralmente não é inicializado e nunca é usado?O último loop antes de gravar o arquivo de saída modifica a coleção durante a iteração :
for (size_t h = 0; h < nodes.size(); h++) { // ... nodes.push_back(forNewPE);Este é um antipadrão. Você só consegue escapar por causa de
if (nodes[h].processid == 29) { break; }que obviamente sofre de números mágicos e poderia facilmente ter sido colocado na condição de loop em vez disso:
for (size_t h = 0; h < NoOfNodes; ++h) {void PESpecificParameters(DAG_data Sample, int processorID)não é usado.Quando usado, nunca terá qualquer efeito (porque tem valores de retorno líquidos nem contém referências a nada externo)
Mesmo com
whenPEisGPUDepois de remover o código duplicado, parece que
PEParametersera idênticoPESpecificParameters(veja abaixo)Da mesma forma,
CreateandAssignEdgesnão foi usado e parece estar duplicandoEdgeAssignment?
Notas principais:
Nomeando!
DAG_Datasignifica quase nada. Seu modelo gráfico representa algo na vida real. O fato de ser um DAG é como chamar variáveis "texttring" em vez de "FirstName" e "ZipCode"Extraia algumas funções. Use-os para
- responsabilidades separadas,
- níveis de abstração
- reduzir duplicação
Opcionalmente, agrupe funções relacionadas com seus dados em classes (consulte a seção "BÔNUS" abaixo)
Aí vem um golpe a golpe das coisas que abordei:
Use os avisos (-Wall -Wextra -pedantic no mínimo) e golpeie-os:
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 | }Alterar:
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++)A execução da verificação de modernização / legibilidade mostra muitos avisos de números mágicos e algumas melhorias fáceis:
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 ...Faça pelo menos o loop range for imediatamente:
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; }Não separe desnecessariamente a inicialização da declaração.
std::ofstream myFile; // 40 lines... myFile.open("TG_Data_30NewEdges.txt");Não gerencie recursos desnecessariamente manualmente:
myFile.close();O padrão RAII do C ++ significa que o arquivo sempre será fechado.
{ std::ofstream output("TG_Data_30NewEdges.txt"); for (auto& DAG : All_DAGs) { // ... } }Observe que também renomeei
myFilepara algo mais descritivo.É hora de extrair algumas funções para o acima:
std::ofstream output("TG_Data_30NewEdges.txt"); writeReport(output, All_DAGs);E então em outro lugar:
using DAGs = std::vector<DAG_data>; void writeReport(std::ostream& output, DAGs const& graphs) { for (auto& g : graphs) { // ... } }Loops de desmistificação
unsigned int i = 0; while (i != myTaskGraph.size()) { // ... i++; }É convencionalmente escrito como
for (size_t i = 0; i < myTaskGraph.size(); ++i) { // ... }Ou, desde c ++ 0x:
for (Node& node : myTaskGraph) { // ... }Da mesma forma, os loops que criam contêineres provavelmente devem ser mais como:
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); }E
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.
Eu provavelmente os escreveria como
std::generate_nligações na vida real, mas talvez possamos chegar lá naturalmente, mais tarde abaixoNomenclatura. Em algum lugar no meio do código, de repente temos um vislumbre do que realmente estamos lidando:
void generateEdges(std::vector<DAG_data> &myTaskGraph)Então, acho que poderíamos nomear
DAG_dataNodeouTask(ou mesmoTaskNode?).Da mesma forma, temos dicas sutis aqui:
if (Sample.processid == 0) { //parent process- so there will be no edgese
else if (node.processid == NoOfNodes - 1) { // sink process- so there will be no following edgesNota lateral: você usa
parentcomo se significasse "sem bordas". Que é demonstrativamente imprecisa, porque você imediatamente não definir uma borda seguidor. O que você parece querer dizer é o "pai sem pai", que em um DAG normalmente é conhecido como "raiz". Observe também que, se você tiver um DAG com apenas 1 raiz, por que não chamá-lo de Árvore?// arquivo em: a nomenclatura é importante
Portanto, devemos tornar isso mais legível:
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?Na verdade, talvez seja melhor combinar tudo:
enum ProcessID : int { RootNodeId = 0, NoOfNodes = 30, SinkNodeId = NoOfNodes -1, };Isso leva a uma grande redução de todos os números mágicos (
= 0torna-se= RootNodeIdetc.).No entanto, isso nos força a resolver o problema com as outras atribuições "mágicas":
node.follow = rand() % NoOfEdges + 1; node.follow = (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1));Quer dizer, íamos resolver isso de uma maneira (porque, ugh e enviesado ao acaso).
Então, vamos abordar o aleatório! Você começou corretamente:
#include <random>mas nunca usei nada daquele tesouro !
std::mt19937 prng { std::random_device{} () };Agora temos nosso UniformRandomBitGenerator e o semeamos com segurança!
Vamos criar algumas funções auxiliares que nos ajudarão a gerar números uniformemente distribuídos:
Gere números até e incluindo no máximo:
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)); }Adicionar uma abreviação para [1, max] amostra aleatória:
auto gen_positive(int max) { return gen_number(max, false); }Agora, para gerar ProcessID, precisamos de algumas conversões e podemos assumir alguns padrões para os limites do intervalo:
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))); }Agora podemos reformular as expressões:
// node.follow = rand() % NoOfEdges + 1; node.follow = gen_follower(FirstFollow, NoOfEdges);E
// node.follow = // (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1)); node.follow = gen_follower(node.processid+1);Muito mais simples, seguro de tipo e uniforme!
Agora, há algumas coisas estranhas sobre isso.
Em todos os lugares
followestá implícito que seja doProcessIddomínio. No entanto, a expressãogen_follower(FirstFollow, NoOfEdges)usa emNoOfEdgesvez deNoOfNodes?!NoOfEdgestambém está codificado apenas em10para uma chamada paraEdgeAssignment.Tem certeza de que pretendia limitar "arbitrariamente" os nós seguidores para o nó raiz
[1..10]independentemente deNoOfNodes?Uma vez que os seguidores subsequentes são sempre levados "a jusante", posso supor que você quis escolher uma das "dez primeiras" partições apenas para aumentar a probabilidade de subtarefas gerarem "netos". Se sim, o nome
NoOfEdgesé completamente enganador e pode ser algo comoFirstGenerationNodes?)Existem dois locais onde o resultado dessas expressões está sendo corrigido:
if (myTaskGraph[i].follow == 30) { myTaskGraph[i].follow -= 1; } if (Sample.follow == 30) { Sample.follow -= 1; }Se esse for o intervalo desejado, simplesmente corrija suas expressões!
Conforme escrito, torna o código difícil de entender, espalha responsabilidade entre funções (o que atrai bugs) e também distorce ainda mais a distribuição:
29agora é um alvo de borda muito mais provável.Eu escolhi corrigir a expressão para corresponder à intenção implícita deste outro comentário:
// 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);
Duplicação de código. A geração de subtarefas (
node.Node_config) é duplicada, com algumas diferenças espúrias que podem ser bugs, mas podem ser intencionais?Por exemplo:
sub_task.number_Copies = rand() % 3 + 1;Uma das três cópias é omitida, o
+1que provavelmente é um bug.De maneira semelhante, vemos uma cópia do
sub_task.execTime = rand() % static_cast<int>(node.ExecTime / 2);que adiciona um
+1. Provavelmente, isso evita zeroexecTimee é um cheiro de código que também deveria ter sido uma distribuição aleatória real uniforme e de tipo forte.É difícil adivinhar o que você realmente quer
execTimedizer. Se você pretende que execTime do nó pai sempre totalize a soma de suas subtarefas, isso é muito mais fácil de expressar com alguma lógica de negócios, em vez de ter os dados redundantes em sua estrutura de dados e adicionar invariantes não documentados (que, novamente, geram bugs )Para me divertir, acrescentei como escreveria a distribuição por capricho:
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; } }Para o consumo total de energia, parece haver coisas semelhantes acontecendo. Talvez você possa substituir o powerDraw por uma função:
double powerDraw() const { return std::accumulate(begin(Node_config), end(Node_config), 0.); };
BÔNUS
Indo além, podemos imaginar um mundo onde a geração é "automática", assim como o relatório:
Considere mover a geração para os construtores:
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 };Nota
- estamos usando C ++ 11 NSMI para gerar o construtor padrão para nós
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(); };Agora,
Nodepode agrupar com suas funções de manipulação:Isso pressupõe que os tipos ainda não estão em uso em outro lugar. Caso esse não seja o caso, podemos subclassificar os tipos e nos beneficiar da divisão de objetos para converter de volta à sua classe base.
Observe também que vários lugares no código (PEParameters, output e EdgeAssignment) alternam o comportamento no PEid que aparentemente tem apenas dois valores válidos. Eu mudei isso para ser um enum refletindo esse fato:
enum Type { CPUNode, GPUNode }; Type PEid; // Processor's ID to which node is assignedComo exercício para o leitor, pode fazer sentido mudar
Nodepara algum tipo de tipo polimórfico em vez de mudar o tempo todo:using Node = std::variant<CPUNode, GPUNode>;Ou usando tipos virtuais (herança).
Listagem (s) de demonstração
Todas as revisões estão aqui em uma essência: 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;
}
Impressões, por exemplo
DONE
E gera 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
Acho que seria melhor usar uma static constexprmacro aqui do que uma macro de pré-processador.
//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; }
Onde é que as constantes 29e 30vem? Eles deveriam ser derivados em NoOfNodesvez disso?
Pode ser melhor usar a <random>biblioteca C ++ do que std::rand().
CreateandAssignEdges()e EdgeAssignment()são muito semelhantes - acho que a duplicação pode ser bastante reduzida.
//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; //}
Pedaços de código comentado como esse costumam se tornar um problema, tornando-se desatualizados e inconsistentes conforme o código ao redor muda. Remova-o ou encontre uma maneira de garantir que ele seja compilado e testado em unidade com o resto do código.
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;
Não há nenhuma necessidade real para lavar myFilecada declaração - preferem '\n'a std::endlpara todos eles (e mais / todos os usos restantes).