Код C ++ для генерации случайных DAG
Некоторое время назад я написал следующий код на C ++ для генерации случайных графиков для проекта, над которым я работал:
#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();
}
Код выполнил свою задачу для меня, но для этого кода есть много возможностей для улучшения. Пожалуйста, посоветуйте, как можно переписать этот код, чтобы он лучше соответствовал желаемой практике C ++.
Ответы
Важные ошибки:
ваш случайный не случайный (засейте его)
ваш случайный случай не является однородным (используйте равномерные распределения, а не просто принимайте модуль, который исказит распределение)
precedeчасто не инициализируется;NoOfConfigsчасто не инициализируется и никогда не используется?Последний цикл перед записью выходного файла изменяет коллекцию во время итерации :
for (size_t h = 0; h < nodes.size(); h++) { // ... nodes.push_back(forNewPE);Это антипаттерн. Тебе это сходит с рук только из-за
if (nodes[h].processid == 29) { break; }который, конечно, страдает от магических чисел и может быть легко помещен в условие цикла:
for (size_t h = 0; h < NoOfNodes; ++h) {void PESpecificParameters(DAG_data Sample, int processorID)не используется.При использовании он никогда не будет иметь никакого эффекта (потому что он имеет более низкие возвращаемые значения и не содержит ссылок на что-либо внешнее)
То же самое с
whenPEisGPUПосле удаления повторяющегося кода он выглядит
PEParametersидентичноPESpecificParameters(см. Ниже)Точно так же
CreateandAssignEdgesне использовался и кажется дублируетсяEdgeAssignment?
Основные примечания:
Именование!
DAG_Dataпрактически ничего не значит. Ваша графическая модель представляет что-то в реальной жизни. Тот факт, что это DAG, похож на вызов переменных «textstring» вместо «FirstName» и «ZipCode».Извлеките некоторые функции. Используйте их, чтобы
- отдельные обязанности,
- уровни абстракции
- уменьшить дублирование
При желании сгруппируйте связанные функции с их данными в классы (см. Раздел «БОНУС» ниже)
Вот и все, к чему я обратился:
Используйте предупреждения (как минимум -Wall -Wextra -pedantic) и удаляйте их:
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 | }Изменения:
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++)Запуск проверки модернизации / читаемости показывает множество предупреждений о магических числах и некоторые простые улучшения:
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 ...По крайней мере, немедленно возьмите цикл дальнего действия:
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; }Не отделяйте инициализацию от объявления без необходимости.
std::ofstream myFile; // 40 lines... myFile.open("TG_Data_30NewEdges.txt");Не управляйте ресурсами вручную без необходимости:
myFile.close();Шаблон RAII C ++ означает, что файл всегда будет закрыт.
{ std::ofstream output("TG_Data_30NewEdges.txt"); for (auto& DAG : All_DAGs) { // ... } }Обратите внимание, что я также переименовал его
myFileв нечто более описательное.Пора извлечь некоторые функции из вышеперечисленного:
std::ofstream output("TG_Data_30NewEdges.txt"); writeReport(output, All_DAGs);А потом еще где-нибудь:
using DAGs = std::vector<DAG_data>; void writeReport(std::ostream& output, DAGs const& graphs) { for (auto& g : graphs) { // ... } }Демистифицирующие петли
unsigned int i = 0; while (i != myTaskGraph.size()) { // ... i++; }Условно записывается как
for (size_t i = 0; i < myTaskGraph.size(); ++i) { // ... }Или, начиная с c ++ 0x:
for (Node& node : myTaskGraph) { // ... }Точно так же циклы, которые создают контейнеры, вероятно, должны выглядеть примерно так:
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); }И
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); } }и т.п.
Я бы, наверное, написал их как
std::generate_nзвонки в реальной жизни, но, возможно, мы приедем туда, позжеИменование. Где-то на полпути кода мы внезапно получаем представление о том, с чем на самом деле имеем дело:
void generateEdges(std::vector<DAG_data> &myTaskGraph)Итак, я думаю, мы могли бы назвать
DAG_dataNodeилиTask(или дажеTaskNode?).Точно так же мы получаем здесь тонкие подсказки:
if (Sample.processid == 0) { //parent process- so there will be no edgesи
else if (node.processid == NoOfNodes - 1) { // sink process- so there will be no following edgesБоковое примечание: вы используете,
parentкак будто это означает «без краев». Что демонстративно неточно, потому что вы сразу же устанавливаете преимущество последователя. Кажется, вы имеете в виду «родитель без родителя», который в DAG обычно называется «корнем». Также обратите внимание: если у вас есть группа DAG только с одним корнем, почему бы не назвать ее деревом?// файл ниже: имя важно
Итак, мы должны сделать это более читаемым:
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?На самом деле, может, лучше все это объединить:
enum ProcessID : int { RootNodeId = 0, NoOfNodes = 30, SinkNodeId = NoOfNodes -1, };Это приводит к значительному уменьшению всех магических чисел (
= 0становится и= RootNodeIdт.д.).Однако это заставляет нас решать проблему с помощью других «волшебных» назначений:
node.follow = rand() % NoOfEdges + 1; node.follow = (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1));Я имею в виду, что мы собирались решить эти проблемы всегда (потому что, тьфу, и случайный перекос).
Итак, обратимся к случайному! Вы правильно начали:
#include <random>но никогда не использовал ничего из этой сокровищницы !
std::mt19937 prng { std::random_device{} () };Теперь у нас есть UniformRandomBitGenerator, и мы его надежно засеяли !
Давайте создадим несколько вспомогательных функций, которые помогут нам генерировать равномерно распределенные числа:
Генерация чисел до макс. Включительно:
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)); }Добавление короткой стрелки для [1, max] случайной выборки:
auto gen_positive(int max) { return gen_number(max, false); }Теперь, чтобы сгенерировать ProcessID, нам нужны некоторые преобразования, и мы можем принять некоторые значения по умолчанию для пределов диапазона:
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))); }Теперь мы можем перефразировать выражения:
// node.follow = rand() % NoOfEdges + 1; node.follow = gen_follower(FirstFollow, NoOfEdges);И
// node.follow = // (node.processid + 1) + (std::rand() % (29 - (node.processid) + 1)); node.follow = gen_follower(node.processid+1);Намного проще, безопаснее и единообразнее!
В этом есть некоторые странности.
Везде
followподразумевается изProcessIdдомена. Однако выражениеgen_follower(FirstFollow, NoOfEdges)используетNoOfEdgesвместоNoOfNodes?!NoOfEdgesтакже просто жестко запрограммирован10для одного вызоваEdgeAssignment.Вы уверены, что имели в виду «произвольно» ограничить число последователей для корневого узла
[1..10]независимо отNoOfNodes?Поскольку последующие последователи всегда принимаются «ниже по течению», я могу предположить, что вы хотели выбрать из «первых 10» разделов только для того, чтобы повысить вероятность того, что подзадачи породят «внуков». Если да, то название
NoOfEdgesвводит в заблуждение, а может быть что-то вродеFirstGenerationNodes?)Есть два места, где исправляется результат этих выражений:
if (myTaskGraph[i].follow == 30) { myTaskGraph[i].follow -= 1; } if (Sample.follow == 30) { Sample.follow -= 1; }Если это желаемый диапазон, просто исправьте свои выражения!
В том виде, в каком он написан, он затрудняет понимание кода, распределяет ответственность между функциями (что приводит к появлению ошибок), а также еще больше искажает распределение:
29теперь это гораздо более вероятная конечная цель.Я решил исправить выражение, чтобы оно соответствовало подразумеваемому намерению из этого другого комментария:
// 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);
Дублирование кода. Генерация subtasks (
node.Node_config) дублируется с некоторыми ложными отличиями, которые могут быть ошибками, но могут быть преднамеренными?Например:
sub_task.number_Copies = rand() % 3 + 1;Одна из трех копий не указана,
+1что, вероятно, является ошибкой.Аналогичным образом мы видим одну копию
sub_task.execTime = rand() % static_cast<int>(node.ExecTime / 2);который добавляет
+1. Скорее всего, это позволяет избежать нуляexecTime, и это запах кода, который тоже должен быть строго типизированным, однородным реальным случайным распределением.Трудно догадаться, что вы на самом деле хотите иметь
execTimeв виду. Если вы имеете в виду, что execTime родительского узла всегда суммирует сумму их подзадач, это гораздо проще выразить с помощью некоторой бизнес-логики, чем иметь избыточные данные в вашей структуре данных и добавлять недокументированные инварианты (которые, опять же, вызывают ошибки ).Ради интереса добавил, как по прихоти написал раздачу:
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; } }По общему потреблению энергии, похоже, происходят похожие вещи. Возможно, вы можете заменить powerDraw функцией:
double powerDraw() const { return std::accumulate(begin(Node_config), end(Node_config), 0.); };
БОНУС
Переходя через край, мы можем представить себе мир, в котором генерация "автоматическая", как и отчетность:
Подумайте о переносе генерации в конструкторы:
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 };Заметка
- мы используем C ++ 11 NSMI для генерации конструктора по умолчанию для нас
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(); };Теперь
Nodeможно сгруппировать с помощью управляющих функций:Предполагается, что эти типы еще нигде не используются. В случае, если это не так, мы можем подклассифицировать типы и извлечь выгоду из срезов объекта для преобразования обратно в его базовый класс.
Также обратите внимание, что несколько мест в коде (PEParameters, output и EdgeAssignment) переключают поведение на PEid, который, по-видимому, имеет только два действительных значения. Я изменил это на перечисление, отражающее этот факт:
enum Type { CPUNode, GPUNode }; Type PEid; // Processor's ID to which node is assignedВ качестве упражнения для читателя может иметь смысл перейти
Nodeна какой-то полиморфный тип вместо того, чтобы постоянно переключаться:using Node = std::variant<CPUNode, GPUNode>;Или с помощью виртуальных типов (наследование).
Демо листинг (ы)
Все ревизии здесь в 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;
}
Печать, например
DONE
И генерирует 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
Я думаю, что лучше было бы использовать static constexprмакрос здесь, а не препроцессор.
//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; }
Откуда берутся константы 29и 30? Должны ли они быть производными NoOfNodesвместо этого?
Возможно, лучше использовать <random>библиотеку C ++, чем std::rand().
CreateandAssignEdges()и EdgeAssignment()очень похожи - думаю, дублирование можно значительно уменьшить.
//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; //}
Подобные фрагменты закомментированного кода часто становятся проблемой, поскольку они устаревают и становятся непоследовательными по мере изменения окружающего кода. Либо удалите его, либо найдите способ обеспечить его компиляцию и модульное тестирование с остальной частью кода.
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;
Нет никакой реальной необходимости сбрасывать myFileкаждый оператор - предпочитайте '\n'это std::endlдля всех (и для большинства / всех оставшихся вариантов использования).