close

Вход

Забыли?

вход по аккаунту

?

kargin (2)

код для вставкиСкачать
Московский Государственный Технический Университет
имени Н.Э. Баумана
Факультет "Робототехника и комплексная автоматизация"
Кафедра "Системы автоматизированного проектирования"
Лабораторная работа №6
"Исследование эффективности динамической диффузной балансировки загрузки МВС с помощью имитационного моделирования"
по курсу
"Параллельные вычисления"
Вариант 22
Выполнил: студент Каргин А.А.
группа РК6-112 (119)
Москва
2013
1. Цель работы
Целью работы является изучение метода динамической диффузной балансировки загрузки многопроцессорной вычислительной системы (МВС), как приближенного способа решения задачи оптимального отображения вычислительных процессов на архитектуру многопроцессорной ЭВМ, а также исследование эффективности этого метода балансировки с помощью имитационного моделирования [1, 3].
2. Теоретическая часть 2.1. Постановка задачи - вектор параметров задачи, где - n-мерное арифметическое пространство; - множество допустимых значений вектора X. Здесь параллелепипед , где - заданные константы; множество , где - непрерывные ограничивающие функции. На множестве определена вектор-функция со значениями в пространстве . Ставится задача поиска значения некоторого функционала . Полагается, что приближенное решение поставленной задачи может быть найдено по следующей схеме. Шаг 1. Покрываем параллелепипед П некоторой сеткой с узлами . Шаг 2. В тех узлах сетки , которые принадлежат множеству , вычисляем значения вектор функции . Шаг 3. На основе вычисленных значений вектор функции находим приближенное значение функционала .
Введем следующие обозначения: - суммарная вычислительная сложность ограничений, формирующих множество , ; - вычислительная сложность вектор-функции , ; - вычислительная сложность генерации сетки ; - вычислительная сложность конечномерной аппроксимации функционала . Здесь - общее количество узлов сетки , принадлежащих множеству .
В качестве вычислительной системы рассматривается однородная МВС с распределенной памятью, состоящая из процессоров и host-процессора, имеющих следующие параметры: * - время выполнения одной арифметической операции с плавающей запятой; * - диаметр коммуникационной сети; * l - длина вещественного числа в байтах; * - латентность коммуникационной сети; * - время передачи байта данных между двумя соседними процессорами системы без учета времени .
Эффективность параллельных вычислений оценивается ускорением ,
где - время последовательного решения задачи на одном процессоре системы, - время параллельного решения той же задачи на N процессорах
2.2. Схема балансировки загрузки Введем понятие соседства процессоров МВС. Процессоры , называются соседними, если расстояние между ними равно единице [1]. Например, для МВС с коммуникационной сетью типа "решетка" соседними для процессора являются процессоры , , , (рисунок 1).
Рис. 1. Иллюстрация понятия "соседства" процессоров
Пусть "соседями" процессора являются процессоры , Идея диффузной балансировки загрузки заключается в следующем. Если процессора завершил обработку распределенных ему узлов сетки и переслал результаты обработки на host-процессор, то этот процессор в некотором порядке (например, случайным образом) посылает запросы своим соседним процессорам. Получив такой запрос, процессор определяет количество ) еще необработанных им узлов сетки и, если количество этих узлов превышает узлов, то пересылает процессору -ю их часть. Здесь , - заданный коэффициент диффузии, - рассматриваемый момент времени. Таким образом, если , то процессор передает процессору координаты узлов, где - символ ближайшего большего целого.
Схема параллельных вычислений при решении поставленной задачи с использованием метода диффузной балансировки загрузки имеет следующий вид.
Шаг 1. Host-процессор выполняет следующие действия:
* строит сетку ;
* разбивает ее узлы на N множеств ;
* посылает процессору координаты узлов множества , .
Шаг 2. Процессор :
* принимает от host-процессора координаты узлов множества ; * для всех узлов этого множества определяет их принадлежность множеству ;
* последовательно для всех узлов множества , принадлежащих множеству , вычисляет значения вектор-функции ;
* передает host-процессору вычисленные значения этой функции.
Шаг 3. Если процессор закончил вычисления и передал host-процессору вычисленные значения вектор функции , то этот процессор:
* последовательно посылает запросы каждому из своих "соседних" процессоров , ,...;
* если "соседний" процессор , имеет необработанные узлы, принадлежащие множеству , то процессор выполняет следующие действия: принимает от процессора координаты их -ой части; последовательно для всех принятых узлов вычисляет значения вектор-функции ; передает host-процессору вычисленные значения этой функции.
* если ни одни из "соседних" процессоров не имеет достаточного количества необработанных узлов, то процессор посылает host-процессору сообщение о завершении вычислений.
Шаг 4. Процессор при получении запроса от процессора выполняет следующие действия:
* прерывает текущие вычисления;
* определяет количество всех своих необработанных узлов, принадлежащих множеству ;
* определяет -ю часть этих узлов;
* пересылает координаты выделенных узлов процессору ;
* продолжает прерванные вычисления.
Шаг 5. Host-процессор после получения от всех процессоров сообщений о завершении вычислений посылает всем им сообщение о завершении решения задачи и на основе полученных значение вектор-функции вычисляет приближенное значение функционала .
Легко видеть, что если вычислительные сложности одинаковы и равны , то при диффузной балансировке перераспределения узлов не производится и диффузная балансировка превращается в статическую балансировку.
3. Экспериментальная часть
Рассмотрим двумерную задачу (), когда параллелепипед представляет собой единичный квадрат (рисунок 2). Множество формируется с помощью линейной ограничивающей функции , т.е. . Здесь - заданные преподавателем константы. Рис. 2. Расчетная область задачи
В качестве сетки используем равномерную детерминированную сетку с количеством узлов по осям , равным 256, т.е. сетку с количеством узлов . Будем исходить из следующих значений параметров задачи и МВС:
* ; * l=8;
* ;
* ;
* ;
* .
Пренебрежем вычислительными затратами на построение сетки , на вычисление значений ограничивающей функции , а также на построение приближенного значения функционала , т.е. положим , , . Положим также, что вычислительная сложность вектор-функции есть случая величина с равномерным законом распределения, математическое ожидание которой равно . По результатам "прогонов" оценка математического ожидания ускорении вычисляется по формуле
,
а оценка дисперсии этого ускорения и оценка его среднего квадратичного ускорения - по формулам ,
соответственно [4]. Здесь , - оценка ускорения вычислений, полученная в -ом "прогоне".
3.1. Моделирование динамической диффузной балансировки загрузки МВС с помощью языка программирования C++
Из-за крайней негибкости язык GPSS плохо подходит для моделирования динамической диффузной балансировки загрузки МВС. Поэтому для написания данной модели был использован язык программирования C++.
В частности использование С++ было продиктовано следующими факторами:
1) Лёгкость отладки модели: возможен просмотр значений любых переменных и, как следствие, наблюдение за состоянием МВС на любом шаге работы алгоритма балансировки;
2) Лёгкость генерации матрицы смежности процессоров в соответствии с заданной топологией МВС;
3) Как показала практика, для написания данной модели на GPSS, в любом случае, требуется программа на C++, генерирующая код для GPSS. Это связано, в первую очередь, с трудоёмкостью заполнения матрицы смежности процессоров вручную;
4) Требуется дополнительное время для изучения GPSS, в то время как С++ является одним из самых популярных языков программирования и знаком много большему числу пользователей. Таким образом, чтение и изменение исходного кода программы для своих нужд сторонним пользователем требует намного меньших затрат времени.
5) Стабильность работы программы вне зависимости от задаваемых параметров.
3.2. Описание работы программы
Для МВС событием является окончание работы одного из процессоров. Идея моделирования состоит в расчёте времени окончания работы освободившегося процессора и перевод МВС в состояние, соответствующее этому моменту времени (вызовом функции CorrectSystem()). Далее производится перераспределение узлов между соседними процессорами (функция RedistributeComputingPoints()).
Учёт коммуникационных расходов производится увеличением времени обработки первого (учёт времени на получение данных) и последнего узлов (учёт времени на пересылку результатов расчётов) в соответствии с количеством пересылаемых данных (формулы приведены в учебно-методическом пособии по проведению лабораторной работы №2 "Аналитическое исследование эффективности статической балансировки загрузки МВС" данного цикла работ). Также учитываются коммуникационные расходы вследствие перераспределения загрузки между процессорами (в функции RedistributeComputingPoints()). Программа реализована в виде приложения diffusebalance.exe с файлом parameters.txt для возможности изменения параметров задачи без перекомпиляции программы.
Ниже детально описаны все функции, используемые в программе.
Вначале объявляются и инициализируются переменные-параметры модели.
intN = 2,
Zmin = 4, nGridPoints = 1024;
N - количество процессоров, Zmin - минимальное число узлов, при котором происходит перераспределение загрузки между соседними процессорами, nGridPoints - общее количество узлов сетки.
floatp = 0.5;
p - часть узлов, передаваемая для вычислений соседнему процессору в случае, если он завершил вычисления.
const double t = 0.00000001, ts = 50 * 1e-6, tc = 0.0125 * 1e-6;
t - время выполнения 1 арифметической операции;
ts - латентность коммуникационной сети;
tc - время передачи 1 байта;
const double Cfmax = 1e9 + 1;
Cfmax - максимальная сложность вычислений одного узла;
const double pointComputationT = t * Cfmax;
pointComputationT - максимальное время, которое затратит процессор на вычисления в одном узле;
const int l = 8, m = 100, n = 2, nRounds = 300;
l - количество байт в вещественном числе;
m - размерность вектор-функции F(X); n - размерность вектора параметров; nRounds - число прогонов задачи;
double *complexities; - указатель на массив, в котором хранятся времена обработки всех узлов сетки;
int nGroupPoints = 0; - данной переменной будет присвоено количество узлов в группе;
short **adjacencyMatrix; - указатель на матрицу смежности процессоров;
void ParseInputParameters() - функция, используемая для чтения параметров задачи из файла Parameters.txt и соответствующей инициализации вышеуказанных переменных. Для её работы написаны служебные функции, предназначенные для обработки строк:
static void Initialize(), void InitializeMap(),
void delSpace(char* inStr, char* outStr),
double Multiply(char* inStr).
int NearestLargerInt(float arg) - функция, возвращающая наибольшее ближайшее целое аргумента arg;
int d = NearestLargerInt(2.0 * sqrt((float)N) - 1); - расчёт диаметра коммуникационной сети;
int IntDiv(float arg1, float arg2) - функция, возвращающая наибольшее ближайшее целое результата деления arg1 на arg2;
int IntMul(float arg1, float arg2) - функция, возвращающая наибольшее ближайшее целое произведения arg1 и arg2;
void GenAdjacencyMatrix(void) - функция, генерирующая матрицу смежности для текущего количества процессоров (в данном случае - для топологии МВС типа линейка создана функция void GenLineAdjacencyMatrix(void), но в случае необходимости, можно заменить её на нужный вариант);
void DelAdjacencyMatrix(void) - функция удаления матрицы смежности процессоров;
Для реализации МВС создан класс Processor, содержащий следующие поля и методы:
boolm_computationEnded - переменная, отражающая состояние процессора и равная true, если данный процессор закончил свои вычисления, и false в противном случае;
int m_nPoints - количество узлов, переданных для расчёта данному процессору;
int m_curPoint - номер узла, в котором производятся вычисления данным процессором в текущий момент времени;
double m_Cfsum - суммарное расчётное время работы данного процессора (может меняться вследствие перераспределения загрузки);
double m_resultSendTime - расчётное время обмена результатами вычислений с хост-процессором;
void CountCfSum() - метод, рассчитывающий m_Cfsum в соответствии с текущими значениями m_nPoints и m_curPoint;
void Initialize(unsigned int w, unsigned int nPoints) - метод, инициализирующий переменные объекта класса Processor, в соответствии с переданной хост-процессором координатой первого узла - w и предполагаемым количеством узлов - nPoints;
double GetCommunicatonTime(const int dimension) - метод, возвращающий предполагаемое время коммуникационных расходов на получение (отправку) данных в зависимости от размерности X (F(X)), указанной в dimension, и параметров МВС, отвечающих за коммуникационные расходы: ts, l, d, tc. Возвращаемое значение вычисляется по формуле ts + m_nPoints * dimension * l * d * tc;
void SetCurState(double minCfsum) - метод, корректирующий переменные процессора в зависимости от текущего состояния МВС, отталкиваясь от minCfsum - времени, прошедшего с момента последнего события в системе - окончания работы одного из процессоров;
На этом описание класса Processor окончено.
void InitProcessors(Processor *processors) - функция, инициализирующая состояние всех процессоров в системе перед началом расчётов;
void PrintProcessorsInfo(Processor *processors) - функция, выводящая информацию о текущем состоянии процессоров;
int RedistributeComputingPoints(Processor *processors, int endedProcessor) - функция, производящая перераспределение загрузки МВС в случае окончания работы одного из процессоров. В данной функции также учтена корректировка коммуникационных расходов: передающий/принимающий процессор задержится в своём первом (учёт времени на получение данных) и последнем (учёт времени на пересылку результатов расчётов) узлах на время, обусловленное новым (изменившимся после обмена данными друг с другом) количеством узлов. В случае если процессор ни с кем не должен обмениваться узлами и окончил свою работу, его переменной состояния m_computationEnded присваивается значение true;
void CorrectSystem(Processor *processors, int endedProcessor, double minCfsum) - функция, переводящая МВС в состояние, соответствующее моменту текущего события на основании времени minCfsum , прошедшего с момента предыдущего события - окончания работы одного из процессоров;
void GenComplexities() - функция, генерирующая сложности узлов;
double ComputeImitation(Processor *processors) - функция, отвечающая за имитацию МВС. В ней рассчитывается момент окончания работы одного из процессоров, перевод всей системы в состояние, соответствующее этому моменту, вызовом функции CorrectSystem(processors, endedProcessor, minCfsum) и, как следствие, реакция МВС - перераспределение загрузки между процессорами (посредством вызова функции RedistributeComputingPoints(processors, i));
bool CheckImitationEnd(Processor *processors) - функция, проверяющая, все ли процессоры закончили свои расчёты и возвращающая true в случае успеха, false - в противном случае;
void SetImitationBeginning(Processor *processors) - функция, устанавливающая состояние всех процессоров в позицию "вычисления не закончены";
void AddCommunicationExpense(Processor *processors) - функция, добавляющая коммуникационные расходы, обусловленные пересылкой данных с хост-процессора и результатов вычислений с процессоров на хост-процессор. Коммуникационные расходы учитываются увеличением времени, затрачиваемого процессором на обработку первого (перед его обработкой происходит получение узлов с хост-процессора) и последнего (после его обработки происходит передача результатов расчёта на хост-процессор) узлов;
void UpdateProcessorsCfsum(Processor *processors) - функция, обновляющая значения Cfsum для всех процессоров;
double ComputeSigma(double M, double *S) - функция, вычисляющая среднее квадратичное отклонение ускорения;
В функции int main() производится создание матрицы смежности, генерация времен обработки узлов задачи, имитация работы однопроцессорной системы функцией GetSequentialComputingTime(), имитация динамической диффузной балансировки загрузки МВС для 2, 4, 8, 16, 32, 64, 128, 256 процессоров в течение 300 прогонов, расчёт математического ожидания ускорения работы МВС, по сравнению с однопроцессорной системой, и среднего квадратичного отклонения ускорения.
3.3. Результат работы программы
a = 0.2; b = -0.2; Количество узлов в области - 65536
Количество "прогонов" модели =1. Для заданных преподавателем величин , , вычислить с помощью разработанной GPSS-модели значения ускорения для
N = 2, 4, 8, 16, 32, 64, 128, 256
/ N248163264128256 1.9993.9897.97115.93431.49862.429121.768228.2260.9791.5292.0502.8383.1823.5183.1392.606
Количество "прогонов" модели = 300. Для заданных преподавателем величин
, , вычислить с помощью разработанной GPSS-модели оценки математического ожидания ускорения и его дисперсии для N = 2, 4, 8, 16, 32, 64, 128, 256
Математическое ожидание
/ N2481632641282561.9993.9947.97215.89631.57562.422121.510228.0550.9801.5272.0512.8423.1823.5063.1392.604 Среднеквадратическое отклонение
/ N2481632641282560.0010.0020.0100.0310.1000.2580.7392.1100.0010.0030.0050.0070.0080.0080.0070.006 Дисперсия
N / 20.0000010.00000140.0000040.00000980.0001000.000025160.0009610.000049320.0100000.000064640.0665640.0000641280.5461210.0000492564.4521000.000036 Сравнив эффективность диффузной балансировки с эффективностью других видов балансировок, представленных в работе А.П. Карпенко, В.Г. Федорук, Е.В. Федорук "Исследование эффективности некоторых методов балансировки загрузки распределенной ЭВМ с помощью имитационного моделирования", можно сделать вывод, что динамическую диффузную балансировку загрузки МВС целесообразно использовать в тех случаях, когда не менее 106. При таких значениях эффективность диффузной балансировки намного выше эффективности динамической равномерной балансировки и довольно близка к эффективности динамической экспоненциальной балансировки. При маленьком значении доля коммуникационных расходов из-за постоянных обменов между соседними процессорами становится достаточно высокой, тем самым снижется эффективность применения динамической диффузной балансировки.
Приложение А. Текст программы на С++
#include <iostream>
#include <ctime>
#include <cmath>
#include <fstream>
#include <map>
#include <string>
using namespace std;
static void Initialize();
static enum StringValue {evNotDefined,
evZmin, evnGridPoints, evP, evT,
evTs,
evTc,
evCfmax,
evL,
evM,
evN,
evnRounds};
static std::map<std::string, StringValue> s_mapStringValues;
intN = 2, Zmin = 4, nGridPoints = 1024;
floatp = 0.5;
doublet = 0.00000001, ts = 50 * 1e-6, tc = 0.0125 * 1e-6;
doubleCfmax = 1e9 + 1;
doublepointComputationT = t * Cfmax;
intl = 8, m = 100, n = 2, nRounds = 300;
double *complexities;
intnGroupPoints = 0;
short**adjacencyMatrix;
void InitializeMap()
{
s_mapStringValues["Zmin"] = evZmin;
s_mapStringValues["nGridPoints"] = evnGridPoints;
s_mapStringValues["p"] = evP;
s_mapStringValues["t"] = evT;
s_mapStringValues["ts"] = evTs;
s_mapStringValues["tc"] = evTc;
s_mapStringValues["Cfmax"] = evCfmax;
s_mapStringValues["l"] = evL;
s_mapStringValues["m"] = evM;
s_mapStringValues["n"] = evN;
s_mapStringValues["nRounds"] = evnRounds;
}
void delSpace(char* inStr, char* outStr)
{
while(*inStr)
{
if(*inStr!=' '&&*inStr!='\n')
{
*outStr=*inStr;
outStr++;
}
inStr++;
}
*outStr = '\0';
}
double Multiply(char* inStr)
{
double multiplicand = atof(inStr);
for(int i = 0;i < strlen(inStr);i++)
if(*inStr!='*')
inStr++;
if(*inStr == '*')
{
inStr++;
double factor = atof(inStr);
return (multiplicand*factor);
}
else
return multiplicand;
}
void ParseInputParameters()
{
char* str, *str_without_space;
str = new char[sizeof(string)];
str_without_space = new char[sizeof(string)];
ifstream input_file("parameters.txt");
if(!input_file.is_open())
{
cout<<"Couldn't open parameters file"<<endl;
getchar();
exit(1);
}
InitializeMap();
while(!input_file.eof())
{
input_file.getline(str,sizeof(string),'=');
delSpace(str,str_without_space);
//cout<<str_without_space<<endl;
switch(s_mapStringValues[str_without_space]){
case evZmin: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
Zmin = atoi(str_without_space);
cout<<"Zmin = "<<Zmin<<endl;
}
break;
case evnGridPoints: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
nGridPoints = atoi(str_without_space);
cout<<"nGridPoints = "<<nGridPoints<<endl;
}
break;
case evP: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
p = atof(str_without_space);
cout<<"p = "<<p<<endl;
}
break;
case evT: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
t = atof(str_without_space);
cout<<"t = "<<t<<endl;
}
break;
case evTs: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
ts = Multiply(str_without_space);
cout<<"ts = "<<ts<<endl;
}
break;
case evTc: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
tc = Multiply(str_without_space);
cout<<"tc = "<<tc<<endl;
}
break;
case evCfmax: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
Cfmax = atof(str_without_space) + 1;
cout<<"Cfmax = "<<Cfmax<<endl;
}
break;
case evL: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
l = atoi(str_without_space);
cout<<"l = "<<l<<endl;
}
break;
case evM: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
m = atoi(str_without_space);
cout<<"m = "<<m<<endl;
}
break;
case evN: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
n = atoi(str_without_space);
cout<<"n = "<<n<<endl;
}
break;
case evnRounds: {
input_file.getline(str,sizeof(string),'=\n');
delSpace(str,str_without_space);
nRounds = atoi(str_without_space);
cout<<"nRounds = "<<nRounds<<endl;
}
break;
default:
break;
}
}
cout << endl;
delete str;
delete str_without_space;
input_file.close();
}
int NearestLargerInt(float arg)
{
int argNearestInt = (int)arg;
if(arg - argNearestInt)
{
return argNearestInt + 1;
}
else
return argNearestInt;
}
int d = NearestLargerInt(2.0 * sqrt((float)N) - 1);
int IntDiv(float arg1, float arg2)
{
float divResult = arg1 / arg2;
return NearestLargerInt(divResult);
}
int IntMul(float arg1, float arg2)
{
float mulResult = arg1 * arg2;
return NearestLargerInt(mulResult);
}
void GenLineAdjacencyMatrix(void)
{
int lastElem = N - 1;
adjacencyMatrix = new short* [N];
adjacencyMatrix[0] = new short[N];
memset(adjacencyMatrix[0], 0, sizeof(short) * N);
adjacencyMatrix[0][1] = 1;
for(int i = 1; i < lastElem; i++)
{
adjacencyMatrix[i] = new short[N];
memset(adjacencyMatrix[i], 0, sizeof(short) * N);
adjacencyMatrix[i][i - 1] = 1;
adjacencyMatrix[i][i + 1] = 1;
}
adjacencyMatrix[lastElem] = new short[N];
memset(adjacencyMatrix[lastElem], 0, sizeof(short) * N);
adjacencyMatrix[lastElem][lastElem - 1] = 1;
}
void GenAdjacencyMatrix(void)
{
GenLineAdjacencyMatrix();
//Code for fully-connected adjacency matrix:
/*
int lastElem = N - 1;
adjacencyMatrix = new short* [N];
for(int i = 0; i < N; i++)
{
adjacencyMatrix[i] = new short[N];
memset(adjacencyMatrix[i], 1, sizeof(short) * N);
adjacencyMatrix[i][i] = 0;
}
*/
}
void DelAdjacencyMatrix(void)
{
for(int i = 0; i < N; i++)
{
delete [] adjacencyMatrix[i];
}
delete [] adjacencyMatrix;
}
class Processor
{
public:
boolm_computationEnded;
intm_nPoints,
m_curPoint;
doublem_Cfsum,
m_resultSendTime;
Processor()
{
m_computationEnded = false;
m_nPoints = 0;
m_curPoint = 0;
m_Cfsum = 0,
m_resultSendTime = 0;
}
void CountCfSum()
{
m_Cfsum = 0;
int nextGroupFirstElem = m_curPoint + m_nPoints;
for(int i = m_curPoint; i < nextGroupFirstElem; i++)
{
m_Cfsum += complexities[i];
}
}
void Initialize(unsigned int w, unsigned int nPoints)
{
m_nPoints = nPoints;
m_curPoint = w;
CountCfSum();
}
void PrintComplexities(int procNum)
{
printf("processor[%d]:\n");
int nextGroupFirstElem = m_curPoint + m_nPoints;
for(int i = m_curPoint; i < nextGroupFirstElem; i++)
{
printf("%.0lf\n", complexities[i]);
}
printf("\n");
}
double GetCommunicatonTime(const int dimension)
{
return ts + m_nPoints * dimension * l * d * tc;
}
void SetCurState(double minCfsum)
{
if(m_Cfsum == minCfsum)
{
m_Cfsum = 0;
m_curPoint += (m_nPoints - 1);
m_nPoints = 0;
}
else
{
double curCfsum = 0.0;
for(; curCfsum < minCfsum; m_curPoint++, m_nPoints--)
{
curCfsum += complexities[m_curPoint];
}
double remainedCf = curCfsum - minCfsum;
if(remainedCf)
{
m_curPoint--;
m_nPoints++;
complexities[m_curPoint] = remainedCf;
}
CountCfSum();
}
}
};
void InitProcessors(Processor *processors)
{
int wCur = 0;
int lastProc = N - 1;
for(int i = 0; i < lastProc; i++, wCur += nGroupPoints)
{
processors[i].Initialize(wCur, nGroupPoints);
}
processors[lastProc].Initialize(wCur, nGridPoints - wCur);
}
void PrintProcessorsInfo(Processor *processors)
{
printf("proc[i] curP nP\n\n");
for(int i = 0; i < N; i++)
{
printf("proc[%d] %d %d\n", i, processors[i].m_curPoint, processors[i].m_nPoints);
}
}
int RedistributeComputingPoints(Processor *processors, int endedProcessor)
{
for(int i = 0; i < N; i++)
{
if(adjacencyMatrix[endedProcessor][i])
{
if(processors[i].m_nPoints > Zmin)
{
processors[endedProcessor].m_nPoints = IntMul(processors[i].m_nPoints, p);
complexities[processors[i].m_curPoint + processors[i].m_nPoints - 1] -= processors[i].m_resultSendTime; //restore last point counting time
processors[i].m_nPoints -= processors[endedProcessor].m_nPoints;
processors[endedProcessor].m_curPoint = processors[i].m_curPoint + processors[i].m_nPoints;
//set communication expenses time for ended processor
double exchangeTime = processors[endedProcessor].GetCommunicatonTime(n);
complexities[processors[endedProcessor].m_curPoint] += exchangeTime;
complexities[processors[i].m_curPoint] += exchangeTime;
//update communication expenses time for exchanging processor
processors[i].m_resultSendTime = processors[i].GetCommunicatonTime(m);
complexities[processors[i].m_curPoint + processors[i].m_nPoints - 1] += processors[i].m_resultSendTime;
processors[endedProcessor].m_resultSendTime = processors[endedProcessor].GetCommunicatonTime(m);
complexities[processors[endedProcessor].m_curPoint + processors[endedProcessor].m_nPoints - 1] += processors[endedProcessor].m_resultSendTime;
processors[i].CountCfSum();
processors[endedProcessor].CountCfSum();
processors[endedProcessor].m_computationEnded = false; //reanimate ended processor
return 0;
}
}
}
processors[endedProcessor].m_Cfsum = 0;
processors[endedProcessor].m_computationEnded = true;
}
void CorrectSystem(Processor *processors, int endedProcessor, double minCfsum)
{
processors[endedProcessor].m_curPoint += (processors[endedProcessor].m_nPoints - 1);
processors[endedProcessor].m_nPoints = 0;
processors[endedProcessor].m_Cfsum = 0;
for(int proc = 0; proc < endedProcessor; proc++)
{
if(!processors[proc].m_computationEnded)
processors[proc].SetCurState(minCfsum);
}
for(int proc = endedProcessor + 1; proc < N; proc++)
{
if(!processors[proc].m_computationEnded)
processors[proc].SetCurState(minCfsum);
}
}
void GenComplexities()
{
for(int i = 0; i < nGridPoints; i++)
{
complexities[i] = (((double)rand()/RAND_MAX) * pointComputationT);
if(!complexities[i])
{
complexities[i] = pointComputationT / 2;
}
//modf(complexities[i], &complexities[i]);
}
}
double ComputeImitation(Processor *processors)
{
doubleminCfsum = 1.7E308;
intendedProcessor = 0;
//printf("\n");
//printf("---------------------------------------------\n");
for(int curProc = 0; curProc < N; curProc++)
{
//printf("proc[%d] time remained: %lf\n", curProc, processors[curProc].m_Cfsum);
if(processors[curProc].m_Cfsum < minCfsum && !processors[curProc].m_computationEnded)
{
minCfsum = processors[curProc].m_Cfsum;
endedProcessor = curProc;
}
}
//printf("min is proc[%d] time remained: %lf\n", endedProcessor, minCfsum);
//printf("\n");
CorrectSystem(processors, endedProcessor, minCfsum);
//PrintProcessorsInfo(processors);
//printf("\n");
for(int i = 0; i < N; i++)
{
if(!processors[i].m_Cfsum)
{
RedistributeComputingPoints(processors, i);
}
}
//PrintProcessorsInfo(processors);
//printf("---------------------------------------------\n");
return minCfsum;
}
bool CheckImitationEnd(Processor *processors)
{
bool computationEnded = true;
for(int i = 0; i < N; i++)
{
computationEnded *= processors[i].m_computationEnded;
}
return computationEnded;
}
void SetImitationBeginning(Processor *processors)
{
for(int i = 0; i < N; i++)
{
processors[i].m_computationEnded = false;
}
}
double GetSequentialComputingTime()
{
double sequentialComputingTime = 0;
for(int i = 0; i < nGridPoints; i++)
{
sequentialComputingTime += complexities[i];
}
return sequentialComputingTime;
}
void AddCommunicationExpense(Processor *processors)
{
double hostSendTime = 0.0, hostReceiveTime = 0.0;
for(int i = 0; i < N; i++)
{
hostSendTime += processors[i].GetCommunicatonTime(n);
complexities[processors[i].m_curPoint] += hostSendTime;
hostReceiveTime = processors[i].GetCommunicatonTime(m);
complexities[processors[i].m_curPoint + processors[i].m_nPoints - 1] += hostReceiveTime;
processors[i].CountCfSum();
processors[i].m_resultSendTime = hostReceiveTime;
}
}
void UpdateProcessorsCfsum(Processor *processors)
{
for(int i = 0; i < N; i++)
{
processors[i].CountCfSum();
}
}
double ComputeSigma(double M, double *S)
{
double D = 0;
for(int round = 0; round < nRounds; round++)
{
D += (S[round] - M)*(S[round] - M);
}
D /= (double)(nRounds - 1);
return sqrt(D);
}
int main()
{
void InitProcessors(Processor *, int);
void PrintProcessorsInfo(Processor *);
double ComputeImitation(Processor *);
void delSpace(char*,char*);
ParseInputParameters();
pointComputationT = t * Cfmax;
double *S;
S = new double [nRounds];
srand(time(NULL));
complexities = new double[nGridPoints];
for(;N != 512; N*=2)
{
d = NearestLargerInt(2.0 * sqrt((float)N) - 1);
GenAdjacencyMatrix();
nGroupPoints = IntDiv((float)nGridPoints, (float)N);
Processor *processors;
processors = new Processor[N];
double sumS = 0;
for(int round = 0; round < nRounds; round++)
{
double parallelComputingTime = 0, sequentialComputingTime = 0;
GenComplexities();
sequentialComputingTime = GetSequentialComputingTime();
InitProcessors(processors);
AddCommunicationExpense(processors);
while(!CheckImitationEnd(processors))
{
parallelComputingTime += ComputeImitation(processors);
}
SetImitationBeginning(processors);
S[round] = sequentialComputingTime / parallelComputingTime;
sumS += S[round];
}
double M = sumS / (double)nRounds;
double Sigma = ComputeSigma(M, S);
printf("%d processors:M = %.3lf, Sigma = %.3lf\n", N, M, Sigma);
delete [] processors;
DelAdjacencyMatrix();
}
delete [] complexities;
delete [] S;
getchar();
}
2
Документ
Категория
Рефераты
Просмотров
22
Размер файла
425 Кб
Теги
kargin
1/--страниц
Пожаловаться на содержимое документа